|
1
21 package com.db4o.foundation;
22
23
24
27 public abstract class Tree implements ShallowClone , DeepClone{
28
29 public static final class ByRef {
30
31 public ByRef() {
32 }
33
34 public ByRef(Tree initialValue) {
35 value = initialValue;
36 }
37
38 public Tree value;
39 }
40
41 public Tree _preceding;
42 public int _size = 1;
43 public Tree _subsequent;
44
45 public static final Tree add(Tree a_old, Tree a_new){
46 if(a_old == null){
47 return a_new;
48 }
49 return a_old.add(a_new);
50 }
51
52 public Tree add(final Tree a_new){
53 return add(a_new, compare(a_new));
54 }
55
56
63 public Tree add(final Tree a_new, final int a_cmp){
64 if(a_cmp < 0){
65 if(_subsequent == null){
66 _subsequent = a_new;
67 _size ++;
68 }else{
69 _subsequent = _subsequent.add(a_new);
70 if(_preceding == null){
71 return rotateLeft();
72 }
73 return balance();
74 }
75 }else if(a_cmp > 0 || a_new.duplicates()){
76 if(_preceding == null){
77 _preceding = a_new;
78 _size ++;
79 }else{
80 _preceding = _preceding.add(a_new);
81 if(_subsequent == null){
82 return rotateRight();
83 }
84 return balance();
85 }
86 }else{
87 a_new.isDuplicateOf(this);
88 }
89 return this;
90 }
91
92
93
100 public Tree duplicateOrThis(){
101 if(_size == 0){
102 return _preceding;
103 }
104 return this;
105 }
106
107 public final Tree balance(){
108 int cmp = _subsequent.nodes() - _preceding.nodes();
109 if(cmp < -2){
110 return rotateRight();
111 }else if(cmp > 2){
112 return rotateLeft();
113 }else{
114 setSizeOwnPrecedingSubsequent();
115 return this;
116 }
117 }
118
119 public Tree balanceCheckNulls(){
120 if(_subsequent == null){
121 if(_preceding == null){
122 setSizeOwn();
123 return this;
124 }
125 return rotateRight();
126 }else if(_preceding == null){
127 return rotateLeft();
128 }
129 return balance();
130 }
131
132 public void calculateSize(){
133 if(_preceding == null){
134 if (_subsequent == null){
135 setSizeOwn();
136 }else{
137 setSizeOwnSubsequent();
138 }
139 }else{
140 if(_subsequent == null){
141 setSizeOwnPreceding();
142 }else{
143 setSizeOwnPrecedingSubsequent();
144 }
145 }
146 }
147
148
149
155 public abstract int compare(Tree a_to);
156
157 public static Tree deepClone(Tree a_tree, Object  a_param){
158 if(a_tree == null){
159 return null;
160 }
161 Tree newNode = (Tree)a_tree.deepClone(a_param);
162 newNode._size = a_tree._size;
163 newNode._preceding = Tree.deepClone(a_tree._preceding, a_param);
164 newNode._subsequent = Tree.deepClone(a_tree._subsequent, a_param);
165 return newNode;
166 }
167
168
169 public Object deepClone(Object a_param){
170 return shallowClone();
171 }
172
173 public boolean duplicates(){
174 return true;
175 }
176
177 public final Tree filter(final Predicate4 a_filter){
178 if(_preceding != null){
179 _preceding = _preceding.filter(a_filter);
180 }
181 if(_subsequent != null){
182 _subsequent = _subsequent.filter(a_filter);
183 }
184 if(! a_filter.match(this)){
185 return remove();
186 }
187 return this;
188 }
189
190 public static final Tree find(Tree a_in, Tree a_tree){
191 if(a_in == null){
192 return null;
193 }
194 return a_in.find(a_tree);
195 }
196
197 public final Tree find(final Tree a_tree){
198 int cmp = compare(a_tree);
199 if (cmp < 0){
200 if(_subsequent != null){
201 return _subsequent.find(a_tree);
202 }
203 }else{
204 if (cmp > 0){
205 if(_preceding != null){
206 return _preceding.find(a_tree);
207 }
208 }else{
209 return this;
210 }
211 }
212 return null;
213 }
214
215 public static final Tree findGreaterOrEqual(Tree a_in, Tree a_finder){
216 if(a_in == null){
217 return null;
218 }
219 int cmp = a_in.compare(a_finder);
220 if(cmp == 0){
221 return a_in; }
223 if(cmp > 0){
224 Tree node = findGreaterOrEqual(a_in._preceding, a_finder);
225 if(node != null){
226 return node;
227 }
228 return a_in;
229 }
230 return findGreaterOrEqual(a_in._subsequent, a_finder);
231 }
232
233
234 public final static Tree findSmaller(Tree a_in, Tree a_node){
235 if(a_in == null){
236 return null;
237 }
238 int cmp = a_in.compare(a_node);
239 if(cmp < 0){
240 Tree node = findSmaller(a_in._subsequent, a_node);
241 if(node != null){
242 return node;
243 }
244 return a_in;
245 }
246 return findSmaller(a_in._preceding, a_node);
247 }
248
249 public final Tree first(){
250 if(_preceding == null){
251 return this;
252 }
253 return _preceding.first();
254 }
255
256 public void isDuplicateOf(Tree a_tree){
257 _size = 0;
258 _preceding = a_tree;
259 }
260
261
264 public int nodes(){
265 return _size;
266 }
267
268 public int ownSize(){
269 return 1;
270 }
271
272 public Tree remove(){
273 if(_subsequent != null && _preceding != null){
274 _subsequent = _subsequent.rotateSmallestUp();
275 _subsequent._preceding = _preceding;
276 _subsequent.calculateSize();
277 return _subsequent;
278 }
279 if(_subsequent != null){
280 return _subsequent;
281 }
282 return _preceding;
283 }
284
285 public void removeChildren(){
286 _preceding = null;
287 _subsequent = null;
288 setSizeOwn();
289 }
290
291 public Tree removeFirst(){
292 if(_preceding == null){
293 return _subsequent;
294 }
295 _preceding = _preceding.removeFirst();
296 calculateSize();
297 return this;
298 }
299
300 public static Tree removeLike(Tree from, Tree a_find){
301 if(from == null){
302 return null;
303 }
304 return from.removeLike(a_find);
305 }
306
307 public final Tree removeLike(final Tree a_find){
308 int cmp = compare(a_find);
309 if(cmp == 0){
310 return remove();
311 }
312 if (cmp > 0){
313 if(_preceding != null){
314 _preceding = _preceding.removeLike(a_find);
315 }
316 }else{
317 if(_subsequent != null){
318 _subsequent = _subsequent.removeLike(a_find);
319 }
320 }
321 calculateSize();
322 return this;
323 }
324
325 public final Tree removeNode(final Tree a_tree){
326 if (this == a_tree){
327 return remove();
328 }
329 int cmp = compare(a_tree);
330 if (cmp >= 0){
331 if(_preceding != null){
332 _preceding = _preceding.removeNode(a_tree);
333 }
334 }
335 if(cmp <= 0){
336 if(_subsequent != null){
337 _subsequent = _subsequent.removeNode(a_tree);
338 }
339 }
340 calculateSize();
341 return this;
342 }
343
344 public final Tree rotateLeft(){
345 Tree tree = _subsequent;
346 _subsequent = tree._preceding;
347 calculateSize();
348 tree._preceding = this;
349 if(tree._subsequent == null){
350 tree.setSizeOwnPlus(this);
351 }else{
352 tree.setSizeOwnPlus(this, tree._subsequent);
353 }
354 return tree;
355 }
356
357 public final Tree rotateRight(){
358 Tree tree = _preceding;
359 _preceding = tree._subsequent;
360 calculateSize();
361 tree._subsequent = this;
362 if(tree._preceding == null){
363 tree.setSizeOwnPlus(this);
364 }else{
365 tree.setSizeOwnPlus(this, tree._preceding);
366 }
367 return tree;
368 }
369
370 private final Tree rotateSmallestUp(){
371 if(_preceding != null){
372 _preceding = _preceding.rotateSmallestUp();
373 return rotateRight();
374 }
375 return this;
376 }
377
378 public void setSizeOwn(){
379 _size = ownSize();
380 }
381
382 public void setSizeOwnPrecedingSubsequent(){
383 _size = ownSize() + _preceding._size + _subsequent._size;
384 }
385
386 public void setSizeOwnPreceding(){
387 _size = ownSize() + _preceding._size;
388 }
389
390 public void setSizeOwnSubsequent(){
391 _size = ownSize() + _subsequent._size;
392 }
393
394 public void setSizeOwnPlus(Tree tree){
395 _size = ownSize() + tree._size;
396 }
397
398 public void setSizeOwnPlus(Tree tree1, Tree tree2){
399 _size = ownSize() + tree1._size + tree2._size;
400 }
401
402 public static int size(Tree a_tree){
403 if(a_tree == null){
404 return 0;
405 }
406 return a_tree.size();
407 }
408
409
412 public int size(){
413 return _size;
414 }
415
416 public static final void traverse(Tree tree, Visitor4 visitor){
417 if(tree == null){
418 return;
419 }
420 tree.traverse(visitor);
421 }
422
423 public final void traverse(final Visitor4 a_visitor){
424 if(_preceding != null){
425 _preceding.traverse(a_visitor);
426 }
427 a_visitor.visit(this);
428 if(_subsequent != null){
429 _subsequent.traverse(a_visitor);
430 }
431 }
432
433 public final void traverseFromLeaves(Visitor4 a_visitor){
434 if(_preceding != null){
435 _preceding.traverseFromLeaves(a_visitor);
436 }
437 if(_subsequent != null){
438 _subsequent.traverseFromLeaves(a_visitor);
439 }
440 a_visitor.visit(this);
441 }
442
443
445
463 protected Tree shallowCloneInternal(Tree tree) {
464 tree._preceding=_preceding;
465 tree._size=_size;
466 tree._subsequent=_subsequent;
467 return tree;
468 }
469
470 public Object shallowClone() {
471 throw new com.db4o.foundation.NotImplementedException();
472 }
473
474 public abstract Object key();
475 }
476 |
Popular Tags |
Java API By Example, From Geeks To Geeks.