001: /*
002: * $Id: TTree.java,v 1.1 2005/06/30 01:14:44 ahimanikya Exp $
003: * =======================================================================
004: * Copyright (c) 2005 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.Comparator;
045: import java.util.Iterator;
046:
047: import org.apache.commons.collections.primitives.IntListIterator;
048: import org.axiondb.AxionException;
049: import org.axiondb.util.IntListIteratorChain;
050: import org.axiondb.util.NullObject;
051:
052: /**
053: * T-Tree contaniner for objects. T-Tree is most efficient data structure for exact and
054: * range data queries in the assumption that all data is present in memory. This class is
055: * used in implementation of query iterators to provide fast indexed access to the
056: * records.
057: *
058: * @version $Revision: 1.1 $ $Date: 2005/06/30 01:14:44 $
059: * @author Pavels Andrejevs
060: */
061: public abstract class TTree {
062:
063: public abstract static class Processor {
064: public void process(AbstractTTreeNode node)
065: throws AxionException {
066: }
067:
068: public void process(AbstractTTreeNode node, int index)
069: throws AxionException {
070: }
071:
072: public void process(int value) throws AxionException {
073: }
074: }
075:
076: protected static class NextNodeLinker extends Processor {
077: AbstractTTreeNode _next = null;
078:
079: public void process(AbstractTTreeNode node)
080: throws AxionException {
081: node._next = _next;
082: _next = node;
083: }
084: }
085:
086: protected static class NodeChecker extends Processor {
087: AbstractTTreeNode first = null;
088: AbstractTTreeNode last = null;
089:
090: public void process(AbstractTTreeNode node)
091: throws AxionException {
092: if (first == null) {
093: first = node;
094: }
095: last = node;
096: node.getPrev();
097: node.getNext();
098: }
099: }
100:
101: protected static class PrevNodeLinker extends Processor {
102: AbstractTTreeNode first = null;
103: AbstractTTreeNode last = null;
104: AbstractTTreeNode prev = null;
105:
106: public void process(AbstractTTreeNode node)
107: throws AxionException {
108: node._prev = prev;
109: prev = node;
110: if (first == null) {
111: first = node;
112: }
113: last = node;
114: }
115: }
116:
117: protected static class TreeForwardNotNullTraverser extends
118: TreeTraverser {
119: TreeForwardNotNullTraverser(IntListIteratorChain chain) {
120: super (chain);
121: }
122:
123: public void process(AbstractTTreeNode node)
124: throws AxionException {
125: Object nullKey = node.getTree().getNullKey();
126: Object[] keys = node.getKeys();
127: int[] values = node.getValues();
128: int n = node.getNodeSize();
129: for (int i = 0; i < n; i++) {
130: if (keys[i] != nullKey) {
131: _chain.addIterator(values[i]);
132: }
133: }
134: }
135: }
136:
137: protected static class TreeForwardNullTraverser extends
138: TreeTraverser {
139: TreeForwardNullTraverser(IntListIteratorChain chain) {
140: super (chain);
141: }
142:
143: public void process(AbstractTTreeNode node)
144: throws AxionException {
145: Object nullKey = node.getTree().getNullKey();
146: Object[] keys = node.getKeys();
147: int[] values = node.getValues();
148: int n = node.getNodeSize();
149: for (int i = 0; i < n; i++) {
150: if (keys[i] == nullKey) {
151: _chain.addIterator(values[i]);
152: }
153: }
154: }
155: }
156:
157: protected static class TreeForwardTraverser extends TreeTraverser {
158: TreeForwardTraverser(IntListIteratorChain chain) {
159: super (chain);
160: }
161:
162: public void process(AbstractTTreeNode node)
163: throws AxionException {
164: int[] values = node.getValues();
165: int n = node.getNodeSize();
166: for (int i = 0; i < n; i++) {
167: _chain.addIterator(values[i]);
168: }
169: }
170: }
171:
172: protected static class TreeSerializer extends Processor {
173: java.io.ObjectOutputStream out;
174:
175: TreeSerializer(java.io.ObjectOutputStream s) {
176: out = s;
177: }
178:
179: public void process(AbstractTTreeNode node) {
180: try {
181: out.writeObject(node);
182: } catch (java.io.IOException x) {
183: throw new Error("Failed to serialize T-Tree: " + x);
184: }
185: }
186: }
187:
188: protected static class TreeStripper extends Processor {
189: TreeStripper() {
190: }
191:
192: public void process(AbstractTTreeNode node)
193: throws AxionException {
194: node.destroy();
195: }
196: }
197:
198: protected abstract static class TreeTraverser extends Processor {
199: IntListIteratorChain _chain;
200:
201: TreeTraverser(IntListIteratorChain chain) {
202: _chain = chain;
203: }
204:
205: public void process(AbstractTTreeNode node, int index)
206: throws AxionException {
207: _chain.addIterator(node.getValue(index));
208: }
209:
210: public void process(int value) {
211: _chain.addIterator(value);
212: }
213: }
214:
215: protected static class ValueReplacer extends Processor {
216: int _newValue;
217: int _oldValue;
218:
219: ValueReplacer(int oldValue, int newValue) {
220: _oldValue = oldValue;
221: _newValue = newValue;
222: }
223:
224: public void process(AbstractTTreeNode node, int index)
225: throws AxionException {
226: if (node.getValue(index) == _oldValue) {
227: node.setValue(index, _newValue);
228: }
229: }
230: }
231:
232: private Comparator _comparator;
233: private AbstractTTreeNode _first;
234: private AbstractTTreeNode _last;
235:
236: private int _maxNodeSize;
237: private TTreeMetaData _metaData;
238: private AbstractTTreeNode _root;
239:
240: // Constructors
241: // ---------------------------------------------------------------------
242:
243: public TTree(int maxNodeSize, Comparator comparator,
244: TTreeMetaData metaData) throws AxionException {
245: _maxNodeSize = maxNodeSize;
246: _comparator = comparator;
247: _metaData = metaData;
248: // Create all nodes
249: if (metaData.getFileById(metaData.getRootFileId()).exists()) {
250: setRoot(newNode(metaData.getRootFileId()));
251: linkNodes();
252: } else {
253: setRoot(null);
254: }
255: }
256:
257: public final void check() throws AxionException {
258: NodeChecker checker = new NodeChecker();
259: traverseForward(checker);
260: if (checker.first != getFirst()) {
261: System.out.println("'FIRST' ERROR");
262: }
263: if (checker.last != getLast()) {
264: System.out.println("'LAST' ERROR");
265: }
266: }
267:
268: public final void delete(Object key, int value)
269: throws AxionException {
270: if (getRoot() != null) {
271: NodeReference ref = new NodeReference(getRoot());
272: getRoot().delete(key, value, ref);
273: setRoot(ref.pg);
274: size(size() - 1);
275: }
276: // check();
277: }
278:
279: public final void deleteAll(Object key) throws AxionException {
280: IntListIterator it = getAll(key);
281: while (it.hasNext()) {
282: int value = it.next();
283: delete(key, value);
284: }
285: }
286:
287: public void deleteNode(AbstractTTreeNode node) {
288: _metaData.clearDirty(node);
289: File file = _metaData.getFileById(node.getFileId());
290: if (file.exists()) {
291: file.delete();
292: }
293: }
294:
295: public Comparator getComparator() {
296: return _comparator;
297: }
298:
299: public final AbstractTTreeNode getFirst() {
300: return _first;
301: }
302:
303: public final AbstractTTreeNode getLast() {
304: return _last;
305: }
306:
307: public int getMaxNodeSize() {
308: return _maxNodeSize;
309: }
310:
311: public TTreeMetaData getMetaData() {
312: return _metaData;
313: }
314:
315: public int getMinNodeSize() {
316: return _maxNodeSize - 1; // if bigger than 1, tests do fail
317: }
318:
319: public Object getNullKey() {
320: return NullObject.INSTANCE;
321: }
322:
323: public final AbstractTTreeNode getRoot() {
324: return _root;
325: }
326:
327: public final void insert(Object key, int value, boolean unique)
328: throws AxionException {
329: if (getRoot() != null) {
330: NodeReference ref = new NodeReference(getRoot());
331: getRoot().insert(key, value, unique, ref);
332: setRoot(ref.pg);
333: } else {
334: setRoot(newNode());
335: getRoot().addKeyValue(key, value);
336: setFirst(getRoot());
337: setLast(getRoot());
338: }
339: size(size() + 1);
340: // check();
341: }
342:
343: public boolean isMemoryOnly() {
344: return _metaData.isMemoryOnly();
345: }
346:
347: public boolean isValid() {
348: return true;
349: }
350:
351: public abstract AbstractTTreeNode newNode() throws AxionException;
352:
353: public abstract AbstractTTreeNode newNode(int fileId)
354: throws AxionException;
355:
356: public final void save(File dataDirectory) throws AxionException {
357: _metaData.setDataDirectory(dataDirectory);
358: if (_metaData.hasDirtyNodes()) {
359: _metaData.saveMetaDataFile();
360: }
361: for (Iterator iter = _metaData.getDirtyNodes(); iter.hasNext();) {
362: AbstractTTreeNode node = (AbstractTTreeNode) iter.next();
363: node.write();
364: node.clearDirty();
365: iter.remove();
366: }
367: }
368:
369: public final void saveAfterTruncate(File dataDirectory)
370: throws AxionException {
371: _metaData.setAllClean();
372: save(dataDirectory);
373: }
374:
375: public void scanBackward(Processor proc) throws AxionException {
376: AbstractTTreeNode node = getLast();
377: while (node != null) {
378: proc.process(node);
379: node = node.getPrev();
380: }
381: }
382:
383: public void scanForward(Processor proc) throws AxionException {
384: AbstractTTreeNode node = getFirst();
385: while (node != null) {
386: proc.process(node);
387: node = node.getNext();
388: }
389: }
390:
391: public IntListIteratorChain getInorderIterator()
392: throws AxionException {
393: IntListIteratorChain chain = new IntListIteratorChain();
394: scanForward(new TreeForwardTraverser(chain));
395: return chain;
396: }
397:
398: public final IntListIterator getAllNotNull() throws AxionException {
399: IntListIteratorChain chain = new IntListIteratorChain();
400: scanForward(new TreeForwardNotNullTraverser(chain));
401: return chain;
402: }
403:
404: public final IntListIterator getAllNull() throws AxionException {
405: IntListIteratorChain chain = new IntListIteratorChain();
406: scanForward(new TreeForwardNullTraverser(chain));
407: return chain;
408: }
409:
410: public final void replace(Object key, int oldValue, int newValue)
411: throws AxionException {
412: select(key, key, 1, new ValueReplacer(oldValue, newValue),
413: false);
414: }
415:
416: public final Integer get(Object key) throws AxionException {
417: IntListIteratorChain chain = select(key, key, true, true);
418: return chain.hasNext() ? new Integer(chain.next()) : null;
419: }
420:
421: public final IntListIterator getAll(Object key)
422: throws AxionException {
423: return select(key, key, true, false);
424: }
425:
426: public IntListIteratorChain select(Object minValue,
427: Object maxValue, boolean inclusive) throws AxionException {
428: return select(minValue, maxValue, inclusive, false);
429: }
430:
431: public IntListIteratorChain select(Object minValue,
432: Object maxValue, boolean inclusive, boolean first)
433: throws AxionException {
434: IntListIteratorChain chain = new IntListIteratorChain();
435: if (false) {
436: if (getRoot() != null) {
437: getRoot().select(minValue, maxValue, inclusive ? 1 : 0,
438: new TreeForwardTraverser(chain), first);
439: }
440: } else {
441: select(minValue, maxValue, inclusive ? 1 : 0,
442: new TreeForwardTraverser(chain), first);
443: }
444: return chain;
445: }
446:
447: // Ultra-fast
448: public final boolean select(Object minValue, Object maxValue,
449: int inclusive, TTree.Processor proc, boolean first)
450: throws AxionException {
451: AbstractTTreeNode node = getFirst();
452: int r = 0;
453:
454: if (minValue != null) {
455: AbstractTTreeNode x = getRoot();
456: while (x != null) {
457: if (isLess(minValue, x.getMinKey(), inclusive)) {
458: x = x.getLeft();
459: } else {
460: node = x;
461: x = x.getRight();
462: }
463: }
464: while (node != null
465: && !isLess(minValue, node.getMaxKey(), inclusive)) {
466: node = node.getNext();
467: }
468: if (node == null) {
469: return false;
470: }
471: int l;
472: for (l = 0, r = node.getNodeSize(); l < r;) {
473: int m = (l + r) >> 1;
474: if (!isLess(minValue, node.getKey(m), inclusive)) {
475: l = m + 1;
476: } else {
477: r = m;
478: }
479: }
480: }
481:
482: if (node == null) {
483: node = getFirst();
484: if (node == null) {
485: return false;
486: }
487: }
488:
489: do {
490: int n = node.getNodeSize();
491: while (r < n) {
492: if (maxValue != null
493: && !isLess(node.getKey(r), maxValue, inclusive)) {
494: return false;
495: }
496: proc.process(node, r);
497: if (first) {
498: return false;
499: }
500: r++;
501: }
502: node = node.getNext();
503: r = 0;
504: } while (node != null);
505:
506: return true;
507: }
508:
509: public final void setFirst(AbstractTTreeNode first) {
510: _first = first;
511: }
512:
513: public final void setLast(AbstractTTreeNode last) {
514: _last = last;
515: }
516:
517: public void setMaxNodeSize(int maxNodeSize) {
518: _maxNodeSize = maxNodeSize;
519: }
520:
521: public final int size() {
522: return _metaData.getTreeSize();
523: }
524:
525: public final String toString() {
526: try {
527: StringBuffer buf = new StringBuffer();
528: buf.append(getRoot() != null ? getRoot().toString(0)
529: : "empty\n");
530: buf.append("<");
531: buf.append("F:"
532: + (getFirst() != null ? "" + getFirst().getFileId()
533: : ""));
534: buf.append(" ");
535: buf.append("L:"
536: + (getLast() != null ? "" + getLast().getFileId()
537: : ""));
538: buf.append(">\n");
539: return buf.toString();
540: } catch (AxionException e) {
541: return "ERROR: " + e;
542: }
543: }
544:
545: /**
546: * Traverse T-Tree elements in descent order
547: */
548: public void traverseBackward(Processor proc) throws AxionException {
549: if (getRoot() != null) {
550: getRoot().traverseBackward(proc);
551: }
552: }
553:
554: /**
555: * Traverse T-Tree elements in ascent order
556: */
557: public void traverseForward(Processor proc) throws AxionException {
558: if (getRoot() != null) {
559: getRoot().traverseForward(proc);
560: }
561: }
562:
563: public void truncate() throws AxionException {
564: setRoot(null);
565: setFirst(null);
566: setLast(null);
567: }
568:
569: final int compare(Object x, Object y) {
570: Comparator c = getComparator();
571: Object nullKey = getNullKey();
572: if (x == nullKey && y == nullKey) {
573: return 0;
574: }
575: if (x == nullKey && y != nullKey) {
576: return -1;
577: } else if (y == nullKey && x != nullKey) {
578: return 1;
579: }
580: return c.compare(x, y);
581: }
582:
583: final boolean isEqual(Object x, Object y) {
584: return compare(x, y) == 0;
585: }
586:
587: final boolean isGreater(Object x, Object y, int inclusive) {
588: return compare(x, y) > -inclusive;
589: }
590:
591: final boolean isGreaterThan(Object x, Object y) {
592: return compare(x, y) > 0;
593: }
594:
595: final boolean isGreaterThanOrEqual(Object x, Object y) {
596: return compare(x, y) >= 0;
597: }
598:
599: final boolean isLess(Object x, Object y, int inclusive) {
600: return compare(x, y) < inclusive;
601: }
602:
603: final boolean isLessThan(Object x, Object y) {
604: return compare(x, y) < 0;
605: }
606:
607: final boolean isLessThanOrEqual(Object x, Object y) {
608: return compare(x, y) <= 0;
609: }
610:
611: final boolean isNotEqual(Object x, Object y) {
612: return compare(x, y) != 0;
613: }
614:
615: protected final void setRoot(AbstractTTreeNode root) {
616: _root = root;
617: if (root != null) {
618: _metaData.setRootFileId(root.getFileId());
619: }
620: }
621:
622: protected final void size(int size) {
623: _metaData.setTreeSize(size);
624: }
625:
626: private void linkNodes() throws AxionException {
627: PrevNodeLinker prevLinker = new PrevNodeLinker();
628: traverseForward(prevLinker);
629: traverseBackward(new NextNodeLinker());
630: setFirst(prevLinker.first);
631: setLast(prevLinker.last);
632: }
633:
634: }
|