001: /*
002: * $Id: TestObjectBTree.java,v 1.18 2005/05/02 22:32:01 ahimanikya Exp $
003: * =======================================================================
004: * Copyright (c) 2002 Axion Development Team. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * 1. Redistributions of source code must retain the above
011: * copyright notice, this list of conditions and the following
012: * disclaimer.
013: *
014: * 2. Redistributions in binary form must reproduce the above copyright
015: * notice, this list of conditions and the following disclaimer in
016: * the documentation and/or other materials provided with the
017: * distribution.
018: *
019: * 3. The names "Tigris", "Axion", nor the names of its contributors may
020: * not be used to endorse or promote products derived from this
021: * software without specific prior written permission.
022: *
023: * 4. Products derived from this software may not be called "Axion", nor
024: * may "Tigris" or "Axion" appear in their names without specific prior
025: * written permission.
026: *
027: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
028: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
029: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
030: * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
031: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
032: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
033: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
034: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
035: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
036: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
037: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
038: * =======================================================================
039: */
040:
041: package org.axiondb.util;
042:
043: import java.io.File;
044: import java.util.ArrayList;
045: import java.util.HashMap;
046: import java.util.HashSet;
047: import java.util.Iterator;
048: import java.util.List;
049: import java.util.Map;
050: import java.util.Random;
051: import java.util.Set;
052:
053: import junit.framework.Test;
054: import junit.framework.TestSuite;
055:
056: import org.apache.commons.collections.comparators.ComparableComparator;
057: import org.apache.commons.collections.primitives.ArrayIntList;
058: import org.apache.commons.collections.primitives.IntIterator;
059: import org.apache.commons.collections.primitives.IntList;
060: import org.apache.commons.logging.Log;
061: import org.apache.commons.logging.LogFactory;
062: import org.axiondb.AbstractDbdirTest;
063:
064: /**
065: * @version $Revision: 1.18 $ $Date: 2005/05/02 22:32:01 $
066: * @author Dave Pekarek Krohn
067: */
068: public class TestObjectBTree extends AbstractDbdirTest {
069: private static Log _log = LogFactory.getLog(TestObjectBTree.class);
070: private ObjectBTree _tree = null;
071: private int _deg = 3;
072: private int _max = (int) Math.pow(2 * _deg, 2);
073: private Random _random = new Random();
074: private static String[] _stringArray = { "abc", "bcd", "cde",
075: "def", "efg", "fgh", "ghi", "hij", "ijk", "jkl", "lmn",
076: "mno", "nop", "pqr", "qrs", "rst", "stu", "tuv", "uvw",
077: "vwx", "wxy", "xyz", "yza", "zab" };
078:
079: //------------------------------------------------------------ Conventional
080:
081: public TestObjectBTree(String testName) {
082: super (testName);
083: }
084:
085: public static void main(String args[]) {
086: String[] testCaseName = { TestIntBTree.class.getName() };
087: junit.textui.TestRunner.main(testCaseName);
088: }
089:
090: public static Test suite() {
091: return new TestSuite(TestObjectBTree.class);
092: }
093:
094: //--------------------------------------------------------------- Lifecycle
095:
096: public void setUp() throws Exception {
097: super .setUp();
098: long newSeed = _random.nextLong();
099: _log.debug("New Seed: " + newSeed);
100: _random.setSeed(newSeed);
101: _tree = new ObjectBTree(getDbdir(), "idx", _deg,
102: new ComparableComparator());
103: }
104:
105: public void tearDown() throws Exception {
106: _tree = null;
107: super .tearDown();
108: }
109:
110: //------------------------------------------------------------------- Tests
111:
112: public void testDeleteOneOfMany() throws Exception {
113: IntList expected = new ArrayIntList();
114: for (int i = 0; i < 10; i++) {
115: _tree.insert("key", i);
116: expected.add(i);
117: }
118: {
119: IntList found = new ArrayIntList();
120: for (IntIterator iter = _tree.getAll("key"); iter.hasNext();) {
121: found.add(iter.next());
122: }
123: assertEquals(expected.size(), found.size());
124: assertTrue(found.containsAll(expected));
125: }
126: _tree.delete("key", 5);
127: expected.removeElement(5);
128: {
129: IntList found = new ArrayIntList();
130: for (IntIterator iter = _tree.getAll("key"); iter.hasNext();) {
131: found.add(iter.next());
132: }
133: assertEquals(expected.size(), found.size());
134: assertTrue(found.containsAll(expected));
135: }
136: }
137:
138: public void testCreate() throws Exception {
139: assertTrue("Should have dbdir avail", getDbdir().exists());
140: assertTrue("Dbdir should be directory", getDbdir()
141: .isDirectory());
142: assertNotNull("Should not be null", _tree);
143: assertTrue("Should be leaf", _tree.isLeaf());
144: assertEquals("Should have no entries", 0, _tree.size());
145: File idx = new File(getDbdir(), "IDX" + ".0");
146: assertTrue("Should not have an index file before save", !idx
147: .exists());
148: _tree.insert("key", 1);
149: _tree.save(getDbdir());
150: assertTrue("Should have an index file after save", idx.exists());
151: }
152:
153: public void testInsertAndRetrieve() throws Exception {
154: _tree.insert("abc", 456);
155: assertTrue("Tree should be valid after insert", _tree.isValid());
156: assertEquals("Should have one value", 1, _tree.size());
157: assertEquals("Should get value back", new Integer(456), _tree
158: .get("abc"));
159: }
160:
161: public void testInsertAndRetrieveMany() throws Exception {
162: for (int i = 0; i < _stringArray.length; i++) {
163: _log.debug("Inserting key " + i);
164: _tree.insert(_stringArray[i], _stringArray.length - i);
165: _log.debug(_tree.toString());
166: assertTrue("Tree should be valid after insert", _tree
167: .isValid());
168: assertEquals("Should get the value back as inserting for "
169: + i, new Integer(_stringArray.length - i), _tree
170: .get(_stringArray[i]));
171: }
172: for (int i = 0; i < _stringArray.length; i++) {
173: assertEquals("Should get the value back for " + i,
174: new Integer(_stringArray.length - i), _tree
175: .get(_stringArray[i]));
176: }
177: }
178:
179: public void testReloadTree() throws Exception {
180: //Insert a bunch of items
181: {
182: for (int i = 0; i < _stringArray.length; i++) {
183: _log.debug("Inserting key " + i);
184: _tree.insert(_stringArray[i], _stringArray.length - i);
185: _log.debug(_tree.toString());
186: assertTrue("Tree should be valid after insert", _tree
187: .isValid());
188: assertEquals(
189: "Should get the value back as inserting for "
190: + i, new Integer(_stringArray.length
191: - i), _tree.get(_stringArray[i]));
192: }
193: _tree.save(getDbdir());
194: }
195:
196: //Reload tree and make sure items are still there
197: //then delete some of them
198: {
199: _tree = new ObjectBTree(getDbdir(), "idx", _deg,
200: new ComparableComparator());
201: for (int i = 0; i < _stringArray.length; i++) {
202: assertEquals("Should get the value back for " + i,
203: new Integer(_stringArray.length - i), _tree
204: .get(_stringArray[i]));
205: }
206:
207: for (int i = 0; i < _stringArray.length / 2; i++) {
208: _tree.delete(_stringArray[i], _stringArray.length - i);
209: assertEquals("Should not get the value back for " + i,
210: null, _tree.get(_stringArray[i]));
211: }
212: _tree.save(getDbdir());
213: }
214:
215: //Reload the tree and make sure that items that should be there are there
216: //and those that should not aren't. Then add the deleted items back
217: {
218: _tree = new ObjectBTree(getDbdir(), "idx", _deg,
219: new ComparableComparator());
220: for (int i = _stringArray.length / 2; i < _stringArray.length; i++) {
221: assertEquals("Should get the value back for " + i,
222: new Integer(_stringArray.length - i), _tree
223: .get(_stringArray[i]));
224: }
225:
226: for (int i = 0; i < _stringArray.length / 2; i++) {
227: assertEquals("Should not get the value back for " + i,
228: null, _tree.get(_stringArray[i]));
229: _tree.insert(_stringArray[i], _stringArray.length - i);
230: }
231: _tree.save(getDbdir());
232: }
233:
234: //Reload the tree and make sure that all items are there
235: {
236: _tree = new ObjectBTree(getDbdir(), "idx", _deg,
237: new ComparableComparator());
238: for (int i = 0; i < _stringArray.length; i++) {
239: assertEquals("Should get the value back for " + i,
240: new Integer(_stringArray.length - i), _tree
241: .get(_stringArray[i]));
242: }
243: _tree.save(getDbdir());
244: }
245: }
246:
247: public void testInsertIdenticalAndGetAll() throws Exception {
248: _tree = new ObjectBTree(getDbdir(), "idx", 8,
249: new ComparableComparator());
250: int max = 100;
251: for (int i = 0; i < max; i++) {
252: _log.debug("Inserting key " + i);
253: _tree.insert(new Integer(i), i);
254: _tree.insert(new Integer(i), max - i);
255: _tree.insert(new Integer(i), -1 * i);
256: _log.debug(_tree.toString());
257: assertTrue("Tree should be valid after insert", _tree
258: .isValid());
259: IntIterator iter = _tree.getAll(new Integer(i));
260: List valList = new ArrayList();
261: valList.add(new Integer(i));
262: valList.add(new Integer(max - i));
263: valList.add(new Integer(-1 * i));
264: for (int j = 0; j < 3; j++) {
265: assertTrue("Should have another value for: " + i, iter
266: .hasNext());
267: Integer val = new Integer(iter.next());
268: assertTrue("Should contain value: " + val + " for: "
269: + i, valList.contains(val));
270: valList.remove(val);
271: }
272: }
273: for (int i = 0; i < max; i++) {
274: IntIterator iter = _tree.getAll(new Integer(i));
275: List valList = new ArrayList();
276: valList.add(new Integer(i));
277: valList.add(new Integer(max - i));
278: valList.add(new Integer(-1 * i));
279: for (int j = 0; j < 3; j++) {
280: assertTrue("Should have another value for: " + i, iter
281: .hasNext());
282: Integer val = new Integer(iter.next());
283: assertTrue("Should contain value: " + val + " for: "
284: + i, valList.contains(val));
285: valList.remove(val);
286: }
287: }
288: }
289:
290: public void testInsertAndRetrieveManyRandom() throws Exception {
291: Map tests = new HashMap();
292: for (int i = 0; i < _stringArray.length; i++) {
293: Integer key;
294: while (tests.containsKey(key = new Integer(_random
295: .nextInt(_stringArray.length)))) {
296: }
297: ;
298: Integer value = new Integer(_random.nextInt());
299: if (!tests.containsKey(key)) {
300: tests.put(key, value);
301: _log.debug("Inserting key " + key);
302: _tree.insert(_stringArray[key.intValue()], value
303: .intValue());
304: _log.debug(_tree.toString());
305: assertTrue("Tree should be valid after insert", _tree
306: .isValid());
307: assertEquals("Should get value back as inserting",
308: value, _tree.get(_stringArray[key.intValue()]));
309: }
310: }
311: assertEquals("Should have " + _stringArray.length
312: + " insertions", _stringArray.length, tests.keySet()
313: .size());
314: Iterator i = tests.keySet().iterator();
315: while (i.hasNext()) {
316: Integer cur = (Integer) i.next();
317: assertEquals("Should get value back", tests.get(cur), _tree
318: .get(_stringArray[cur.intValue()]));
319: }
320: }
321:
322: public void testInsertAndRetrieveManyIdentical() throws Exception {
323: Set tests = new HashSet();
324: for (int i = 0; i < _max; i++) {
325: _log.debug("Insertion number " + (i + 1));
326: _tree.insert("abc", i);
327: assertTrue("Tree should be valid after insert", _tree
328: .isValid());
329: tests.add(new Integer(i));
330: _log.debug(_tree.toString());
331: }
332: assertEquals("Should have full number of tests", _max, tests
333: .size());
334: IntIterator i = _tree.getAll("abc");
335: int count = 0;
336: while (i.hasNext()) {
337: tests.remove(new Integer(i.next()));
338: count++;
339: }
340: assertEquals("Should have found all matching inserts", _max,
341: count);
342: assertTrue("All test vals should have been retrieved", tests
343: .isEmpty());
344: i = _tree.getAll("def");
345: assertTrue("Should not have any matches", !i.hasNext());
346: }
347:
348: public void testInsertAndDeleteLots() throws Exception {
349: //Do inserts
350: for (int i = 0; i < _stringArray.length; i++) {
351: _log.debug("Inserting key " + i);
352: _tree.insert(_stringArray[i], i);
353: _log.debug(_tree.toString());
354: assertTrue("Tree should be valid after insert", _tree
355: .isValid());
356: assertEquals("Should get value back as inserting", i, _tree
357: .get(_stringArray[i]).intValue());
358: }
359:
360: for (int i = 0; i < _stringArray.length; i++) {
361: int val = (i + 20) % (_stringArray.length);
362: assertEquals("Should get value back", val, _tree.get(
363: _stringArray[val]).intValue());
364: _log.debug("Deleting key " + val);
365: _log.debug("Tree before delete: " + _tree.toString());
366: _tree.delete(_stringArray[val], val);
367: _log.debug("Tree after delete: " + _tree.toString());
368: assertTrue("Tree should be valid after delete", _tree
369: .isValid());
370: assertNull("Value should be deleted for key: " + val, _tree
371: .get(_stringArray[val]));
372: }
373:
374: assertTrue("Tree should be empty", _tree.size() == 0);
375: }
376:
377: public void testInsertAndDeleteLotsWithReload() throws Exception {
378: //Do inserts
379: for (int i = 0; i < _stringArray.length; i++) {
380: _log.debug("Inserting key " + i);
381: _tree.insert(_stringArray[i], i);
382: _log.debug(_tree.toString());
383: assertTrue("Tree should be valid after insert", _tree
384: .isValid());
385: assertEquals("Should get value back as inserting", i, _tree
386: .get(_stringArray[i]).intValue());
387: }
388: _tree.save(getDbdir());
389:
390: _tree = new ObjectBTree(getDbdir(), "idx", _deg,
391: new ComparableComparator());
392: for (int i = 0; i < _stringArray.length; i++) {
393: int val = (i + 20) % (_stringArray.length);
394: assertEquals("Should get value back", val, _tree.get(
395: _stringArray[val]).intValue());
396: _log.debug("Deleting key " + val);
397: _log.debug("Tree before delete: " + _tree.toString());
398: _tree.delete(_stringArray[val], val);
399: _log.debug("Tree after delete: " + _tree.toString());
400: assertTrue("Tree should be valid after delete", _tree
401: .isValid());
402: assertNull("Value should be deleted for key: " + val, _tree
403: .get(_stringArray[val]));
404: }
405: _tree.save(getDbdir());
406:
407: _tree = new ObjectBTree(getDbdir(), "idx", _deg,
408: new ComparableComparator());
409: assertTrue("Tree should be empty", _tree.size() == 0);
410: }
411:
412: public void testInsertAndDeleteRandom() throws Exception {
413: Map tests = new HashMap();
414: //Do inserts
415: int max = _max * 10;
416: for (int i = 0; i < max; i++) {
417: Integer value = new Integer(_random.nextInt());
418: String key = value.toString();
419: if (!tests.containsKey(key)) {
420: tests.put(key, value);
421: _log.debug("Inserting key " + key);
422: _tree.insert(key, value.intValue());
423: _log.debug(_tree.toString());
424: assertTrue("Tree should be valid after insert", _tree
425: .isValid());
426: assertEquals("Should get value back as inserting",
427: value, _tree.get(key));
428: }
429: }
430: assertEquals("Should have " + max + " insertions", max, tests
431: .keySet().size());
432: //Do deletes
433: Iterator i = tests.keySet().iterator();
434: while (i.hasNext()) {
435: String cur = (String) i.next();
436: Integer val = (Integer) tests.get(cur);
437: assertEquals("Should get value back", val, _tree.get(cur));
438: _log.debug("Deleting key " + cur);
439: _log.debug("Tree before delete: " + _tree.toString());
440: _tree.delete(cur, val.intValue());
441: _log.debug("Tree after delete: " + _tree.toString());
442: assertTrue("Tree should be valid after delete", _tree
443: .isValid());
444: assertNull("Value should be deleted for key: " + cur, _tree
445: .get(cur));
446: }
447: assertEquals("Tree should be empty", 0, _tree.size());
448: }
449:
450: public void testInsertAndDeleteRandomWithReload() throws Exception {
451: Map tests = new HashMap();
452: //Do inserts
453: int max = _max * 10;
454: for (int i = 0; i < max; i++) {
455: Integer value = new Integer(_random.nextInt());
456: String key = value.toString();
457: if (!tests.containsKey(key)) {
458: tests.put(key, value);
459: _log.debug("Inserting key " + key);
460: _tree.insert(key, value.intValue());
461: _log.debug(_tree.toString());
462: assertTrue("Tree should be valid after insert", _tree
463: .isValid());
464: assertEquals("Should get value back as inserting",
465: value, _tree.get(key));
466: }
467: }
468: assertEquals("Should have " + max + " insertions", max, tests
469: .keySet().size());
470:
471: _tree.save(getDbdir());
472:
473: _tree = new ObjectBTree(getDbdir(), "idx", _deg,
474: new ComparableComparator());
475: //Do deletes
476: Iterator i = tests.keySet().iterator();
477: while (i.hasNext()) {
478: String cur = (String) i.next();
479: Integer val = (Integer) tests.get(cur);
480: assertEquals("Should get value back", val, _tree.get(cur));
481: _log.debug("Deleting key " + cur);
482: _log.debug("Tree before delete: " + _tree.toString());
483: _tree.delete(cur, val.intValue());
484: _log.debug("Tree after delete: " + _tree.toString());
485: assertTrue("Tree should be valid after delete", _tree
486: .isValid());
487: assertNull("Value should be deleted for key: " + cur, _tree
488: .get(cur));
489: }
490:
491: _tree.save(getDbdir());
492:
493: _tree = new ObjectBTree(getDbdir(), "idx", _deg,
494: new ComparableComparator());
495: assertEquals("Tree should be empty", 0, _tree.size());
496: }
497:
498: public void testGetAllTo() throws Exception {
499: testInsertAndRetrieveMany();
500:
501: int topNum = 19;
502: String topKey = _stringArray[topNum];
503: IntIterator iter = _tree.getAllTo(topKey);
504: for (int i = 0; i < topNum; i++) {
505: assertTrue("Iterator should have another value", iter
506: .hasNext());
507: Integer val = new Integer(iter.next());
508: _log.debug("Iterator Value: " + val);
509: assertEquals("Should get the value back for " + i,
510: new Integer(_stringArray.length - i), val);
511: }
512: }
513:
514: public void testGetAllFrom() throws Exception {
515: testInsertAndRetrieveMany();
516:
517: int bottomNum = 19;
518: String bottomKey = _stringArray[bottomNum];
519: IntIterator iter = _tree.getAllFrom(bottomKey);
520: for (int i = bottomNum; i < _stringArray.length; i++) {
521: assertTrue("Iterator should have another value", iter
522: .hasNext());
523: Integer val = new Integer(iter.next());
524: _log.debug("Iterator Value: " + val);
525: assertEquals("Should get the value back for " + i,
526: new Integer(_stringArray.length - i), val);
527: }
528: }
529:
530: public void testChangeId() throws Exception {
531: testInsertAndRetrieveMany();
532:
533: String key = "def";
534: int oldId = (_tree.get(key)).intValue();
535: _tree.replaceId(key, oldId, oldId + 1000);
536: assertEquals("Should get new id back for " + key, oldId + 1000,
537: (_tree.get(key)).intValue());
538: }
539:
540: public void testChangeIdIdentical() throws Exception {
541: testInsertAndRetrieveManyIdentical();
542:
543: String key = "abc";
544: IntList oldIdList = new ArrayIntList();
545: IntIterator iter = null;
546: {
547: ArrayIntList ids = new ArrayIntList();
548: for (IntIterator tocopy = _tree.getAll(key); tocopy
549: .hasNext();) {
550: ids.add(tocopy.next());
551: }
552: iter = ids.iterator();
553: }
554: for (int i = 0; iter.hasNext(); i++) {
555: int oldId = iter.next();
556: oldIdList.add(oldId);
557: if ((i % 2) == 0) {
558: _tree.replaceId(key, oldId, oldId + 1000);
559: }
560: }
561: {
562: ArrayIntList ids = new ArrayIntList();
563: for (IntIterator tocopy = _tree.getAll(key); tocopy
564: .hasNext();) {
565: ids.add(tocopy.next());
566: }
567: iter = ids.iterator();
568: }
569: for (int i = 0; iter.hasNext(); i++) {
570: int newId = iter.next();
571: int oldId = oldIdList.get(i);
572: if ((i % 2) == 0) {
573: assertEquals("Should get new id back for " + key,
574: oldId + 1000, newId);
575: } else {
576: assertEquals("Should get old id back for " + key,
577: oldId, newId);
578: }
579: }
580: }
581: }
|