001: /*
002: * $Id: AbstractTTreeNode.java,v 1.1 2005/06/30 01:14:44 ahimanikya Exp $
003: * ======================================================================= Copyright (c)
004: * 2002-2004 Axion Development Team. All rights reserved. Redistribution and use in source
005: * and binary forms, with or without modification, are permitted provided that the
006: * following conditions are met: 1. Redistributions of source code must retain the above
007: * copyright notice, this list of conditions and the following disclaimer. 2.
008: * Redistributions in binary form must reproduce the above copyright notice, this list of
009: * conditions and the following disclaimer in the documentation and/or other materials
010: * provided with the distribution. 3. The names "Tigris", "Axion", nor the names of its
011: * contributors may not be used to endorse or promote products derived from this software
012: * without specific prior written permission. 4. Products derived from this software may
013: * not be called "Axion", nor may "Tigris" or "Axion" appear in their names without
014: * specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS
015: * AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
016: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
017: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
018: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
019: * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
020: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
021: * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
022: * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
023: * POSSIBILITY OF SUCH DAMAGE.
024: * =======================================================================
025: */
026:
027: package org.axiondb.ext.indexes.ttree;
028:
029: import java.io.File;
030: import java.io.IOException;
031: import java.io.ObjectInputStream;
032: import java.io.ObjectOutputStream;
033:
034: import org.axiondb.AxionException;
035: import org.axiondb.io.AxionFileSystem;
036:
037: /**
038: * Base Node implementation for T-Tree.
039: *
040: * @version $Revision: 1.1 $ $Date: 2005/06/30 01:14:44 $
041: * @author Pavels Andrejevs
042: */
043:
044: public abstract class AbstractTTreeNode {
045:
046: protected static AxionFileSystem FS = new AxionFileSystem();
047:
048: /**
049: * Return a String comprised of N spaces.
050: */
051: protected static final String space(int n) {
052: StringBuffer buf = new StringBuffer(0);
053: for (int i = 0; i < n; i++) {
054: buf.append(" ");
055: }
056: return buf.toString();
057: }
058:
059: protected int _balance;
060: protected int _fileId;
061: protected AbstractTTreeNode _left;
062: protected AbstractTTreeNode _next;
063: protected int _nodeSize;
064: protected AbstractTTreeNode _prev;
065: protected AbstractTTreeNode _right;
066: protected TTree _tree;
067: private boolean _dirty;
068:
069: public AbstractTTreeNode(TTree tree, int fileId)
070: throws AxionException {
071: _tree = tree;
072: if (tree.isMemoryOnly()) {
073: _dirty = true;
074: }
075: if (fileId != 0) {
076: // Load existing node from disk.
077: setFileId(fileId);
078: read();
079: } else {
080: // A new node is just created.
081: setFileId(tree.getMetaData().incrementCounter());
082: create();
083: }
084: }
085:
086: public abstract void addKeyValue(Object key, int value)
087: throws AxionException;
088:
089: public void clearDirty() {
090: _dirty = false;
091: }
092:
093: public abstract void copyKeysValues(int from, int to, int length)
094: throws AxionException;
095:
096: // Return value:
097: // 1: The tree diminished in height.
098: // 0: The tree didn't change in height.
099: // -1: The key was not found.
100: public final int delete(Object key, int value, NodeReference ref)
101: throws AxionException {
102: AbstractTTreeNode pg;
103: int n = _nodeSize;
104: int diff = _tree.compare(key, getKey(0));
105: if (diff <= 0) {
106: if (_left != null) {
107: pg = ref.pg;
108: ref.pg = _left;
109: int h = _left.delete(key, value, ref);
110: if (_left != ref.pg) {
111: _left = ref.pg;
112: markDirty();
113: }
114: ref.pg = pg;
115: if (h > 0) {
116: return balanceLeftBranch(ref, false);
117: } else if (h == 0) {
118: return 0;
119: }
120: }
121: }
122: diff = _tree.compare(key, getKey(n - 1));
123: if (diff <= 0) {
124: for (int i = 0; i < n; i++) {
125: if (getValue(i) == value) {
126: if (n == 1) {
127: if (_right == null || _left == null) {
128: // delete this
129: if (_right == null) {
130: ref.pg = _left;
131: } else {
132: ref.pg = _right;
133: }
134: unlinkThis();
135: _tree.deleteNode(this );
136: return 1;
137: }
138: }
139: if (n <= _tree.getMinNodeSize()) {
140: if (_left != null && _balance <= 0) {
141: AbstractTTreeNode prev = getPrev();
142: if (i > 0) {
143: copyKeysValues(0, 1, i);
144: }
145:
146: Object tKey = prev
147: .getKey(prev._nodeSize - 1);
148: int tValue = prev
149: .getValue(prev._nodeSize - 1);
150: setKeyValue(0, tKey, tValue);
151: pg = ref.pg;
152: ref.pg = _left;
153: int h = _left.delete(tKey, tValue, ref);
154: if (_left != ref.pg) {
155: _left = ref.pg;
156: markDirty();
157: }
158: ref.pg = pg;
159: if (h > 0) {
160: h = balanceLeftBranch(ref, false);
161: }
162: return h;
163: } else if (_right != null) {
164: AbstractTTreeNode next = getNext();
165: int len = n - i - 1;
166: if (len > 0) {
167: copyKeysValues(i + 1, i, len);
168: }
169: Object tKey = next.getKey(0);
170: int tValue = next.getValue(0);
171: setKeyValue(n - 1, tKey, tValue);
172: pg = ref.pg;
173: ref.pg = _right;
174: int h = _right.delete(tKey, tValue, ref);
175: if (_right != ref.pg) {
176: _right = ref.pg;
177: markDirty();
178: }
179: ref.pg = pg;
180: if (h > 0) {
181: h = balanceRightBranch(ref, false);
182: }
183: return h;
184: }
185: }
186: int len = n - i - 1;
187: if (len > 0) {
188: copyKeysValues(i + 1, i, len);
189: }
190: removeKeyValue(n - 1);
191: return 0;
192: }
193: }
194: }
195: if (_right != null) {
196: pg = ref.pg;
197: ref.pg = _right;
198: int h = _right.delete(key, value, ref);
199: if (_right != ref.pg) {
200: _right = ref.pg;
201: markDirty();
202: }
203: ref.pg = pg;
204: if (h > 0) {
205: return balanceRightBranch(ref, false);
206: } else {
207: return h;
208: }
209: }
210: return -1;
211: }
212:
213: public final int getFileId() {
214: return _fileId;
215: }
216:
217: public AbstractTTreeNode getLeft() {
218: return _left;
219: }
220:
221: public Object getMaxKey() throws AxionException {
222: return getKey(_nodeSize - 1);
223: }
224:
225: public Object getMinKey() throws AxionException {
226: return getKey(0);
227: }
228:
229: public AbstractTTreeNode getRight() {
230: return _right;
231: }
232:
233: public final TTree getTree() {
234: return _tree;
235: }
236:
237: // Return value: Has the tree grown in height?
238: public final boolean insert(Object key, int value, boolean unique,
239: NodeReference ref) throws AxionException {
240: int n = _nodeSize;
241: int diff = _tree.compare(key, getKey(0));
242: AbstractTTreeNode pg;
243: if (diff <= 0) {
244: if (diff == 0 && unique) {
245: throw new AxionException("Expected the indexed column"
246: + " to be unique, found '" + key + "' already.");
247: }
248: if ((_left == null || diff == 0)
249: && n != _tree.getMaxNodeSize()) {
250: insertKeyValue(0, key, value);
251: return false;
252: }
253: if (_left == null) {
254: linkAsLeft(_tree.newNode());
255: _left.addKeyValue(key, value);
256: } else {
257: pg = ref.pg;
258: ref.pg = _left;
259: boolean grow = _left.insert(key, value, unique, ref);
260: if (_left != ref.pg) {
261: _left = ref.pg;
262: markDirty();
263: }
264: ref.pg = pg;
265: if (!grow)
266: return false;
267: }
268: return balanceRightBranch(ref, true) == 0 ? true : false;
269: }
270: diff = _tree.compare(key, getKey(n - 1));
271: if (diff >= 0) {
272: if (diff == 0 && unique) {
273: throw new AxionException("Expected the indexed column"
274: + " to be unique, found '" + key + "' already.");
275: }
276: if ((_right == null || diff == 0)
277: && n != _tree.getMaxNodeSize()) {
278: addKeyValue(key, value);
279: return false;
280: }
281: if (_right == null) {
282: linkAsRight(_tree.newNode());
283: _right.addKeyValue(key, value);
284: } else {
285: pg = ref.pg;
286: ref.pg = _right;
287: boolean grow = _right.insert(key, value, unique, ref);
288: if (_right != ref.pg) {
289: _right = ref.pg;
290: markDirty();
291: }
292: ref.pg = pg;
293: if (!grow)
294: return false;
295: }
296: return balanceLeftBranch(ref, true) == 0 ? true : false;
297: }
298: int l = 1, r = n - 1;
299: while (l < r) {
300: int i = (l + r) >> 1;
301: diff = _tree.compare(key, getKey(i));
302: if (diff > 0) {
303: l = i + 1;
304: } else {
305: r = i;
306: if (diff == 0) {
307: if (unique) {
308: throw new AxionException(
309: "Expected the indexed column"
310: + " to be unique, found '"
311: + key + "' already.");
312: }
313: break;
314: }
315: }
316: }
317: // Insert before r
318: if (n != _tree.getMaxNodeSize()) {
319: insertKeyValue(r, key, value);
320: return false;
321: } else {
322: Object tKey;
323: int tValue;
324: if (_balance >= 0) {
325: tKey = getKey(0);
326: tValue = getValue(0);
327: copyKeysValues(1, 0, r - 1);
328: setKeyValue(r - 1, key, value);
329: } else {
330: tKey = getKey(n - 1);
331: tValue = getValue(n - 1);
332: copyKeysValues(r, r + 1, _nodeSize - r - 1);
333: setKeyValue(r, key, value);
334: }
335: return insert(tKey, tValue, unique, ref);
336: }
337: }
338:
339: public abstract void insertKeyValue(int index, Object key, int value)
340: throws AxionException;
341:
342: public final boolean isLeaf() {
343: return _left == null && _right == null;
344: }
345:
346: public final boolean isValid() {
347: return true;
348: }
349:
350: public void markDirty() {
351: if (!_dirty) {
352: _tree.getMetaData().setDirty(this );
353: _dirty = true;
354: }
355: }
356:
357: public final void read() throws AxionException {
358: ObjectInputStream in = null;
359: try {
360: File file = _tree.getMetaData().getFileById(_fileId);
361: in = FS.openObjectInputSteam(file);
362:
363: // Read node size
364: _nodeSize = in.readInt();
365:
366: if (_tree.isMemoryOnly()) {
367: // Load data right away
368: Object[] keys = createKeys();
369: int[] values = createValues();
370: for (int i = 0; i < _nodeSize; i++) {
371: Object key = in.readObject();
372: int value = in.readInt();
373: keys[i] = key;
374: values[i] = value;
375: }
376: } else {
377: // We can load data later
378: for (int i = 0; i < _nodeSize; i++) {
379: in.readObject();
380: in.readInt();
381: }
382: }
383:
384: // Read balance
385: _balance = in.readInt();
386: // Read childs
387: int hasLeft = in.readInt();
388: if (hasLeft == 1) {
389: _left = _tree.newNode(in.readInt());
390: } else {
391: _left = null;
392: }
393: int hasRight = in.readInt();
394: if (hasRight == 1) {
395: _right = _tree.newNode(in.readInt());
396: } else {
397: _right = null;
398: }
399: } catch (ClassNotFoundException e) {
400: throw new AxionException(e);
401: } catch (IOException e) {
402: throw new AxionException(e);
403: } finally {
404: FS.closeInputStream(in);
405: }
406: }
407:
408: public abstract void removeKeyValue(int index)
409: throws AxionException;
410:
411: // Slow select.
412: // Return value: do we need to continue search?
413: public final boolean select(Object minValue, Object maxValue,
414: int inclusive, TTree.Processor proc, boolean first)
415: throws AxionException {
416: int l, r, m, n = _nodeSize;
417:
418: if (minValue != null
419: && !_tree.isLess(minValue, getMinKey(), inclusive)) {
420: if (!_tree.isLess(minValue, getMaxKey(), inclusive)) {
421: if (_right != null) {
422: return _right.select(minValue, maxValue, inclusive,
423: proc, first);
424: }
425: return true;
426: }
427: for (l = 0, r = n; l < r;) {
428: m = (l + r) >> 1;
429: if (!_tree.isLess(minValue, getKey(m), inclusive)) {
430: l = m + 1;
431: } else {
432: r = m;
433: }
434: }
435: while (r < n) {
436: if (maxValue != null
437: && !_tree
438: .isLess(getKey(r), maxValue, inclusive)) {
439: return false;
440: }
441: proc.process(this , r);
442: if (first) {
443: return false;
444: }
445: r++;
446: }
447: if (_right != null) {
448: return _right.select(minValue, maxValue, inclusive,
449: proc, first);
450: }
451: return true;
452: }
453: if (_left != null) {
454: if (!_left.select(minValue, maxValue, inclusive, proc,
455: first)) {
456: return false;
457: }
458: }
459: for (l = 0; l < n; l++) {
460: if (maxValue != null
461: && !_tree.isLess(getKey(l), maxValue, inclusive)) {
462: return false;
463: }
464: proc.process(this , l);
465: if (first) {
466: return false;
467: }
468: }
469: if (_right != null) {
470: return _right.select(minValue, maxValue, inclusive, proc,
471: first);
472: }
473: return true;
474: }
475:
476: public abstract void setKeyValue(int index, Object key, int value)
477: throws AxionException;
478:
479: public final String toString() {
480: return "" + getFileId();
481: }
482:
483: public final void traverseBackward(TTree.Processor proc)
484: throws AxionException {
485: if (_right != null) {
486: _right.traverseBackward(proc);
487: }
488: proc.process(this );
489: if (_left != null) {
490: _left.traverseBackward(proc);
491: }
492: }
493:
494: public final void traverseForward(TTree.Processor proc)
495: throws AxionException {
496: if (_left != null) {
497: _left.traverseForward(proc);
498: }
499: proc.process(this );
500: if (_right != null) {
501: _right.traverseForward(proc);
502: }
503: }
504:
505: public final void write() throws AxionException {
506: ObjectOutputStream out = null;
507: try {
508: File file = _tree.getMetaData().getFileById(_fileId);
509: out = FS.createObjectOutputSteam(file);
510:
511: // Write data
512: out.writeInt(_nodeSize);
513: Object[] keys = getKeys();
514: int[] values = getValues();
515: for (int i = 0; i < _nodeSize; i++) {
516: out.writeObject(keys[i]);
517: out.writeInt(values[i]);
518: }
519:
520: // Write balance
521: out.writeInt(_balance);
522:
523: // Write childs
524: if (_left != null) {
525: out.writeInt(1);
526: out.writeInt(_left.getFileId());
527: } else {
528: out.writeInt(0);
529: }
530: if (_right != null) {
531: out.writeInt(1);
532: out.writeInt(_right.getFileId());
533: } else {
534: out.writeInt(0);
535: }
536: } catch (IOException e) {
537: throw new AxionException(e);
538: } finally {
539: FS.closeOutputStream(out);
540: }
541: }
542:
543: // Return value:
544: // 1: The tree changed in height.
545: // 0: The tree didn't change in height.
546: protected final int balanceLeftBranch(NodeReference ref,
547: boolean insert) throws AxionException {
548: if (_balance < 0) {
549: _balance = 0;
550: markDirty();
551: return 1;
552: } else if (_balance == 0) {
553: _balance = 1;
554: markDirty();
555: return 0;
556: } else {
557: AbstractTTreeNode righty = this ._right;
558: if (righty._balance > 0) { // single RR turn (1)
559: this ._right = righty._left;
560: righty._left = this ;
561: _balance = 0;
562: righty._balance = 0;
563: ref.pg = righty;
564: righty.markDirty();
565: markDirty();
566: return 1;
567: } else if (righty._balance == 0 && !insert) { // single RR turn (2)
568: this ._right = righty._left;
569: righty._left = this ;
570: _balance = 1;
571: righty._balance = -1;
572: ref.pg = righty;
573: righty.markDirty();
574: markDirty();
575: return 0;
576: } else { // double RL turn
577: AbstractTTreeNode lefty = righty._left;
578: righty._left = lefty._right;
579: lefty._right = righty;
580: this ._right = lefty._left;
581: lefty._left = this ;
582: _balance = lefty._balance > 0 ? -1 : 0;
583: righty._balance = lefty._balance < 0 ? 1 : 0;
584: lefty._balance = 0;
585: ref.pg = lefty;
586: lefty.markDirty();
587: righty.markDirty();
588: markDirty();
589: return 1;
590: }
591: }
592: }
593:
594: // Return value:
595: // 1: The tree changed in height.
596: // 0: The tree didn't change in height.
597: protected final int balanceRightBranch(NodeReference ref,
598: boolean insert) throws AxionException {
599: if (_balance > 0) {
600: _balance = 0;
601: markDirty();
602: return 1;
603: } else if (_balance == 0) {
604: _balance = -1;
605: markDirty();
606: return 0;
607: } else {
608: AbstractTTreeNode lefty = this ._left;
609: if (lefty._balance < 0) { // single LL turn (1)
610: this ._left = lefty._right;
611: lefty._right = this ;
612: _balance = 0;
613: lefty._balance = 0;
614: ref.pg = lefty;
615: lefty.markDirty();
616: markDirty();
617: return 1;
618: } else if (lefty._balance == 0 && !insert) { // single LL turn (2)
619: this ._left = lefty._right;
620: lefty._right = this ;
621: _balance = -1;
622: lefty._balance = 1;
623: ref.pg = lefty;
624: lefty.markDirty();
625: markDirty();
626: return 0;
627: } else { // double LR turn
628: AbstractTTreeNode righty = lefty._right;
629: lefty._right = righty._left;
630: righty._left = lefty;
631: this ._left = righty._right;
632: righty._right = this ;
633: _balance = righty._balance < 0 ? 1 : 0;
634: lefty._balance = righty._balance > 0 ? -1 : 0;
635: righty._balance = 0;
636: ref.pg = righty;
637: lefty.markDirty();
638: righty.markDirty();
639: markDirty();
640: return 1;
641: }
642: }
643: }
644:
645: protected void create() {
646: createKeys();
647: createValues();
648: }
649:
650: protected abstract Object[] createKeys();
651:
652: protected abstract int[] createValues();
653:
654: protected void destroy() {
655: destroyKeys();
656: destroyValues();
657: }
658:
659: protected abstract void destroyKeys();
660:
661: protected abstract void destroyValues();
662:
663: protected abstract Object getKey(int index) throws AxionException;
664:
665: protected abstract Object[] getKeys() throws AxionException;
666:
667: protected AbstractTTreeNode getNext() {
668: return _next;
669: }
670:
671: protected final int getNodeSize() throws AxionException {
672: return _nodeSize;
673: }
674:
675: protected AbstractTTreeNode getPrev() {
676: return _prev;
677: }
678:
679: protected abstract int getValue(int index) throws AxionException;
680:
681: protected abstract int[] getValues() throws AxionException;
682:
683: protected abstract void setKey(int index, Object key)
684: throws AxionException;
685:
686: protected final void setNodeSize(int nodeSize)
687: throws AxionException {
688: _nodeSize = nodeSize;
689: }
690:
691: protected abstract void setValue(int index, int value)
692: throws AxionException;
693:
694: /**
695: * Print this node, with every line prefixed by N*space spaces.
696: */
697: protected final String toString(int space) throws AxionException {
698: StringBuffer buf = new StringBuffer();
699: buf.append(space(space));
700: buf.append(getFileId());
701: buf.append(" (");
702: buf
703: .append("P:"
704: + (_prev != null ? "" + _prev.getFileId() : ""));
705: buf.append(" ");
706: buf
707: .append("N:"
708: + (_next != null ? "" + _next.getFileId() : ""));
709: buf.append(")");
710: buf.append(": ");
711:
712: Object[] keys = getKeys();
713: int[] values = getValues();
714: int length = _nodeSize;
715: for (int i = 0; i < length; i++) {
716: if (i != 0) {
717: buf.append(", ");
718: }
719: buf.append(keys[i] + "/" + values[i]);
720: }
721:
722: buf.append("\n");
723: if (_left != null) {
724: buf.append(_left.toString(space + 1));
725: } else {
726: buf.append(space(space + 1));
727: buf.append("null");
728: buf.append("\n");
729: }
730: if (_right != null) {
731: buf.append(_right.toString(space + 1));
732: } else {
733: buf.append(space(space + 1));
734: buf.append("null");
735: buf.append("\n");
736: }
737: return buf.toString();
738: }
739:
740: private void linkAsLeft(AbstractTTreeNode node) {
741: _left = node;
742: _left._prev = _prev;
743: if (_prev != null) {
744: _prev._next = _left;
745: }
746: _left._next = this ;
747: _prev = _left;
748: if (_left._prev == null) {
749: _tree.setFirst(_left);
750: }
751: markDirty();
752: }
753:
754: private void linkAsRight(AbstractTTreeNode node) {
755: _right = node;
756: _right._next = _next;
757: if (_next != null) {
758: _next._prev = _right;
759: }
760: _right._prev = this ;
761: _next = _right;
762: if (_right._next == null) {
763: _tree.setLast(_right);
764: }
765: markDirty();
766: }
767:
768: private final void setFileId(int fileId) {
769: _fileId = fileId;
770: }
771:
772: private void unlinkThis() {
773: if (_prev != null) {
774: _prev._next = _next;
775: } else {
776: _tree.setFirst(_next);
777: }
778: if (_next != null) {
779: _next._prev = _prev;
780: } else {
781: _tree.setLast(_prev);
782: }
783: }
784:
785: }
786:
787: class NodeReference {
788: AbstractTTreeNode pg;
789:
790: NodeReference(AbstractTTreeNode p) {
791: pg = p;
792: }
793: }
|