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