KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > poi > hdf > extractor > util > BTreeSet


1
2 /* ====================================================================
3    Copyright 2002-2004 Apache Software Foundation
4
5    Licensed under the Apache License, Version 2.0 (the "License");
6    you may not use this file except in compliance with the License.
7    You may obtain a copy of the License at
8
9        http://www.apache.org/licenses/LICENSE-2.0
10
11    Unless required by applicable law or agreed to in writing, software
12    distributed under the License is distributed on an "AS IS" BASIS,
13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14    See the License for the specific language governing permissions and
15    limitations under the License.
16 ==================================================================== */

17         
18
19
20 package org.apache.poi.hdf.extractor.util;
21
22 import java.util.*;
23
24
25 /*
26  * A B-Tree like implementation of the java.util.Set inteface. This is a modifiable set
27  * and thus allows elements to be added and removed. An instance of java.util.Comparator
28  * must be provided at construction else all Objects added to the set must implement
29  * java.util.Comparable and must be comparable to one another. No duplicate elements
30  * will be allowed in any BTreeSet in accordance with the specifications of the Set interface.
31  * Any attempt to add a null element will result in an IllegalArgumentException being thrown.
32  * The java.util.Iterator returned by the iterator method guarantees the elements returned
33  * are in ascending order. The Iterator.remove() method is supported.
34  * Comment me
35  *
36  * @author Ryan Ackley
37  *
38 */

