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.internal.ix;
022:
023: import com.db4o.foundation.*;
024: import com.db4o.internal.*;
025: import com.db4o.internal.freespace.*;
026: import com.db4o.internal.query.processor.*;
027:
028: /**
029: * @exclude
030: */
031: public class IxTraverser {
032:
033: // for debugging purposes, search for _constraint to uncomment
034: // public Object _constraint;
035:
036: private IxPath i_appendHead;
037: private IxPath i_appendTail;
038:
039: private IxPath i_greatHead;
040: private IxPath i_greatTail;
041:
042: Indexable4 i_handler;
043:
044: private IxPath i_smallHead;
045: private IxPath i_smallTail;
046:
047: // Bitmap that denotes, which elements to take, consisting of four booleans:
048: // [0] take nulls
049: // [1] take smaller
050: // [2] take equal
051: // [3] take greater
052:
053: boolean[] i_take;
054:
055: private void add(Visitor4 visitor, IxPath a_previousPath,
056: IxPath a_great, IxPath a_small) {
057: addPathTree(visitor, a_previousPath);
058: if (a_great != null && a_small != null
059: && a_great.carriesTheSame(a_small)) {
060: add(visitor, a_great, a_great.i_next, a_small.i_next);
061: return;
062: }
063: addGreater(visitor, a_small);
064: addSmaller(visitor, a_great);
065: }
066:
067: private void addAll(Visitor4 visitor, Tree a_tree) {
068: if (a_tree != null) {
069: ((IxTree) a_tree).visit(visitor, null);
070: addAll(visitor, a_tree._preceding);
071: addAll(visitor, a_tree._subsequent);
072: }
073: }
074:
075: private void addGreater(Visitor4 visitor, IxPath a_path) {
076: if (a_path != null) {
077: if (a_path.i_next == null) {
078: addSubsequent(visitor, a_path);
079: } else {
080: if (a_path.i_next.i_tree == a_path.i_tree._preceding) {
081: addSubsequent(visitor, a_path);
082: } else {
083: addPathTree(visitor, a_path);
084: }
085: addGreater(visitor, a_path.i_next);
086: }
087: }
088: }
089:
090: private void addPathTree(Visitor4 visitor, IxPath a_path) {
091: if (a_path != null) {
092: a_path.add(visitor);
093: }
094: }
095:
096: private void addPreceding(Visitor4 visitor, IxPath a_path) {
097: addPathTree(visitor, a_path);
098: addAll(visitor, a_path.i_tree._preceding);
099: }
100:
101: private void addSmaller(Visitor4 visitor, IxPath a_path) {
102: if (a_path != null) {
103: if (a_path.i_next == null) {
104: addPreceding(visitor, a_path);
105: } else {
106: if (a_path.i_next.i_tree == a_path.i_tree._subsequent) {
107: addPreceding(visitor, a_path);
108: } else {
109: addPathTree(visitor, a_path);
110: }
111: addSmaller(visitor, a_path.i_next);
112: }
113: }
114: }
115:
116: private void addSubsequent(Visitor4 visitor, IxPath a_path) {
117: addPathTree(visitor, a_path);
118: addAll(visitor, a_path.i_tree._subsequent);
119: }
120:
121: private int countGreater(IxPath a_path, int a_sum) {
122: if (a_path.i_next == null) {
123: return a_sum + countSubsequent(a_path);
124: }
125: if (a_path.i_next.i_tree == a_path.i_tree._preceding) {
126: a_sum += countSubsequent(a_path);
127: } else {
128: a_sum += a_path.countMatching();
129: }
130: return countGreater(a_path.i_next, a_sum);
131: }
132:
133: private int countPreceding(IxPath a_path) {
134: return Tree.size(a_path.i_tree._preceding)
135: + a_path.countMatching();
136: }
137:
138: private int countSmaller(IxPath a_path, int a_sum) {
139: if (a_path.i_next == null) {
140: return a_sum + countPreceding(a_path);
141: }
142: if (a_path.i_next.i_tree == a_path.i_tree._subsequent) {
143: a_sum += countPreceding(a_path);
144: } else {
145: a_sum += a_path.countMatching();
146: }
147: return countSmaller(a_path.i_next, a_sum);
148: }
149:
150: private int countSpan(IxPath a_previousPath, IxPath a_great,
151: IxPath a_small) {
152: //System.out.println("countSpan");
153: if (a_great == null) {
154: if (a_small == null) {
155: return a_previousPath.countMatching();
156: }
157: return countGreater(a_small, a_previousPath.countMatching());
158: } else if (a_small == null) {
159: return countSmaller(a_great, a_previousPath.countMatching());
160: }
161: if (a_great.carriesTheSame(a_small)) {
162: return countSpan(a_great, a_great.i_next, a_small.i_next);
163: }
164: return a_previousPath.countMatching()
165: + countGreater(a_small, 0) + countSmaller(a_great, 0);
166: }
167:
168: private int countSubsequent(IxPath a_path) {
169: return Tree.size(a_path.i_tree._subsequent)
170: + a_path.countMatching();
171: }
172:
173: private void delayedAppend(IxTree a_tree, int a_comparisonResult,
174: int[] lowerAndUpperMatch) {
175: if (i_appendHead == null) {
176: i_appendHead = new IxPath(this , null, a_tree,
177: a_comparisonResult, lowerAndUpperMatch);
178: i_appendTail = i_appendHead;
179: } else {
180: i_appendTail = i_appendTail.append(a_tree,
181: a_comparisonResult, lowerAndUpperMatch);
182: }
183: }
184:
185: private void findBoth() {
186: if (i_greatTail.i_comparisonResult == 0) {
187: findSmallestEqualFromEqual((IxTree) i_greatTail.i_tree._preceding);
188: resetDelayedAppend();
189: findGreatestEqualFromEqual((IxTree) i_greatTail.i_tree._subsequent);
190: } else if (i_greatTail.i_comparisonResult < 0) {
191: findBoth1((IxTree) i_greatTail.i_tree._subsequent);
192: } else {
193: findBoth1((IxTree) i_greatTail.i_tree._preceding);
194: }
195: }
196:
197: private void findBoth1(IxTree a_tree) {
198: if (a_tree != null) {
199: int res = a_tree.compare(null);
200: int[] lowerAndUpperMatch = a_tree.lowerAndUpperMatch();
201: i_greatTail = i_greatTail.append(a_tree, res,
202: lowerAndUpperMatch);
203: i_smallTail = i_smallTail.append(a_tree, res,
204: lowerAndUpperMatch);
205: findBoth();
206: }
207: }
208:
209: private void findNullPath1(IxPath[] headTail) {
210: if (headTail[1].i_comparisonResult == 0) {
211: findGreatestNullFromNull(headTail,
212: (IxTree) headTail[1].i_tree._subsequent);
213: } else if (headTail[1].i_comparisonResult < 0) {
214: findNullPath2(headTail,
215: (IxTree) headTail[1].i_tree._subsequent);
216: } else {
217: findNullPath2(headTail,
218: (IxTree) headTail[1].i_tree._preceding);
219: }
220: }
221:
222: private void findNullPath2(IxPath[] headTail, IxTree tree) {
223: if (tree != null) {
224: int res = tree.compare(null);
225: headTail[1] = headTail[1].append(tree, res, tree
226: .lowerAndUpperMatch());
227: findNullPath1(headTail);
228: }
229: }
230:
231: private void findGreatestNullFromNull(IxPath[] headTail, IxTree tree) {
232: if (tree != null) {
233: int res = tree.compare(null);
234: delayedAppend(tree, res, tree.lowerAndUpperMatch());
235: if (res == 0) {
236: headTail[1] = headTail[1].append(i_appendHead,
237: i_appendTail);
238: resetDelayedAppend();
239: }
240: if (res > 0) {
241: findGreatestNullFromNull(headTail,
242: (IxTree) tree._preceding);
243: } else {
244: findGreatestNullFromNull(headTail,
245: (IxTree) tree._subsequent);
246: }
247: }
248: }
249:
250: public int findBounds(Object a_constraint, IxTree a_tree) {
251:
252: if (a_tree != null) {
253:
254: // for debugging
255: // _constraint = a_constraint;
256:
257: i_handler = a_tree.handler();
258: i_handler.prepareComparison(a_constraint);
259:
260: // TODO: Only use small or big path where necessary.
261:
262: int res = a_tree.compare(null);
263:
264: i_greatHead = new IxPath(this , null, a_tree, res, a_tree
265: .lowerAndUpperMatch());
266: i_greatTail = i_greatHead;
267:
268: i_smallHead = (IxPath) i_greatHead.shallowClone();
269: i_smallTail = i_smallHead;
270:
271: findBoth();
272:
273: int span = 0;
274:
275: if (i_take[QE.EQUAL]) {
276: span += countSpan(i_greatHead, i_greatHead.i_next,
277: i_smallHead.i_next);
278: }
279: if (i_take[QE.SMALLER]) {
280: IxPath head = i_smallHead;
281: while (head != null) {
282: span += head.countPreceding(i_take[QE.NULLS]);
283: head = head.i_next;
284: }
285: }
286: if (i_take[QE.GREATER]) {
287: IxPath head = i_greatHead;
288: while (head != null) {
289: span += head.countSubsequent();
290: head = head.i_next;
291: }
292: }
293:
294: //System.out.println("findBounds() span = " + span);
295:
296: return span;
297: }
298: return 0;
299: }
300:
301: public int findBoundsExactMatch(Object a_constraint, IxTree a_tree) {
302: i_take = new boolean[] { false, false, false, false };
303: i_take[QE.EQUAL] = true;
304: return findBounds(a_constraint, a_tree);
305: }
306:
307: private void findGreatestEqualFromEqual(IxTree a_tree) {
308: if (a_tree != null) {
309: int res = a_tree.compare(null);
310: delayedAppend(a_tree, res, a_tree.lowerAndUpperMatch());
311: if (res == 0) {
312: i_greatTail = i_greatTail.append(i_appendHead,
313: i_appendTail);
314: resetDelayedAppend();
315: }
316: if (res > 0) {
317: findGreatestEqualFromEqual((IxTree) a_tree._preceding);
318: } else {
319: findGreatestEqualFromEqual((IxTree) a_tree._subsequent);
320: }
321: }
322: }
323:
324: private void findSmallestEqualFromEqual(IxTree a_tree) {
325: if (a_tree != null) {
326: int res = a_tree.compare(null);
327: delayedAppend(a_tree, res, a_tree.lowerAndUpperMatch());
328: if (res == 0) {
329: i_smallTail = i_smallTail.append(i_appendHead,
330: i_appendTail);
331: resetDelayedAppend();
332: }
333: if (res < 0) {
334: findSmallestEqualFromEqual((IxTree) a_tree._subsequent);
335: } else {
336: findSmallestEqualFromEqual((IxTree) a_tree._preceding);
337: }
338: }
339: }
340:
341: private void resetDelayedAppend() {
342: i_appendHead = null;
343: i_appendTail = null;
344: }
345:
346: public void visitAll(Visitor4 visitor) {
347: if (i_take[QE.EQUAL]) {
348: if (i_greatHead != null) {
349: add(visitor, i_greatHead, i_greatHead.i_next,
350: i_smallHead.i_next);
351: }
352: }
353: if (i_take[QE.SMALLER]) {
354: IxPath head = i_smallHead;
355: while (head != null) {
356: head.addPrecedingToCandidatesTree(visitor);
357: head = head.i_next;
358: }
359: }
360: if (i_take[QE.GREATER]) {
361: IxPath head = i_greatHead;
362: while (head != null) {
363: head.addSubsequentToCandidatesTree(visitor);
364: head = head.i_next;
365: }
366: }
367: }
368:
369: public void visitPreceding(FreespaceVisitor visitor) {
370: if (i_smallHead != null) {
371: i_smallHead.visitPreceding(visitor);
372: }
373: }
374:
375: public void visitSubsequent(FreespaceVisitor visitor) {
376: if (i_greatHead != null) {
377: i_greatHead.visitSubsequent(visitor);
378: }
379: }
380:
381: public void visitMatch(FreespaceVisitor visitor) {
382: if (i_smallHead != null) {
383: i_smallHead.visitMatch(visitor);
384: }
385:
386: }
387:
388: }
|