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