39
40 public class BTreeSet extends AbstractSet implements Set {
41
42     /*
43      * Instance Variables
44     */

45     public BTreeNode root;
46     private Comparator comparator = null;
47     private int order;
48     private int size = 0;
49
50     /*
51      * Constructors
52      * A no-arg constructor is supported in accordance with the specifications of the
53      * java.util.Collections interface. If the order for the B-Tree is not specified
54      * at construction it defaults to 32.
55     */

56
57     public BTreeSet() {
58         this(6); // Default order for a BTreeSet is 32
59
}
60
61     public BTreeSet(Collection c) {
62         this(6); // Default order for a BTreeSet is 32
63
addAll(c);
64     }
65
66     public BTreeSet(int order) {
67         this(order, null);
68     }
69
70     public BTreeSet(int order, Comparator comparator) {
71         this.order = order;
72         this.comparator = comparator;
73         root = new BTreeNode(null);
74     }
75
76
77     /*
78      * Public Methods
79     */

80     public boolean add(Object JavaDoc x) throws IllegalArgumentException JavaDoc {
81         if (x == null) throw new IllegalArgumentException JavaDoc();
82         return root.insert(x, -1);
83     }
84
85     public boolean contains(Object JavaDoc x) {
86         return root.includes(x);
87     }
88
89     public boolean remove(Object JavaDoc x) {
90         if (x == null) return false;
91         return root.delete(x, -1);
92     }
93
94     public int size() {
95         return size;
96     }
97
98     public void clear() {
99         root = new BTreeNode(null);
100         size = 0;
101     }
102
103     public java.util.Iterator JavaDoc iterator() {
104         return new Iterator();
105     }
106
107
108     /*
109      * Private methods
110     */

111     private int compare(Object JavaDoc x, Object JavaDoc y) {
112         return (comparator == null ? ((Comparable JavaDoc)x).compareTo(y) : comparator.compare(x, y));
113     }
114
115
116
117     /*
118      * Inner Classes
119     */

120
121     /*
122      * Guarantees that the Objects are returned in ascending order. Due to the volatile
123      * structure of a B-Tree (many splits, steals and merges can happen in a single call to remove)
124      * this Iterator does not attempt to track any concurrent changes that are happening to
125      * it's BTreeSet. Therefore, after every call to BTreeSet.remove or BTreeSet.add a new
126      * Iterator should be constructed. If no new Iterator is constructed than there is a
127      * chance of receiving a NullPointerException. The Iterator.delete method is supported.
128     */

129
130     private class Iterator implements java.util.Iterator JavaDoc {
131         private int index = 0;
132         private Stack parentIndex = new Stack(); // Contains all parentIndicies for currentNode
133
private Object JavaDoc lastReturned = null;
134         private Object JavaDoc next;
135         private BTreeNode currentNode;
136
137         Iterator() {
138             currentNode = firstNode();
139             next = nextElement();
140         }
141
142         public boolean hasNext() {
143             return next != null;
144         }
145
146         public Object JavaDoc next() {
147             if (next == null) throw new NoSuchElementException();
148
149             lastReturned = next;
150             next = nextElement();
151             return lastReturned;
152         }
153
154         public void remove() {
155             if (lastReturned == null) throw new NoSuchElementException();
156
157             BTreeSet.this.remove(lastReturned);
158             lastReturned = null;
159         }
160
161         private BTreeNode firstNode() {
162             BTreeNode temp = BTreeSet.this.root;
163
164             while (temp.entries[0].child != null) {
165                 temp = temp.entries[0].child;
166                 parentIndex.push(new Integer JavaDoc(0));
167             }
168
169             return temp;
170         }
171
172         private Object JavaDoc nextElement() {
173             if (currentNode.isLeaf()) {
174                 if (index < currentNode.nrElements) return currentNode.entries[index++].element;
175
176                 else if (!parentIndex.empty()) { //All elements have been returned, return successor of lastReturned if it exists
177
currentNode = currentNode.parent;
178                     index = ((Integer JavaDoc)parentIndex.pop()).intValue();
179
180                     while (index == currentNode.nrElements) {
181                         if (parentIndex.empty()) break;
182                         currentNode = currentNode.parent;
183                         index = ((Integer JavaDoc)parentIndex.pop()).intValue();
184                     }
185
186                     if (index == currentNode.nrElements) return null; //Reached root and he has no more children
187
return currentNode.entries[index++].element;
188                 }
189
190                 else { //Your a leaf and the root
191
if (index == currentNode.nrElements) return null;
192                     return currentNode.entries[index++].element;
193                 }
194             }
195
196             else { //Your not a leaf so simply find and return the successor of lastReturned
197
currentNode = currentNode.entries[index].child;
198                 parentIndex.push(new Integer JavaDoc(index));
199
200                 while (currentNode.entries[0].child != null) {
201                     currentNode = currentNode.entries[0].child;
202                     parentIndex.push(new Integer JavaDoc(0));
203                 }
204
205                 index = 1;
206                 return currentNode.entries[0].element;
207             }
208         }
209     }
210
211
212     public static class Entry {
213
214         public Object JavaDoc element;
215         public BTreeNode child;
216     }
217
218
219     public class BTreeNode {
220
221         public Entry[] entries;
222         public BTreeNode parent;
223         private int nrElements = 0;
224         private final int MIN = (BTreeSet.this.order - 1) / 2;
225
226         BTreeNode(BTreeNode parent) {
227             this.parent = parent;
228             entries = new Entry[BTreeSet.this.order];
229             entries[0] = new Entry();
230         }
231
232         boolean insert(Object JavaDoc x, int parentIndex) {
233             if (isFull()) { // If full, you must split and promote splitNode before inserting
234
Object JavaDoc splitNode = entries[nrElements / 2].element;
235                 BTreeNode rightSibling = split();
236
237                 if (isRoot()) { // Grow a level
238
splitRoot(splitNode, this, rightSibling);
239                     // Determine where to insert
240
if (BTreeSet.this.compare(x, BTreeSet.this.root.entries[0].element) < 0) insert(x, 0);
241                     else rightSibling.insert(x, 1);
242                 }
243
244                 else { // Promote splitNode
245
parent.insertSplitNode(splitNode, this, rightSibling, parentIndex);
246                     if (BTreeSet.this.compare(x, parent.entries[parentIndex].element) < 0) return insert(x, parentIndex);
247                     else return rightSibling.insert(x, parentIndex + 1);
248                 }
249             }
250
251             else if (isLeaf()) { // If leaf, simply insert the non-duplicate element
252
int insertAt = childToInsertAt(x, true);
253                 if (insertAt == -1) return false; // Determine if the element already exists
254
else {
255                     insertNewElement(x, insertAt);
256                     BTreeSet.this.size++;
257                     return true;
258                 }
259             }
260
261             else { // If not full and not leaf recursively find correct node to insert at
262
int insertAt = childToInsertAt(x, true);
263                 return (insertAt == -1 ? false : entries[insertAt].child.insert(x, insertAt));
264             }
265             return false;
266         }
267
268         boolean includes(Object JavaDoc x) {
269             int index = childToInsertAt(x, true);
270             if (index == -1) return true;
271             if (entries[index] == null || entries[index].child == null) return false;
272             return entries[index].child.includes(x);
273         }
274
275         boolean delete(Object JavaDoc x, int parentIndex) {
276             int i = childToInsertAt(x, true);
277             int priorParentIndex = parentIndex;
278             BTreeNode temp = this;
279             if (i != -1) {
280                 do {
281                     if (temp.entries[i] == null || temp.entries[i].child == null) return false;
282                     temp = temp.entries[i].child;
283                     priorParentIndex = parentIndex;
284                     parentIndex = i;
285                     i = temp.childToInsertAt(x, true);
286                 } while (i != -1);
287             } // Now temp contains element to delete and temp's parentIndex is parentIndex
288

289             if (temp.isLeaf()) { // If leaf and have more than MIN elements, simply delete
290
if (temp.nrElements > MIN) {
291                     temp.deleteElement(x);
292                     BTreeSet.this.size--;
293                     return true;
294                 }
295
296                 else { // If leaf and have less than MIN elements, than prepare the BTreeSet for deletion
297
temp.prepareForDeletion(parentIndex);
298                     temp.deleteElement(x);
299                     BTreeSet.this.size--;
300                     temp.fixAfterDeletion(priorParentIndex);
301                     return true;
302                 }
303             }
304
305             else { // Only delete at leaf so first switch with successor than delete
306
temp.switchWithSuccessor(x);
307                 parentIndex = temp.childToInsertAt(x, false) + 1;
308                 return temp.entries[parentIndex].child.delete(x, parentIndex);
309             }
310         }
311
312
313         private boolean isFull() { return nrElements == (BTreeSet.this.order - 1); }
314
315         private boolean isLeaf() { return entries[0].child == null; }
316
317         private boolean isRoot() { return parent == null; }
318
319         /*
320          * Splits a BTreeNode into two BTreeNodes, removing the splitNode from the
321          * calling BTreeNode.
322         */

323         private BTreeNode split() {
324             BTreeNode rightSibling = new BTreeNode(parent);
325             int index = nrElements / 2;
326             entries[index++].element = null;
327
328             for (int i = 0, nr = nrElements; index <= nr; i++, index++) {
329                 rightSibling.entries[i] = entries[index];
330                 if (rightSibling.entries[i] != null && rightSibling.entries[i].child != null)
331                     rightSibling.entries[i].child.parent = rightSibling;
332                 entries[index] = null;
333                 nrElements--;
334                 rightSibling.nrElements++;
335             }
336
337             rightSibling.nrElements--; // Need to correct for copying the last Entry which has a null element and a child
338
return rightSibling;
339         }
340
341         /*
342          * Creates a new BTreeSet.root which contains only the splitNode and pointers
343          * to it's left and right child.
344         */

345         private void splitRoot(Object JavaDoc splitNode, BTreeNode left, BTreeNode right) {
346             BTreeNode newRoot = new BTreeNode(null);
347             newRoot.entries[0].element = splitNode;
348             newRoot.entries[0].child = left;
349             newRoot.entries[1] = new Entry();
350             newRoot.entries[1].child = right;
351             newRoot.nrElements = 1;
352             left.parent = right.parent = newRoot;
353             BTreeSet.this.root = newRoot;
354         }
355
356         private void insertSplitNode(Object JavaDoc splitNode, BTreeNode left, BTreeNode right, int insertAt) {
357             for (int i = nrElements; i >= insertAt; i--) entries[i + 1] = entries[i];
358
359             entries[insertAt] = new Entry();
360             entries[insertAt].element = splitNode;
361             entries[insertAt].child = left;
362             entries[insertAt + 1].child = right;
363
364             nrElements++;
365         }
366
367         private void insertNewElement(Object JavaDoc x, int insertAt) {
368
369             for (int i = nrElements; i > insertAt; i--) entries[i] = entries[i - 1];
370
371             entries[insertAt] = new Entry();
372             entries[insertAt].element = x;
373
374             nrElements++;
375         }
376
377         /*
378          * Possibly a deceptive name for a pretty cool method. Uses binary search
379          * to determine the postion in entries[] in which to traverse to find the correct
380          * BTreeNode in which to insert a new element. If the element exists in the calling
381          * BTreeNode than -1 is returned. When the parameter position is true and the element
382          * is present in the calling BTreeNode -1 is returned, if position is false and the
383          * element is contained in the calling BTreeNode than the position of the element
384          * in entries[] is returned.
385         */

386         private int childToInsertAt(Object JavaDoc x, boolean position) {
387             int index = nrElements / 2;
388
389             if (entries[index] == null || entries[index].element == null) return index;
390
391             int lo = 0, hi = nrElements - 1;
392             while (lo <= hi) {
393                 if (BTreeSet.this.compare(x, entries[index].element) > 0) {
394                     lo = index + 1;
395                     index = (hi + lo) / 2;
396                 }
397                 else {
398                     hi = index - 1;
399                     index = (hi + lo) / 2;
400                 }
401             }
402
403             hi++;
404             if (entries[hi] == null || entries[hi].element == null) return hi;
405             return (!position ? hi : BTreeSet.this.compare(x, entries[hi].element) == 0 ? -1 : hi);
406         }
407
408
409         private void deleteElement(Object JavaDoc x) {
410             int index = childToInsertAt(x, false);
411             for (; index < (nrElements - 1); index++) entries[index] = entries[index + 1];
412
413             if (nrElements == 1) entries[index] = new Entry(); // This is root and it is empty
414
else entries[index] = null;
415
416             nrElements--;
417         }
418
419         private void prepareForDeletion(int parentIndex) {
420             if (isRoot()) return; // Don't attempt to steal or merge if your the root
421

422             // If not root then try to steal left
423
else if (parentIndex != 0 && parent.entries[parentIndex - 1].child.nrElements > MIN) {
424                 stealLeft(parentIndex);
425                 return;
426             }
427
428             // If not root and can't steal left try to steal right
429
else if (parentIndex < entries.length && parent.entries[parentIndex + 1] != null && parent.entries[parentIndex + 1].child != null && parent.entries[parentIndex + 1].child.nrElements > MIN) {
430                     stealRight(parentIndex);
431                     return;
432             }
433
434             // If not root and can't steal left or right then try to merge left
435
else if (parentIndex != 0) {
436                 mergeLeft(parentIndex);
437                 return;
438             }
439
440             // If not root and can't steal left or right and can't merge left you must be able to merge right
441
else mergeRight(parentIndex);
442         }
443
444         private void fixAfterDeletion(int parentIndex) {
445             if (isRoot() || parent.isRoot()) return; // No fixing needed
446

447             if (parent.nrElements < MIN) { // If parent lost it's n/2 element repair it
448
BTreeNode temp = parent;
449                 temp.prepareForDeletion(parentIndex);
450                 if (temp.parent == null) return; // Root changed
451
if (!temp.parent.isRoot() && temp.parent.nrElements < MIN) { // If need be recurse
452
BTreeNode x = temp.parent.parent;
453                     int i = 0;
454                     // Find parent's parentIndex
455
for (; i < entries.length; i++) if (x.entries[i].child == temp.parent) break;
456                     temp.parent.fixAfterDeletion(i);
457                 }
458             }
459         }
460
461         private void switchWithSuccessor(Object JavaDoc x) {
462             int index = childToInsertAt(x, false);
463             BTreeNode temp = entries[index + 1].child;
464             while (temp.entries[0] != null && temp.entries[0].child != null) temp = temp.entries[0].child;
465             Object JavaDoc successor = temp.entries[0].element;
466             temp.entries[0].element = entries[index].element;
467             entries[index].element = successor;
468         }
469
470         /*
471          * This method is called only when the BTreeNode has the minimum number of elements,
472          * has a leftSibling, and the leftSibling has more than the minimum number of elements.
473         */

474         private void stealLeft(int parentIndex) {
475             BTreeNode p = parent;
476             BTreeNode ls = parent.entries[parentIndex - 1].child;
477
478             if (isLeaf()) { // When stealing from leaf to leaf don't worry about children
479
int add = childToInsertAt(p.entries[parentIndex - 1].element, true);
480                 insertNewElement(p.entries[parentIndex - 1].element, add);
481                 p.entries[parentIndex - 1].element = ls.entries[ls.nrElements - 1].element;
482                 ls.entries[ls.nrElements - 1] = null;
483                 ls.nrElements--;
484             }
485
486             else { // Was called recursively to fix an undermanned parent
487
entries[0].element = p.entries[parentIndex - 1].element;
488                 p.entries[parentIndex - 1].element = ls.entries[ls.nrElements - 1].element;
489                 entries[0].child = ls.entries[ls.nrElements].child;
490                 entries[0].child.parent = this;
491                 ls.entries[ls.nrElements] = null;
492                 ls.entries[ls.nrElements - 1].element = null;
493                 nrElements++;
494                 ls.nrElements--;
495             }
496         }
497
498         /*
499          * This method is called only when stealLeft can't be called, the BTreeNode
500          * has the minimum number of elements, has a rightSibling, and the rightSibling
501          * has more than the minimum number of elements.
502         */

503         private void stealRight(int parentIndex) {
504             BTreeNode p = parent;
505             BTreeNode rs = p.entries[parentIndex + 1].child;
506
507             if (isLeaf()) { // When stealing from leaf to leaf don't worry about children
508
entries[nrElements] = new Entry();
509                 entries[nrElements].element = p.entries[parentIndex].element;
510                 p.entries[parentIndex].element = rs.entries[0].element;
511                 for (int i = 0; i < rs.nrElements; i++) rs.entries[i] = rs.entries[i + 1];
512                 rs.entries[rs.nrElements - 1] = null;
513                 nrElements++;
514                 rs.nrElements--;
515             }
516
517             else { // Was called recursively to fix an undermanned parent
518
for (int i = 0; i <= nrElements; i++) entries[i] = entries[i + 1];
519                 entries[nrElements].element = p.entries[parentIndex].element;
520                 p.entries[parentIndex].element = rs.entries[0].element;
521                 entries[nrElements + 1] = new Entry();
522                 entries[nrElements + 1].child = rs.entries[0].child;
523                 entries[nrElements + 1].child.parent = this;
524                 for (int i = 0; i <= rs.nrElements; i++) rs.entries[i] = rs.entries[i + 1];
525                 rs.entries[rs.nrElements] = null;
526                 nrElements++;
527                 rs.nrElements--;
528             }
529         }
530
531         /*
532          * This method is called only when stealLeft and stealRight could not be called,
533          * the BTreeNode has the minimum number of elements, has a leftSibling, and the
534          * leftSibling has more than the minimum number of elements. If after completion
535          * parent has fewer than the minimum number of elements than the parents entries[0]
536          * slot is left empty in anticipation of a recursive call to stealLeft, stealRight,
537          * mergeLeft, or mergeRight to fix the parent. All of the before-mentioned methods
538          * expect the parent to be in such a condition.
539         */

540         private void mergeLeft(int parentIndex) {
541             BTreeNode p = parent;
542             BTreeNode ls = p.entries[parentIndex - 1].child;
543
544             if (isLeaf()) { // Don't worry about children
545
int add = childToInsertAt(p.entries[parentIndex - 1].element, true);
546                 insertNewElement(p.entries[parentIndex - 1].element, add); // Could have been a successor switch
547
p.entries[parentIndex - 1].element = null;
548
549                 for (int i = nrElements - 1, nr = ls.nrElements; i >= 0; i--)
550                     entries[i + nr] = entries[i];
551
552                 for (int i = ls.nrElements - 1; i >= 0; i--) {
553                     entries[i] = ls.entries[i];
554                     nrElements++;
555                 }
556
557                 if (p.nrElements == MIN && p != BTreeSet.this.root) {
558
559                     for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x--, y--)
560                         p.entries[x] = p.entries[y];
561                     p.entries[0] = new Entry();
562                     p.entries[0].child = ls; //So p doesn't think it's a leaf this will be deleted in the next recursive call
563
}
564
565                 else {
566
567                     for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++)
568                         p.entries[x] = p.entries[y];
569                     p.entries[p.nrElements] = null;
570                 }
571
572                 p.nrElements--;
573
574                 if (p.isRoot() && p.nrElements == 0) { // It's the root and it's empty
575
BTreeSet.this.root = this;
576                     parent = null;
577                 }
578             }
579
580             else { // I'm not a leaf but fixing the tree structure
581
entries[0].element = p.entries[parentIndex - 1].element;
582                 entries[0].child = ls.entries[ls.nrElements].child;
583                 nrElements++;
584
585                 for (int x = nrElements, nr = ls.nrElements; x >= 0; x--)
586                     entries[x + nr] = entries[x];
587
588                 for (int x = ls.nrElements - 1; x >= 0; x--) {
589                     entries[x] = ls.entries[x];
590                     entries[x].child.parent = this;
591                     nrElements++;
592                 }
593
594                 if (p.nrElements == MIN && p != BTreeSet.this.root) { // Push everything to the right
595
for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x++, y++){
596                         System.out.println(x + " " + y);
597                         p.entries[x] = p.entries[y];}
598                     p.entries[0] = new Entry();
599                 }
600
601                 else { // Either p.nrElements > MIN or p == BTreeSet.this.root so push everything to the left
602
for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++)
603                         p.entries[x] = p.entries[y];
604                     p.entries[p.nrElements] = null;
605                 }
606
607                 p.nrElements--;
608
609                 if (p.isRoot() && p.nrElements == 0) { // p == BTreeSet.this.root and it's empty
610
BTreeSet.this.root = this;
611                     parent = null;
612                 }
613             }
614         }
615
616         /*
617          * This method is called only when stealLeft, stealRight, and mergeLeft could not be called,
618          * the BTreeNode has the minimum number of elements, has a rightSibling, and the
619          * rightSibling has more than the minimum number of elements. If after completion
620          * parent has fewer than the minimum number of elements than the parents entries[0]
621          * slot is left empty in anticipation of a recursive call to stealLeft, stealRight,
622          * mergeLeft, or mergeRight to fix the parent. All of the before-mentioned methods
623          * expect the parent to be in such a condition.
624         */

