|
1
21 package com.db4o.inside.ix;
22
23 import com.db4o.*;
24 import com.db4o.foundation.*;
25 import com.db4o.inside.freespace.*;
26
27
30 public class IxTraverser{
31
32
35 private IxPath i_appendHead;
36 private IxPath i_appendTail;
37
38 private IxPath i_greatHead;
39 private IxPath i_greatTail;
40
41 Indexable4 i_handler;
42
43 private IxPath i_smallHead;
44 private IxPath i_smallTail;
45
46
52 boolean[] i_take;
53
54 private void add(Visitor4 visitor, IxPath a_previousPath, IxPath a_great, IxPath a_small) {
55 addPathTree(visitor, a_previousPath);
56 if (a_great != null && a_small != null && a_great.carriesTheSame(a_small)) {
57 add(visitor, a_great, a_great.i_next, a_small.i_next);
58 return;
59 }
60 addGreater(visitor, a_small);
61 addSmaller(visitor, a_great);
62 }
63
64 private void addAll(Visitor4 visitor, Tree a_tree){
65 if(a_tree != null){
66 ((IxTree)a_tree).visit(visitor, null);
67 addAll(visitor, a_tree._preceding);
68 addAll(visitor, a_tree._subsequent);
69 }
70 }
71
72 private void addGreater(Visitor4 visitor, IxPath a_path) {
73 if (a_path != null) {
74 if (a_path.i_next == null) {
75 addSubsequent(visitor, a_path);
76 } else {
77 if (a_path.i_next.i_tree == a_path.i_tree._preceding) {
78 addSubsequent(visitor, a_path);
79 } else {
80 addPathTree(visitor, a_path);
81 }
82 addGreater(visitor, a_path.i_next);
83 }
84 }
85 }
86
87 private void addPathTree(Visitor4 visitor, IxPath a_path) {
88 if (a_path != null) {
89 a_path.add(visitor);
90 }
91 }
92
93 private void addPreceding(Visitor4 visitor, IxPath a_path) {
94 addPathTree(visitor, a_path);
95 addAll(visitor, a_path.i_tree._preceding);
96 }
97
98 private void addSmaller(Visitor4 visitor, IxPath a_path) {
99 if (a_path != null) {
100 if (a_path.i_next == null) {
101 addPreceding(visitor, a_path);
102 } else {
103 if (a_path.i_next.i_tree == a_path.i_tree._subsequent) {
104 addPreceding(visitor, a_path);
105 } else {
106 addPathTree(visitor, a_path);
107 }
108 addSmaller(visitor, a_path.i_next);
109 }
110 }
111 }
112
113 private void addSubsequent(Visitor4 visitor, IxPath a_path) {
114 addPathTree(visitor, a_path);
115 addAll(visitor, a_path.i_tree._subsequent);
116 }
117
118 private int countGreater(IxPath a_path, int a_sum) {
119 if (a_path.i_next == null) {
120 return a_sum + countSubsequent(a_path);
121 }
122 if (a_path.i_next.i_tree == a_path.i_tree._preceding) {
123 a_sum += countSubsequent(a_path);
124 } else {
125 a_sum += a_path.countMatching();
126 }
127 return countGreater(a_path.i_next, a_sum);
128 }
129
130 private int countPreceding(IxPath a_path) {
131 return Tree.size(a_path.i_tree._preceding) + a_path.countMatching();
132 }
133
134 private int countSmaller(IxPath a_path, int a_sum) {
135 if (a_path.i_next == null) {
136 return a_sum + countPreceding(a_path);
137 }
138 if (a_path.i_next.i_tree == a_path.i_tree._subsequent) {
139 a_sum += countPreceding(a_path);
140 } else {
141 a_sum += a_path.countMatching();
142 }
143 return countSmaller(a_path.i_next, a_sum);
144 }
145
146 private int countSpan(IxPath a_previousPath, IxPath a_great, IxPath a_small) {
147 if (a_great == null) {
149 if (a_small == null) {
150 return a_previousPath.countMatching();
151 }
152 return countGreater(a_small, a_previousPath.countMatching());
153 } else if (a_small == null) {
154 return countSmaller(a_great, a_previousPath.countMatching());
155 }
156 if (a_great.carriesTheSame(a_small)) {
157 return countSpan(a_great, a_great.i_next, a_small.i_next);
158 }
159 return a_previousPath.countMatching() + countGreater(a_small, 0) + countSmaller(a_great, 0);
160 }
161
162 private int countSubsequent(IxPath a_path) {
163 return Tree.size(a_path.i_tree._subsequent) + a_path.countMatching();
164 }
165
166 private void delayedAppend(IxTree a_tree, int a_comparisonResult, int[] lowerAndUpperMatch) {
167 if (i_appendHead == null) {
168 i_appendHead = new IxPath(this, null, a_tree, a_comparisonResult, lowerAndUpperMatch);
169 i_appendTail = i_appendHead;
170 } else {
171 i_appendTail = i_appendTail.append(a_tree, a_comparisonResult, lowerAndUpperMatch);
172 }
173 }
174
175 private void findBoth() {
176 if (i_greatTail.i_comparisonResult == 0) {
177 findSmallestEqualFromEqual((IxTree)i_greatTail.i_tree._preceding);
178 resetDelayedAppend();
179 findGreatestEqualFromEqual((IxTree)i_greatTail.i_tree._subsequent);
180 } else if (i_greatTail.i_comparisonResult < 0) {
181 findBoth1((IxTree)i_greatTail.i_tree._subsequent);
182 } else {
183 findBoth1((IxTree)i_greatTail.i_tree._preceding);
184 }
185 }
186
187 private void findBoth1(IxTree a_tree) {
188 if (a_tree != null) {
189 int res = a_tree.compare(null);
190 int[] lowerAndUpperMatch = a_tree.lowerAndUpperMatch();
191 i_greatTail = i_greatTail.append(a_tree, res, lowerAndUpperMatch);
192 i_smallTail = i_smallTail.append(a_tree, res, lowerAndUpperMatch);
193 findBoth();
194 }
195 }
196
197 private void findNullPath1(IxPath[] headTail) {
198 if(headTail[1].i_comparisonResult == 0){
199 findGreatestNullFromNull(headTail, (IxTree)headTail[1].i_tree._subsequent);
200 } else if (headTail[1].i_comparisonResult < 0) {
201 findNullPath2(headTail, (IxTree)headTail[1].i_tree._subsequent);
202 } else {
203 findNullPath2(headTail, (IxTree)headTail[1].i_tree._preceding);
204 }
205 }
206
207 private void findNullPath2(IxPath[] headTail, IxTree tree) {
208 if (tree != null) {
209 int res = tree.compare(null);
210 headTail[1] = headTail[1].append(tree, res, tree.lowerAndUpperMatch());
211 findNullPath1(headTail);
212 }
213 }
214
215 private void findGreatestNullFromNull(IxPath[] headTail, IxTree tree) {
216 if (tree != null) {
217 int res = tree.compare(null);
218 delayedAppend(tree, res, tree.lowerAndUpperMatch());
219 if (res == 0) {
220 headTail[1] = headTail[1].append(i_appendHead, i_appendTail);
221 resetDelayedAppend();
222 }
223 if (res > 0) {
224 findGreatestNullFromNull(headTail, (IxTree)tree._preceding);
225 } else {
226 findGreatestNullFromNull(headTail, (IxTree)tree._subsequent);
227 }
228 }
229 }
230
231
232 public int findBounds(Object  a_constraint, IxTree a_tree) {
233
234 if (a_tree != null) {
235
236
237
240
241 i_handler = a_tree.handler();
242 i_handler.prepareComparison(a_constraint);
243
244
246 int res = a_tree.compare(null);
247
248 i_greatHead = new IxPath(this, null, a_tree, res, a_tree.lowerAndUpperMatch());
249 i_greatTail = i_greatHead;
250
251 i_smallHead = (IxPath)i_greatHead.shallowClone();
252 i_smallTail = i_smallHead;
253
254 findBoth();
255
256 int span = 0;
257
258 if (i_take[QE.EQUAL]) {
259 span += countSpan(i_greatHead, i_greatHead.i_next, i_smallHead.i_next);
260 }
261 if (i_take[QE.SMALLER]) {
262 IxPath head = i_smallHead;
263 while (head != null) {
264 span += head.countPreceding(i_take[QE.NULLS]);
265 head = head.i_next;
266 }
267 }
268 if (i_take[QE.GREATER]) {
269 IxPath head = i_greatHead;
270 while (head != null) {
271 span += head.countSubsequent();
272 head = head.i_next;
273 }
274 }
275
276
278 return span;
279 }
280 return 0;
281 }
282
283 public int findBoundsExactMatch(Object a_constraint, IxTree a_tree){
284 i_take = new boolean[] { false, false, false, false};
285 i_take[QE.EQUAL] = true;
286 return findBounds(a_constraint, a_tree);
287 }
288
289 private void findGreatestEqualFromEqual(IxTree a_tree) {
290 if (a_tree != null) {
291 int res = a_tree.compare(null);
292 delayedAppend(a_tree, res, a_tree.lowerAndUpperMatch());
293 if (res == 0) {
294 i_greatTail = i_greatTail.append(i_appendHead, i_appendTail);
295 resetDelayedAppend();
296 }
297 if (res > 0) {
298 findGreatestEqualFromEqual((IxTree)a_tree._preceding);
299 } else {
300 findGreatestEqualFromEqual((IxTree)a_tree._subsequent);
301 }
302 }
303 }
304
305 private void findSmallestEqualFromEqual(IxTree a_tree) {
306 if (a_tree != null) {
307 int res = a_tree.compare(null);
308 delayedAppend(a_tree, res, a_tree.lowerAndUpperMatch());
309 if (res == 0) {
310 i_smallTail = i_smallTail.append(i_appendHead, i_appendTail);
311 resetDelayedAppend();
312 }
313 if (res < 0) {
314 findSmallestEqualFromEqual((IxTree)a_tree._subsequent);
315 } else {
316 findSmallestEqualFromEqual((IxTree)a_tree._preceding);
317 }
318 }
319 }
320
321 private void resetDelayedAppend() {
322 i_appendHead = null;
323 i_appendTail = null;
324 }
325
326 public void visitAll(Visitor4 visitor) {
327 if (i_take[QE.EQUAL]) {
328 if (i_greatHead != null) {
329 add(visitor, i_greatHead, i_greatHead.i_next, i_smallHead.i_next);
330 }
331 }
332 if (i_take[QE.SMALLER]) {
333 IxPath head = i_smallHead;
334 while (head != null) {
335 head.addPrecedingToCandidatesTree(visitor);
336 head = head.i_next;
337 }
338 }
339 if (i_take[QE.GREATER]) {
340 IxPath head = i_greatHead;
341 while (head != null) {
342 head.addSubsequentToCandidatesTree(visitor);
343 head = head.i_next;
344 }
345 }
346 }
347
348 public void visitPreceding(FreespaceVisitor visitor){
349 if(i_smallHead != null){
350 i_smallHead.visitPreceding(visitor);
351 }
352 }
353
354 public void visitSubsequent(FreespaceVisitor visitor){
355 if(i_greatHead != null){
356 i_greatHead.visitSubsequent(visitor);
357 }
358 }
359
360 public void visitMatch(FreespaceVisitor visitor){
361 if(i_smallHead != null){
362 i_smallHead.visitMatch(visitor);
363 }
364
365 }
366
367 }
368 |
Popular Tags |
Java API By Example, From Geeks To Geeks.