001: /*
002: * $Id: AbstractTestTTreeInt.java,v 1.2 2007/11/13 19:04:02 rwald 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.ext.indexes.ttree;
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 org.apache.commons.collections.comparators.ComparableComparator;
054: import org.apache.commons.collections.primitives.ArrayIntList;
055: import org.apache.commons.collections.primitives.IntIterator;
056: import org.apache.commons.collections.primitives.IntList;
057: import org.apache.commons.logging.Log;
058: import org.apache.commons.logging.LogFactory;
059: import org.axiondb.AbstractDbdirTest;
060: import org.axiondb.ext.indexes.ttree.TTree;
061: import org.axiondb.ext.indexes.ttree.DiskTTree;
062: import org.axiondb.ext.indexes.ttree.TTreeMetaData;
063:
064: /**
065: * @version $Revision: 1.2 $ $Date: 2007/11/13 19:04:02 $
066: * @author Pauls Andrejevs
067: */
068: public class AbstractTestTTreeInt extends AbstractDbdirTest {
069: private static Log _log = LogFactory
070: .getLog(AbstractTestTTreeInt.class);
071: private TTree _tree = null;
072: private int _deg = 2;
073: private int _max = (int) Math.pow(2 * _deg, 2);
074: private Random _random = new Random();
075: private static Integer[] _intArray = { new Integer(12345),
076: new Integer(22131), new Integer(33756), new Integer(67890),
077: new Integer(77838), new Integer(88183), new Integer(99312),
078: new Integer(111037), new Integer(222338),
079: new Integer(333192), new Integer(444938),
080: new Integer(555657), new Integer(661027),
081: new Integer(778046), new Integer(889282),
082: new Integer(942739), new Integer(1190642),
083: new Integer(2222567), new Integer(3333643),
084: new Integer(4490833), new Integer(5555677),
085: new Integer(6661278), new Integer(7797355),
086: new Integer(8832121) };
087: private TTreeMetaData _metaData = null;
088:
089: //------------------------------------------------------------ Conventional
090:
091: public AbstractTestTTreeInt(String testName) {
092: super (testName);
093: }
094:
095: public void setMetaData(TTreeMetaData metaData) {
096: this ._metaData = metaData;
097: }
098:
099: public TTreeMetaData getMetaData() {
100: return this ._metaData;
101: }
102:
103: //--------------------------------------------------------------- Lifecycle
104:
105: public void setUp() throws Exception {
106: super .setUp();
107: long newSeed = _random.nextLong();
108: _log.debug("New Seed: " + newSeed);
109: _random.setSeed(newSeed);
110: setMetaData(new TTreeMetaData("idx", getDbdir(),
111: getDbdir() == null));
112: _tree = new DiskTTree(_deg, new ComparableComparator(),
113: getMetaData());
114: }
115:
116: public void tearDown() throws Exception {
117: _tree = null;
118: super .tearDown();
119: }
120:
121: //------------------------------------------------------------------- Tests
122:
123: public void testCreate() throws Exception {
124: assertTrue("Should have dbdir avail", getDbdir().exists());
125: assertTrue("Dbdir should be directory", getDbdir()
126: .isDirectory());
127: assertNotNull("Should not be null", _tree);
128: assertTrue("Should be empty", _tree.getRoot() == null);
129: assertEquals("Should have no entries", 0, _tree.size());
130: File idx = new File(getDbdir(), "IDX" + ".1");
131: assertTrue("Should not have an index file before save", !idx
132: .exists());
133: _tree.insert(new Integer(12345), 1, false);
134: _tree.save(getDbdir());
135: assertTrue("Should have an index file after save", idx.exists());
136: }
137:
138: public void testInsertAndRetrieve() throws Exception {
139: _tree.insert(new Integer(67890), 456, false);
140: assertTrue("Tree should be valid after insert", _tree.isValid());
141: assertEquals("Should have one value", 1, _tree.size());
142: assertEquals("Should get value back", new Integer(456), _tree
143: .get(new Integer(67890)));
144: }
145:
146: public void testInsertAndRetrieveMany() throws Exception {
147: for (int i = 0; i < _intArray.length; i++) {
148: _log.debug("Inserting key " + i);
149: _tree.insert(_intArray[i], _intArray.length - i, false);
150: _log.debug(_tree.toString());
151: assertTrue("Tree should be valid after insert", _tree
152: .isValid());
153: assertEquals("Should get the value back as inserting for "
154: + i, new Integer(_intArray.length - i), _tree
155: .get(_intArray[i]));
156: }
157: for (int i = 0; i < _intArray.length; i++) {
158: assertEquals("Should get the value back for " + i,
159: new Integer(_intArray.length - i), _tree
160: .get(_intArray[i]));
161: }
162: }
163:
164: public void testReloadTree() throws Exception {
165: //Insert a bunch of items
166: {
167: for (int i = 0; i < _intArray.length; i++) {
168: _log.debug("Inserting key " + i);
169: _tree.insert(_intArray[i], _intArray.length - i, false);
170: _log.debug(_tree.toString());
171: assertTrue("Tree should be valid after insert", _tree
172: .isValid());
173: assertEquals(
174: "Should get the value back as inserting for ["
175: + i + "]", new Integer(_intArray.length
176: - i), _tree.get(_intArray[i]));
177: }
178: _tree.save(getDbdir());
179: }
180:
181: //Reload tree and make sure items are still there
182: //then delete some of them
183: {
184: _tree = new DiskTTree(_deg, new ComparableComparator(),
185: getMetaData());
186: for (int i = 0; i < _intArray.length; i++) {
187: assertEquals("Should get the value back for " + i,
188: new Integer(_intArray.length - i), _tree
189: .get(_intArray[i]));
190: }
191:
192: for (int i = 0; i < _intArray.length / 2; i++) {
193: _tree.delete(_intArray[i], _intArray.length - i);
194: assertEquals("Should not get the value back for " + i,
195: null, _tree.get(_intArray[i]));
196: }
197: _tree.save(getDbdir());
198: }
199:
200: //Reload the tree and make sure that items that should be there are there
201: //and those that should not aren't. Then add the deleted items back
202: {
203: _tree = new DiskTTree(_deg, new ComparableComparator(),
204: getMetaData());
205: for (int i = _intArray.length / 2; i < _intArray.length; i++) {
206: assertEquals("Should get the value back for " + i,
207: new Integer(_intArray.length - i), _tree
208: .get(_intArray[i]));
209: }
210:
211: for (int i = 0; i < _intArray.length / 2; i++) {
212: assertEquals("Should not get the value back for " + i,
213: null, _tree.get(_intArray[i]));
214: _tree.insert(_intArray[i], _intArray.length - i, false);
215: }
216: _tree.save(getDbdir());
217: }
218:
219: //Reload the tree and make sure that all items are there
220: {
221: _tree = new DiskTTree(_deg, new ComparableComparator(),
222: getMetaData());
223: for (int i = 0; i < _intArray.length; i++) {
224: assertEquals("Should get the value back for " + i,
225: new Integer(_intArray.length - i), _tree
226: .get(_intArray[i]));
227: }
228: _tree.save(getDbdir());
229: }
230: }
231:
232: public void testInsertIdenticalAndGetAll() throws Exception {
233: _tree = new DiskTTree(8, new ComparableComparator(),
234: getMetaData());
235: int max = 100;
236: for (int i = 0; i < max; i++) {
237: _log.debug("Inserting key " + i);
238: _tree.insert(new Integer(i), i, false);
239: _tree.insert(new Integer(i), max - i, false);
240: _tree.insert(new Integer(i), -1 * i, false);
241: _log.debug(_tree.toString());
242: assertTrue("Tree should be valid after insert", _tree
243: .isValid());
244: IntIterator iter = _tree.getAll(new Integer(i));
245: List<Integer> valList = new ArrayList<Integer>();
246: valList.add(new Integer(i));
247: valList.add(new Integer(max - i));
248: valList.add(new Integer(-1 * i));
249: for (int j = 0; j < 3; j++) {
250: assertTrue("Should have another value for: " + i, iter
251: .hasNext());
252: Integer val = new Integer(iter.next());
253: assertTrue("Should contain value: " + val + " for: "
254: + i, valList.contains(val));
255: valList.remove(val);
256: }
257: }
258: for (int i = 0; i < max; i++) {
259: IntIterator iter = _tree.getAll(new Integer(i));
260: List<Integer> valList = new ArrayList<Integer>();
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: }
274:
275: public void testInsertAndRetrieveManyRandom() throws Exception {
276: Map tests = new HashMap();
277: for (int i = 0; i < _intArray.length; i++) {
278: Integer key;
279: while (tests.containsKey(key = new Integer(_random
280: .nextInt(_intArray.length)))) {
281: }
282: ;
283: Integer value = new Integer(_random.nextInt());
284: if (!tests.containsKey(key)) {
285: tests.put(key, value);
286: _log.debug("Inserting key " + key);
287: _tree.insert(_intArray[key.intValue()], value
288: .intValue(), false);
289: _log.debug(_tree.toString());
290: assertTrue("Tree should be valid after insert", _tree
291: .isValid());
292: assertEquals("Should get value back as inserting",
293: value, _tree.get(_intArray[key.intValue()]));
294: }
295: }
296: assertEquals("Should have " + _intArray.length + " insertions",
297: _intArray.length, tests.keySet().size());
298: Iterator i = tests.keySet().iterator();
299: while (i.hasNext()) {
300: Integer cur = (Integer) i.next();
301: assertEquals("Should get value back", tests.get(cur), _tree
302: .get(_intArray[cur.intValue()]));
303: }
304: }
305:
306: public void testInsertAndRetrieveManyIdentical() throws Exception {
307: Set tests = new HashSet();
308: for (int i = 0; i < _max; i++) {
309: _log.debug("Insertion number " + (i + 1));
310: _tree.insert(new Integer(12345), i, false);
311: assertTrue("Tree should be valid after insert", _tree
312: .isValid());
313: tests.add(new Integer(i));
314: _log.debug(_tree.toString());
315: }
316: assertEquals("Should have full number of tests", _max, tests
317: .size());
318: IntIterator i = _tree.getAll(new Integer(12345));
319: int count = 0;
320: while (i.hasNext()) {
321: tests.remove(new Integer(i.next()));
322: count++;
323: }
324: assertEquals("Should have found all matching inserts", _max,
325: count);
326: assertTrue("All test vals should have been retrieved", tests
327: .isEmpty());
328: i = _tree.getAll(new Integer(67890));
329: assertTrue("Should not have any matches", !i.hasNext());
330: }
331:
332: public void testInsertAndDeleteLots() throws Exception {
333: //Do inserts
334: for (int i = 0; i < _intArray.length; i++) {
335: _log.debug("Inserting key " + i);
336: _tree.insert(_intArray[i], i, false);
337: _log.debug(_tree.toString());
338: assertTrue("Tree should be valid after insert", _tree
339: .isValid());
340: assertEquals("Should get value back as inserting", i, _tree
341: .get(_intArray[i]).intValue());
342: }
343:
344: for (int i = 0; i < _intArray.length; i++) {
345: int val = (i + 20) % (_intArray.length);
346: assertEquals("Should get value back", val, _tree.get(
347: _intArray[val]).intValue());
348: _log.debug("Deleting key " + val);
349: _log.debug("Tree before delete: " + _tree.toString());
350: _tree.delete(_intArray[val], val);
351: _log.debug("Tree after delete: " + _tree.toString());
352: assertTrue("Tree should be valid after delete", _tree
353: .isValid());
354: assertNull("Value should be deleted for key: " + val, _tree
355: .get(_intArray[val]));
356: }
357:
358: assertTrue("Tree should be empty", _tree.size() == 0);
359: }
360:
361: public void testInsertAndDeleteLotsWithReload() throws Exception {
362: //Do inserts
363: for (int i = 0; i < _intArray.length; i++) {
364: _log.debug("Inserting key " + i);
365: _tree.insert(_intArray[i], i, false);
366: _log.debug(_tree.toString());
367: assertTrue("Tree should be valid after insert", _tree
368: .isValid());
369: assertEquals("Should get value back as inserting", i, _tree
370: .get(_intArray[i]).intValue());
371: }
372: _tree.save(getDbdir());
373:
374: _tree = new DiskTTree(_deg, new ComparableComparator(),
375: getMetaData());
376: for (int i = 0; i < _intArray.length; i++) {
377: int val = (i + 20) % (_intArray.length);
378: assertEquals("Should get value back", val, _tree.get(
379: _intArray[val]).intValue());
380: _log.debug("Deleting key " + val);
381: _log.debug("Tree before delete: " + _tree.toString());
382: _tree.delete(_intArray[val], val);
383: _log.debug("Tree after delete: " + _tree.toString());
384: assertTrue("Tree should be valid after delete", _tree
385: .isValid());
386: assertNull("Value should be deleted for key: " + val, _tree
387: .get(_intArray[val]));
388: }
389: _tree.save(getDbdir());
390:
391: _tree = new DiskTTree(_deg, new ComparableComparator(),
392: getMetaData());
393: assertTrue("Tree should be empty", _tree.size() == 0);
394: }
395:
396: public void testInsertAndDeleteRandom() throws Exception {
397: Map tests = new HashMap();
398: //Do inserts
399: int max = _max * 10;
400: for (int i = 0; i < max; i++) {
401: Integer value = new Integer(_random.nextInt());
402: Integer key = value;
403: if (!tests.containsKey(key)) {
404: tests.put(key, value);
405: _log.debug("Inserting key " + key);
406: _tree.insert(key, value.intValue(), false);
407: _log.debug(_tree.toString());
408: assertTrue("Tree should be valid after insert", _tree
409: .isValid());
410: assertEquals("Should get value back as inserting",
411: value, _tree.get(key));
412: }
413: }
414: assertEquals("Should have " + max + " insertions", max, tests
415: .keySet().size());
416: //Do deletes
417: Iterator i = tests.keySet().iterator();
418: while (i.hasNext()) {
419: Integer cur = (Integer) i.next();
420: assertEquals("Should get value back", tests.get(cur), _tree
421: .get(cur));
422: _log.debug("Deleting key " + cur);
423: _log.debug("Tree before delete: " + _tree.toString());
424: _tree.delete(cur, ((Integer) tests.get(cur)).intValue());
425: _log.debug("Tree after delete: " + _tree.toString());
426: assertTrue("Tree should be valid after delete", _tree
427: .isValid());
428: assertNull("Value should be deleted for key: " + cur, _tree
429: .get(cur));
430: }
431: assertEquals("Tree should be empty", 0, _tree.size());
432: }
433:
434: public void testInsertAndDeleteRandomWithReload() throws Exception {
435: Map tests = new HashMap();
436: //Do inserts
437: int max = _max * 10;
438: for (int i = 0; i < max; i++) {
439: Integer value = new Integer(_random.nextInt());
440: Integer key = value;
441: if (!tests.containsKey(key)) {
442: tests.put(key, value);
443: _log.debug("Inserting key " + key);
444: _tree.insert(key, value.intValue(), false);
445: _log.debug(_tree.toString());
446: assertTrue("Tree should be valid after insert", _tree
447: .isValid());
448: assertEquals("Should get value back as inserting",
449: value, _tree.get(key));
450: }
451: }
452: assertEquals("Should have " + max + " insertions", max, tests
453: .keySet().size());
454:
455: _tree.save(getDbdir());
456:
457: _tree = new DiskTTree(_deg, new ComparableComparator(),
458: getMetaData());
459: //Do deletes
460: Iterator i = tests.keySet().iterator();
461: while (i.hasNext()) {
462: Integer cur = (Integer) i.next();
463: assertEquals("Should get value back", tests.get(cur), _tree
464: .get(cur));
465: _log.debug("Deleting key " + cur);
466: _log.debug("Tree before delete: " + _tree.toString());
467: _tree.delete(cur, ((Integer) tests.get(cur)).intValue());
468: _log.debug("Tree after delete: " + _tree.toString());
469: assertTrue("Tree should be valid after delete", _tree
470: .isValid());
471: assertNull("Value should be deleted for key: " + cur, _tree
472: .get(cur));
473: }
474:
475: _tree.save(getDbdir());
476:
477: _tree = new DiskTTree(_deg, new ComparableComparator(),
478: getMetaData());
479: assertEquals("Tree should be empty", 0, _tree.size());
480: }
481:
482: public void testGetAllTo() throws Exception {
483: testInsertAndRetrieveMany();
484:
485: int topNum = 19;
486: Integer topKey = _intArray[topNum];
487: IntIterator iter = _tree.select(null, topKey, true);
488: for (int i = 0; i < topNum; i++) {
489: assertTrue("Iterator should have another value", iter
490: .hasNext());
491: Integer val = new Integer(iter.next());
492: _log.debug("Iterator Value: " + val);
493: assertEquals("Should get the value back for " + i,
494: new Integer(_intArray.length - i), val);
495: }
496: }
497:
498: public void testGetAllFrom() throws Exception {
499: testInsertAndRetrieveMany();
500:
501: int bottomNum = 19;
502: Integer bottomKey = _intArray[bottomNum];
503: IntIterator iter = _tree.select(bottomKey, null, true);
504: for (int i = bottomNum; i < _intArray.length; 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(_intArray.length - i), val);
511: }
512: }
513:
514: public void testChangeId() throws Exception {
515: testInsertAndRetrieveMany();
516:
517: Integer key = new Integer(67890);
518: int oldId = (_tree.get(key)).intValue();
519: _tree.replace(key, oldId, oldId + 1000);
520: assertEquals("Should get new id back for " + key, oldId + 1000,
521: (_tree.get(key)).intValue());
522: }
523:
524: public void testChangeIdIdentical() throws Exception {
525: testInsertAndRetrieveManyIdentical();
526:
527: Integer key = new Integer(12345);
528: IntList oldIdList = new ArrayIntList();
529: IntIterator iter = null;
530: {
531: ArrayIntList ids = new ArrayIntList();
532: for (IntIterator tocopy = _tree.getAll(key); tocopy
533: .hasNext();) {
534: ids.add(tocopy.next());
535: }
536: iter = ids.iterator();
537: }
538: for (int i = 0; iter.hasNext(); i++) {
539: int oldId = iter.next();
540: oldIdList.add(oldId);
541: if ((i % 2) == 0) {
542: _tree.replace(key, oldId, oldId + 1000);
543: }
544: }
545: {
546: ArrayIntList ids = new ArrayIntList();
547: for (IntIterator tocopy = _tree.getAll(key); tocopy
548: .hasNext();) {
549: ids.add(tocopy.next());
550: }
551: iter = ids.iterator();
552: }
553: for (int i = 0; iter.hasNext(); i++) {
554: int newId = iter.next();
555: int oldId = oldIdList.get(i);
556: if ((i % 2) == 0) {
557: assertEquals("Should get new id back for " + key,
558: oldId + 1000, newId);
559: } else {
560: assertEquals("Should get old id back for " + key,
561: oldId, newId);
562: }
563: }
564: }
565: }
|