001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package com.db4o.foundation;
022:
023: /**
024: * @exclude
025: */
026: public abstract class Tree implements ShallowClone, DeepClone {
027:
028: public static final class ByRef {
029:
030: public ByRef() {
031: }
032:
033: public ByRef(Tree initialValue) {
034: value = initialValue;
035: }
036:
037: public Tree value;
038: }
039:
040: public Tree _preceding;
041: public int _size = 1;
042: public Tree _subsequent;
043:
044: public static final Tree add(Tree a_old, Tree a_new) {
045: if (a_old == null) {
046: return a_new;
047: }
048: return a_old.add(a_new);
049: }
050:
051: public Tree add(final Tree a_new) {
052: return add(a_new, compare(a_new));
053: }
054:
055: /**
056: * On adding a node to a tree, if it already exists, and if
057: * Tree#duplicates() returns false, #isDuplicateOf() will be
058: * called. The added node can then be asked for the node that
059: * prevails in the tree using #duplicateOrThis(). This mechanism
060: * allows doing find() and add() in one run.
061: */
062: public Tree add(final Tree a_new, final int a_cmp) {
063: if (a_cmp < 0) {
064: if (_subsequent == null) {
065: _subsequent = a_new;
066: _size++;
067: } else {
068: _subsequent = _subsequent.add(a_new);
069: if (_preceding == null) {
070: return rotateLeft();
071: }
072: return balance();
073: }
074: } else if (a_cmp > 0 || a_new.duplicates()) {
075: if (_preceding == null) {
076: _preceding = a_new;
077: _size++;
078: } else {
079: _preceding = _preceding.add(a_new);
080: if (_subsequent == null) {
081: return rotateRight();
082: }
083: return balance();
084: }
085: } else {
086: a_new.onAttemptToAddDuplicate(this );
087: }
088: return this ;
089: }
090:
091: /**
092: * On adding a node to a tree, if it already exists, and if
093: * Tree#duplicates() returns false, #onAttemptToAddDuplicate()
094: * will be called and the existing node will be stored in
095: * this._preceding.
096: * This node node can then be asked for the node that prevails
097: * in the tree on adding, using the #addedOrExisting() method.
098: * This mechanism allows doing find() and add() in one run.
099: */
100: public Tree addedOrExisting() {
101: if (wasAddedToTree()) {
102: return this ;
103: }
104: return _preceding;
105: }
106:
107: public boolean wasAddedToTree() {
108: return _size != 0;
109: }
110:
111: public final Tree balance() {
112: int cmp = _subsequent.nodes() - _preceding.nodes();
113: if (cmp < -2) {
114: return rotateRight();
115: } else if (cmp > 2) {
116: return rotateLeft();
117: } else {
118: setSizeOwnPrecedingSubsequent();
119: return this ;
120: }
121: }
122:
123: public Tree balanceCheckNulls() {
124: if (_subsequent == null) {
125: if (_preceding == null) {
126: setSizeOwn();
127: return this ;
128: }
129: return rotateRight();
130: } else if (_preceding == null) {
131: return rotateLeft();
132: }
133: return balance();
134: }
135:
136: public void calculateSize() {
137: if (_preceding == null) {
138: if (_subsequent == null) {
139: setSizeOwn();
140: } else {
141: setSizeOwnSubsequent();
142: }
143: } else {
144: if (_subsequent == null) {
145: setSizeOwnPreceding();
146: } else {
147: setSizeOwnPrecedingSubsequent();
148: }
149: }
150: }
151:
152: /**
153: * returns 0, if keys are equal
154: * uses this - other
155: * returns positive if this is greater than a_to
156: * returns negative if this is smaller than a_to
157: */
158: public abstract int compare(Tree a_to);
159:
160: public static Tree deepClone(Tree a_tree, Object a_param) {
161: if (a_tree == null) {
162: return null;
163: }
164: Tree newNode = (Tree) a_tree.deepClone(a_param);
165: newNode._size = a_tree._size;
166: newNode._preceding = Tree.deepClone(a_tree._preceding, a_param);
167: newNode._subsequent = Tree.deepClone(a_tree._subsequent,
168: a_param);
169: return newNode;
170: }
171:
172: public Object deepClone(Object a_param) {
173: return shallowClone();
174: }
175:
176: public boolean duplicates() {
177: return true;
178: }
179:
180: public final Tree filter(final Predicate4 a_filter) {
181: if (_preceding != null) {
182: _preceding = _preceding.filter(a_filter);
183: }
184: if (_subsequent != null) {
185: _subsequent = _subsequent.filter(a_filter);
186: }
187: if (!a_filter.match(this )) {
188: return remove();
189: }
190: return this ;
191: }
192:
193: public static final Tree find(Tree a_in, Tree a_tree) {
194: if (a_in == null) {
195: return null;
196: }
197: return a_in.find(a_tree);
198: }
199:
200: public final Tree find(final Tree a_tree) {
201: int cmp = compare(a_tree);
202: if (cmp < 0) {
203: if (_subsequent != null) {
204: return _subsequent.find(a_tree);
205: }
206: } else {
207: if (cmp > 0) {
208: if (_preceding != null) {
209: return _preceding.find(a_tree);
210: }
211: } else {
212: return this ;
213: }
214: }
215: return null;
216: }
217:
218: public static final Tree findGreaterOrEqual(Tree a_in, Tree a_finder) {
219: if (a_in == null) {
220: return null;
221: }
222: int cmp = a_in.compare(a_finder);
223: if (cmp == 0) {
224: return a_in; // the highest node in the hierarchy !!!
225: }
226: if (cmp > 0) {
227: Tree node = findGreaterOrEqual(a_in._preceding, a_finder);
228: if (node != null) {
229: return node;
230: }
231: return a_in;
232: }
233: return findGreaterOrEqual(a_in._subsequent, a_finder);
234: }
235:
236: public final static Tree findSmaller(Tree a_in, Tree a_node) {
237: if (a_in == null) {
238: return null;
239: }
240: int cmp = a_in.compare(a_node);
241: if (cmp < 0) {
242: Tree node = findSmaller(a_in._subsequent, a_node);
243: if (node != null) {
244: return node;
245: }
246: return a_in;
247: }
248: return findSmaller(a_in._preceding, a_node);
249: }
250:
251: public final Tree first() {
252: if (_preceding == null) {
253: return this ;
254: }
255: return _preceding.first();
256: }
257:
258: public static Tree last(Tree tree) {
259: if (tree == null) {
260: return null;
261: }
262: return tree.last();
263: }
264:
265: public final Tree last() {
266: if (_subsequent == null) {
267: return this ;
268: }
269: return _subsequent.last();
270: }
271:
272: public void onAttemptToAddDuplicate(Tree a_tree) {
273: _size = 0;
274: _preceding = a_tree;
275: }
276:
277: /**
278: * @return the number of nodes in this tree for balancing
279: */
280: public int nodes() {
281: return _size;
282: }
283:
284: public int ownSize() {
285: return 1;
286: }
287:
288: public Tree remove() {
289: if (_subsequent != null && _preceding != null) {
290: _subsequent = _subsequent.rotateSmallestUp();
291: _subsequent._preceding = _preceding;
292: _subsequent.calculateSize();
293: return _subsequent;
294: }
295: if (_subsequent != null) {
296: return _subsequent;
297: }
298: return _preceding;
299: }
300:
301: public void removeChildren() {
302: _preceding = null;
303: _subsequent = null;
304: setSizeOwn();
305: }
306:
307: public Tree removeFirst() {
308: if (_preceding == null) {
309: return _subsequent;
310: }
311: _preceding = _preceding.removeFirst();
312: calculateSize();
313: return this ;
314: }
315:
316: public static Tree removeLike(Tree from, Tree a_find) {
317: if (from == null) {
318: return null;
319: }
320: return from.removeLike(a_find);
321: }
322:
323: public final Tree removeLike(final Tree a_find) {
324: int cmp = compare(a_find);
325: if (cmp == 0) {
326: return remove();
327: }
328: if (cmp > 0) {
329: if (_preceding != null) {
330: _preceding = _preceding.removeLike(a_find);
331: }
332: } else {
333: if (_subsequent != null) {
334: _subsequent = _subsequent.removeLike(a_find);
335: }
336: }
337: calculateSize();
338: return this ;
339: }
340:
341: public final Tree removeNode(final Tree a_tree) {
342: if (this == a_tree) {
343: return remove();
344: }
345: int cmp = compare(a_tree);
346: if (cmp >= 0) {
347: if (_preceding != null) {
348: _preceding = _preceding.removeNode(a_tree);
349: }
350: }
351: if (cmp <= 0) {
352: if (_subsequent != null) {
353: _subsequent = _subsequent.removeNode(a_tree);
354: }
355: }
356: calculateSize();
357: return this ;
358: }
359:
360: public final Tree rotateLeft() {
361: Tree tree = _subsequent;
362: _subsequent = tree._preceding;
363: calculateSize();
364: tree._preceding = this ;
365: if (tree._subsequent == null) {
366: tree.setSizeOwnPlus(this );
367: } else {
368: tree.setSizeOwnPlus(this , tree._subsequent);
369: }
370: return tree;
371: }
372:
373: public final Tree rotateRight() {
374: Tree tree = _preceding;
375: _preceding = tree._subsequent;
376: calculateSize();
377: tree._subsequent = this ;
378: if (tree._preceding == null) {
379: tree.setSizeOwnPlus(this );
380: } else {
381: tree.setSizeOwnPlus(this , tree._preceding);
382: }
383: return tree;
384: }
385:
386: private final Tree rotateSmallestUp() {
387: if (_preceding != null) {
388: _preceding = _preceding.rotateSmallestUp();
389: return rotateRight();
390: }
391: return this ;
392: }
393:
394: public void setSizeOwn() {
395: _size = ownSize();
396: }
397:
398: public void setSizeOwnPrecedingSubsequent() {
399: _size = ownSize() + _preceding._size + _subsequent._size;
400: }
401:
402: public void setSizeOwnPreceding() {
403: _size = ownSize() + _preceding._size;
404: }
405:
406: public void setSizeOwnSubsequent() {
407: _size = ownSize() + _subsequent._size;
408: }
409:
410: public void setSizeOwnPlus(Tree tree) {
411: _size = ownSize() + tree._size;
412: }
413:
414: public void setSizeOwnPlus(Tree tree1, Tree tree2) {
415: _size = ownSize() + tree1._size + tree2._size;
416: }
417:
418: public static int size(Tree a_tree) {
419: if (a_tree == null) {
420: return 0;
421: }
422: return a_tree.size();
423: }
424:
425: /**
426: * @return the number of objects represented.
427: */
428: public int size() {
429: return _size;
430: }
431:
432: public static final void traverse(Tree tree, Visitor4 visitor) {
433: if (tree == null) {
434: return;
435: }
436: tree.traverse(visitor);
437: }
438:
439: public final void traverse(final Visitor4 a_visitor) {
440: if (_preceding != null) {
441: _preceding.traverse(a_visitor);
442: }
443: a_visitor.visit(this );
444: if (_subsequent != null) {
445: _subsequent.traverse(a_visitor);
446: }
447: }
448:
449: public final void traverseFromLeaves(Visitor4 a_visitor) {
450: if (_preceding != null) {
451: _preceding.traverseFromLeaves(a_visitor);
452: }
453: if (_subsequent != null) {
454: _subsequent.traverseFromLeaves(a_visitor);
455: }
456: a_visitor.visit(this );
457: }
458:
459: // Keep the debug methods to debug the depth
460:
461: // final void debugDepth(){
462: // System.out.println("Tree depth: " + debugDepth(0));
463: // }
464: //
465: // final int debugDepth(int d){
466: // int max = d + 1;
467: // if (i_preceding != null){
468: // max = i_preceding.debugDepth(d + 1);
469: // }
470: // if(i_subsequent != null){
471: // int ms = i_subsequent.debugDepth(d + 1);
472: // if(ms > max){
473: // max = ms;
474: // }
475: // }
476: // return max;
477: // }
478:
479: protected Tree shallowCloneInternal(Tree tree) {
480: tree._preceding = _preceding;
481: tree._size = _size;
482: tree._subsequent = _subsequent;
483: return tree;
484: }
485:
486: public Object shallowClone() {
487: throw new com.db4o.foundation.NotImplementedException();
488: }
489:
490: public abstract Object key();
491:
492: public Object root() {
493: return this;
494: }
495: }
|