001: /* ====================================================================
002: Licensed to the Apache Software Foundation (ASF) under one or more
003: contributor license agreements. See the NOTICE file distributed with
004: this work for additional information regarding copyright ownership.
005: The ASF licenses this file to You under the Apache License, Version 2.0
006: (the "License"); you may not use this file except in compliance with
007: the License. You may obtain a copy of the License at
008:
009: http://www.apache.org/licenses/LICENSE-2.0
010:
011: Unless required by applicable law or agreed to in writing, software
012: distributed under the License is distributed on an "AS IS" BASIS,
013: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: See the License for the specific language governing permissions and
015: limitations under the License.
016: ==================================================================== */
017:
018: package org.apache.poi.hdf.extractor.util;
019:
020: import java.util.*;
021:
022: /*
023: * A B-Tree like implementation of the java.util.Set inteface. This is a modifiable set
024: * and thus allows elements to be added and removed. An instance of java.util.Comparator
025: * must be provided at construction else all Objects added to the set must implement
026: * java.util.Comparable and must be comparable to one another. No duplicate elements
027: * will be allowed in any BTreeSet in accordance with the specifications of the Set interface.
028: * Any attempt to add a null element will result in an IllegalArgumentException being thrown.
029: * The java.util.Iterator returned by the iterator method guarantees the elements returned
030: * are in ascending order. The Iterator.remove() method is supported.
031: * Comment me
032: *
033: * @author Ryan Ackley
034: *
035: */
036:
037: public class BTreeSet extends AbstractSet implements Set {
038:
039: /*
040: * Instance Variables
041: */
042: public BTreeNode root;
043: private Comparator comparator = null;
044: private int order;
045: private int size = 0;
046:
047: /*
048: * Constructors
049: * A no-arg constructor is supported in accordance with the specifications of the
050: * java.util.Collections interface. If the order for the B-Tree is not specified
051: * at construction it defaults to 32.
052: */
053:
054: public BTreeSet() {
055: this (6); // Default order for a BTreeSet is 32
056: }
057:
058: public BTreeSet(Collection c) {
059: this (6); // Default order for a BTreeSet is 32
060: addAll(c);
061: }
062:
063: public BTreeSet(int order) {
064: this (order, null);
065: }
066:
067: public BTreeSet(int order, Comparator comparator) {
068: this .order = order;
069: this .comparator = comparator;
070: root = new BTreeNode(null);
071: }
072:
073: /*
074: * Public Methods
075: */
076: public boolean add(Object x) throws IllegalArgumentException {
077: if (x == null)
078: throw new IllegalArgumentException();
079: return root.insert(x, -1);
080: }
081:
082: public boolean contains(Object x) {
083: return root.includes(x);
084: }
085:
086: public boolean remove(Object x) {
087: if (x == null)
088: return false;
089: return root.delete(x, -1);
090: }
091:
092: public int size() {
093: return size;
094: }
095:
096: public void clear() {
097: root = new BTreeNode(null);
098: size = 0;
099: }
100:
101: public java.util.Iterator iterator() {
102: return new Iterator();
103: }
104:
105: /*
106: * Private methods
107: */
108: private int compare(Object x, Object y) {
109: return (comparator == null ? ((Comparable) x).compareTo(y)
110: : comparator.compare(x, y));
111: }
112:
113: /*
114: * Inner Classes
115: */
116:
117: /*
118: * Guarantees that the Objects are returned in ascending order. Due to the volatile
119: * structure of a B-Tree (many splits, steals and merges can happen in a single call to remove)
120: * this Iterator does not attempt to track any concurrent changes that are happening to
121: * it's BTreeSet. Therefore, after every call to BTreeSet.remove or BTreeSet.add a new
122: * Iterator should be constructed. If no new Iterator is constructed than there is a
123: * chance of receiving a NullPointerException. The Iterator.delete method is supported.
124: */
125:
126: private class Iterator implements java.util.Iterator {
127: private int index = 0;
128: private Stack parentIndex = new Stack(); // Contains all parentIndicies for currentNode
129: private Object lastReturned = null;
130: private Object next;
131: private BTreeNode currentNode;
132:
133: Iterator() {
134: currentNode = firstNode();
135: next = nextElement();
136: }
137:
138: public boolean hasNext() {
139: return next != null;
140: }
141:
142: public Object next() {
143: if (next == null)
144: throw new NoSuchElementException();
145:
146: lastReturned = next;
147: next = nextElement();
148: return lastReturned;
149: }
150:
151: public void remove() {
152: if (lastReturned == null)
153: throw new NoSuchElementException();
154:
155: BTreeSet.this .remove(lastReturned);
156: lastReturned = null;
157: }
158:
159: private BTreeNode firstNode() {
160: BTreeNode temp = BTreeSet.this .root;
161:
162: while (temp.entries[0].child != null) {
163: temp = temp.entries[0].child;
164: parentIndex.push(new Integer(0));
165: }
166:
167: return temp;
168: }
169:
170: private Object nextElement() {
171: if (currentNode.isLeaf()) {
172: if (index < currentNode.nrElements)
173: return currentNode.entries[index++].element;
174:
175: else if (!parentIndex.empty()) { //All elements have been returned, return successor of lastReturned if it exists
176: currentNode = currentNode.parent;
177: index = ((Integer) parentIndex.pop()).intValue();
178:
179: while (index == currentNode.nrElements) {
180: if (parentIndex.empty())
181: break;
182: currentNode = currentNode.parent;
183: index = ((Integer) parentIndex.pop())
184: .intValue();
185: }
186:
187: if (index == currentNode.nrElements)
188: return null; //Reached root and he has no more children
189: return currentNode.entries[index++].element;
190: }
191:
192: else { //Your a leaf and the root
193: if (index == currentNode.nrElements)
194: return null;
195: return currentNode.entries[index++].element;
196: }
197: }
198:
199: else { //Your not a leaf so simply find and return the successor of lastReturned
200: currentNode = currentNode.entries[index].child;
201: parentIndex.push(new Integer(index));
202:
203: while (currentNode.entries[0].child != null) {
204: currentNode = currentNode.entries[0].child;
205: parentIndex.push(new Integer(0));
206: }
207:
208: index = 1;
209: return currentNode.entries[0].element;
210: }
211: }
212: }
213:
214: public static class Entry {
215:
216: public Object element;
217: public BTreeNode child;
218: }
219:
220: public class BTreeNode {
221:
222: public Entry[] entries;
223: public BTreeNode parent;
224: private int nrElements = 0;
225: private final int MIN = (BTreeSet.this .order - 1) / 2;
226:
227: BTreeNode(BTreeNode parent) {
228: this .parent = parent;
229: entries = new Entry[BTreeSet.this .order];
230: entries[0] = new Entry();
231: }
232:
233: boolean insert(Object x, int parentIndex) {
234: if (isFull()) { // If full, you must split and promote splitNode before inserting
235: Object splitNode = entries[nrElements / 2].element;
236: BTreeNode rightSibling = split();
237:
238: if (isRoot()) { // Grow a level
239: splitRoot(splitNode, this , rightSibling);
240: // Determine where to insert
241: if (BTreeSet.this .compare(x,
242: BTreeSet.this .root.entries[0].element) < 0)
243: insert(x, 0);
244: else
245: rightSibling.insert(x, 1);
246: }
247:
248: else { // Promote splitNode
249: parent.insertSplitNode(splitNode, this ,
250: rightSibling, parentIndex);
251: if (BTreeSet.this .compare(x,
252: parent.entries[parentIndex].element) < 0)
253: return insert(x, parentIndex);
254: else
255: return rightSibling.insert(x, parentIndex + 1);
256: }
257: }
258:
259: else if (isLeaf()) { // If leaf, simply insert the non-duplicate element
260: int insertAt = childToInsertAt(x, true);
261: if (insertAt == -1)
262: return false; // Determine if the element already exists
263: else {
264: insertNewElement(x, insertAt);
265: BTreeSet.this .size++;
266: return true;
267: }
268: }
269:
270: else { // If not full and not leaf recursively find correct node to insert at
271: int insertAt = childToInsertAt(x, true);
272: return (insertAt == -1 ? false
273: : entries[insertAt].child.insert(x, insertAt));
274: }
275: return false;
276: }
277:
278: boolean includes(Object x) {
279: int index = childToInsertAt(x, true);
280: if (index == -1)
281: return true;
282: if (entries[index] == null || entries[index].child == null)
283: return false;
284: return entries[index].child.includes(x);
285: }
286:
287: boolean delete(Object x, int parentIndex) {
288: int i = childToInsertAt(x, true);
289: int priorParentIndex = parentIndex;
290: BTreeNode temp = this ;
291: if (i != -1) {
292: do {
293: if (temp.entries[i] == null
294: || temp.entries[i].child == null)
295: return false;
296: temp = temp.entries[i].child;
297: priorParentIndex = parentIndex;
298: parentIndex = i;
299: i = temp.childToInsertAt(x, true);
300: } while (i != -1);
301: } // Now temp contains element to delete and temp's parentIndex is parentIndex
302:
303: if (temp.isLeaf()) { // If leaf and have more than MIN elements, simply delete
304: if (temp.nrElements > MIN) {
305: temp.deleteElement(x);
306: BTreeSet.this .size--;
307: return true;
308: }
309:
310: else { // If leaf and have less than MIN elements, than prepare the BTreeSet for deletion
311: temp.prepareForDeletion(parentIndex);
312: temp.deleteElement(x);
313: BTreeSet.this .size--;
314: temp.fixAfterDeletion(priorParentIndex);
315: return true;
316: }
317: }
318:
319: else { // Only delete at leaf so first switch with successor than delete
320: temp.switchWithSuccessor(x);
321: parentIndex = temp.childToInsertAt(x, false) + 1;
322: return temp.entries[parentIndex].child.delete(x,
323: parentIndex);
324: }
325: }
326:
327: private boolean isFull() {
328: return nrElements == (BTreeSet.this .order - 1);
329: }
330:
331: private boolean isLeaf() {
332: return entries[0].child == null;
333: }
334:
335: private boolean isRoot() {
336: return parent == null;
337: }
338:
339: /*
340: * Splits a BTreeNode into two BTreeNodes, removing the splitNode from the
341: * calling BTreeNode.
342: */
343: private BTreeNode split() {
344: BTreeNode rightSibling = new BTreeNode(parent);
345: int index = nrElements / 2;
346: entries[index++].element = null;
347:
348: for (int i = 0, nr = nrElements; index <= nr; i++, index++) {
349: rightSibling.entries[i] = entries[index];
350: if (rightSibling.entries[i] != null
351: && rightSibling.entries[i].child != null)
352: rightSibling.entries[i].child.parent = rightSibling;
353: entries[index] = null;
354: nrElements--;
355: rightSibling.nrElements++;
356: }
357:
358: rightSibling.nrElements--; // Need to correct for copying the last Entry which has a null element and a child
359: return rightSibling;
360: }
361:
362: /*
363: * Creates a new BTreeSet.root which contains only the splitNode and pointers
364: * to it's left and right child.
365: */
366: private void splitRoot(Object splitNode, BTreeNode left,
367: BTreeNode right) {
368: BTreeNode newRoot = new BTreeNode(null);
369: newRoot.entries[0].element = splitNode;
370: newRoot.entries[0].child = left;
371: newRoot.entries[1] = new Entry();
372: newRoot.entries[1].child = right;
373: newRoot.nrElements = 1;
374: left.parent = right.parent = newRoot;
375: BTreeSet.this .root = newRoot;
376: }
377:
378: private void insertSplitNode(Object splitNode, BTreeNode left,
379: BTreeNode right, int insertAt) {
380: for (int i = nrElements; i >= insertAt; i--)
381: entries[i + 1] = entries[i];
382:
383: entries[insertAt] = new Entry();
384: entries[insertAt].element = splitNode;
385: entries[insertAt].child = left;
386: entries[insertAt + 1].child = right;
387:
388: nrElements++;
389: }
390:
391: private void insertNewElement(Object x, int insertAt) {
392:
393: for (int i = nrElements; i > insertAt; i--)
394: entries[i] = entries[i - 1];
395:
396: entries[insertAt] = new Entry();
397: entries[insertAt].element = x;
398:
399: nrElements++;
400: }
401:
402: /*
403: * Possibly a deceptive name for a pretty cool method. Uses binary search
404: * to determine the postion in entries[] in which to traverse to find the correct
405: * BTreeNode in which to insert a new element. If the element exists in the calling
406: * BTreeNode than -1 is returned. When the parameter position is true and the element
407: * is present in the calling BTreeNode -1 is returned, if position is false and the
408: * element is contained in the calling BTreeNode than the position of the element
409: * in entries[] is returned.
410: */
411: private int childToInsertAt(Object x, boolean position) {
412: int index = nrElements / 2;
413:
414: if (entries[index] == null
415: || entries[index].element == null)
416: return index;
417:
418: int lo = 0, hi = nrElements - 1;
419: while (lo <= hi) {
420: if (BTreeSet.this .compare(x, entries[index].element) > 0) {
421: lo = index + 1;
422: index = (hi + lo) / 2;
423: } else {
424: hi = index - 1;
425: index = (hi + lo) / 2;
426: }
427: }
428:
429: hi++;
430: if (entries[hi] == null || entries[hi].element == null)
431: return hi;
432: return (!position ? hi : BTreeSet.this .compare(x,
433: entries[hi].element) == 0 ? -1 : hi);
434: }
435:
436: private void deleteElement(Object x) {
437: int index = childToInsertAt(x, false);
438: for (; index < (nrElements - 1); index++)
439: entries[index] = entries[index + 1];
440:
441: if (nrElements == 1)
442: entries[index] = new Entry(); // This is root and it is empty
443: else
444: entries[index] = null;
445:
446: nrElements--;
447: }
448:
449: private void prepareForDeletion(int parentIndex) {
450: if (isRoot())
451: return; // Don't attempt to steal or merge if your the root
452:
453: // If not root then try to steal left
454: else if (parentIndex != 0
455: && parent.entries[parentIndex - 1].child.nrElements > MIN) {
456: stealLeft(parentIndex);
457: return;
458: }
459:
460: // If not root and can't steal left try to steal right
461: else if (parentIndex < entries.length
462: && parent.entries[parentIndex + 1] != null
463: && parent.entries[parentIndex + 1].child != null
464: && parent.entries[parentIndex + 1].child.nrElements > MIN) {
465: stealRight(parentIndex);
466: return;
467: }
468:
469: // If not root and can't steal left or right then try to merge left
470: else if (parentIndex != 0) {
471: mergeLeft(parentIndex);
472: return;
473: }
474:
475: // If not root and can't steal left or right and can't merge left you must be able to merge right
476: else
477: mergeRight(parentIndex);
478: }
479:
480: private void fixAfterDeletion(int parentIndex) {
481: if (isRoot() || parent.isRoot())
482: return; // No fixing needed
483:
484: if (parent.nrElements < MIN) { // If parent lost it's n/2 element repair it
485: BTreeNode temp = parent;
486: temp.prepareForDeletion(parentIndex);
487: if (temp.parent == null)
488: return; // Root changed
489: if (!temp.parent.isRoot()
490: && temp.parent.nrElements < MIN) { // If need be recurse
491: BTreeNode x = temp.parent.parent;
492: int i = 0;
493: // Find parent's parentIndex
494: for (; i < entries.length; i++)
495: if (x.entries[i].child == temp.parent)
496: break;
497: temp.parent.fixAfterDeletion(i);
498: }
499: }
500: }
501:
502: private void switchWithSuccessor(Object x) {
503: int index = childToInsertAt(x, false);
504: BTreeNode temp = entries[index + 1].child;
505: while (temp.entries[0] != null
506: && temp.entries[0].child != null)
507: temp = temp.entries[0].child;
508: Object successor = temp.entries[0].element;
509: temp.entries[0].element = entries[index].element;
510: entries[index].element = successor;
511: }
512:
513: /*
514: * This method is called only when the BTreeNode has the minimum number of elements,
515: * has a leftSibling, and the leftSibling has more than the minimum number of elements.
516: */
517: private void stealLeft(int parentIndex) {
518: BTreeNode p = parent;
519: BTreeNode ls = parent.entries[parentIndex - 1].child;
520:
521: if (isLeaf()) { // When stealing from leaf to leaf don't worry about children
522: int add = childToInsertAt(
523: p.entries[parentIndex - 1].element, true);
524: insertNewElement(p.entries[parentIndex - 1].element,
525: add);
526: p.entries[parentIndex - 1].element = ls.entries[ls.nrElements - 1].element;
527: ls.entries[ls.nrElements - 1] = null;
528: ls.nrElements--;
529: }
530:
531: else { // Was called recursively to fix an undermanned parent
532: entries[0].element = p.entries[parentIndex - 1].element;
533: p.entries[parentIndex - 1].element = ls.entries[ls.nrElements - 1].element;
534: entries[0].child = ls.entries[ls.nrElements].child;
535: entries[0].child.parent = this ;
536: ls.entries[ls.nrElements] = null;
537: ls.entries[ls.nrElements - 1].element = null;
538: nrElements++;
539: ls.nrElements--;
540: }
541: }
542:
543: /*
544: * This method is called only when stealLeft can't be called, the BTreeNode
545: * has the minimum number of elements, has a rightSibling, and the rightSibling
546: * has more than the minimum number of elements.
547: */
548: private void stealRight(int parentIndex) {
549: BTreeNode p = parent;
550: BTreeNode rs = p.entries[parentIndex + 1].child;
551:
552: if (isLeaf()) { // When stealing from leaf to leaf don't worry about children
553: entries[nrElements] = new Entry();
554: entries[nrElements].element = p.entries[parentIndex].element;
555: p.entries[parentIndex].element = rs.entries[0].element;
556: for (int i = 0; i < rs.nrElements; i++)
557: rs.entries[i] = rs.entries[i + 1];
558: rs.entries[rs.nrElements - 1] = null;
559: nrElements++;
560: rs.nrElements--;
561: }
562:
563: else { // Was called recursively to fix an undermanned parent
564: for (int i = 0; i <= nrElements; i++)
565: entries[i] = entries[i + 1];
566: entries[nrElements].element = p.entries[parentIndex].element;
567: p.entries[parentIndex].element = rs.entries[0].element;
568: entries[nrElements + 1] = new Entry();
569: entries[nrElements + 1].child = rs.entries[0].child;
570: entries[nrElements + 1].child.parent = this ;
571: for (int i = 0; i <= rs.nrElements; i++)
572: rs.entries[i] = rs.entries[i + 1];
573: rs.entries[rs.nrElements] = null;
574: nrElements++;
575: rs.nrElements--;
576: }
577: }
578:
579: /*
580: * This method is called only when stealLeft and stealRight could not be called,
581: * the BTreeNode has the minimum number of elements, has a leftSibling, and the
582: * leftSibling has more than the minimum number of elements. If after completion
583: * parent has fewer than the minimum number of elements than the parents entries[0]
584: * slot is left empty in anticipation of a recursive call to stealLeft, stealRight,
585: * mergeLeft, or mergeRight to fix the parent. All of the before-mentioned methods
586: * expect the parent to be in such a condition.
587: */
588: private void mergeLeft(int parentIndex) {
589: BTreeNode p = parent;
590: BTreeNode ls = p.entries[parentIndex - 1].child;
591:
592: if (isLeaf()) { // Don't worry about children
593: int add = childToInsertAt(
594: p.entries[parentIndex - 1].element, true);
595: insertNewElement(p.entries[parentIndex - 1].element,
596: add); // Could have been a successor switch
597: p.entries[parentIndex - 1].element = null;
598:
599: for (int i = nrElements - 1, nr = ls.nrElements; i >= 0; i--)
600: entries[i + nr] = entries[i];
601:
602: for (int i = ls.nrElements - 1; i >= 0; i--) {
603: entries[i] = ls.entries[i];
604: nrElements++;
605: }
606:
607: if (p.nrElements == MIN && p != BTreeSet.this .root) {
608:
609: for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x--, y--)
610: p.entries[x] = p.entries[y];
611: p.entries[0] = new Entry();
612: p.entries[0].child = ls; //So p doesn't think it's a leaf this will be deleted in the next recursive call
613: }
614:
615: else {
616:
617: for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++)
618: p.entries[x] = p.entries[y];
619: p.entries[p.nrElements] = null;
620: }
621:
622: p.nrElements--;
623:
624: if (p.isRoot() && p.nrElements == 0) { // It's the root and it's empty
625: BTreeSet.this .root = this ;
626: parent = null;
627: }
628: }
629:
630: else { // I'm not a leaf but fixing the tree structure
631: entries[0].element = p.entries[parentIndex - 1].element;
632: entries[0].child = ls.entries[ls.nrElements].child;
633: nrElements++;
634:
635: for (int x = nrElements, nr = ls.nrElements; x >= 0; x--)
636: entries[x + nr] = entries[x];
637:
638: for (int x = ls.nrElements - 1; x >= 0; x--) {
639: entries[x] = ls.entries[x];
640: entries[x].child.parent = this ;
641: nrElements++;
642: }
643:
644: if (p.nrElements == MIN && p != BTreeSet.this .root) { // Push everything to the right
645: for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x++, y++) {
646: System.out.println(x + " " + y);
647: p.entries[x] = p.entries[y];
648: }
649: p.entries[0] = new Entry();
650: }
651:
652: else { // Either p.nrElements > MIN or p == BTreeSet.this.root so push everything to the left
653: for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++)
654: p.entries[x] = p.entries[y];
655: p.entries[p.nrElements] = null;
656: }
657:
658: p.nrElements--;
659:
660: if (p.isRoot() && p.nrElements == 0) { // p == BTreeSet.this.root and it's empty
661: BTreeSet.this .root = this ;
662: parent = null;
663: }
664: }
665: }
666:
667: /*
668: * This method is called only when stealLeft, stealRight, and mergeLeft could not be called,
669: * the BTreeNode has the minimum number of elements, has a rightSibling, and the
670: * rightSibling has more than the minimum number of elements. If after completion
671: * parent has fewer than the minimum number of elements than the parents entries[0]
672: * slot is left empty in anticipation of a recursive call to stealLeft, stealRight,
673: * mergeLeft, or mergeRight to fix the parent. All of the before-mentioned methods
674: * expect the parent to be in such a condition.
675: */
676: private void mergeRight(int parentIndex) {
677: BTreeNode p = parent;
678: BTreeNode rs = p.entries[parentIndex + 1].child;
679:
680: if (isLeaf()) { // Don't worry about children
681: entries[nrElements] = new Entry();
682: entries[nrElements].element = p.entries[parentIndex].element;
683: nrElements++;
684: for (int i = 0, nr = nrElements; i < rs.nrElements; i++, nr++) {
685: entries[nr] = rs.entries[i];
686: nrElements++;
687: }
688: p.entries[parentIndex].element = p.entries[parentIndex + 1].element;
689: if (p.nrElements == MIN && p != BTreeSet.this .root) {
690: for (int x = parentIndex + 1, y = parentIndex; y >= 0; x--, y--)
691: p.entries[x] = p.entries[y];
692: p.entries[0] = new Entry();
693: p.entries[0].child = rs; // So it doesn't think it's a leaf, this child will be deleted in the next recursive call
694: }
695:
696: else {
697: for (int x = parentIndex + 1, y = parentIndex + 2; y <= p.nrElements; x++, y++)
698: p.entries[x] = p.entries[y];
699: p.entries[p.nrElements] = null;
700: }
701:
702: p.nrElements--;
703: if (p.isRoot() && p.nrElements == 0) { // It's the root and it's empty
704: BTreeSet.this .root = this ;
705: parent = null;
706: }
707: }
708:
709: else { // It's not a leaf
710:
711: entries[nrElements].element = p.entries[parentIndex].element;
712: nrElements++;
713:
714: for (int x = nrElements + 1, y = 0; y <= rs.nrElements; x++, y++) {
715: entries[x] = rs.entries[y];
716: rs.entries[y].child.parent = this ;
717: nrElements++;
718: }
719: nrElements--;
720:
721: p.entries[++parentIndex].child = this ;
722:
723: if (p.nrElements == MIN && p != BTreeSet.this .root) {
724: for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x--, y--)
725: p.entries[x] = p.entries[y];
726: p.entries[0] = new Entry();
727: }
728:
729: else {
730: for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++)
731: p.entries[x] = p.entries[y];
732: p.entries[p.nrElements] = null;
733: }
734:
735: p.nrElements--;
736:
737: if (p.isRoot() && p.nrElements == 0) { // It's the root and it's empty
738: BTreeSet.this.root = this;
739: parent = null;
740: }
741: }
742: }
743: }
744: }
|