625         private void mergeRight(int parentIndex) {
626             BTreeNode p = parent;
627             BTreeNode rs = p.entries[parentIndex + 1].child;
628
629             if (isLeaf()) { // Don't worry about children
630
entries[nrElements] = new Entry();
631                 entries[nrElements].element = p.entries[parentIndex].element;
632                 nrElements++;
633                 for (int i = 0, nr = nrElements; i < rs.nrElements; i++, nr++) {
634                     entries[nr] = rs.entries[i];
635                     nrElements++;
636                 }
637                 p.entries[parentIndex].element = p.entries[parentIndex + 1].element;
638                 if (p.nrElements == MIN && p != BTreeSet.this.root) {
639                     for (int x = parentIndex + 1, y = parentIndex; y >= 0; x--, y--)
640                         p.entries[x] = p.entries[y];
641                     p.entries[0] = new Entry();
642                     p.entries[0].child = rs; // So it doesn't think it's a leaf, this child will be deleted in the next recursive call
643
}
644
645                 else {
646                     for (int x = parentIndex + 1, y = parentIndex + 2; y <= p.nrElements; x++, y++)
647                         p.entries[x] = p.entries[y];
648                     p.entries[p.nrElements] = null;
649                 }
650
651                 p.nrElements--;
652                 if (p.isRoot() && p.nrElements == 0) { // It's the root and it's empty
653
BTreeSet.this.root = this;
654                     parent = null;
655                 }
656            }
657
658            else { // It's not a leaf
659

660                entries[nrElements].element = p.entries[parentIndex].element;
661                nrElements++;
662
663                for (int x = nrElements + 1, y = 0; y <= rs.nrElements; x++, y++) {
664                    entries[x] = rs.entries[y];
665                    rs.entries[y].child.parent = this;
666                    nrElements++;
667                }
668                nrElements--;
669
670                p.entries[++parentIndex].child = this;
671
672                if (p.nrElements == MIN && p != BTreeSet.this.root) {
673                   for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x--, y--)
674                       p.entries[x] = p.entries[y];
675                   p.entries[0] = new Entry();
676                }
677
678                else {
679                    for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++)
680                        p.entries[x] = p.entries[y];
681                    p.entries[p.nrElements] = null;
682                }
683
684                p.nrElements--;
685
686                if (p.isRoot() && p.nrElements == 0) { // It's the root and it's empty
687
BTreeSet.this.root = this;
688                    parent = null;
689                }
690             }
691         }
692   }
693 }
694
695
Popular Tags