Java > Open Source Codes > org > eclipse > jface > viewers > deferred > LazySortedCollection


1 /*******************************************************************************
2  * Copyright (c) 2004, 2006 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.jface.viewers.deferred;
12
13 import java.util.Collection ;
14 import java.util.Comparator ;
15 import java.util.Iterator ;
16
17 import org.eclipse.core.runtime.Assert;
18
19 /**
20  * This object maintains a collection of elements, sorted by a comparator
21  * given in the constructor. The collection is lazily sorted, allowing
22  * more efficient runtimes for most methods. There are several methods on this
23  * object that allow objects to be queried by their position in the sorted
24  * collection.
25  *
26  * <p>
27  * This is a modified binary search tree. Each subtree has a value, a left and right subtree,
28  * a count of the number of children, and a set of unsorted children.
29  * Insertion happens lazily. When a new node N is inserted into a subtree T, it is initially
30  * added to the set of unsorted children for T without actually comparing it with the value for T.
31  * </p>
32  * <p>
33  * The unsorted children will remain in the unsorted set until some subsequent operation requires
34  * us to know the exact set of elements in one of the subtrees. At that time, we partition
35  * T by comparing all of its unsorted children with T's value and moving them into the left
36  * or right subtrees.
37  * </p>
38  *
39  * @since 3.1
40  */
41 public class LazySortedCollection {
42     private final int MIN_CAPACITY = 8;
43     private Object [] contents = new Object [MIN_CAPACITY];
44     private int[] leftSubTree = new int[MIN_CAPACITY];
45     private int[] rightSubTree = new int[MIN_CAPACITY];
46     private int[] nextUnsorted = new int[MIN_CAPACITY];
47     private int[] treeSize = new int[MIN_CAPACITY];
48     private int[] parentTree = new int[MIN_CAPACITY];
49     private int root = -1;
50     private int lastNode = 0;
51     private int firstUnusedNode = -1;
52     
53     private static final float loadFactor = 0.75f;
54     
55     private IntHashMap objectIndices;
56     private Comparator comparator;
57     private static int counter = 0;
58     
59     /**
60      * Disables randomization and enables additional runtime error checking.
61      * Severely degrades performance if set to true. Intended for use in test
62      * suites only.
63      */
64     public boolean enableDebug = false;
65     
66     // This object is inserted as the value into any node scheduled for lazy removal
67 private Object lazyRemovalFlag = new Object () {
68         public String toString() {
69             return "Lazy removal flag"; //$NON-NLS-1$
70 }
71     };
72     
73     private final static int DIR_LEFT = 0;
74     private final static int DIR_RIGHT = 1;
75     private final static int DIR_UNSORTED = 2;
76     
77     // Direction constants indicating root nodes
78 private final static int DIR_ROOT = 3;
79     private final static int DIR_UNUSED = 4;
80        
81     private final class Edge {
82         private int startNode;
83         private int direction;
84         
85         private Edge() {
86             startNode = -1;
87             direction = -1;
88         }
89         
90         private Edge(int node, int dir) {
91             startNode = node;
92             direction = dir;
93         }
94         
95         private int getStart() {
96             return startNode;
97         }
98         
99         private int getTarget() {
100             if (startNode == -1) {
101                 if (direction == DIR_UNSORTED) {
102                     return firstUnusedNode;
103                 } else if (direction == DIR_ROOT) {
104                     return root;
105                 }
106                 return -1;
107             }
108             
109             if (direction == DIR_LEFT) {
110                 return leftSubTree[startNode];
111             }
112             if (direction == DIR_RIGHT) {
113                 return rightSubTree[startNode];
114             }
115             return nextUnsorted[startNode];
116         }
117         
118         private boolean isNull() {
119             return getTarget() == -1;
120         }
121      
122         /**
123          * Redirects this edge to a new node
124          * @param newNode
125          * @since 3.1
126          */
127         private void setTarget(int newNode) {
128             if (direction == DIR_LEFT) {
129                 leftSubTree[startNode] = newNode;
130             } else if (direction == DIR_RIGHT) {
131                 rightSubTree[startNode] = newNode;
132             } else if (direction == DIR_UNSORTED) {
133                 nextUnsorted[startNode] = newNode;
134             } else if (direction == DIR_ROOT) {
135                 root = newNode;
136             } else if (direction == DIR_UNUSED) {
137                 firstUnusedNode = newNode;
138             }
139             
140             if (newNode != -1) {
141                 parentTree[newNode] = startNode;
142             }
143         }
144         
145         private void advance(int direction) {
146             startNode = getTarget();
147             this.direction = direction;
148         }
149     }
150
151     private void setRootNode(int node) {
152         root = node;
153         if (node != -1) {
154             parentTree[node] = -1;
155         }
156     }
157     
158     /**
159      * Creates a new sorted collection using the given comparator to determine
160      * sort order.
161      *
162      * @param c comparator that determines the sort order
163      */
164     public LazySortedCollection(Comparator c) {
165         this.comparator = c;
166     }
167     
168     /**
169      * Tests if this object's internal state is valid. Throws a runtime
170      * exception if the state is invalid, indicating a programming error
171      * in this class. This method is intended for use in test
172      * suites and should not be called by clients.
173      */
174     public void testInvariants() {
175         if (!enableDebug) {
176             return;
177         }
178         
179         testInvariants(root);
180     }
181     
182     private void testInvariants(int node) {
183         if (node == -1) {
184             return;
185         }
186         
187         // Get the current tree size (we will later force the tree size
188 // to be recomputed from scratch -- if everything works properly, then
189 // there should be no change.
190 int treeSize = getSubtreeSize(node);
191
192         int left = leftSubTree[node];
193         int right = rightSubTree[node];
194         int unsorted = nextUnsorted[node];
195         
196         if (isUnsorted(node)) {
197             Assert.isTrue(left == -1, "unsorted nodes shouldn't have a left subtree"); //$NON-NLS-1$
198 Assert.isTrue(right == -1, "unsorted nodes shouldn't have a right subtree"); //$NON-NLS-1$
199 }
200         
201         if (left != -1) {
202             testInvariants(left);
203             Assert.isTrue(parentTree[left] == node, "left node has invalid parent pointer"); //$NON-NLS-1$
204 }
205         if (right != -1) {
206             testInvariants(right);
207             Assert.isTrue(parentTree[right] == node, "right node has invalid parent pointer"); //$NON-NLS-1$
208 }
209
210         int previous = node;
211         while (unsorted != -1) {
212             int oldTreeSize = this.treeSize[unsorted];
213             recomputeTreeSize(unsorted);
214             
215             Assert.isTrue(this.treeSize[unsorted] == oldTreeSize,
216                     "Invalid node size for unsorted node"); //$NON-NLS-1$
217 Assert.isTrue(leftSubTree[unsorted] == -1, "unsorted nodes shouldn't have left subtrees"); //$NON-NLS-1$
218 Assert.isTrue(rightSubTree[unsorted] == -1, "unsorted nodes shouldn't have right subtrees"); //$NON-NLS-1$
219 Assert.isTrue(parentTree[unsorted] == previous, "unsorted node has invalid parent pointer"); //$NON-NLS-1$
220 Assert.isTrue(contents[unsorted] != lazyRemovalFlag, "unsorted nodes should not be lazily removed"); //$NON-NLS-1$
221 previous = unsorted;
222             unsorted = nextUnsorted[unsorted];
223         }
224         
225         // Note that we've already tested that the child sizes are correct... if our size is
226 // correct, then recomputing it now should not cause any change.
227 recomputeTreeSize(node);
228                 
229         Assert.isTrue(treeSize == getSubtreeSize(node), "invalid tree size"); //$NON-NLS-1$
230 }
231     
232     private boolean isUnsorted(int node) {
233         int parent = parentTree[node];
234         
235         if (parent != -1) {
236             return nextUnsorted[parent] == node;
237         }
238         
239         return false;
240     }
241     
242     private final boolean isLess(int element1, int element2) {
243         return comparator.compare(contents[element1], contents[element2]) < 0;
244     }
245     
246     /**
247      * Adds the given element to the given subtree. Returns the new
248      * root of the subtree.
249      *
250      * @param subTree index of the subtree to insert elementToAdd into. If -1,
251      * then a new subtree will be created for elementToAdd
252      * @param elementToAdd index of the element to add to the subtree. If -1, this method
253      * is a NOP.
254      * @since 3.1
255      */
256     private final int addUnsorted(int subTree, int elementToAdd) {
257         if (elementToAdd == -1) {
258             return subTree;
259         }
260         
261         if (subTree == -1) {
262             nextUnsorted[elementToAdd] = -1;
263             treeSize[elementToAdd] = 1;
264             return elementToAdd;
265         }
266         
267         // If the subTree is empty (ie: it only contains nodes flagged for lazy removal),
268 // chop it off.
269 if (treeSize[subTree] == 0) {
270             removeSubTree(subTree);
271             nextUnsorted[elementToAdd] = -1;
272             treeSize[elementToAdd] = 1;
273             return elementToAdd;
274         }
275         
276         // If neither subtree has any children, add a pseudorandom chance of the
277 // newly added element becoming the new pivot for this node. Note: instead
278 // of a real pseudorandom generator, we simply use a counter here.
279 if (!enableDebug && leftSubTree[subTree] == -1 && rightSubTree[subTree] == -1
280                 && leftSubTree[elementToAdd] == -1 && rightSubTree[elementToAdd] == -1) {
281             counter--;
282             
283             if (counter % treeSize[subTree] == 0) {
284                 // Make the new node into the new pivot
285 nextUnsorted[elementToAdd] = subTree;
286                 parentTree[elementToAdd] = parentTree[subTree];
287                 parentTree[subTree] = elementToAdd;
288                 treeSize[elementToAdd] = treeSize[subTree] + 1;
289                 return elementToAdd;
290             }
291         }
292         
293         int oldNextUnsorted = nextUnsorted[subTree];
294         nextUnsorted[elementToAdd] = oldNextUnsorted;
295         
296         if (oldNextUnsorted == -1) {
297             treeSize[elementToAdd] = 1;
298         } else {
299             treeSize[elementToAdd] = treeSize[oldNextUnsorted] + 1;
300             parentTree[oldNextUnsorted] = elementToAdd;
301         }
302         
303         parentTree[elementToAdd] = subTree;
304         
305         nextUnsorted[subTree] = elementToAdd;
306         treeSize[subTree]++;
307         return subTree;
308     }
309     
310     /**
311      * Returns the number of elements in the collection
312      *
313      * @return the number of elements in the collection
314      */
315     public int size() {
316         int result = getSubtreeSize(root);
317         
318         testInvariants();
319         
320         return result;
321     }
322     
323     /**
324      * Given a tree and one of its unsorted children, this sorts the child by moving
325      * it into the left or right subtrees. Returns the next unsorted child or -1 if none
326      *
327      * @param subTree parent tree
328      * @param toMove child (unsorted) subtree
329      * @since 3.1
330      */
331     private final int partition(int subTree, int toMove) {
332         int result = nextUnsorted[toMove];
333         
334         if (isLess(toMove, subTree)) {
335             int nextLeft = addUnsorted(leftSubTree[subTree], toMove);
336             leftSubTree[subTree] = nextLeft;
337             parentTree[nextLeft] = subTree;
338         } else {
339             int nextRight = addUnsorted(rightSubTree[subTree], toMove);
340             rightSubTree[subTree] = nextRight;
341             parentTree[nextRight] = subTree;
342         }
343         
344         return result;
345     }
346     
347     /**
348      * Partitions the given subtree. Moves all unsorted elements at the given node
349      * to either the left or right subtrees. If the node itself was scheduled for
350      * lazy removal, this will force the node to be removed immediately. Returns
351      * the new subTree.
352      *
353      * @param subTree
354      * @return the replacement node (this may be different from subTree if the subtree
355      * was replaced during the removal)
356      * @since 3.1
357      */
358     private final int partition(int subTree, FastProgressReporter mon) throws InterruptedException {
359         if (subTree == -1) {
360             return -1;
361         }
362         
363         if (contents[subTree] == lazyRemovalFlag) {
364             subTree = removeNode(subTree);
365             if (subTree == -1) {
366                 return -1;
367             }
368         }
369         
370         for (int idx = nextUnsorted[subTree]; idx != -1;) {
371             idx = partition(subTree, idx);
372             nextUnsorted[subTree] = idx;
373             if (idx != -1) {
374                 parentTree[idx] = subTree;
375             }
376             
377             if (mon.isCanceled()) {
378                 throw new InterruptedException ();
379             }
380         }
381         
382         // At this point, there are no remaining unsorted nodes in this subtree
383 nextUnsorted[subTree] = -1;
384         
385         return subTree;
386     }
387     
388     private final int getSubtreeSize(int subTree) {
389         if (subTree == -1) {
390             return 0;
391         }
392         return treeSize[subTree];
393     }
394     
395     /**
396      * Increases the capacity of this collection, if necessary, so that it can hold the
397      * given number of elements. This can be used prior to a sequence of additions to
398      * avoid memory reallocation. This cannot be used to reduce the amount
399      * of memory used by the collection.
400      *
401      * @param newSize capacity for this collection
402      */
403     public final void setCapacity(int newSize) {
404         if (newSize > contents.length) {
405             setArraySize(newSize);
406         }
407     }
408     
409     /**
410      * Adjusts the capacity of the array.
411      *
412      * @param newCapacity
413      */
414     private final void setArraySize(int newCapacity) {
415         Object [] newContents = new Object [newCapacity];
416         System.arraycopy(contents, 0, newContents, 0, lastNode);
417         contents = newContents;
418         
419         int[] newLeftSubTree = new int[newCapacity];
420         System.arraycopy(leftSubTree, 0, newLeftSubTree, 0, lastNode);
421         leftSubTree = newLeftSubTree;
422         
423         int[] newRightSubTree = new int[newCapacity];
424         System.arraycopy(rightSubTree, 0, newRightSubTree, 0, lastNode);
425         rightSubTree = newRightSubTree;
426         
427         int[] newNextUnsorted = new int[newCapacity];
428         System.arraycopy(nextUnsorted, 0, newNextUnsorted, 0, lastNode);
429         nextUnsorted = newNextUnsorted;
430         
431         int[] newTreeSize = new int[newCapacity];
432         System.arraycopy(treeSize, 0, newTreeSize, 0, lastNode);
433         treeSize = newTreeSize;
434         
435         int[] newParentTree = new int[newCapacity];
436         System.arraycopy(parentTree, 0, newParentTree, 0, lastNode);
437         parentTree = newParentTree;
438     }
439     
440     /**
441      * Creates a new node with the given value. Returns the index of the newly
442      * created node.
443      *
444      * @param value
445      * @return the index of the newly created node
446      * @since 3.1
447      */
448     private final int createNode(Object value) {
449         int result = -1;
450
451         if (firstUnusedNode == -1) {
452             // If there are no unused nodes from prior removals, then
453 // we add a node at the end
454 result = lastNode;
455             
456             // If this would cause the array to overflow, reallocate the array
457 if (contents.length <= lastNode) {
458                 setCapacity(lastNode * 2);
459             }
460             
461             lastNode++;
462         } else {
463             // Reuse a node from a prior removal
464 result = firstUnusedNode;
465             firstUnusedNode = nextUnsorted[result];
466         }
467         
468         contents[result] = value;
469         treeSize[result] = 1;
470         
471         // Clear pointers
472 leftSubTree[result] = -1;
473         rightSubTree[result] = -1;
474         nextUnsorted[result] = -1;
475         
476         // As long as we have a hash table of values onto tree indices, incrementally
477 // update the hash table. Note: the table is only constructed as needed, and it
478 // is destroyed whenever the arrays are reallocated instead of reallocating it.
479 if (objectIndices != null) {
480             objectIndices.put(value, result);
481         }
482         
483         return result;
484     }
485     
486     /**
487      * Returns the current tree index for the given object.
488      *
489      * @param value
490      * @return the current tree index
491      * @since 3.1
492      */
493     private int getObjectIndex(Object value) {
494         // If we don't have a map of values onto tree indices, build the map now.
495 if (objectIndices == null) {
496             int result = -1;
497             
498             objectIndices = new IntHashMap((int)(contents.length / loadFactor) + 1, loadFactor);
499             
500             for (int i = 0; i < lastNode; i++) {
501                 Object element = contents[i];
502                 
503                 if (element != null && element != lazyRemovalFlag) {
504                     objectIndices.put(element, i);
505                     
506                     if (value == element) {
507                         result = i;
508                     }
509                 }
510             }
511             
512             return result;
513         }
514         
515         // If we have a map of values onto tree indices, return the result by looking it up in
516 // the map
517 return objectIndices.get(value, -1);
518     }
519     
520     /**
521      * Redirects any pointers from the original to the replacement. If the replacement
522      * causes a change in the number of elements in the parent tree, the changes are
523      * propogated toward the root.
524      *
525      * @param nodeToReplace
526      * @param replacementNode
527      * @since 3.1
528      */
529     private void replaceNode(int nodeToReplace, int replacementNode) {
530         int parent = parentTree[nodeToReplace];
531         
532         if (parent == -1) {
533             if (root == nodeToReplace) {
534                 setRootNode(replacementNode);
535             }
536         } else {
537             if (leftSubTree[parent] == nodeToReplace) {
538                 leftSubTree[parent] = replacementNode;
539             } else if (rightSubTree[parent] == nodeToReplace) {
540                 rightSubTree[parent] = replacementNode;
541             } else if (nextUnsorted[parent] == nodeToReplace) {
542                 nextUnsorted[parent] = replacementNode;
543             }
544             if (replacementNode != -1) {
545                 parentTree[replacementNode] = parent;
546             }
547         }
548     }
549     
550     private void recomputeAncestorTreeSizes(int node) {
551         while (node != -1) {
552             int oldSize = treeSize[node];
553             
554             recomputeTreeSize(node);
555             
556             if (treeSize[node] == oldSize) {
557                 break;
558             }
559             
560             node = parentTree[node];
561         }
562     }
563     
564     /**
565      * Recomputes the tree size for the given node.
566      *
567      * @param node
568      * @since 3.1
569      */
570     private void recomputeTreeSize(int node) {
571         if (node == -1) {
572             return;
573         }
574         treeSize[node] = getSubtreeSize(leftSubTree[node])
575             + getSubtreeSize(rightSubTree[node])
576             + getSubtreeSize(nextUnsorted[node])
577             + (contents[node] == lazyRemovalFlag ? 0 : 1);
578     }
579     
580     /**
581      *
582      * @param toRecompute
583      * @param whereToStop
584      * @since 3.1
585      */
586     private void forceRecomputeTreeSize(int toRecompute, int whereToStop) {
587         while (toRecompute != -1 && toRecompute != whereToStop) {
588             recomputeTreeSize(toRecompute);
589             
590             toRecompute = parentTree[toRecompute];
591         }
592     }
593     
594     /**
595      * Destroy the node at the given index in the tree
596      * @param nodeToDestroy
597      * @since 3.1
598      */
599     private void destroyNode(int nodeToDestroy) {
600         // If we're maintaining a map of values onto tree indices, remove this entry from
601 // the map
602 if (objectIndices != null) {
603             Object oldContents = contents[nodeToDestroy];
604             if (oldContents != lazyRemovalFlag) {
605                 objectIndices.remove(oldContents);
606             }
607         }
608         
609         contents[nodeToDestroy] = null;
610         leftSubTree[nodeToDestroy] = -1;
611         rightSubTree[nodeToDestroy] = -1;
612         
613         if (firstUnusedNode == -1) {
614             treeSize[nodeToDestroy] = 1;
615         } else {
616             treeSize[nodeToDestroy] = treeSize[firstUnusedNode] + 1;
617             parentTree[firstUnusedNode] = nodeToDestroy;
618         }
619         
620         nextUnsorted[nodeToDestroy] = firstUnusedNode;
621         
622         firstUnusedNode = nodeToDestroy;
623     }
624     
625     /**
626      * Frees up memory by clearing the list of nodes that have been freed up through removals.
627      *
628      * @since 3.1
629      */
630     private final void pack() {
631         
632         // If there are no unused nodes, then there is nothing to do
633 if (firstUnusedNode == -1) {
634             return;
635         }
636         
637         int reusableNodes = getSubtreeSize(firstUnusedNode);
638         int nonPackableNodes = lastNode - reusableNodes;
639         
640         // Only pack the array if we're utilizing less than 1/4 of the array (note:
641 // this check is important, or it will change the time bounds for removals)
642 if (contents.length < MIN_CAPACITY || nonPackableNodes > contents.length / 4) {
643             return;
644         }
645         
646         // Rather than update the entire map, just null it out. If it is needed,
647 // it will be recreated lazily later. This will save some memory if the
648 // map isn't needed, and it takes a similar amount of time to recreate the
649 // map as to update all the indices.
650 objectIndices = null;
651         
652         // Maps old index -> new index
653 int[] mapNewIdxOntoOld = new int[contents.length];
654         int[] mapOldIdxOntoNew = new int[contents.length];
655         
656         int nextNewIdx = 0;
657         // Compute the mapping. Determine the new index for each element
658 for (int oldIdx = 0; oldIdx < lastNode; oldIdx++) {
659             if (contents[oldIdx] != null) {
660                 mapOldIdxOntoNew[oldIdx] = nextNewIdx;
661                 mapNewIdxOntoOld[nextNewIdx] = oldIdx;
662                 nextNewIdx++;
663             } else {
664                 mapOldIdxOntoNew[oldIdx] = -1;
665             }
666         }
667         
668         // Make the actual array size double the number of nodes to allow
669 // for expansion.
670 int newNodes = nextNewIdx;
671         int newCapacity = Math.max(newNodes * 2, MIN_CAPACITY);
672         
673         // Allocate new arrays
674 Object [] newContents = new Object [newCapacity];
675         int[] newTreeSize = new int[newCapacity];
676         int[] newNextUnsorted = new int[newCapacity];
677         int[] newLeftSubTree = new int[newCapacity];
678         int[] newRightSubTree = new int[newCapacity];
679         int[] newParentTree = new int[newCapacity];
680         
681         for (int newIdx = 0; newIdx < newNodes; newIdx++) {
682             int oldIdx = mapNewIdxOntoOld[newIdx];
683             newContents[newIdx] = contents[oldIdx];
684             newTreeSize[newIdx] = treeSize[oldIdx];
685             
686             int left = leftSubTree[oldIdx];
687             if (left == -1) {
688                 newLeftSubTree[newIdx] = -1;
689             } else {
690                 newLeftSubTree[newIdx] = mapOldIdxOntoNew[left];
691             }
692             
693             int right = rightSubTree[oldIdx];
694             if (right == -1) {
695                 newRightSubTree[newIdx] = -1;
696             } else {
697                 newRightSubTree[newIdx] = mapOldIdxOntoNew[right];
698             }
699
700             int unsorted = nextUnsorted[oldIdx];
701             if (unsorted == -1) {
702                 newNextUnsorted[newIdx] = -1;
703             } else {
704                 newNextUnsorted[newIdx] = mapOldIdxOntoNew[unsorted];
705             }
706             
707             int parent = parentTree[oldIdx];
708             if (parent == -1) {
709                 newParentTree[newIdx] = -1;
710             } else {
711                 newParentTree[newIdx] = mapOldIdxOntoNew[parent];
712             }
713         }
714         
715         contents = newContents;
716         nextUnsorted = newNextUnsorted;
717         treeSize = newTreeSize;
718         leftSubTree = newLeftSubTree;
719         rightSubTree = newRightSubTree;
720         parentTree = newParentTree;
721         
722         if (root != -1) {
723             root = mapOldIdxOntoNew[root];
724         }
725         
726         // All unused nodes have been removed
727 firstUnusedNode = -1;
728         lastNode = newNodes;
729     }
730     
731     /**
732      * Adds the given object to the collection. Runs in O(1) amortized time.
733      *
734      * @param toAdd object to add
735      */
736     public final void add(Object toAdd) {
737         Assert.isNotNull(toAdd);
738         // Create the new node
739 int newIdx = createNode(toAdd);
740         
741         // Insert the new node into the root tree
742 setRootNode(addUnsorted(root, newIdx));
743         
744         testInvariants();
745     }
746     
747     /**
748      * Adds all items from the given collection to this collection
749      *
750      * @param toAdd objects to add
751      */
752     public final void addAll(Collection toAdd) {
753         Assert.isNotNull(toAdd);
754         Iterator iter = toAdd.iterator();
755         while (iter.hasNext()) {
756             add(iter.next());
757         }
758         
759         testInvariants();
760     }
761     
762     /**
763      * Adds all items from the given array to the collection
764      *
765      * @param toAdd objects to add
766      */
767     public final void addAll(Object [] toAdd) {
768         Assert.isNotNull(toAdd);
769         for (int i = 0; i < toAdd.length; i++) {
770             Object object = toAdd[i];
771             
772             add(object);
773         }
774         
775         testInvariants();
776     }
777     
778     /**
779      * Returns true iff the collection is empty
780      *
781      * @return true iff the collection contains no elements
782      */
783     public final boolean isEmpty() {
784         boolean result = (root == -1);
785         
786         testInvariants();
787         
788         return result;
789     }
790     
791     /**
792      * Removes the given object from the collection. Has no effect if
793      * the element does not exist in this collection.
794      *
795      * @param toRemove element to remove
796      */
797     public final void remove(Object toRemove) {
798         internalRemove(toRemove);
799         
800         pack();
801         
802         testInvariants();
803     }
804     
805     /**
806      * Internal implementation of remove. Removes the given element but does not
807      * pack the container after the removal.
808      *
809      * @param toRemove element to remove
810      */
811     private void internalRemove(Object toRemove) {
812         int objectIndex = getObjectIndex(toRemove);
813         
814         if (objectIndex != -1) {
815             int parent = parentTree[objectIndex];
816             lazyRemoveNode(objectIndex);
817             //Edge parentEdge = getEdgeTo(objectIndex);
818 //parentEdge.setTarget(lazyRemoveNode(objectIndex));
819 recomputeAncestorTreeSizes(parent);
820         }
821         
822         //testInvariants();
823 }
824     
825     /**
826      * Removes all elements in the given array from this collection.
827      *
828      * @param toRemove elements to remove
829      */
830     public final void removeAll(Object [] toRemove) {
831         Assert.isNotNull(toRemove);
832         
833         for (int i = 0; i < toRemove.length; i++) {
834             Object object = toRemove[i];
835             
836             internalRemove(object);
837         }
838         pack();
839     }
840     
841     /**
842      * Retains the n smallest items in the collection, removing the rest. When
843      * this method returns, the size of the collection will be n. Note that
844      * this is a no-op if n > the current size of the collection.
845      *
846      * Temporarily package visibility until the implementation of FastProgressReporter
847      * is finished.
848      *
849      * @param n number of items to retain
850      * @param mon progress monitor
851      * @throws InterruptedException if the progress monitor is cancelled in another thread
852      */
853     /* package */ final void retainFirst(int n, FastProgressReporter mon) throws InterruptedException {
854         int sz = size();
855         
856         if (n >= sz) {
857             return;
858         }
859         
860         removeRange(n, sz - n, mon);
861         
862         testInvariants();
863     }
864     
865     /**
866      * Retains the n smallest items in the collection, removing the rest. When
867      * this method returns, the size of the collection will be n. Note that
868      * this is a no-op if n > the current size of the collection.
869      *
870      * @param n number of items to retain
871      */
872     public final void retainFirst(int n) {
873         try {
874             retainFirst(n, new FastProgressReporter());
875         } catch (InterruptedException e) {
876         }
877         
878         testInvariants();
879     }
880     
881     /**
882      * Removes all elements in the given range from this collection.
883      * For example, removeRange(10, 3) would remove the 11th through 13th
884      * smallest items from the collection.
885      *
886      * @param first 0-based index of the smallest item to remove
887      * @param length number of items to remove
888      */
889     public final void removeRange(int first, int length) {
890         try {
891             removeRange(first, length, new FastProgressReporter());
892         } catch (InterruptedException e) {
893         }
894         
895         testInvariants();
896     }
897     
898     /**
899      * Removes all elements in the given range from this collection.
900      * For example, removeRange(10, 3) would remove the 11th through 13th
901      * smallest items from the collection.
902      *
903      * Temporarily package visiblity until the implementation of FastProgressReporter is
904      * finished.
905      *
906      * @param first 0-based index of the smallest item to remove
907      * @param length number of items to remove
908      * @param mon progress monitor
909      * @throws InterruptedException if the progress monitor is cancelled in another thread
910      */
911     /* package */ final void removeRange(int first, int length, FastProgressReporter mon) throws InterruptedException {
912         removeRange(root, first, length, mon);
913         
914         pack();
915         
916         testInvariants();
917     }
918     
919     private final void removeRange(int node, int rangeStart, int rangeLength, FastProgressReporter mon) throws InterruptedException {
920         if (rangeLength == 0) {
921             return;
922         }
923         
924         int size = getSubtreeSize(node);
925         
926         if (size <= rangeStart) {
927             return;
928         }
929         
930         // If we can chop off this entire subtree without any sorting, do so.
931 if (rangeStart == 0 && rangeLength >= size) {
932             removeSubTree(node);
933             return;
934         }
935         try {
936             // Partition any unsorted nodes
937 node = partition(node, mon);
938             
939             int left = leftSubTree[node];
940             int leftSize = getSubtreeSize(left);
941             
942             int toRemoveFromLeft = Math.min(leftSize - rangeStart, rangeLength);
943             
944             // If we're removing anything from the left node
945 if (toRemoveFromLeft >= 0) {
946                 removeRange(leftSubTree[node], rangeStart, toRemoveFromLeft, mon);
947                 
948                 // Check if we're removing from both sides
949 int toRemoveFromRight = rangeStart + rangeLength - leftSize - 1;
950                 
951                 if (toRemoveFromRight >= 0) {
952                     // Remove from right subtree
953 removeRange(rightSubTree[node], 0, toRemoveFromRight, mon);
954                     
955                     // ... removing from both sides means we need to remove the node itself too
956 removeNode(node);
957                     return;
958                 }
959             } else {
960                 // If removing from the right side only
961 removeRange(rightSubTree[node], rangeStart - leftSize - 1, rangeLength, mon);
962             }
963         } finally {
964             recomputeTreeSize(node);
965         }
966     }
967     
968     /**
969      * Prunes the given subtree (and all child nodes, sorted or unsorted).
970      *
971      * @param subTree
972      * @since 3.1
973      */
974     private final void removeSubTree(int subTree) {
975         if (subTree == -1) {
976             return;
977         }
978         
979         // Destroy all unsorted nodes
980 for (int next = nextUnsorted[subTree]; next != -1;) {
981             int current = next;
982             next = nextUnsorted[next];
983             
984             // Destroy this unsorted node
985 destroyNode(current);
986         }
987         
988         // Destroy left subtree
989 removeSubTree(leftSubTree[subTree]);
990         
991         // Destroy right subtree
992 removeSubTree(rightSubTree[subTree]);
993         
994         replaceNode(subTree, -1);
995         // Destroy pivot node
996 destroyNode(subTree);
997     }
998     
999     /**
1000     * Schedules the node for removal. If the node can be removed in constant time,
1001     * it is removed immediately.
1002     *
1003     * @param subTree
1004     * @return the replacement node
1005     * @since 3.1
1006     */
1007    private final int lazyRemoveNode(int subTree) {
1008        int left = leftSubTree[subTree];
1009        int right = rightSubTree[subTree];
1010
1011        // If this is a leaf node, remove it immediately
1012 if (left == -1 && right == -1) {
1013            int result = nextUnsorted[subTree];
1014            replaceNode(subTree, result);
1015            destroyNode(subTree);
1016            return result;
1017        }
1018        
1019        // Otherwise, flag it for future removal
1020 Object value = contents[subTree];
1021        contents[subTree] = lazyRemovalFlag;
1022        treeSize[subTree]--;
1023        if (objectIndices != null) {
1024            objectIndices.remove(value);
1025        }
1026        
1027        return subTree;
1028    }
1029    
1030    /**
1031     * Removes the given subtree, replacing it with one of its children.
1032     * Returns the new root of the subtree
1033     *
1034     * @param subTree
1035     * @return the index of the new root
1036     * @since 3.1
1037     */
1038    private final int removeNode(int subTree) {
1039        int left = leftSubTree[subTree];
1040        int right = rightSubTree[subTree];
1041        
1042        if (left == -1 || right == -1) {
1043            int result = -1;
1044            
1045            if (left == -1 && right == -1) {
1046                // If this is a leaf node, replace it with its first unsorted child
1047 result = nextUnsorted[subTree];
1048            } else {
1049                // Either the left or right child is missing -- replace with the remaining child
1050 if (left == -1) {
1051                    result = right;
1052                } else {
1053                    result = left;
1054                }
1055
1056                try {
1057                    result = partition(result, new FastProgressReporter());
1058                } catch (InterruptedException e) {
1059                    
1060                }
1061                if (result == -1) {
1062                    result = nextUnsorted[subTree];
1063                } else {
1064                    int unsorted = nextUnsorted[subTree];
1065                    nextUnsorted[result] = unsorted;
1066                    int additionalNodes = 0;
1067                    if (unsorted != -1) {
1068                        parentTree[unsorted] = result;
1069                        additionalNodes = treeSize[unsorted];
1070                    }
1071                    treeSize[result] += additionalNodes;
1072                }
1073            }
1074            
1075            replaceNode(subTree, result);
1076            destroyNode(subTree);
1077            return result;
1078        }
1079                
1080        // Find the edges that lead to the next-smallest and
1081 // next-largest nodes
1082 Edge nextSmallest = new Edge(subTree, DIR_LEFT);
1083        while (!nextSmallest.isNull()) {
1084            nextSmallest.advance(DIR_RIGHT);
1085        }
1086        
1087        Edge nextLargest = new Edge(subTree, DIR_RIGHT);
1088        while (!nextLargest.isNull()) {
1089            nextLargest.advance(DIR_LEFT);
1090        }
1091        
1092        // Index of the replacement node
1093 int replacementNode = -1;
1094        
1095        // Count of number of nodes moved to the right
1096
1097        int leftSize = getSubtreeSize(left);
1098        int rightSize = getSubtreeSize(right);
1099        
1100        // Swap with a child from the larger subtree
1101 if (leftSize > rightSize) {
1102            replacementNode = nextSmallest.getStart();
1103
1104            // Move any unsorted nodes that are larger than the replacement node into
1105 // the left subtree of the next-largest node
1106 Edge unsorted = new Edge(replacementNode, DIR_UNSORTED);
1107            while (!unsorted.isNull()) {
1108                int target = unsorted.getTarget();
1109                
1110                if (!isLess(target, replacementNode)) {
1111                    unsorted.setTarget(nextUnsorted[target]);
1112                    nextLargest.setTarget(addUnsorted(nextLargest.getTarget(), target));
1113                } else {
1114                    unsorted.advance(DIR_UNSORTED);
1115                }
1116            }
1117            
1118            forceRecomputeTreeSize(unsorted.getStart(), replacementNode);
1119            forceRecomputeTreeSize(nextLargest.getStart(), subTree);
1120        } else {
1121            replacementNode = nextLargest.getStart();
1122
1123            // Move any unsorted nodes that are smaller than the replacement node into
1124 // the right subtree of the next-smallest node
1125 Edge unsorted = new Edge(replacementNode, DIR_UNSORTED);
1126            while (!unsorted.isNull()) {
1127                int target = unsorted.getTarget();
1128                
1129                if (isLess(target, replacementNode)) {
1130                    unsorted.setTarget(nextUnsorted[target]);
1131                    nextSmallest.setTarget(addUnsorted(nextSmallest.getTarget(), target));
1132                } else {
1133                    unsorted.advance(DIR_UNSORTED);
1134                }
1135            }
1136            
1137            forceRecomputeTreeSize(unsorted.getStart(), replacementNode);
1138            forceRecomputeTreeSize(nextSmallest.getStart(), subTree);
1139        }
1140        
1141        // Now all the affected treeSize[...] elements should be updated to reflect the
1142 // unsorted nodes that moved. Swap nodes.
1143 Object replacementContent = contents[replacementNode];
1144        contents[replacementNode] = contents[subTree];
1145        contents[subTree] = replacementContent;
1146        
1147        if (objectIndices != null) {
1148            objectIndices.put(replacementContent, subTree);
1149            // Note: currently we don't bother updating the index of the replacement
1150 // node since we're going to remove it immediately afterwards and there's
1151 // no good reason to search for the index in a method that was given the
1152 // index as a parameter...
1153
1154            // objectIndices.put(contents[replacementNode], replacementNode)
1155 }
1156        
1157        int replacementParent = parentTree[replacementNode];
1158        
1159        replaceNode(replacementNode, removeNode(replacementNode));
1160        //Edge parentEdge = getEdgeTo(replacementNode);
1161 //parentEdge.setTarget(removeNode(replacementNode));
1162
1163        forceRecomputeTreeSize(replacementParent, subTree);
1164        recomputeTreeSize(subTree);
1165        
1166        //testInvariants();
1167
1168        return subTree;
1169    }
1170   
1171    /**
1172     * Removes all elements from the collection
1173     */
1174    public final void clear() {
1175        lastNode = 0;
1176        setArraySize(MIN_CAPACITY);
1177        root = -1;
1178        firstUnusedNode = -1;
1179        objectIndices = null;
1180        
1181        testInvariants();
1182    }
1183    
1184    /**
1185     * Returns the comparator that is determining the sort order for this collection
1186     *
1187     * @return comparator for this collection
1188     */
1189    public Comparator getComparator() {
1190        return comparator;
1191    }
1192    
1193    /**
1194     * Fills in an array of size n with the n smallest elements from the collection.
1195     * Can compute the result in sorted or unsorted order.
1196     *
1197     * Currently package visible until the implementation of FastProgressReporter is finished.
1198     *
1199     * @param result array to be filled
1200     * @param sorted if true, the result array will be sorted. If false, the result array
1201     * may be unsorted. This does not affect which elements appear in the result, only their
1202     * order.
1203     * @param mon monitor used to report progress and check for cancellation
1204     * @return the number of items inserted into the result array. This will be equal to the minimum
1205     * of result.length and container.size()
1206     * @throws InterruptedException if the progress monitor is cancelled
1207     */
1208    /* package */ final int getFirst(Object [] result, boolean sorted, FastProgressReporter mon) throws InterruptedException {
1209        int returnValue = getRange(result, 0, sorted, mon);
1210        
1211        testInvariants();
1212        
1213        return returnValue;
1214    }
1215    
1216    /**
1217     * Fills in an array of size n with the n smallest elements from the collection.
1218     * Can compute the result in sorted or unsorted order.
1219     *
1220     * @param result array to be filled
1221     * @param sorted if true, the result array will be sorted. If false, the result array
1222     * may be unsorted. This does not affect which elements appear in the result. It only
1223     * affects their order. Computing an unsorted result is asymptotically faster.
1224     * @return the number of items inserted into the result array. This will be equal to the minimum
1225     * of result.length and container.size()
1226     */
1227    public final int getFirst(Object [] result, boolean sorted) {
1228        int returnValue = 0;
1229        
1230        try {
1231            returnValue = getFirst(result, sorted, new FastProgressReporter());
1232        } catch (InterruptedException e) {
1233        }
1234        
1235        testInvariants();
1236        
1237        return returnValue;
1238    }
1239    
1240    /**
1241     * Given a position defined by k and an array of size n, this fills in the array with
1242     * the kth smallest element through to the (k+n)th smallest element. For example,
1243     * getRange(myArray, 10, false) would fill in myArray starting with the 10th smallest item
1244     * in the collection. The result can be computed in sorted or unsorted order. Computing the
1245     * result in unsorted order is more efficient.
1246     * <p>
1247     * Temporarily set to package visibility until the implementation of FastProgressReporter
1248     * is finished.
1249     * </p>
1250     *
1251     * @param result array to be filled in
1252     * @param rangeStart index of the smallest element to appear in the result
1253     * @param sorted true iff the result array should be sorted
1254     * @param mon progress monitor used to cancel the operation
1255     * @throws InterruptedException if the progress monitor was cancelled in another thread
1256     */
1257    /* package */ final int getRange(Object [] result, int rangeStart, boolean sorted, FastProgressReporter mon) throws InterruptedException {
1258        return getRange(result, 0, rangeStart, root, sorted, mon);
1259    }
1260    
1261    /**
1262     * Computes the n through n+k items in this collection.
1263     * Computing the result in unsorted order is more efficient. Sorting the result will
1264     * not change which elements actually show up in the result. That is, even if the result is
1265     * unsorted, it will still contain the same elements as would have been at that range in
1266     * a fully sorted collection.
1267     *
1268     * @param result array containing the result
1269     * @param rangeStart index of the first element to be inserted into the result array
1270     * @param sorted true iff the result will be computed in sorted order
1271     * @return the number of items actually inserted into the result array (will be the minimum
1272     * of result.length and this.size())
1273     */
1274    public final int getRange(Object [] result, int rangeStart, boolean sorted) {
1275        int returnValue = 0;
1276        
1277        try {
1278            returnValue = getRange(result, rangeStart, sorted, new FastProgressReporter());
1279        } catch (InterruptedException e) {
1280        }
1281        
1282        testInvariants();
1283        
1284        return returnValue;
1285    }
1286    
1287    /**
1288     * Returns the item at the given index. Indexes are based on sorted order.
1289     *
1290     * @param index index to test
1291     * @return the item at the given index
1292     */
1293    public final Object getItem(int index) {
1294        Object [] result = new Object [1];
1295        try {
1296            getRange(result, index, false, new FastProgressReporter());
1297        } catch (InterruptedException e) {
1298            // shouldn't happen
1299 }
1300        Object returnValue = result[0];
1301        
1302        testInvariants();
1303        
1304        return returnValue;
1305    }
1306    
1307    /**
1308     * Returns the contents of this collection as a sorted or unsorted
1309     * array. Computing an unsorted array is more efficient.
1310     *
1311     * @param sorted if true, the result will be in sorted order. If false,
1312     * the result may be in unsorted order.
1313     * @return the contents of this collection as an array.
1314     */
1315    public final Object [] getItems(boolean sorted) {
1316        Object [] result = new Object [size()];
1317        
1318        getRange(result, 0, sorted);
1319        
1320        return result;
1321    }
1322    
1323    private final int getRange(Object [] result, int resultIdx, int rangeStart, int node, boolean sorted, FastProgressReporter mon) throws InterruptedException {
1324        if (node == -1) {
1325            return 0;
1326        }
1327
1328        int availableSpace = result.length - resultIdx;
1329        
1330        // If we're asking for all children of the current node, simply call getChildren
1331 if (rangeStart == 0) {
1332            if (treeSize[node] <= availableSpace) {
1333                return getChildren(result, resultIdx, node, sorted, mon);
1334            }
1335        }
1336        
1337        node = partition(node, mon);
1338        if (node == -1) {
1339            return 0;
1340        }
1341        
1342        int inserted = 0;
1343        
1344        int numberLessThanNode = getSubtreeSize(leftSubTree[node]);
1345                
1346        if (rangeStart < numberLessThanNode) {
1347            if (inserted < availableSpace) {
1348                inserted += getRange(result, resultIdx, rangeStart, leftSubTree[node], sorted, mon);
1349            }
1350        }
1351        
1352        if (rangeStart <= numberLessThanNode) {
1353            if (inserted < availableSpace) {
1354                result[resultIdx + inserted] = contents[node];
1355                inserted++;
1356            }
1357        }
1358        
1359        if (inserted < availableSpace) {
1360            inserted += getRange(result, resultIdx + inserted,
1361                Math.max(rangeStart - numberLessThanNode - 1, 0), rightSubTree[node], sorted, mon);
1362        }
1363        
1364        return inserted;
1365    }
1366    
1367    /**
1368     * Fills in the available space in the given array with all children of the given node.
1369     *
1370     * @param result
1371     * @param resultIdx index in the result array where we will begin filling in children
1372     * @param node
1373     * @return the number of children added to the array
1374     * @since 3.1
1375     */
1376    private final int getChildren(Object [] result, int resultIdx, int node, boolean sorted, FastProgressReporter mon) throws InterruptedException {
1377        if (node == -1) {
1378            return 0;
1379        }
1380        
1381        int tempIdx = resultIdx;
1382        
1383        if (sorted) {
1384            node = partition(node, mon);
1385            if (node == -1) {
1386                return 0;
1387            }
1388        }
1389        
1390        // Add child nodes smaller than this one
1391 if (tempIdx < result.length) {
1392            tempIdx += getChildren(result, tempIdx, leftSubTree[node], sorted, mon);
1393        }
1394        
1395        // Add the pivot
1396 if (tempIdx < result.length) {
1397            Object value = contents[node];
1398            if (value != lazyRemovalFlag) {
1399                result[tempIdx++] = value;
1400            }
1401        }
1402        
1403        // Add child nodes larger than this one
1404 if (tempIdx < result.length) {
1405            tempIdx += getChildren(result, tempIdx, rightSubTree[node], sorted, mon);
1406        }
1407        
1408        // Add unsorted children (should be empty if the sorted flag was true)
1409 for (int unsortedNode = nextUnsorted[node]; unsortedNode != -1 && tempIdx < result.length;
1410            unsortedNode = nextUnsorted[unsortedNode]) {
1411            
1412            result[tempIdx++] = contents[unsortedNode];
1413        }
1414        
1415        return tempIdx - resultIdx;
1416    }
1417
1418    /**
1419     * Returns true iff this collection contains the given item
1420     *
1421     * @param item item to test
1422     * @return true iff this collection contains the given item
1423     */
1424    public boolean contains(Object item) {
1425        Assert.isNotNull(item);
1426        boolean returnValue = (getObjectIndex(item) != -1);
1427        
1428        testInvariants();
1429        
1430        return returnValue;
1431    }
1432}
1433

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags