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