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.freespace.*;
025: import com.db4o.internal.query.processor.*;
026:
027: /**
028: * Index Path to represent a list of traversed index tree entries,
029: * used by IxTraverser
030: */
031: class IxPath implements ShallowClone, Visitor4 {
032:
033: int i_comparisonResult;
034:
035: int[] i_lowerAndUpperMatch;
036: int i_upperNull = -1;
037:
038: IxPath i_next;
039:
040: IxTraverser i_traverser;
041: IxTree i_tree;
042:
043: Visitor4 _visitor;
044:
045: IxPath(IxTraverser a_traverser, IxPath a_next, IxTree a_tree,
046: int a_comparisonResult, int[] lowerAndUpperMatch) {
047: i_traverser = a_traverser;
048: i_next = a_next;
049: i_tree = a_tree;
050: i_comparisonResult = a_comparisonResult;
051: i_lowerAndUpperMatch = lowerAndUpperMatch;
052: }
053:
054: void add(Visitor4 visitor) {
055: if (i_comparisonResult == 0 && i_traverser.i_take[QE.EQUAL]) {
056: i_tree.visit(visitor, i_lowerAndUpperMatch);
057: }
058: }
059:
060: void addPrecedingToCandidatesTree(Visitor4 visitor) {
061: _visitor = visitor;
062: if (i_tree._preceding != null) {
063: if (i_next == null || i_next.i_tree != i_tree._preceding) {
064: i_tree._preceding.traverse(this );
065: }
066: }
067: if (i_lowerAndUpperMatch != null) {
068: int[] lowerAndUpperMatch = new int[] { i_upperNull,
069: i_lowerAndUpperMatch[0] - 1 };
070: i_tree.visit(visitor, lowerAndUpperMatch);
071: } else {
072: if (i_comparisonResult < 0) {
073: visit(i_tree);
074: }
075: }
076: }
077:
078: void addSubsequentToCandidatesTree(Visitor4 visitor) {
079: _visitor = visitor;
080: if (i_tree._subsequent != null) {
081: if (i_next == null || i_next.i_tree != i_tree._subsequent) {
082: i_tree._subsequent.traverse(this );
083: }
084: }
085: if (i_lowerAndUpperMatch != null) {
086: int[] lowerAndUpperMatch = new int[] {
087: i_lowerAndUpperMatch[1] + 1,
088: ((IxFileRange) i_tree)._entries - 1 };
089: i_tree.visit(visitor, lowerAndUpperMatch);
090: } else {
091: if (i_comparisonResult > 0) {
092: visit(i_tree);
093: }
094: }
095: }
096:
097: IxPath append(IxPath a_head, IxPath a_tail) {
098: if (a_head == null) {
099: return this ;
100: }
101: i_next = a_head;
102: return a_tail;
103: }
104:
105: IxPath append(IxTree a_tree, int a_comparisonResult,
106: int[] lowerAndUpperMatch) {
107: i_next = new IxPath(i_traverser, null, a_tree,
108: a_comparisonResult, lowerAndUpperMatch);
109: i_next.i_tree = a_tree;
110: return i_next;
111: }
112:
113: boolean carriesTheSame(IxPath a_path) {
114: return i_tree == a_path.i_tree;
115: }
116:
117: private void checkUpperNull() {
118: if (i_upperNull == -1) {
119: i_upperNull = 0;
120: i_traverser.i_handler.prepareComparison(null);
121: int res = i_tree.compare(null);
122: if (res != 0) {
123: return;
124: }
125: int[] nullMatches = i_tree.lowerAndUpperMatch();
126: if (nullMatches[0] == 0) {
127: i_upperNull = nullMatches[1] + 1;
128: } else {
129: i_upperNull = 0;
130: }
131: }
132: }
133:
134: public void visitMatch(FreespaceVisitor visitor) {
135: if (i_next != null) {
136: i_next.visitMatch(visitor);
137: }
138: if (visitor.visited()) {
139: return;
140: }
141: if (i_comparisonResult != 0) {
142: return;
143: }
144:
145: if (i_lowerAndUpperMatch == null) {
146: i_tree.freespaceVisit(visitor, 0);
147: return;
148: }
149:
150: if (i_lowerAndUpperMatch[1] < i_lowerAndUpperMatch[0]) {
151: return;
152: }
153:
154: int ix = i_lowerAndUpperMatch[0];
155: if (ix >= 0) {
156: i_tree.freespaceVisit(visitor, ix);
157: }
158: }
159:
160: public void visitPreceding(FreespaceVisitor visitor) {
161: if (i_next != null) {
162: i_next.visitPreceding(visitor);
163: if (visitor.visited()) {
164: return;
165: }
166: }
167: if (i_lowerAndUpperMatch != null) {
168: int ix = i_lowerAndUpperMatch[0] - 1;
169: if (ix >= 0) {
170: i_tree.freespaceVisit(visitor, ix);
171: }
172: } else {
173: if (i_comparisonResult < 0) {
174: i_tree.freespaceVisit(visitor, 0);
175: }
176: }
177: if (visitor.visited()) {
178: return;
179: }
180: if (i_tree._preceding != null) {
181: if (i_next == null || i_next.i_tree != i_tree._preceding) {
182: ((IxTree) i_tree._preceding).visitLast(visitor);
183: }
184: }
185: }
186:
187: public void visitSubsequent(FreespaceVisitor visitor) {
188: if (i_next != null) {
189: i_next.visitSubsequent(visitor);
190: if (visitor.visited()) {
191: return;
192: }
193: }
194: if (i_lowerAndUpperMatch != null) {
195: int ix = i_lowerAndUpperMatch[1] + 1;
196: if (ix < ((IxFileRange) i_tree)._entries) {
197: i_tree.freespaceVisit(visitor, ix);
198: }
199: } else {
200: if (i_comparisonResult > 0) {
201: i_tree.freespaceVisit(visitor, 0);
202: }
203: }
204: if (visitor.visited()) {
205: return;
206: }
207: if (i_tree._subsequent != null) {
208: if (i_next == null || i_next.i_tree != i_tree._subsequent) {
209: ((IxTree) i_tree._subsequent).visitFirst(visitor);
210: }
211: }
212: }
213:
214: int countMatching() {
215: if (i_comparisonResult == 0) {
216: if (i_lowerAndUpperMatch == null) {
217: if (i_tree instanceof IxRemove) {
218: return 0;
219: }
220: return 1;
221: }
222: return i_lowerAndUpperMatch[1] - i_lowerAndUpperMatch[0]
223: + 1;
224: }
225: return 0;
226: }
227:
228: int countPreceding(boolean a_takenulls) {
229: int preceding = 0;
230: if (i_tree._preceding != null) {
231: if (i_next == null || i_next.i_tree != i_tree._preceding) {
232: preceding += i_tree._preceding.size();
233: }
234: }
235: if (i_lowerAndUpperMatch != null) {
236: if (a_takenulls) {
237: i_upperNull = 0;
238: } else {
239: checkUpperNull();
240: }
241: preceding += i_lowerAndUpperMatch[0] - i_upperNull;
242: } else {
243: if (i_comparisonResult < 0 && !(i_tree instanceof IxRemove)) {
244: preceding++;
245: }
246: }
247: return preceding;
248: }
249:
250: int countSubsequent() {
251: int subsequent = 0;
252: if (i_tree._subsequent != null) {
253: if (i_next == null || i_next.i_tree != i_tree._subsequent) {
254: subsequent += i_tree._subsequent.size();
255: }
256: }
257: if (i_lowerAndUpperMatch != null) {
258: subsequent += ((IxFileRange) i_tree)._entries
259: - i_lowerAndUpperMatch[1] - 1;
260: } else {
261: if (i_comparisonResult > 0 && !(i_tree instanceof IxRemove)) {
262: subsequent++;
263: }
264: }
265: return subsequent;
266: }
267:
268: public Object shallowClone() {
269: int[] lowerAndUpperMatch = null;
270: if (i_lowerAndUpperMatch != null) {
271: lowerAndUpperMatch = new int[] { i_lowerAndUpperMatch[0],
272: i_lowerAndUpperMatch[1] };
273: }
274: IxPath ret = new IxPath(i_traverser, i_next, i_tree,
275: i_comparisonResult, lowerAndUpperMatch);
276: ret.i_upperNull = i_upperNull;
277: ret._visitor = _visitor;
278: return ret;
279: }
280:
281: public String toString() {
282: if (!Debug4.prettyToStrings) {
283: return super .toString();
284: }
285: return i_tree.toString();
286: }
287:
288: public void visit(Object a_object) {
289: ((Visitor4) a_object).visit(_visitor);
290: }
291:
292: }
|