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