Mercurial > projects > dwt-addons
annotate dwtx/jface/viewers/deferred/LazySortedCollection.d @ 104:04b47443bb01
Reworked the collection uses to make use of a wrapper collection that is compatible to the Java Collections.
These new wrappers now use the tango.util.containers instead of the tango.util.collections.
| author | Frank Benoit <benoit@tionex.de> |
|---|---|
| date | Thu, 07 Aug 2008 15:01:33 +0200 |
| parents | b6c35faf97c8 |
| children |
| rev | line source |
|---|---|
| 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 | |
| 21 import dwtx.core.runtime.Assert; | |
| 22 | |
| 23 import dwt.dwthelper.utils; | |
|
104
04b47443bb01
Reworked the collection uses to make use of a wrapper collection that is compatible to the Java Collections.
Frank Benoit <benoit@tionex.de>
parents:
10
diff
changeset
|
24 import dwtx.dwtxhelper.Collection; |
| 10 | 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 */ | |
|
104
04b47443bb01
Reworked the collection uses to make use of a wrapper collection that is compatible to the Java Collections.
Frank Benoit <benoit@tionex.de>
parents:
10
diff
changeset
|
770 public final void addAll( Collection toAdd) { |
| 10 | 771 Assert.isNotNull(cast(Object)toAdd); |
|
104
04b47443bb01
Reworked the collection uses to make use of a wrapper collection that is compatible to the Java Collections.
Frank Benoit <benoit@tionex.de>
parents:
10
diff
changeset
|
772 Iterator iter = toAdd.iterator(); |
|
04b47443bb01
Reworked the collection uses to make use of a wrapper collection that is compatible to the Java Collections.
Frank Benoit <benoit@tionex.de>
parents:
10
diff
changeset
|
773 while (iter.hasNext()) { |
|
04b47443bb01
Reworked the collection uses to make use of a wrapper collection that is compatible to the Java Collections.
Frank Benoit <benoit@tionex.de>
parents:
10
diff
changeset
|
774 add(iter.next()); |
| 10 | 775 } |
| 776 | |
| 777 testInvariants(); | |
| 778 } | |
| 779 | |
| 780 /** | |
| 781 * Adds all items from the given array to the collection | |
| 782 * | |
| 783 * @param toAdd objects to add | |
| 784 */ | |
| 785 public final void addAll(Object[] toAdd) { | |
| 786 // Assert.isNotNull(toAdd); | |
| 787 for (int i = 0; i < toAdd.length; i++) { | |
| 788 Object object = toAdd[i]; | |
| 789 | |
| 790 add(object); | |
| 791 } | |
| 792 | |
| 793 testInvariants(); | |
| 794 } | |
| 795 | |
| 796 /** | |
| 797 * Returns true iff the collection is empty | |
| 798 * | |
| 799 * @return true iff the collection contains no elements | |
| 800 */ | |
| 801 public final bool isEmpty() { | |
| 802 bool result = (root is -1); | |
| 803 | |
| 804 testInvariants(); | |
| 805 | |
| 806 return result; | |
| 807 } | |
| 808 | |
| 809 /** | |
| 810 * Removes the given object from the collection. Has no effect if | |
| 811 * the element does not exist in this collection. | |
| 812 * | |
| 813 * @param toRemove element to remove | |
| 814 */ | |
| 815 public final void remove(Object toRemove) { | |
| 816 internalRemove(toRemove); | |
| 817 | |
| 818 pack(); | |
| 819 | |
| 820 testInvariants(); | |
| 821 } | |
| 822 | |
| 823 /** | |
| 824 * Internal implementation of remove. Removes the given element but does not | |
| 825 * pack the container after the removal. | |
| 826 * | |
| 827 * @param toRemove element to remove | |
| 828 */ | |
| 829 private void internalRemove(Object toRemove) { | |
| 830 int objectIndex = getObjectIndex(toRemove); | |
| 831 | |
| 832 if (objectIndex !is -1) { | |
| 833 int parent = parentTree[objectIndex]; | |
| 834 lazyRemoveNode(objectIndex); | |
| 835 //Edge parentEdge = getEdgeTo(objectIndex); | |
| 836 //parentEdge.setTarget(lazyRemoveNode(objectIndex)); | |
| 837 recomputeAncestorTreeSizes(parent); | |
| 838 } | |
| 839 | |
| 840 //testInvariants(); | |
| 841 } | |
| 842 | |
| 843 /** | |
| 844 * Removes all elements in the given array from this collection. | |
| 845 * | |
| 846 * @param toRemove elements to remove | |
| 847 */ | |
| 848 public final void removeAll(Object[] toRemove) { | |
| 849 // Assert.isNotNull(toRemove); | |
| 850 | |
| 851 for (int i = 0; i < toRemove.length; i++) { | |
| 852 Object object = toRemove[i]; | |
| 853 | |
| 854 internalRemove(object); | |
| 855 } | |
| 856 pack(); | |
| 857 } | |
| 858 | |
| 859 /** | |
| 860 * Retains the n smallest items in the collection, removing the rest. When | |
| 861 * this method returns, the size of the collection will be n. Note that | |
| 862 * this is a no-op if n > the current size of the collection. | |
| 863 * | |
| 864 * Temporarily package visibility until the implementation of FastProgressReporter | |
| 865 * is finished. | |
| 866 * | |
| 867 * @param n number of items to retain | |
| 868 * @param mon progress monitor | |
| 869 * @throws InterruptedException if the progress monitor is cancelled in another thread | |
| 870 */ | |
| 871 /* package */ final void retainFirst(int n, FastProgressReporter mon) { | |
| 872 int sz = size(); | |
| 873 | |
| 874 if (n >= sz) { | |
| 875 return; | |
| 876 } | |
| 877 | |
| 878 removeRange(n, sz - n, mon); | |
| 879 | |
| 880 testInvariants(); | |
| 881 } | |
| 882 | |
| 883 /** | |
| 884 * Retains the n smallest items in the collection, removing the rest. When | |
| 885 * this method returns, the size of the collection will be n. Note that | |
| 886 * this is a no-op if n > the current size of the collection. | |
| 887 * | |
| 888 * @param n number of items to retain | |
| 889 */ | |
| 890 public final void retainFirst(int n) { | |
| 891 try { | |
| 892 retainFirst(n, new FastProgressReporter()); | |
| 893 } catch (InterruptedException e) { | |
| 894 } | |
| 895 | |
| 896 testInvariants(); | |
| 897 } | |
| 898 | |
| 899 /** | |
| 900 * Removes all elements in the given range from this collection. | |
| 901 * For example, removeRange(10, 3) would remove the 11th through 13th | |
| 902 * smallest items from the collection. | |
| 903 * | |
| 904 * @param first 0-based index of the smallest item to remove | |
| 905 * @param length number of items to remove | |
| 906 */ | |
| 907 public final void removeRange(int first, int length) { | |
| 908 try { | |
| 909 removeRange(first, length, new FastProgressReporter()); | |
| 910 } catch (InterruptedException e) { | |
| 911 } | |
| 912 | |
| 913 testInvariants(); | |
| 914 } | |
| 915 | |
| 916 /** | |
| 917 * Removes all elements in the given range from this collection. | |
| 918 * For example, removeRange(10, 3) would remove the 11th through 13th | |
| 919 * smallest items from the collection. | |
| 920 * | |
| 921 * Temporarily package visiblity until the implementation of FastProgressReporter is | |
| 922 * finished. | |
| 923 * | |
| 924 * @param first 0-based index of the smallest item to remove | |
| 925 * @param length number of items to remove | |
| 926 * @param mon progress monitor | |
| 927 * @throws InterruptedException if the progress monitor is cancelled in another thread | |
| 928 */ | |
| 929 /* package */ final void removeRange(int first, int length, FastProgressReporter mon) { | |
| 930 removeRange(root, first, length, mon); | |
| 931 | |
| 932 pack(); | |
| 933 | |
| 934 testInvariants(); | |
| 935 } | |
| 936 | |
| 937 private final void removeRange(int node, int rangeStart, int rangeLength, FastProgressReporter mon) { | |
| 938 if (rangeLength is 0) { | |
| 939 return; | |
| 940 } | |
| 941 | |
| 942 int size = getSubtreeSize(node); | |
| 943 | |
| 944 if (size <= rangeStart) { | |
| 945 return; | |
| 946 } | |
| 947 | |
| 948 // If we can chop off this entire subtree without any sorting, do so. | |
| 949 if (rangeStart is 0 && rangeLength >= size) { | |
| 950 removeSubTree(node); | |
| 951 return; | |
| 952 } | |
| 953 try { | |
| 954 // Partition any unsorted nodes | |
| 955 node = partition(node, mon); | |
| 956 | |
| 957 int left = leftSubTree[node]; | |
| 958 int leftSize = getSubtreeSize(left); | |
| 959 | |
| 960 int toRemoveFromLeft = Math.min(leftSize - rangeStart, rangeLength); | |
| 961 | |
| 962 // If we're removing anything from the left node | |
| 963 if (toRemoveFromLeft >= 0) { | |
| 964 removeRange(leftSubTree[node], rangeStart, toRemoveFromLeft, mon); | |
| 965 | |
| 966 // Check if we're removing from both sides | |
| 967 int toRemoveFromRight = rangeStart + rangeLength - leftSize - 1; | |
| 968 | |
| 969 if (toRemoveFromRight >= 0) { | |
| 970 // Remove from right subtree | |
| 971 removeRange(rightSubTree[node], 0, toRemoveFromRight, mon); | |
| 972 | |
| 973 // ... removing from both sides means we need to remove the node itself too | |
| 974 removeNode(node); | |
| 975 return; | |
| 976 } | |
| 977 } else { | |
| 978 // If removing from the right side only | |
| 979 removeRange(rightSubTree[node], rangeStart - leftSize - 1, rangeLength, mon); | |
| 980 } | |
| 981 } finally { | |
| 982 recomputeTreeSize(node); | |
| 983 } | |
| 984 } | |
| 985 | |
| 986 /** | |
| 987 * Prunes the given subtree (and all child nodes, sorted or unsorted). | |
| 988 * | |
| 989 * @param subTree | |
| 990 * @since 3.1 | |
| 991 */ | |
| 992 private final void removeSubTree(int subTree) { | |
| 993 if (subTree is -1) { | |
| 994 return; | |
| 995 } | |
| 996 | |
| 997 // Destroy all unsorted nodes | |
| 998 for (int next = nextUnsorted[subTree]; next !is -1;) { | |
| 999 int current = next; | |
| 1000 next = nextUnsorted[next]; | |
| 1001 | |
| 1002 // Destroy this unsorted node | |
| 1003 destroyNode(current); | |
| 1004 } | |
| 1005 | |
| 1006 // Destroy left subtree | |
| 1007 removeSubTree(leftSubTree[subTree]); | |
| 1008 | |
| 1009 // Destroy right subtree | |
| 1010 removeSubTree(rightSubTree[subTree]); | |
| 1011 | |
| 1012 replaceNode(subTree, -1); | |
| 1013 // Destroy pivot node | |
| 1014 destroyNode(subTree); | |
| 1015 } | |
| 1016 | |
| 1017 /** | |
| 1018 * Schedules the node for removal. If the node can be removed in constant time, | |
| 1019 * it is removed immediately. | |
| 1020 * | |
| 1021 * @param subTree | |
| 1022 * @return the replacement node | |
| 1023 * @since 3.1 | |
| 1024 */ | |
| 1025 private final int lazyRemoveNode(int subTree) { | |
| 1026 int left = leftSubTree[subTree]; | |
| 1027 int right = rightSubTree[subTree]; | |
| 1028 | |
| 1029 // If this is a leaf node, remove it immediately | |
| 1030 if (left is -1 && right is -1) { | |
| 1031 int result = nextUnsorted[subTree]; | |
| 1032 replaceNode(subTree, result); | |
| 1033 destroyNode(subTree); | |
| 1034 return result; | |
| 1035 } | |
| 1036 | |
| 1037 // Otherwise, flag it for future removal | |
| 1038 Object value = contents[subTree]; | |
| 1039 contents[subTree] = lazyRemovalFlag; | |
| 1040 treeSize[subTree]--; | |
| 1041 if (objectIndices !is null) { | |
| 1042 objectIndices.remove(value); | |
| 1043 } | |
| 1044 | |
| 1045 return subTree; | |
| 1046 } | |
| 1047 | |
| 1048 /** | |
| 1049 * Removes the given subtree, replacing it with one of its children. | |
| 1050 * Returns the new root of the subtree | |
| 1051 * | |
| 1052 * @param subTree | |
| 1053 * @return the index of the new root | |
| 1054 * @since 3.1 | |
| 1055 */ | |
| 1056 private final int removeNode(int subTree) { | |
| 1057 int left = leftSubTree[subTree]; | |
| 1058 int right = rightSubTree[subTree]; | |
| 1059 | |
| 1060 if (left is -1 || right is -1) { | |
| 1061 int result = -1; | |
| 1062 | |
| 1063 if (left is -1 && right is -1) { | |
| 1064 // If this is a leaf node, replace it with its first unsorted child | |
| 1065 result = nextUnsorted[subTree]; | |
| 1066 } else { | |
| 1067 // Either the left or right child is missing -- replace with the remaining child | |
| 1068 if (left is -1) { | |
| 1069 result = right; | |
| 1070 } else { | |
| 1071 result = left; | |
| 1072 } | |
| 1073 | |
| 1074 try { | |
| 1075 result = partition(result, new FastProgressReporter()); | |
| 1076 } catch (InterruptedException e) { | |
| 1077 | |
| 1078 } | |
| 1079 if (result is -1) { | |
| 1080 result = nextUnsorted[subTree]; | |
| 1081 } else { | |
| 1082 int unsorted = nextUnsorted[subTree]; | |
| 1083 nextUnsorted[result] = unsorted; | |
| 1084 int additionalNodes = 0; | |
| 1085 if (unsorted !is -1) { | |
| 1086 parentTree[unsorted] = result; | |
| 1087 additionalNodes = treeSize[unsorted]; | |
| 1088 } | |
| 1089 treeSize[result] += additionalNodes; | |
| 1090 } | |
| 1091 } | |
| 1092 | |
| 1093 replaceNode(subTree, result); | |
| 1094 destroyNode(subTree); | |
| 1095 return result; | |
| 1096 } | |
| 1097 | |
| 1098 // Find the edges that lead to the next-smallest and | |
| 1099 // next-largest nodes | |
| 1100 Edge nextSmallest = new Edge(subTree, DIR_LEFT); | |
| 1101 while (!nextSmallest.isNull()) { | |
| 1102 nextSmallest.advance(DIR_RIGHT); | |
| 1103 } | |
| 1104 | |
| 1105 Edge nextLargest = new Edge(subTree, DIR_RIGHT); | |
| 1106 while (!nextLargest.isNull()) { | |
| 1107 nextLargest.advance(DIR_LEFT); | |
| 1108 } | |
| 1109 | |
| 1110 // Index of the replacement node | |
| 1111 int replacementNode = -1; | |
| 1112 | |
| 1113 // Count of number of nodes moved to the right | |
| 1114 | |
| 1115 int leftSize = getSubtreeSize(left); | |
| 1116 int rightSize = getSubtreeSize(right); | |
| 1117 | |
| 1118 // Swap with a child from the larger subtree | |
| 1119 if (leftSize > rightSize) { | |
| 1120 replacementNode = nextSmallest.getStart(); | |
| 1121 | |
| 1122 // Move any unsorted nodes that are larger than the replacement node into | |
| 1123 // the left subtree of the next-largest node | |
| 1124 Edge unsorted = new Edge(replacementNode, DIR_UNSORTED); | |
| 1125 while (!unsorted.isNull()) { | |
| 1126 int target = unsorted.getTarget(); | |
| 1127 | |
| 1128 if (!isLess(target, replacementNode)) { | |
| 1129 unsorted.setTarget(nextUnsorted[target]); | |
| 1130 nextLargest.setTarget(addUnsorted(nextLargest.getTarget(), target)); | |
| 1131 } else { | |
| 1132 unsorted.advance(DIR_UNSORTED); | |
| 1133 } | |
| 1134 } | |
| 1135 | |
| 1136 forceRecomputeTreeSize(unsorted.getStart(), replacementNode); | |
| 1137 forceRecomputeTreeSize(nextLargest.getStart(), subTree); | |
| 1138 } else { | |
| 1139 replacementNode = nextLargest.getStart(); | |
| 1140 | |
| 1141 // Move any unsorted nodes that are smaller than the replacement node into | |
| 1142 // the right subtree of the next-smallest node | |
| 1143 Edge unsorted = new Edge(replacementNode, DIR_UNSORTED); | |
| 1144 while (!unsorted.isNull()) { | |
| 1145 int target = unsorted.getTarget(); | |
| 1146 | |
| 1147 if (isLess(target, replacementNode)) { | |
| 1148 unsorted.setTarget(nextUnsorted[target]); | |
| 1149 nextSmallest.setTarget(addUnsorted(nextSmallest.getTarget(), target)); | |
| 1150 } else { | |
| 1151 unsorted.advance(DIR_UNSORTED); | |
| 1152 } | |
| 1153 } | |
| 1154 | |
| 1155 forceRecomputeTreeSize(unsorted.getStart(), replacementNode); | |
| 1156 forceRecomputeTreeSize(nextSmallest.getStart(), subTree); | |
| 1157 } | |
| 1158 | |
| 1159 // Now all the affected treeSize[...] elements should be updated to reflect the | |
| 1160 // unsorted nodes that moved. Swap nodes. | |
| 1161 Object replacementContent = contents[replacementNode]; | |
| 1162 contents[replacementNode] = contents[subTree]; | |
| 1163 contents[subTree] = replacementContent; | |
| 1164 | |
| 1165 if (objectIndices !is null) { | |
| 1166 objectIndices.put(replacementContent, subTree); | |
| 1167 // Note: currently we don't bother updating the index of the replacement | |
| 1168 // node since we're going to remove it immediately afterwards and there's | |
| 1169 // no good reason to search for the index in a method that was given the | |
| 1170 // index as a parameter... | |
| 1171 | |
| 1172 // objectIndices.put(contents[replacementNode], replacementNode) | |
| 1173 } | |
| 1174 | |
| 1175 int replacementParent = parentTree[replacementNode]; | |
| 1176 | |
| 1177 replaceNode(replacementNode, removeNode(replacementNode)); | |
| 1178 //Edge parentEdge = getEdgeTo(replacementNode); | |
| 1179 //parentEdge.setTarget(removeNode(replacementNode)); | |
| 1180 | |
| 1181 forceRecomputeTreeSize(replacementParent, subTree); | |
| 1182 recomputeTreeSize(subTree); | |
| 1183 | |
| 1184 //testInvariants(); | |
| 1185 | |
| 1186 return subTree; | |
| 1187 } | |
| 1188 | |
| 1189 /** | |
| 1190 * Removes all elements from the collection | |
| 1191 */ | |
| 1192 public final void clear() { | |
| 1193 lastNode = 0; | |
| 1194 setArraySize(MIN_CAPACITY); | |
| 1195 root = -1; | |
| 1196 firstUnusedNode = -1; | |
| 1197 objectIndices = null; | |
| 1198 | |
| 1199 testInvariants(); | |
| 1200 } | |
| 1201 | |
| 1202 /** | |
| 1203 * Returns the comparator that is determining the sort order for this collection | |
| 1204 * | |
| 1205 * @return comparator for this collection | |
| 1206 */ | |
| 1207 public Comparator getComparator() { | |
| 1208 return comparator; | |
| 1209 } | |
| 1210 | |
| 1211 /** | |
| 1212 * Fills in an array of size n with the n smallest elements from the collection. | |
| 1213 * Can compute the result in sorted or unsorted order. | |
| 1214 * | |
| 1215 * Currently package visible until the implementation of FastProgressReporter is finished. | |
| 1216 * | |
| 1217 * @param result array to be filled | |
| 1218 * @param sorted if true, the result array will be sorted. If false, the result array | |
| 1219 * may be unsorted. This does not affect which elements appear in the result, only their | |
| 1220 * order. | |
| 1221 * @param mon monitor used to report progress and check for cancellation | |
| 1222 * @return the number of items inserted into the result array. This will be equal to the minimum | |
| 1223 * of result.length and container.size() | |
| 1224 * @throws InterruptedException if the progress monitor is cancelled | |
| 1225 */ | |
| 1226 /* package */ final int getFirst(Object[] result, bool sorted, FastProgressReporter mon) { | |
| 1227 int returnValue = getRange(result, 0, sorted, mon); | |
| 1228 | |
| 1229 testInvariants(); | |
| 1230 | |
| 1231 return returnValue; | |
| 1232 } | |
| 1233 | |
| 1234 /** | |
| 1235 * Fills in an array of size n with the n smallest elements from the collection. | |
| 1236 * Can compute the result in sorted or unsorted order. | |
| 1237 * | |
| 1238 * @param result array to be filled | |
| 1239 * @param sorted if true, the result array will be sorted. If false, the result array | |
| 1240 * may be unsorted. This does not affect which elements appear in the result. It only | |
| 1241 * affects their order. Computing an unsorted result is asymptotically faster. | |
| 1242 * @return the number of items inserted into the result array. This will be equal to the minimum | |
| 1243 * of result.length and container.size() | |
| 1244 */ | |
| 1245 public final int getFirst(Object[] result, bool sorted) { | |
| 1246 int returnValue = 0; | |
| 1247 | |
| 1248 try { | |
| 1249 returnValue = getFirst(result, sorted, new FastProgressReporter()); | |
| 1250 } catch (InterruptedException e) { | |
| 1251 } | |
| 1252 | |
| 1253 testInvariants(); | |
| 1254 | |
| 1255 return returnValue; | |
| 1256 } | |
| 1257 | |
| 1258 /** | |
| 1259 * Given a position defined by k and an array of size n, this fills in the array with | |
| 1260 * the kth smallest element through to the (k+n)th smallest element. For example, | |
| 1261 * getRange(myArray, 10, false) would fill in myArray starting with the 10th smallest item | |
| 1262 * in the collection. The result can be computed in sorted or unsorted order. Computing the | |
| 1263 * result in unsorted order is more efficient. | |
| 1264 * <p> | |
| 1265 * Temporarily set to package visibility until the implementation of FastProgressReporter | |
| 1266 * is finished. | |
| 1267 * </p> | |
| 1268 * | |
| 1269 * @param result array to be filled in | |
| 1270 * @param rangeStart index of the smallest element to appear in the result | |
| 1271 * @param sorted true iff the result array should be sorted | |
| 1272 * @param mon progress monitor used to cancel the operation | |
| 1273 * @throws InterruptedException if the progress monitor was cancelled in another thread | |
| 1274 */ | |
| 1275 /* package */ final int getRange(Object[] result, int rangeStart, bool sorted, FastProgressReporter mon) { | |
| 1276 return getRange(result, 0, rangeStart, root, sorted, mon); | |
| 1277 } | |
| 1278 | |
| 1279 /** | |
| 1280 * Computes the n through n+k items in this collection. | |
| 1281 * Computing the result in unsorted order is more efficient. Sorting the result will | |
| 1282 * not change which elements actually show up in the result. That is, even if the result is | |
| 1283 * unsorted, it will still contain the same elements as would have been at that range in | |
| 1284 * a fully sorted collection. | |
| 1285 * | |
| 1286 * @param result array containing the result | |
| 1287 * @param rangeStart index of the first element to be inserted into the result array | |
| 1288 * @param sorted true iff the result will be computed in sorted order | |
| 1289 * @return the number of items actually inserted into the result array (will be the minimum | |
| 1290 * of result.length and this.size()) | |
| 1291 */ | |
| 1292 public final int getRange(Object[] result, int rangeStart, bool sorted) { | |
| 1293 int returnValue = 0; | |
| 1294 | |
| 1295 try { | |
| 1296 returnValue = getRange(result, rangeStart, sorted, new FastProgressReporter()); | |
| 1297 } catch (InterruptedException e) { | |
| 1298 } | |
| 1299 | |
| 1300 testInvariants(); | |
| 1301 | |
| 1302 return returnValue; | |
| 1303 } | |
| 1304 | |
| 1305 /** | |
| 1306 * Returns the item at the given index. Indexes are based on sorted order. | |
| 1307 * | |
| 1308 * @param index index to test | |
| 1309 * @return the item at the given index | |
| 1310 */ | |
| 1311 public final Object getItem(int index) { | |
| 1312 Object[] result = new Object[1]; | |
| 1313 try { | |
| 1314 getRange(result, index, false, new FastProgressReporter()); | |
| 1315 } catch (InterruptedException e) { | |
| 1316 // shouldn't happen | |
| 1317 } | |
| 1318 Object returnValue = result[0]; | |
| 1319 | |
| 1320 testInvariants(); | |
| 1321 | |
| 1322 return returnValue; | |
| 1323 } | |
| 1324 | |
| 1325 /** | |
| 1326 * Returns the contents of this collection as a sorted or unsorted | |
| 1327 * array. Computing an unsorted array is more efficient. | |
| 1328 * | |
| 1329 * @param sorted if true, the result will be in sorted order. If false, | |
| 1330 * the result may be in unsorted order. | |
| 1331 * @return the contents of this collection as an array. | |
| 1332 */ | |
| 1333 public final Object[] getItems(bool sorted) { | |
| 1334 Object[] result = new Object[size()]; | |
| 1335 | |
| 1336 getRange(result, 0, sorted); | |
| 1337 | |
| 1338 return result; | |
| 1339 } | |
| 1340 | |
| 1341 private final int getRange(Object[] result, int resultIdx, int rangeStart, int node, bool sorted, FastProgressReporter mon) { | |
| 1342 if (node is -1) { | |
| 1343 return 0; | |
| 1344 } | |
| 1345 | |
| 1346 int availableSpace = result.length - resultIdx; | |
| 1347 | |
| 1348 // If we're asking for all children of the current node, simply call getChildren | |
| 1349 if (rangeStart is 0) { | |
| 1350 if (treeSize[node] <= availableSpace) { | |
| 1351 return getChildren(result, resultIdx, node, sorted, mon); | |
| 1352 } | |
| 1353 } | |
| 1354 | |
| 1355 node = partition(node, mon); | |
| 1356 if (node is -1) { | |
| 1357 return 0; | |
| 1358 } | |
| 1359 | |
| 1360 int inserted = 0; | |
| 1361 | |
| 1362 int numberLessThanNode = getSubtreeSize(leftSubTree[node]); | |
| 1363 | |
| 1364 if (rangeStart < numberLessThanNode) { | |
| 1365 if (inserted < availableSpace) { | |
| 1366 inserted += getRange(result, resultIdx, rangeStart, leftSubTree[node], sorted, mon); | |
| 1367 } | |
| 1368 } | |
| 1369 | |
| 1370 if (rangeStart <= numberLessThanNode) { | |
| 1371 if (inserted < availableSpace) { | |
| 1372 result[resultIdx + inserted] = contents[node]; | |
| 1373 inserted++; | |
| 1374 } | |
| 1375 } | |
| 1376 | |
| 1377 if (inserted < availableSpace) { | |
| 1378 inserted += getRange(result, resultIdx + inserted, | |
| 1379 Math.max(rangeStart - numberLessThanNode - 1, 0), rightSubTree[node], sorted, mon); | |
| 1380 } | |
| 1381 | |
| 1382 return inserted; | |
| 1383 } | |
| 1384 | |
| 1385 /** | |
| 1386 * Fills in the available space in the given array with all children of the given node. | |
| 1387 * | |
| 1388 * @param result | |
| 1389 * @param resultIdx index in the result array where we will begin filling in children | |
| 1390 * @param node | |
| 1391 * @return the number of children added to the array | |
| 1392 * @since 3.1 | |
| 1393 */ | |
| 1394 private final int getChildren(Object[] result, int resultIdx, int node, bool sorted, FastProgressReporter mon) { | |
| 1395 if (node is -1) { | |
| 1396 return 0; | |
| 1397 } | |
| 1398 | |
| 1399 int tempIdx = resultIdx; | |
| 1400 | |
| 1401 if (sorted) { | |
| 1402 node = partition(node, mon); | |
| 1403 if (node is -1) { | |
| 1404 return 0; | |
| 1405 } | |
| 1406 } | |
| 1407 | |
| 1408 // Add child nodes smaller than this one | |
| 1409 if (tempIdx < result.length) { | |
| 1410 tempIdx += getChildren(result, tempIdx, leftSubTree[node], sorted, mon); | |
| 1411 } | |
| 1412 | |
| 1413 // Add the pivot | |
| 1414 if (tempIdx < result.length) { | |
| 1415 Object value = contents[node]; | |
| 1416 if (value !is lazyRemovalFlag) { | |
| 1417 result[tempIdx++] = value; | |
| 1418 } | |
| 1419 } | |
| 1420 | |
| 1421 // Add child nodes larger than this one | |
| 1422 if (tempIdx < result.length) { | |
| 1423 tempIdx += getChildren(result, tempIdx, rightSubTree[node], sorted, mon); | |
| 1424 } | |
| 1425 | |
| 1426 // Add unsorted children (should be empty if the sorted flag was true) | |
| 1427 for (int unsortedNode = nextUnsorted[node]; unsortedNode !is -1 && tempIdx < result.length; | |
| 1428 unsortedNode = nextUnsorted[unsortedNode]) { | |
| 1429 | |
| 1430 result[tempIdx++] = contents[unsortedNode]; | |
| 1431 } | |
| 1432 | |
| 1433 return tempIdx - resultIdx; | |
| 1434 } | |
| 1435 | |
| 1436 /** | |
| 1437 * Returns true iff this collection contains the given item | |
| 1438 * | |
| 1439 * @param item item to test | |
| 1440 * @return true iff this collection contains the given item | |
| 1441 */ | |
| 1442 public bool contains(Object item) { | |
| 1443 Assert.isNotNull(item); | |
| 1444 bool returnValue = (getObjectIndex(item) !is -1); | |
| 1445 | |
| 1446 testInvariants(); | |
| 1447 | |
| 1448 return returnValue; | |
| 1449 } | |
| 1450 } |