| /******************************************************************************* |
| * Copyright (c) 2004, 2005 IBM Corporation and others. |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Eclipse Public License v1.0 |
| * which accompanies this distribution, and is available at |
| * http://www.eclipse.org/legal/epl-v10.html |
| * |
| * Contributors: |
| * IBM Corporation - initial API and implementation |
| *******************************************************************************/ |
| package org.eclipse.jface.viewers.deferred; |
| |
| import java.util.Collection; |
| import java.util.Comparator; |
| import java.util.Iterator; |
| |
| import org.eclipse.jface.util.Assert; |
| |
| /** |
| * This object maintains a collection of elements, sorted by a comparator |
| * given in the constructor. The collection is lazily sorted, allowing |
| * more efficient runtimes for most methods. There are several methods on this |
| * object that allow objects to be queried by their position in the sorted |
| * collection. |
| * |
| * <p> |
| * This is a modified binary search tree. Each subtree has a value, a left and right subtree, |
| * a count of the number of children, and a set of unsorted children. |
| * Insertion happens lazily. When a new node N is inserted into a subtree T, it is initially |
| * added to the set of unsorted children for T without actually comparing it with the value for T. |
| * </p> |
| * <p> |
| * The unsorted children will remain in the unsorted set until some subsequent operation requires |
| * us to know the exact set of elements in one of the subtrees. At that time, we partition |
| * T by comparing all of its unsorted children with T's value and moving them into the left |
| * or right subtrees. |
| * </p> |
| * |
| * @since 3.1 |
| */ |
| public class LazySortedCollection { |
| private final int MIN_CAPACITY = 8; |
| private Object[] contents = new Object[MIN_CAPACITY]; |
| private int[] leftSubTree = new int[MIN_CAPACITY]; |
| private int[] rightSubTree = new int[MIN_CAPACITY]; |
| private int[] nextUnsorted = new int[MIN_CAPACITY]; |
| private int[] treeSize = new int[MIN_CAPACITY]; |
| private int[] parentTree = new int[MIN_CAPACITY]; |
| private int root = -1; |
| private int lastNode = 0; |
| private int firstUnusedNode = -1; |
| |
| private static final float loadFactor = 0.75f; |
| |
| private IntHashMap objectIndices; |
| private Comparator comparator; |
| private static int counter = 0; |
| |
| /** |
| * Disables randomization and enables additional runtime error checking. |
| * Severely degrades performance if set to true. Intended for use in test |
| * suites only. |
| */ |
| public boolean enableDebug = false; |
| |
| // This object is inserted as the value into any node scheduled for lazy removal |
| private Object lazyRemovalFlag = new Object() { |
| public String toString() { |
| return "Lazy removal flag"; //$NON-NLS-1$ |
| } |
| }; |
| |
| private final static int DIR_LEFT = 0; |
| private final static int DIR_RIGHT = 1; |
| private final static int DIR_UNSORTED = 2; |
| |
| // Direction constants indicating root nodes |
| private final static int DIR_ROOT = 3; |
| private final static int DIR_UNUSED = 4; |
| |
| private final class Edge { |
| private int startNode; |
| private int direction; |
| |
| private Edge() { |
| startNode = -1; |
| direction = -1; |
| } |
| |
| private Edge(int node, int dir) { |
| startNode = node; |
| direction = dir; |
| } |
| |
| private int getStart() { |
| return startNode; |
| } |
| |
| private int getTarget() { |
| if (startNode == -1) { |
| if (direction == DIR_UNSORTED) { |
| return firstUnusedNode; |
| } else if (direction == DIR_ROOT) { |
| return root; |
| } |
| return -1; |
| } |
| |
| if (direction == DIR_LEFT) { |
| return leftSubTree[startNode]; |
| } |
| if (direction == DIR_RIGHT) { |
| return rightSubTree[startNode]; |
| } |
| return nextUnsorted[startNode]; |
| } |
| |
| private boolean isNull() { |
| return getTarget() == -1; |
| } |
| |
| /** |
| * Redirects this edge to a new node |
| * @param newNode |
| * @since 3.1 |
| */ |
| private void setTarget(int newNode) { |
| if (direction == DIR_LEFT) { |
| leftSubTree[startNode] = newNode; |
| } else if (direction == DIR_RIGHT) { |
| rightSubTree[startNode] = newNode; |
| } else if (direction == DIR_UNSORTED) { |
| nextUnsorted[startNode] = newNode; |
| } else if (direction == DIR_ROOT) { |
| root = newNode; |
| } else if (direction == DIR_UNUSED) { |
| firstUnusedNode = newNode; |
| } |
| |
| if (newNode != -1) { |
| parentTree[newNode] = startNode; |
| } |
| } |
| |
| private void advance(int direction) { |
| startNode = getTarget(); |
| this.direction = direction; |
| } |
| } |
| |
| private void setRootNode(int node) { |
| root = node; |
| if (node != -1) { |
| parentTree[node] = -1; |
| } |
| } |
| |
| /** |
| * Creates a new sorted collection using the given comparator to determine |
| * sort order. |
| * |
| * @param c comparator that determines the sort order |
| */ |
| public LazySortedCollection(Comparator c) { |
| this.comparator = c; |
| } |
| |
| /** |
| * Tests if this object's internal state is valid. Throws a runtime |
| * exception if the state is invalid, indicating a programming error |
| * in this class. This method is intended for use in test |
| * suites and should not be called by clients. |
| */ |
| public void testInvariants() { |
| if (!enableDebug) { |
| return; |
| } |
| |
| testInvariants(root); |
| } |
| |
| private void testInvariants(int node) { |
| if (node == -1) { |
| return; |
| } |
| |
| // Get the current tree size (we will later force the tree size |
| // to be recomputed from scratch -- if everything works properly, then |
| // there should be no change. |
| int treeSize = getSubtreeSize(node); |
| |
| int left = leftSubTree[node]; |
| int right = rightSubTree[node]; |
| int unsorted = nextUnsorted[node]; |
| |
| if (isUnsorted(node)) { |
| Assert.isTrue(left == -1, "unsorted nodes shouldn't have a left subtree"); //$NON-NLS-1$ |
| Assert.isTrue(right == -1, "unsorted nodes shouldn't have a right subtree"); //$NON-NLS-1$ |
| } |
| |
| if (left != -1) { |
| testInvariants(left); |
| Assert.isTrue(parentTree[left] == node, "left node has invalid parent pointer"); //$NON-NLS-1$ |
| } |
| if (right != -1) { |
| testInvariants(right); |
| Assert.isTrue(parentTree[right] == node, "right node has invalid parent pointer"); //$NON-NLS-1$ |
| } |
| |
| int previous = node; |
| while (unsorted != -1) { |
| int oldTreeSize = this.treeSize[unsorted]; |
| recomputeTreeSize(unsorted); |
| |
| Assert.isTrue(this.treeSize[unsorted] == oldTreeSize, |
| "Invalid node size for unsorted node"); //$NON-NLS-1$ |
| Assert.isTrue(leftSubTree[unsorted] == -1, "unsorted nodes shouldn't have left subtrees"); //$NON-NLS-1$ |
| Assert.isTrue(rightSubTree[unsorted] == -1, "unsorted nodes shouldn't have right subtrees"); //$NON-NLS-1$ |
| Assert.isTrue(parentTree[unsorted] == previous, "unsorted node has invalid parent pointer"); //$NON-NLS-1$ |
| Assert.isTrue(contents[unsorted] != lazyRemovalFlag, "unsorted nodes should not be lazily removed"); //$NON-NLS-1$ |
| previous = unsorted; |
| unsorted = nextUnsorted[unsorted]; |
| } |
| |
| // Note that we've already tested that the child sizes are correct... if our size is |
| // correct, then recomputing it now should not cause any change. |
| recomputeTreeSize(node); |
| |
| Assert.isTrue(treeSize == getSubtreeSize(node), "invalid tree size"); //$NON-NLS-1$ |
| } |
| |
| private boolean isUnsorted(int node) { |
| int parent = parentTree[node]; |
| |
| if (parent != -1) { |
| return nextUnsorted[parent] == node; |
| } |
| |
| return false; |
| } |
| |
| private final boolean isLess(int element1, int element2) { |
| return comparator.compare(contents[element1], contents[element2]) < 0; |
| } |
| |
| /** |
| * Adds the given element to the given subtree. Returns the new |
| * root of the subtree. |
| * |
| * @param subTree index of the subtree to insert elementToAdd into. If -1, |
| * then a new subtree will be created for elementToAdd |
| * @param elementToAdd index of the element to add to the subtree. If -1, this method |
| * is a NOP. |
| * @since 3.1 |
| */ |
| private final int addUnsorted(int subTree, int elementToAdd) { |
| if (elementToAdd == -1) { |
| return subTree; |
| } |
| |
| if (subTree == -1) { |
| nextUnsorted[elementToAdd] = -1; |
| treeSize[elementToAdd] = 1; |
| return elementToAdd; |
| } |
| |
| // If the subTree is empty (ie: it only contains nodes flagged for lazy removal), |
| // chop it off. |
| if (treeSize[subTree] == 0) { |
| removeSubTree(subTree); |
| nextUnsorted[elementToAdd] = -1; |
| treeSize[elementToAdd] = 1; |
| return elementToAdd; |
| } |
| |
| // If neither subtree has any children, add a pseudorandom chance of the |
| // newly added element becoming the new pivot for this node. Note: instead |
| // of a real pseudorandom generator, we simply use a counter here. |
| if (!enableDebug && leftSubTree[subTree] == -1 && rightSubTree[subTree] == -1 |
| && leftSubTree[elementToAdd] == -1 && rightSubTree[elementToAdd] == -1) { |
| counter--; |
| |
| if (counter % treeSize[subTree] == 0) { |
| // Make the new node into the new pivot |
| nextUnsorted[elementToAdd] = subTree; |
| parentTree[elementToAdd] = parentTree[subTree]; |
| parentTree[subTree] = elementToAdd; |
| treeSize[elementToAdd] = treeSize[subTree] + 1; |
| return elementToAdd; |
| } |
| } |
| |
| int oldNextUnsorted = nextUnsorted[subTree]; |
| nextUnsorted[elementToAdd] = oldNextUnsorted; |
| |
| if (oldNextUnsorted == -1) { |
| treeSize[elementToAdd] = 1; |
| } else { |
| treeSize[elementToAdd] = treeSize[oldNextUnsorted] + 1; |
| parentTree[oldNextUnsorted] = elementToAdd; |
| } |
| |
| parentTree[elementToAdd] = subTree; |
| |
| nextUnsorted[subTree] = elementToAdd; |
| treeSize[subTree]++; |
| return subTree; |
| } |
| |
| /** |
| * Returns the number of elements in the collection |
| * |
| * @return the number of elements in the collection |
| */ |
| public int size() { |
| int result = getSubtreeSize(root); |
| |
| testInvariants(); |
| |
| return result; |
| } |
| |
| /** |
| * Given a tree and one of its unsorted children, this sorts the child by moving |
| * it into the left or right subtrees. Returns the next unsorted child or -1 if none |
| * |
| * @param subTree parent tree |
| * @param toMove child (unsorted) subtree |
| * @since 3.1 |
| */ |
| private final int partition(int subTree, int toMove) { |
| int result = nextUnsorted[toMove]; |
| |
| if (isLess(toMove, subTree)) { |
| int nextLeft = addUnsorted(leftSubTree[subTree], toMove); |
| leftSubTree[subTree] = nextLeft; |
| parentTree[nextLeft] = subTree; |
| } else { |
| int nextRight = addUnsorted(rightSubTree[subTree], toMove); |
| rightSubTree[subTree] = nextRight; |
| parentTree[nextRight] = subTree; |
| } |
| |
| return result; |
| } |
| |
| /** |
| * Partitions the given subtree. Moves all unsorted elements at the given node |
| * to either the left or right subtrees. If the node itself was scheduled for |
| * lazy removal, this will force the node to be removed immediately. Returns |
| * the new subTree. |
| * |
| * @param subTree |
| * @return the replacement node (this may be different from subTree if the subtree |
| * was replaced during the removal) |
| * @since 3.1 |
| */ |
| private final int partition(int subTree, FastProgressReporter mon) throws InterruptedException { |
| if (subTree == -1) { |
| return -1; |
| } |
| |
| if (contents[subTree] == lazyRemovalFlag) { |
| subTree = removeNode(subTree); |
| if (subTree == -1) { |
| return -1; |
| } |
| } |
| |
| for (int idx = nextUnsorted[subTree]; idx != -1;) { |
| idx = partition(subTree, idx); |
| nextUnsorted[subTree] = idx; |
| if (idx != -1) { |
| parentTree[idx] = subTree; |
| } |
| |
| if (mon.isCanceled()) { |
| throw new InterruptedException(); |
| } |
| } |
| |
| // At this point, there are no remaining unsorted nodes in this subtree |
| nextUnsorted[subTree] = -1; |
| |
| return subTree; |
| } |
| |
| private final int getSubtreeSize(int subTree) { |
| if (subTree == -1) { |
| return 0; |
| } |
| return treeSize[subTree]; |
| } |
| |
| /** |
| * Increases the capacity of this collection, if necessary, so that it can hold the |
| * given number of elements. This can be used prior to a sequence of additions to |
| * avoid memory reallocation. This cannot be used to reduce the amount |
| * of memory used by the collection. |
| * |
| * @param newSize capacity for this collection |
| */ |
| public final void setCapacity(int newSize) { |
| if (newSize > contents.length) { |
| setArraySize(newSize); |
| } |
| } |
| |
| /** |
| * Adjusts the capacity of the array. |
| * |
| * @param newCapacity |
| */ |
| private final void setArraySize(int newCapacity) { |
| Object[] newContents = new Object[newCapacity]; |
| System.arraycopy(contents, 0, newContents, 0, lastNode); |
| contents = newContents; |
| |
| int[] newLeftSubTree = new int[newCapacity]; |
| System.arraycopy(leftSubTree, 0, newLeftSubTree, 0, lastNode); |
| leftSubTree = newLeftSubTree; |
| |
| int[] newRightSubTree = new int[newCapacity]; |
| System.arraycopy(rightSubTree, 0, newRightSubTree, 0, lastNode); |
| rightSubTree = newRightSubTree; |
| |
| int[] newNextUnsorted = new int[newCapacity]; |
| System.arraycopy(nextUnsorted, 0, newNextUnsorted, 0, lastNode); |
| nextUnsorted = newNextUnsorted; |
| |
| int[] newTreeSize = new int[newCapacity]; |
| System.arraycopy(treeSize, 0, newTreeSize, 0, lastNode); |
| treeSize = newTreeSize; |
| |
| int[] newParentTree = new int[newCapacity]; |
| System.arraycopy(parentTree, 0, newParentTree, 0, lastNode); |
| parentTree = newParentTree; |
| } |
| |
| /** |
| * Creates a new node with the given value. Returns the index of the newly |
| * created node. |
| * |
| * @param value |
| * @return the index of the newly created node |
| * @since 3.1 |
| */ |
| private final int createNode(Object value) { |
| int result = -1; |
| |
| if (firstUnusedNode == -1) { |
| // If there are no unused nodes from prior removals, then |
| // we add a node at the end |
| result = lastNode; |
| |
| // If this would cause the array to overflow, reallocate the array |
| if (contents.length <= lastNode) { |
| setCapacity(lastNode * 2); |
| } |
| |
| lastNode++; |
| } else { |
| // Reuse a node from a prior removal |
| result = firstUnusedNode; |
| firstUnusedNode = nextUnsorted[result]; |
| } |
| |
| contents[result] = value; |
| treeSize[result] = 1; |
| |
| // Clear pointers |
| leftSubTree[result] = -1; |
| rightSubTree[result] = -1; |
| nextUnsorted[result] = -1; |
| |
| // As long as we have a hash table of values onto tree indices, incrementally |
| // update the hash table. Note: the table is only constructed as needed, and it |
| // is destroyed whenever the arrays are reallocated instead of reallocating it. |
| if (objectIndices != null) { |
| objectIndices.put(value, result); |
| } |
| |
| return result; |
| } |
| |
| /** |
| * Returns the current tree index for the given object. |
| * |
| * @param value |
| * @return the current tree index |
| * @since 3.1 |
| */ |
| private int getObjectIndex(Object value) { |
| // If we don't have a map of values onto tree indices, build the map now. |
| if (objectIndices == null) { |
| int result = -1; |
| |
| objectIndices = new IntHashMap((int)(contents.length / loadFactor) + 1, loadFactor); |
| |
| for (int i = 0; i < lastNode; i++) { |
| Object element = contents[i]; |
| |
| if (element != null && element != lazyRemovalFlag) { |
| objectIndices.put(element, i); |
| |
| if (value == element) { |
| result = i; |
| } |
| } |
| } |
| |
| return result; |
| } |
| |
| // If we have a map of values onto tree indices, return the result by looking it up in |
| // the map |
| return objectIndices.get(value, -1); |
| } |
| |
| /** |
| * Redirects any pointers from the original to the replacement. If the replacement |
| * causes a change in the number of elements in the parent tree, the changes are |
| * propogated toward the root. |
| * |
| * @param nodeToReplace |
| * @param replacementNode |
| * @since 3.1 |
| */ |
| private void replaceNode(int nodeToReplace, int replacementNode) { |
| int parent = parentTree[nodeToReplace]; |
| |
| if (parent == -1) { |
| if (root == nodeToReplace) { |
| setRootNode(replacementNode); |
| } |
| } else { |
| if (leftSubTree[parent] == nodeToReplace) { |
| leftSubTree[parent] = replacementNode; |
| } else if (rightSubTree[parent] == nodeToReplace) { |
| rightSubTree[parent] = replacementNode; |
| } else if (nextUnsorted[parent] == nodeToReplace) { |
| nextUnsorted[parent] = replacementNode; |
| } |
| if (replacementNode != -1) { |
| parentTree[replacementNode] = parent; |
| } |
| } |
| } |
| |
| private void recomputeAncestorTreeSizes(int node) { |
| while (node != -1) { |
| int oldSize = treeSize[node]; |
| |
| recomputeTreeSize(node); |
| |
| if (treeSize[node] == oldSize) { |
| break; |
| } |
| |
| node = parentTree[node]; |
| } |
| } |
| |
| /** |
| * Recomputes the tree size for the given node. |
| * |
| * @param node |
| * @since 3.1 |
| */ |
| private void recomputeTreeSize(int node) { |
| if (node == -1) { |
| return; |
| } |
| treeSize[node] = getSubtreeSize(leftSubTree[node]) |
| + getSubtreeSize(rightSubTree[node]) |
| + getSubtreeSize(nextUnsorted[node]) |
| + (contents[node] == lazyRemovalFlag ? 0 : 1); |
| } |
| |
| /** |
| * |
| * @param toRecompute |
| * @param whereToStop |
| * @since 3.1 |
| */ |
| private void forceRecomputeTreeSize(int toRecompute, int whereToStop) { |
| while (toRecompute != -1 && toRecompute != whereToStop) { |
| recomputeTreeSize(toRecompute); |
| |
| toRecompute = parentTree[toRecompute]; |
| } |
| } |
| |
| /** |
| * Destroy the node at the given index in the tree |
| * @param nodeToDestroy |
| * @since 3.1 |
| */ |
| private void destroyNode(int nodeToDestroy) { |
| // If we're maintaining a map of values onto tree indices, remove this entry from |
| // the map |
| if (objectIndices != null) { |
| Object oldContents = contents[nodeToDestroy]; |
| if (oldContents != lazyRemovalFlag) { |
| objectIndices.remove(oldContents); |
| } |
| } |
| |
| contents[nodeToDestroy] = null; |
| leftSubTree[nodeToDestroy] = -1; |
| rightSubTree[nodeToDestroy] = -1; |
| |
| if (firstUnusedNode == -1) { |
| treeSize[nodeToDestroy] = 1; |
| } else { |
| treeSize[nodeToDestroy] = treeSize[firstUnusedNode] + 1; |
| parentTree[firstUnusedNode] = nodeToDestroy; |
| } |
| |
| nextUnsorted[nodeToDestroy] = firstUnusedNode; |
| |
| firstUnusedNode = nodeToDestroy; |
| } |
| |
| /** |
| * Frees up memory by clearing the list of nodes that have been freed up through removals. |
| * |
| * @since 3.1 |
| */ |
| private final void pack() { |
| |
| // If there are no unused nodes, then there is nothing to do |
| if (firstUnusedNode == -1) { |
| return; |
| } |
| |
| int reusableNodes = getSubtreeSize(firstUnusedNode); |
| int nonPackableNodes = lastNode - reusableNodes; |
| |
| // Only pack the array if we're utilizing less than 1/4 of the array (note: |
| // this check is important, or it will change the time bounds for removals) |
| if (contents.length < MIN_CAPACITY || nonPackableNodes > contents.length / 4) { |
| return; |
| } |
| |
| // Rather than update the entire map, just null it out. If it is needed, |
| // it will be recreated lazily later. This will save some memory if the |
| // map isn't needed, and it takes a similar amount of time to recreate the |
| // map as to update all the indices. |
| objectIndices = null; |
| |
| // Maps old index -> new index |
| int[] mapNewIdxOntoOld = new int[contents.length]; |
| int[] mapOldIdxOntoNew = new int[contents.length]; |
| |
| int nextNewIdx = 0; |
| // Compute the mapping. Determine the new index for each element |
| for (int oldIdx = 0; oldIdx < lastNode; oldIdx++) { |
| if (contents[oldIdx] != null) { |
| mapOldIdxOntoNew[oldIdx] = nextNewIdx; |
| mapNewIdxOntoOld[nextNewIdx] = oldIdx; |
| nextNewIdx++; |
| } else { |
| mapOldIdxOntoNew[oldIdx] = -1; |
| } |
| } |
| |
| // Make the actual array size double the number of nodes to allow |
| // for expansion. |
| int newNodes = nextNewIdx; |
| int newCapacity = Math.max(newNodes * 2, MIN_CAPACITY); |
| |
| // Allocate new arrays |
| Object[] newContents = new Object[newCapacity]; |
| int[] newTreeSize = new int[newCapacity]; |
| int[] newNextUnsorted = new int[newCapacity]; |
| int[] newLeftSubTree = new int[newCapacity]; |
| int[] newRightSubTree = new int[newCapacity]; |
| int[] newParentTree = new int[newCapacity]; |
| |
| for (int newIdx = 0; newIdx < newNodes; newIdx++) { |
| int oldIdx = mapNewIdxOntoOld[newIdx]; |
| newContents[newIdx] = contents[oldIdx]; |
| newTreeSize[newIdx] = treeSize[oldIdx]; |
| |
| int left = leftSubTree[oldIdx]; |
| if (left == -1) { |
| newLeftSubTree[newIdx] = -1; |
| } else { |
| newLeftSubTree[newIdx] = mapOldIdxOntoNew[left]; |
| } |
| |
| int right = rightSubTree[oldIdx]; |
| if (right == -1) { |
| newRightSubTree[newIdx] = -1; |
| } else { |
| newRightSubTree[newIdx] = mapOldIdxOntoNew[right]; |
| } |
| |
| int unsorted = nextUnsorted[oldIdx]; |
| if (unsorted == -1) { |
| newNextUnsorted[newIdx] = -1; |
| } else { |
| newNextUnsorted[newIdx] = mapOldIdxOntoNew[unsorted]; |
| } |
| |
| int parent = parentTree[oldIdx]; |
| if (parent == -1) { |
| newParentTree[newIdx] = -1; |
| } else { |
| newParentTree[newIdx] = mapOldIdxOntoNew[parent]; |
| } |
| } |
| |
| contents = newContents; |
| nextUnsorted = newNextUnsorted; |
| treeSize = newTreeSize; |
| leftSubTree = newLeftSubTree; |
| rightSubTree = newRightSubTree; |
| parentTree = newParentTree; |
| |
| if (root != -1) { |
| root = mapOldIdxOntoNew[root]; |
| } |
| |
| // All unused nodes have been removed |
| firstUnusedNode = -1; |
| lastNode = newNodes; |
| } |
| |
| /** |
| * Adds the given object to the collection. Runs in O(1) amortized time. |
| * |
| * @param toAdd object to add |
| */ |
| public final void add(Object toAdd) { |
| Assert.isNotNull(toAdd); |
| // Create the new node |
| int newIdx = createNode(toAdd); |
| |
| // Insert the new node into the root tree |
| setRootNode(addUnsorted(root, newIdx)); |
| |
| testInvariants(); |
| } |
| |
| /** |
| * Adds all items from the given collection to this collection |
| * |
| * @param toAdd objects to add |
| */ |
| public final void addAll(Collection toAdd) { |
| Assert.isNotNull(toAdd); |
| Iterator iter = toAdd.iterator(); |
| while (iter.hasNext()) { |
| add(iter.next()); |
| } |
| |
| testInvariants(); |
| } |
| |
| /** |
| * Adds all items from the given array to the collection |
| * |
| * @param toAdd objects to add |
| */ |
| public final void addAll(Object[] toAdd) { |
| Assert.isNotNull(toAdd); |
| for (int i = 0; i < toAdd.length; i++) { |
| Object object = toAdd[i]; |
| |
| add(object); |
| } |
| |
| testInvariants(); |
| } |
| |
| /** |
| * Returns true iff the collection is empty |
| * |
| * @return true iff the collection contains no elements |
| */ |
| public final boolean isEmpty() { |
| boolean result = (root == -1); |
| |
| testInvariants(); |
| |
| return result; |
| } |
| |
| /** |
| * Removes the given object from the collection. Has no effect if |
| * the element does not exist in this collection. |
| * |
| * @param toRemove element to remove |
| */ |
| public final void remove(Object toRemove) { |
| internalRemove(toRemove); |
| |
| pack(); |
| |
| testInvariants(); |
| } |
| |
| /** |
| * Internal implementation of remove. Removes the given element but does not |
| * pack the container after the removal. |
| * |
| * @param toRemove element to remove |
| */ |
| private void internalRemove(Object toRemove) { |
| int objectIndex = getObjectIndex(toRemove); |
| |
| if (objectIndex != -1) { |
| int parent = parentTree[objectIndex]; |
| lazyRemoveNode(objectIndex); |
| //Edge parentEdge = getEdgeTo(objectIndex); |
| //parentEdge.setTarget(lazyRemoveNode(objectIndex)); |
| recomputeAncestorTreeSizes(parent); |
| } |
| |
| //testInvariants(); |
| } |
| |
| /** |
| * Removes all elements in the given array from this collection. |
| * |
| * @param toRemove elements to remove |
| */ |
| public final void removeAll(Object[] toRemove) { |
| Assert.isNotNull(toRemove); |
| |
| for (int i = 0; i < toRemove.length; i++) { |
| Object object = toRemove[i]; |
| |
| internalRemove(object); |
| } |
| pack(); |
| } |
| |
| /** |
| * Retains the n smallest items in the collection, removing the rest. When |
| * this method returns, the size of the collection will be n. Note that |
| * this is a no-op if n > the current size of the collection. |
| * |
| * Temporarily package visibility until the implementation of FastProgressReporter |
| * is finished. |
| * |
| * @param n number of items to retain |
| * @param mon progress monitor |
| * @throws InterruptedException if the progress monitor is cancelled in another thread |
| */ |
| /* package */ final void retainFirst(int n, FastProgressReporter mon) throws InterruptedException { |
| int sz = size(); |
| |
| if (n >= sz) { |
| return; |
| } |
| |
| removeRange(n, sz - n, mon); |
| |
| testInvariants(); |
| } |
| |
| /** |
| * Retains the n smallest items in the collection, removing the rest. When |
| * this method returns, the size of the collection will be n. Note that |
| * this is a no-op if n > the current size of the collection. |
| * |
| * @param n number of items to retain |
| */ |
| public final void retainFirst(int n) { |
| try { |
| retainFirst(n, new FastProgressReporter()); |
| } catch (InterruptedException e) { |
| } |
| |
| testInvariants(); |
| } |
| |
| /** |
| * Removes all elements in the given range from this collection. |
| * For example, removeRange(10, 3) would remove the 11th through 13th |
| * smallest items from the collection. |
| * |
| * @param first 0-based index of the smallest item to remove |
| * @param length number of items to remove |
| */ |
| public final void removeRange(int first, int length) { |
| try { |
| removeRange(first, length, new FastProgressReporter()); |
| } catch (InterruptedException e) { |
| } |
| |
| testInvariants(); |
| } |
| |
| /** |
| * Removes all elements in the given range from this collection. |
| * For example, removeRange(10, 3) would remove the 11th through 13th |
| * smallest items from the collection. |
| * |
| * Temporarily package visiblity until the implementation of FastProgressReporter is |
| * finished. |
| * |
| * @param first 0-based index of the smallest item to remove |
| * @param length number of items to remove |
| * @param mon progress monitor |
| * @throws InterruptedException if the progress monitor is cancelled in another thread |
| */ |
| /* package */ final void removeRange(int first, int length, FastProgressReporter mon) throws InterruptedException { |
| removeRange(root, first, length, mon); |
| |
| pack(); |
| |
| testInvariants(); |
| } |
| |
| private final void removeRange(int node, int rangeStart, int rangeLength, FastProgressReporter mon) throws InterruptedException { |
| if (rangeLength == 0) { |
| return; |
| } |
| |
| int size = getSubtreeSize(node); |
| |
| if (size <= rangeStart) { |
| return; |
| } |
| |
| // If we can chop off this entire subtree without any sorting, do so. |
| if (rangeStart == 0 && rangeLength >= size) { |
| removeSubTree(node); |
| return; |
| } |
| try { |
| // Partition any unsorted nodes |
| node = partition(node, mon); |
| |
| int left = leftSubTree[node]; |
| int leftSize = getSubtreeSize(left); |
| |
| int toRemoveFromLeft = Math.min(leftSize - rangeStart, rangeLength); |
| |
| // If we're removing anything from the left node |
| if (toRemoveFromLeft >= 0) { |
| removeRange(leftSubTree[node], rangeStart, toRemoveFromLeft, mon); |
| |
| // Check if we're removing from both sides |
| int toRemoveFromRight = rangeStart + rangeLength - leftSize - 1; |
| |
| if (toRemoveFromRight >= 0) { |
| // Remove from right subtree |
| removeRange(rightSubTree[node], 0, toRemoveFromRight, mon); |
| |
| // ... removing from both sides means we need to remove the node itself too |
| removeNode(node); |
| return; |
| } |
| } else { |
| // If removing from the right side only |
| removeRange(rightSubTree[node], rangeStart - leftSize - 1, rangeLength, mon); |
| } |
| } finally { |
| recomputeTreeSize(node); |
| } |
| } |
| |
| /** |
| * Prunes the given subtree (and all child nodes, sorted or unsorted). |
| * |
| * @param subTree |
| * @since 3.1 |
| */ |
| private final void removeSubTree(int subTree) { |
| if (subTree == -1) { |
| return; |
| } |
| |
| // Destroy all unsorted nodes |
| for (int next = nextUnsorted[subTree]; next != -1;) { |
| int current = next; |
| next = nextUnsorted[next]; |
| |
| // Destroy this unsorted node |
| destroyNode(current); |
| } |
| |
| // Destroy left subtree |
| removeSubTree(leftSubTree[subTree]); |
| |
| // Destroy right subtree |
| removeSubTree(rightSubTree[subTree]); |
| |
| replaceNode(subTree, -1); |
| // Destroy pivot node |
| destroyNode(subTree); |
| } |
| |
| /** |
| * Schedules the node for removal. If the node can be removed in constant time, |
| * it is removed immediately. |
| * |
| * @param subTree |
| * @return the replacement node |
| * @since 3.1 |
| */ |
| private final int lazyRemoveNode(int subTree) { |
| int left = leftSubTree[subTree]; |
| int right = rightSubTree[subTree]; |
| |
| // If this is a leaf node, remove it immediately |
| if (left == -1 && right == -1) { |
| int result = nextUnsorted[subTree]; |
| replaceNode(subTree, result); |
| destroyNode(subTree); |
| return result; |
| } |
| |
| // Otherwise, flag it for future removal |
| Object value = contents[subTree]; |
| contents[subTree] = lazyRemovalFlag; |
| treeSize[subTree]--; |
| if (objectIndices != null) { |
| objectIndices.remove(value); |
| } |
| |
| return subTree; |
| } |
| |
| /** |
| * Removes the given subtree, replacing it with one of its children. |
| * Returns the new root of the subtree |
| * |
| * @param subTree |
| * @return the index of the new root |
| * @since 3.1 |
| */ |
| private final int removeNode(int subTree) { |
| int left = leftSubTree[subTree]; |
| int right = rightSubTree[subTree]; |
| |
| if (left == -1 || right == -1) { |
| int result = -1; |
| |
| if (left == -1 && right == -1) { |
| // If this is a leaf node, replace it with its first unsorted child |
| result = nextUnsorted[subTree]; |
| } else { |
| // Either the left or right child is missing -- replace with the remaining child |
| if (left == -1) { |
| result = right; |
| } else { |
| result = left; |
| } |
| |
| try { |
| result = partition(result, new FastProgressReporter()); |
| } catch (InterruptedException e) { |
| |
| } |
| if (result == -1) { |
| result = nextUnsorted[subTree]; |
| } else { |
| int unsorted = nextUnsorted[subTree]; |
| nextUnsorted[result] = unsorted; |
| int additionalNodes = 0; |
| if (unsorted != -1) { |
| parentTree[unsorted] = result; |
| additionalNodes = treeSize[unsorted]; |
| } |
| treeSize[result] += additionalNodes; |
| } |
| } |
| |
| replaceNode(subTree, result); |
| destroyNode(subTree); |
| return result; |
| } |
| |
| // Find the edges that lead to the next-smallest and |
| // next-largest nodes |
| Edge nextSmallest = new Edge(subTree, DIR_LEFT); |
| while (!nextSmallest.isNull()) { |
| nextSmallest.advance(DIR_RIGHT); |
| } |
| |
| Edge nextLargest = new Edge(subTree, DIR_RIGHT); |
| while (!nextLargest.isNull()) { |
| nextLargest.advance(DIR_LEFT); |
| } |
| |
| // Index of the replacement node |
| int replacementNode = -1; |
| |
| // Count of number of nodes moved to the right |
| |
| int leftSize = getSubtreeSize(left); |
| int rightSize = getSubtreeSize(right); |
| |
| // Swap with a child from the larger subtree |
| if (leftSize > rightSize) { |
| replacementNode = nextSmallest.getStart(); |
| |
| // Move any unsorted nodes that are larger than the replacement node into |
| // the left subtree of the next-largest node |
| Edge unsorted = new Edge(replacementNode, DIR_UNSORTED); |
| while (!unsorted.isNull()) { |
| int target = unsorted.getTarget(); |
| |
| if (!isLess(target, replacementNode)) { |
| unsorted.setTarget(nextUnsorted[target]); |
| nextLargest.setTarget(addUnsorted(nextLargest.getTarget(), target)); |
| } else { |
| unsorted.advance(DIR_UNSORTED); |
| } |
| } |
| |
| forceRecomputeTreeSize(unsorted.getStart(), replacementNode); |
| forceRecomputeTreeSize(nextLargest.getStart(), subTree); |
| } else { |
| replacementNode = nextLargest.getStart(); |
| |
| // Move any unsorted nodes that are smaller than the replacement node into |
| // the right subtree of the next-smallest node |
| Edge unsorted = new Edge(replacementNode, DIR_UNSORTED); |
| while (!unsorted.isNull()) { |
| int target = unsorted.getTarget(); |
| |
| if (isLess(target, replacementNode)) { |
| unsorted.setTarget(nextUnsorted[target]); |
| nextSmallest.setTarget(addUnsorted(nextSmallest.getTarget(), target)); |
| } else { |
| unsorted.advance(DIR_UNSORTED); |
| } |
| } |
| |
| forceRecomputeTreeSize(unsorted.getStart(), replacementNode); |
| forceRecomputeTreeSize(nextSmallest.getStart(), subTree); |
| } |
| |
| // Now all the affected treeSize[...] elements should be updated to reflect the |
| // unsorted nodes that moved. Swap nodes. |
| Object replacementContent = contents[replacementNode]; |
| contents[replacementNode] = contents[subTree]; |
| contents[subTree] = replacementContent; |
| |
| if (objectIndices != null) { |
| objectIndices.put(replacementContent, subTree); |
| // Note: currently we don't bother updating the index of the replacement |
| // node since we're going to remove it immediately afterwards and there's |
| // no good reason to search for the index in a method that was given the |
| // index as a parameter... |
| |
| // objectIndices.put(contents[replacementNode], replacementNode) |
| } |
| |
| int replacementParent = parentTree[replacementNode]; |
| |
| replaceNode(replacementNode, removeNode(replacementNode)); |
| //Edge parentEdge = getEdgeTo(replacementNode); |
| //parentEdge.setTarget(removeNode(replacementNode)); |
| |
| forceRecomputeTreeSize(replacementParent, subTree); |
| recomputeTreeSize(subTree); |
| |
| //testInvariants(); |
| |
| return subTree; |
| } |
| |
| /** |
| * Removes all elements from the collection |
| */ |
| public final void clear() { |
| lastNode = 0; |
| setArraySize(MIN_CAPACITY); |
| root = -1; |
| firstUnusedNode = -1; |
| objectIndices = null; |
| |
| testInvariants(); |
| } |
| |
| /** |
| * Returns the comparator that is determining the sort order for this collection |
| * |
| * @return comparator for this collection |
| */ |
| public Comparator getComparator() { |
| return comparator; |
| } |
| |
| /** |
| * Fills in an array of size n with the n smallest elements from the collection. |
| * Can compute the result in sorted or unsorted order. |
| * |
| * Currently package visible until the implementation of FastProgressReporter is finished. |
| * |
| * @param result array to be filled |
| * @param sorted if true, the result array will be sorted. If false, the result array |
| * may be unsorted. This does not affect which elements appear in the result, only their |
| * order. |
| * @param mon monitor used to report progress and check for cancellation |
| * @return the number of items inserted into the result array. This will be equal to the minimum |
| * of result.length and container.size() |
| * @throws InterruptedException if the progress monitor is cancelled |
| */ |
| /* package */ final int getFirst(Object[] result, boolean sorted, FastProgressReporter mon) throws InterruptedException { |
| int returnValue = getRange(result, 0, sorted, mon); |
| |
| testInvariants(); |
| |
| return returnValue; |
| } |
| |
| /** |
| * Fills in an array of size n with the n smallest elements from the collection. |
| * Can compute the result in sorted or unsorted order. |
| * |
| * @param result array to be filled |
| * @param sorted if true, the result array will be sorted. If false, the result array |
| * may be unsorted. This does not affect which elements appear in the result. It only |
| * affects their order. Computing an unsorted result is asymptotically faster. |
| * @return the number of items inserted into the result array. This will be equal to the minimum |
| * of result.length and container.size() |
| */ |
| public final int getFirst(Object[] result, boolean sorted) { |
| int returnValue = 0; |
| |
| try { |
| returnValue = getFirst(result, sorted, new FastProgressReporter()); |
| } catch (InterruptedException e) { |
| } |
| |
| testInvariants(); |
| |
| return returnValue; |
| } |
| |
| /** |
| * Given a position defined by k and an array of size n, this fills in the array with |
| * the kth smallest element through to the (k+n)th smallest element. For example, |
| * getRange(myArray, 10, false) would fill in myArray starting with the 10th smallest item |
| * in the collection. The result can be computed in sorted or unsorted order. Computing the |
| * result in unsorted order is more efficient. |
| * <p> |
| * Temporarily set to package visibility until the implementation of FastProgressReporter |
| * is finished. |
| * </p> |
| * |
| * @param result array to be filled in |
| * @param rangeStart index of the smallest element to appear in the result |
| * @param sorted true iff the result array should be sorted |
| * @param mon progress monitor used to cancel the operation |
| * @throws InterruptedException if the progress monitor was cancelled in another thread |
| */ |
| /* package */ final int getRange(Object[] result, int rangeStart, boolean sorted, FastProgressReporter mon) throws InterruptedException { |
| return getRange(result, 0, rangeStart, root, sorted, mon); |
| } |
| |
| /** |
| * Computes the n through n+k items in this collection. |
| * Computing the result in unsorted order is more efficient. Sorting the result will |
| * not change which elements actually show up in the result. That is, even if the result is |
| * unsorted, it will still contain the same elements as would have been at that range in |
| * a fully sorted collection. |
| * |
| * @param result array containing the result |
| * @param rangeStart index of the first element to be inserted into the result array |
| * @param sorted true iff the result will be computed in sorted order |
| * @return the number of items actually inserted into the result array (will be the minimum |
| * of result.length and this.size()) |
| */ |
| public final int getRange(Object[] result, int rangeStart, boolean sorted) { |
| int returnValue = 0; |
| |
| try { |
| returnValue = getRange(result, rangeStart, sorted, new FastProgressReporter()); |
| } catch (InterruptedException e) { |
| } |
| |
| testInvariants(); |
| |
| return returnValue; |
| } |
| |
| /** |
| * Returns the item at the given index. Indexes are based on sorted order. |
| * |
| * @param index index to test |
| * @return the item at the given index |
| */ |
| public final Object getItem(int index) { |
| Object[] result = new Object[1]; |
| try { |
| getRange(result, index, false, new FastProgressReporter()); |
| } catch (InterruptedException e) { |
| // shouldn't happen |
| } |
| Object returnValue = result[0]; |
| |
| testInvariants(); |
| |
| return returnValue; |
| } |
| |
| /** |
| * Returns the contents of this collection as a sorted or unsorted |
| * array. Computing an unsorted array is more efficient. |
| * |
| * @param sorted if true, the result will be in sorted order. If false, |
| * the result may be in unsorted order. |
| * @return the contents of this collection as an array. |
| */ |
| public final Object[] getItems(boolean sorted) { |
| Object[] result = new Object[size()]; |
| |
| getRange(result, 0, sorted); |
| |
| return result; |
| } |
| |
| private final int getRange(Object[] result, int resultIdx, int rangeStart, int node, boolean sorted, FastProgressReporter mon) throws InterruptedException { |
| if (node == -1) { |
| return 0; |
| } |
| |
| int availableSpace = result.length - resultIdx; |
| |
| // If we're asking for all children of the current node, simply call getChildren |
| if (rangeStart == 0) { |
| if (treeSize[node] <= availableSpace) { |
| return getChildren(result, resultIdx, node, sorted, mon); |
| } |
| } |
| |
| node = partition(node, mon); |
| if (node == -1) { |
| return 0; |
| } |
| |
| int inserted = 0; |
| |
| int numberLessThanNode = getSubtreeSize(leftSubTree[node]); |
| |
| if (rangeStart < numberLessThanNode) { |
| if (inserted < availableSpace) { |
| inserted += getRange(result, resultIdx, rangeStart, leftSubTree[node], sorted, mon); |
| } |
| } |
| |
| if (rangeStart <= numberLessThanNode) { |
| if (inserted < availableSpace) { |
| result[resultIdx + inserted] = contents[node]; |
| inserted++; |
| } |
| } |
| |
| if (inserted < availableSpace) { |
| inserted += getRange(result, resultIdx + inserted, |
| Math.max(rangeStart - numberLessThanNode - 1, 0), rightSubTree[node], sorted, mon); |
| } |
| |
| return inserted; |
| } |
| |
| /** |
| * Fills in the available space in the given array with all children of the given node. |
| * |
| * @param result |
| * @param resultIdx index in the result array where we will begin filling in children |
| * @param node |
| * @return the number of children added to the array |
| * @since 3.1 |
| */ |
| private final int getChildren(Object[] result, int resultIdx, int node, boolean sorted, FastProgressReporter mon) throws InterruptedException { |
| if (node == -1) { |
| return 0; |
| } |
| |
| int tempIdx = resultIdx; |
| |
| if (sorted) { |
| node = partition(node, mon); |
| if (node == -1) { |
| return 0; |
| } |
| } |
| |
| // Add child nodes smaller than this one |
| if (tempIdx < result.length) { |
| tempIdx += getChildren(result, tempIdx, leftSubTree[node], sorted, mon); |
| } |
| |
| // Add the pivot |
| if (tempIdx < result.length) { |
| Object value = contents[node]; |
| if (value != lazyRemovalFlag) { |
| result[tempIdx++] = value; |
| } |
| } |
| |
| // Add child nodes larger than this one |
| if (tempIdx < result.length) { |
| tempIdx += getChildren(result, tempIdx, rightSubTree[node], sorted, mon); |
| } |
| |
| // Add unsorted children (should be empty if the sorted flag was true) |
| for (int unsortedNode = nextUnsorted[node]; unsortedNode != -1 && tempIdx < result.length; |
| unsortedNode = nextUnsorted[unsortedNode]) { |
| |
| result[tempIdx++] = contents[unsortedNode]; |
| } |
| |
| return tempIdx - resultIdx; |
| } |
| |
| /** |
| * Returns true iff this collection contains the given item |
| * |
| * @param item item to test |
| * @return true iff this collection contains the given item |
| */ |
| public boolean contains(Object item) { |
| Assert.isNotNull(item); |
| boolean returnValue = (getObjectIndex(item) != -1); |
| |
| testInvariants(); |
| |
| return returnValue; |
| } |
| } |
