+ * 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. + *
+ *+ * 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. + *
+ * + * @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; + public boolean enableRandomization = true; + + // Cancellation support + private IProgressMonitor progressMonitor = null; + // Normally, we return this cached result when determining if + // we're cancelled. However, periodically (whenever cancelCheckCounter reaches 0) + // we will update the cached value by calling progressMonitor.isCancelled(). + // The rest of these "cancellation + private boolean cancelled = false; + private int cancelCheckCounter = 0; + // Minimum milliseconds between each call to isCancelled + private static final int CANCEL_CHECK_PERIOD = 50; + // Minimum number of elements to process before calling isCancelled + private static final int MIN_CANCEL_CHECK_FREQUENCY = 10; + // Number of bogus checks before a real + private int cancelCheckFrequency = MIN_CANCEL_CHECK_FREQUENCY; + // Timestamp of the last call to isCancelled + private long lastCancelCheckTimestamp = 0; + + + // 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"; + } + }; + + 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 void copy(Edge toCopy) { + startNode = toCopy.startNode; + direction = toCopy.direction; + } + + 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; + } + } + + private void setNextUnsorted(int parent, int next) { + nextUnsorted[parent] = next; + if (next != -1) { + parentTree[next] = parent; + } + recomputeTreeSize(parent); + } + + public LazySortedCollection(Comparator c) { + this.comparator = c; + } + + public void print() { + StringBuffer buf = new StringBuffer(); + System.out.println("----"); + print(0, root); + + System.out.println(buf.toString()); + } + + private String indent(int indent) { + String output = ""; + + for(int i = 0; i < indent; i++) { + output += " "; + } + + return output; + } + + public void print(int indent, int nodeToPrint) { + + String indentString = indent(indent); + if (nodeToPrint == -1) { + System.out.println("null\n"); + return; + } + + if (leftSubTree[nodeToPrint] != -1) { + System.out.println(indentString + "left " + leftSubTree[nodeToPrint]); + print(indent + 1, leftSubTree[nodeToPrint]); + } + + System.out.println(indentString + "value {" + contents[nodeToPrint] + "}"); + int next = nextUnsorted[nodeToPrint]; + while (next != -1) { + System.out.println(indentString + "unsorted " + next + " {" + contents[next] + "}"); + next = nextUnsorted[next]; + } + + if (rightSubTree[nodeToPrint] != -1) { + System.out.println(indentString + "right " + rightSubTree[nodeToPrint]); + print(indent + 1, rightSubTree[nodeToPrint]); + } + } + + public void testInvariants() { + if (enableRandomization) { + 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"); + Assert.isTrue(right == -1, "unsorted nodes shouldn't have a right subtree"); + } + + if (left != -1) { + testInvariants(left); + Assert.isTrue(parentTree[left] == node, "left node has invalid parent pointer"); + } + if (right != -1) { + testInvariants(right); + Assert.isTrue(parentTree[right] == node, "right node has invalid parent pointer"); + } + + 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"); + Assert.isTrue(leftSubTree[unsorted] == -1, "unsorted nodes shouldn't have left subtrees"); + Assert.isTrue(rightSubTree[unsorted] == -1, "unsorted nodes shouldn't have right subtrees"); + Assert.isTrue(parentTree[unsorted] == previous, "unsorted node has invalid parent pointer"); + Assert.isTrue(contents[unsorted] != lazyRemovalFlag, "unsorted nodes should not be lazily removed"); + 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); + + if (treeSize != getSubtreeSize(node)) { + print(); + } + + Assert.isTrue(treeSize == getSubtreeSize(node), "invalid tree size"); + } + + 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 idxToAdd 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; + } + + int addedTreeSize = treeSize[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 (enableRandomization && 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 + * @since 3.1 + */ + 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 cannot be used to reduce the amount of memory used by the collection. + * + * @param newSize + * @since 3.1 + */ + public final void setCapacity(int newSize) { + if (newSize > contents.length) { + setArraySize(newSize); + } + } + + /** + * Adjusts the capacity of the array. + * + * @param newCapacity + * @since 3.1 + */ + 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 + * @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 + * @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; + } + } + } + + /** + * Returns the Edge whose target is the given node + * @param targetNode + * @return + * @since 3.1 + */ + private Edge getEdgeTo(int targetNode) { + int parent = parentTree[targetNode]; + + int direction = DIR_LEFT; + + if (parent == -1) { + if (root == targetNode) { + direction = DIR_ROOT; + } else if (firstUnusedNode == targetNode){ + direction = DIR_UNUSED; + } + } else { + if (leftSubTree[parent] == targetNode) { + direction = DIR_LEFT; + } else if (rightSubTree[parent] == targetNode) { + direction = DIR_RIGHT; + } else if (nextUnsorted[parent] == targetNode) { + direction = DIR_UNSORTED; + } + } + + return new Edge(parent, direction); + } + + 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 toRecompute + * @param stopAtNode + * @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]; + } + } + + /** + * @param subTree + * @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 + * @since 3.1 + */ + public final void add(Object 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. + * + * @param toAdd + * @since 3.1 + */ + public final void addAll(Collection toAdd) { + Iterator iter = toAdd.iterator(); + while (iter.hasNext()) { + add(iter.next()); + } + + testInvariants(); + } + + /** + * Adds all items from the given array to the collection + * @param toAdd + * @since 3.1 + */ + public final void addAll(Object[] toAdd) { + for (int i = 0; i < toAdd.length; i++) { + Object object = toAdd[i]; + + add(object); + } + + testInvariants(); + } + + /** + * Returns true iff the collection is empty + * + * @return + * @since 3.1 + */ + public final boolean isEmpty() { + boolean result = (root == -1); + + testInvariants(); + + return result; + } + + /** + * Removes the given object from the collection + * + * @param toRemove + * @since 3.1 + */ + public final void remove(Object toRemove) { + internalRemove(toRemove); + + pack(); + + testInvariants(); + } + + /** + * @param toRemove + * @since 3.1 + */ + 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(); + } + + public final void removeAll(Collection toRemove, IProgressMonitor mon) throws InterruptedException { + for (Iterator iter = toRemove.iterator(); iter.hasNext();) { + Object next = (Object) iter.next(); + + internalRemove(next); + } + + testInvariants(); + + pack(); + + testInvariants(); + } + + public final void removeAll(Object[] toRemove, IProgressMonitor mon) throws InterruptedException { + for (int i = 0; i < toRemove.length; i++) { + Object object = toRemove[i]; + + internalRemove(object); + } + + testInvariants(); + + pack(); + + testInvariants(); + } + + /** + * Retains the first n 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 toRetain + * @return + * @since 3.1 + */ + public final void retainFirst(int n, FastProgressReporter mon) throws InterruptedException { + int sz = size(); + + if (n >= sz) { + return; + } + + removeRange(n, sz - n, mon); + + testInvariants(); + } + + public final void retainFirst(int n) { + try { + retainFirst(n, new FastProgressReporter()); + } catch (InterruptedException e) { + } + + testInvariants(); + } + + public final void removeRange(int first, int length) { + try { + removeRange(first, length, new FastProgressReporter()); + } catch (InterruptedException e) { + } + + testInvariants(); + } + + public 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 + * @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 + * + * @since 3.1 + */ + public final void clear() { + lastNode = 0; + setArraySize(MIN_CAPACITY); + root = -1; + firstUnusedNode = -1; + objectIndices = null; + + testInvariants(); + } + + public Comparator getComparator() { + return comparator; + } + + /** + * Fills in an array of size n with the n smallest elements from the collection. + * Note that the returned elements are not sorted, however these would be the first + * elements in the list if the collection were sorted. Returns the number of elements + * inserted into the result array (this will always equal the length of the array if + * the array is smaller than the size of the collection). + * + *+ * When returning a sorted array, the algorithm runs in O(s + n * lg (n)) and when returning + * an unsorted array, the algorithm runs in O(s + n) time, where s is the size of the collection + * and n is the size of the output. The partial sort order computed in previous calls to + * this method is remembered and used to speed up subsequent calls. That is, if this method is + * called twice on the same range, its runtime will be closer to O(n) on subsequent calls (regardless + * of sorting). + *
+ * + * @param result + * @since 3.1 + */ + public final int getFirst(Object[] result, boolean sorted, FastProgressReporter mon) throws InterruptedException { + int returnValue = getRange(result, 0, sorted, mon); + + testInvariants(); + + return returnValue; + } + + 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) would fill in myArray starting with the 10th smallest item + * in the collection. + * + *+ * When returning a sorted array, the algorithm runs in O(s + n * lg (n)) and when returning + * an unsorted array, the algorithm runs in O(s + n) time, where s is the size of the collection + * and n is the size of the output. The partial sort order computed in previous calls to + * this method is remembered and used to speed up subsequent calls. That is, if this method is + * called twice on the same range, its runtime will be closer to O(n) on subsequent calls (regardless + * of sorting). + *
+ * + * Returns the number of elements + * inserted into the result array (this will always equal the length of the array if + * the array is smaller than the size of the collection). + * + * @param result + * @since 3.1 + */ + public final int getRange(Object[] result, int rangeStart, boolean sorted, FastProgressReporter mon) throws InterruptedException { + return getRange(result, 0, rangeStart, root, sorted, mon); + } + + 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 + * + * @param index + * @return + * @since 3.1 + */ + 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; + } + + 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; + } + + /** + * @param item + * @return + * @since 3.1 + */ + public boolean contains(Object item) { + boolean returnValue = (getObjectIndex(item) != -1); + + testInvariants(); + + return returnValue; + } +} Index: src/org/eclipse/jface/viewers/deferred/SynchronousTableManager.java =================================================================== RCS file: src/org/eclipse/jface/viewers/deferred/SynchronousTableManager.java diff -N src/org/eclipse/jface/viewers/deferred/SynchronousTableManager.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/jface/viewers/deferred/SynchronousTableManager.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,96 @@ +/******************************************************************************* + * Copyright (c) 2004 IBM Corporation and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Common Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/cpl-v10.html + * + * Contributors: + * IBM Corporation - initial API and implementation + *******************************************************************************/ +package org.eclipse.jface.viewers.deferred; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Comparator; + +import org.eclipse.core.runtime.IProgressMonitor; + +/** + * @since 3.1 + */ +public class SynchronousTableManager extends TableManager { + + private int limit = 100; + private IConcurrentContentProvider content; + private IConcurrentTable table; + private Comparator sortOrder; + private Collection allElement = new ArrayList(); + private Object[] sentElements = new Object[0]; + private int rangeStart = 0; + private int rangeLength = 0; + + public void SynchronousTableManager(IConcurrentTable table, IConcurrentContentProvider contentProvider, Comparator sortOrder) { + content = contentProvider; + this.table = table; + this.sortOrder = sortOrder; + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#add(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor) + */ + public void add(Collection items, IProgressMonitor mon) { + + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#remove(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor) + */ + public void remove(Collection items, IProgressMonitor mon) { + + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#update(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor) + */ + public void update(Collection items, IProgressMonitor mon) { + + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#refresh(org.eclipse.core.runtime.IProgressMonitor) + */ + public void refresh(IProgressMonitor monitor) { + + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#setSortOrder(java.util.Comparator) + */ + public void setSortOrder(Comparator sorter) { + + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#setRangeOfInterest(int, int) + */ + public void setRangeOfInterest(int start, int length) { + rangeStart = start; + rangeLength = length; + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#setLimit(int) + */ + public void setLimit(int maxTableSize) { + + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#getLimit() + */ + public int getLimit() { + return 0; + } + +} Index: src/org/eclipse/jface/viewers/deferred/TableManager.java =================================================================== RCS file: src/org/eclipse/jface/viewers/deferred/TableManager.java diff -N src/org/eclipse/jface/viewers/deferred/TableManager.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/jface/viewers/deferred/TableManager.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,32 @@ +/******************************************************************************* + * Copyright (c) 2004 IBM Corporation and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Common Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/cpl-v10.html + * + * Contributors: + * IBM Corporation - initial API and implementation + *******************************************************************************/ +package org.eclipse.jface.viewers.deferred; + +import java.util.Collection; +import java.util.Comparator; + +import org.eclipse.core.runtime.IProgressMonitor; + +/** + * + * Not intended to be subclassed by clients + * @since 3.1 + */ +public abstract class TableManager { + public abstract void add(Collection items, IProgressMonitor mon); + public abstract void remove(Collection items, IProgressMonitor mon); + public abstract void update(Collection items, IProgressMonitor mon); + public abstract void refresh(IProgressMonitor monitor); + public abstract void setSortOrder(Comparator sorter); + public abstract void setRangeOfInterest(int start, int length); + public abstract void setLimit(int maxTableSize); + public abstract int getLimit(); +} Content-Type: text/plain Index: src/org/eclipse/jface/viewers/deferred/AbstractConcurrentContentProvider.java =================================================================== RCS file: src/org/eclipse/jface/viewers/deferred/AbstractConcurrentContentProvider.java diff -N src/org/eclipse/jface/viewers/deferred/AbstractConcurrentContentProvider.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/jface/viewers/deferred/AbstractConcurrentContentProvider.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,66 @@ +/******************************************************************************* + * Copyright (c) 2004 IBM Corporation and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Common Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/cpl-v10.html + * + * Contributors: + * IBM Corporation - initial API and implementation + *******************************************************************************/ +package org.eclipse.jface.viewers.deferred; + +import org.eclipse.jface.util.ListenerList; + +/** + * @since 3.1 + */ +public abstract class AbstractConcurrentContentProvider implements + IConcurrentContentProvider { + + private ListenerList listeners = new ListenerList(); + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.IConcurrentContentProvider#addListener(org.eclipse.jface.viewers.deferred.IConcurrentContentProviderListener) + */ + public void addListener(IConcurrentContentProviderListener listener) { + listeners.add(listener); + } + + protected void fireAdd(Object[] added) { + Object[] listenerArray = listeners.getListeners(); + + for (int i = 0; i < listenerArray.length; i++) { + IConcurrentContentProviderListener next = (IConcurrentContentProviderListener) listenerArray[i]; + + next.add(added); + } + } + + protected void fireRemove(Object[] removed) { + Object[] listenerArray = listeners.getListeners(); + + for (int i = 0; i < listenerArray.length; i++) { + IConcurrentContentProviderListener next = (IConcurrentContentProviderListener) listenerArray[i]; + + next.remove(removed); + } + } + + protected void fireUpdate(Object[] updated) { + Object[] listenerArray = listeners.getListeners(); + + for (int i = 0; i < listenerArray.length; i++) { + IConcurrentContentProviderListener next = (IConcurrentContentProviderListener) listenerArray[i]; + + next.update(updated); + } + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.IConcurrentContentProvider#removeListener(org.eclipse.jface.viewers.deferred.IConcurrentContentProviderListener) + */ + public void removeListener(IConcurrentContentProviderListener listener) { + listeners.remove(listener); + } +} Index: src/org/eclipse/jface/viewers/deferred/ConcurrentTableManager.java =================================================================== RCS file: src/org/eclipse/jface/viewers/deferred/ConcurrentTableManager.java diff -N src/org/eclipse/jface/viewers/deferred/ConcurrentTableManager.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/jface/viewers/deferred/ConcurrentTableManager.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,305 @@ +/******************************************************************************* + * Copyright (c) 2004 IBM Corporation and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Common Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/cpl-v10.html + * + * Contributors: + * IBM Corporation - initial API and implementation + *******************************************************************************/ +package org.eclipse.jface.viewers.deferred; + +import java.util.Comparator; + +import org.eclipse.core.runtime.IProgressMonitor; +import org.eclipse.core.runtime.IStatus; +import org.eclipse.core.runtime.NullProgressMonitor; +import org.eclipse.core.runtime.Status; +import org.eclipse.core.runtime.jobs.Job; +import org.eclipse.swt.widgets.Display; + +/** + * @since 3.1 + */ +public final class ConcurrentTableManager implements IConcurrentContentProviderListener { + + private int limit = -1; + private IConcurrentContentProvider content; + private IConcurrentTable table; + private Comparator sortOrder; + private boolean containsUnsorted = false; + private boolean dirty = false; + + private LazySortedCollection sorter; + private volatile FastProgressReporter searchReporter = null; + + // Any thread accessing the following objects should synchronize on uiMutex. + // The UI thread will wait on this lock, so it should never be held for anything + // but trivial operations, and threads should never wait for other locks while holding + // uiMutex. + private ConcurrentTableUpdator updator; + private Object sortMutex = new Object(); + private int sortStart = -1; + private int sortLength = -1; + + private Job sortJob = new Job("sorting") { + protected IStatus run(IProgressMonitor monitor) { + doSort(monitor); + return Status.OK_STATUS; + } + }; + + public ConcurrentTableManager(IConcurrentTable table, + IConcurrentContentProvider contentProvider, Comparator sortOrder, + Display display) { + + updator = new ConcurrentTableUpdator(table, display); + content = contentProvider; + this.table = table; + this.sortOrder = sortOrder; + sorter = new LazySortedCollection(sortOrder); + sortJob.setSystem(true); + sortJob.setPriority(Job.SHORT); + contentProvider.addListener(this); + } + + public void dispose() { + content.removeListener(this); + } + + public void refresh() { + content.requestUpdate(this); + } + + /** + * Called from sortJob. Sorts the elements defined by sortStart and sortLength. + * Schedules a UI update when finished + * + * @param mon + * @since 3.1 + */ + private void doSort(IProgressMonitor mon) { + LazySortedCollection collection; + + // Workaround for some weirdness in the Jobs framework: if you cancel a monitor + // for a job that has ended and reschedule that same job, it will start + // the job with a monitor that is already cancelled. We can workaround this by + // removing all references to the progress monitor whenever the job terminates, + // but this would require additional synchronize blocks (which are slow) and more + // complexity. Instead, we just un-cancel the monitor at the start of each job. + mon.setCanceled(false); + + synchronized(sortMutex) { + ConcurrentTableUpdator.Range currentRange = updator.getRange(); + sortStart = currentRange.start; + sortLength = currentRange.length; + collection = sorter; + } + + mon.beginTask("sorting", 100); + try { + + // First, sort the objects that are currently visible in the table + Object[] objectsOfInterest; + int totalElements = 0; + + synchronized(collection) { + FastProgressReporter subMon = new FastProgressReporter(mon, 50); + searchReporter = subMon; + totalElements = collection.size(); + if (limit != -1) { + if (totalElements > limit) { + totalElements = limit; + } + } + + // Send the total items to the updator ASAP -- the user may want + // to scroll to a different section of the table, which would + // cause our sort range to change and cause this job to get cancelled. + updator.setTotalItems(totalElements); + + if (limit != -1) { + collection.retainFirst(limit, subMon); + } + + sortLength = Math.min(sortLength, totalElements - sortStart); + sortLength = Math.max(sortLength, 0); + + objectsOfInterest = new Object[sortLength]; + + collection.getRange(objectsOfInterest, sortStart, true, subMon); + searchReporter = null; + } + + updator.setElements(objectsOfInterest, sortStart, sortLength); + + if (mon.isCanceled()) { + return; + } + + // Finally, sort all objects in the collection + synchronized(collection) { + objectsOfInterest = new Object[collection.size()]; + + FastProgressReporter subMon = new FastProgressReporter(mon, 50); + searchReporter = subMon; + collection.getFirst(objectsOfInterest, true, subMon); + searchReporter = null; + } + + updator.setElements(objectsOfInterest, 0, totalElements); + containsUnsorted = false; + } catch (InterruptedException e) { + mon.setCanceled(true); + } finally { + searchReporter = null; + mon.done(); + } + + } + + public void setSortOrder(Comparator sorter) { + this.sortOrder = sorter; + refresh(); + } + + public void setLimit(int limit) { + this.limit = limit; + refresh(); + } + + public int getLimit() { + return limit; + } + + public void setRangeOfInterest(int start, int length) { + updator.setRangeOfInterest(start, length); + triggerSort(); + } + + private void makeDirty() { + synchronized(sortMutex) { + dirty = true; + containsUnsorted = true; + triggerSort(); + } + } + + private void triggerSort() { + synchronized(sortMutex) { + // If we've already sent everything to the updator, there is nothing to do. + if (!containsUnsorted) { + return; + } + + ConcurrentTableUpdator.Range range = updator.getRange(); + + if (dirty || sortStart != range.start || sortLength != range.length) { + dirty = false; + cancelSortJob(); + sortJob.schedule(); + } + } + } + + private void cancelSortJob() { + FastProgressReporter rep = searchReporter; + if (rep != null) { + rep.cancel(); + } + sortJob.cancel(); + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#add(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor) + */ + public void add(Object[] toAdd) { + cancelSortJob(); + LazySortedCollection collection = sorter; + synchronized(collection) { + collection.addAll(toAdd); + makeDirty(); + } + } + + public void setContents(Object[] contents) { + LazySortedCollection collection = sorter; + synchronized(collection) { + // Flush all current items + flush(collection.getItems(false), collection); + + //LazySortedCollection newCollection = new LazySortedCollection(sortOrder); + //newCollection.addAll(contents); + } + + synchronized(sortMutex) { + LazySortedCollection newCollection = new LazySortedCollection(sortOrder); + newCollection.addAll(contents); + this.sorter = newCollection; + makeDirty(); + } + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#remove(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor) + */ + public void remove(Object[] toRemove) { + cancelSortJob(); + LazySortedCollection collection = sorter; + synchronized(collection) { + + try { + collection.removeAll(toRemove, new NullProgressMonitor()); + } catch (InterruptedException e) { + } + + flush(toRemove, collection); + + makeDirty(); + } + refresh(); + } + + /** + * @param toRemove + * @param collection + * @since 3.1 + */ + private void flush(Object[] toRemove, LazySortedCollection collection) { + for (int i = 0; i < toRemove.length; i++) { + Object item = toRemove[i]; + + if (collection.contains(item)) { + updator.flushCache(item); + } + } + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#update(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor) + */ + public void update(Object[] items) { + + boolean dirty = false; + LazySortedCollection collection = sorter; + synchronized(collection) { + for (int i = 0; i < items.length; i++) { + Object item = items[i]; + + if (collection.contains(item)) { + // TODO: write a collection.update(...) method + collection.remove(item); + collection.add(item); + updator.flushCache(item); + + dirty = true; + } + } + + if (dirty) { + makeDirty(); + } + } + } +} Index: src/org/eclipse/jface/viewers/deferred/ConcurrentTableUpdator.java =================================================================== RCS file: src/org/eclipse/jface/viewers/deferred/ConcurrentTableUpdator.java diff -N src/org/eclipse/jface/viewers/deferred/ConcurrentTableUpdator.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/jface/viewers/deferred/ConcurrentTableUpdator.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,326 @@ +/******************************************************************************* + * Copyright (c) 2004 IBM Corporation and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Common Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/cpl-v10.html + * + * Contributors: + * IBM Corporation - initial API and implementation + *******************************************************************************/ +package org.eclipse.jface.viewers.deferred; + +import org.eclipse.swt.widgets.Display; + + +/** + * @since 3.1 + */ +public class ConcurrentTableUpdator { + private IConcurrentTable table; + + /** + * Set of all non-flushed elements known to this updator. Maps elements + * onto sort positions. + */ + private IntHashMap sentIndices = new IntHashMap(); + + /** + * The array of objects that has been sent to the UI. Maps indices onto elements. + */ + private Object[] sentObjects = new Object[0]; + + private IntHashMap knownIndices = new IntHashMap(); + + private Object[] knownObjects = new Object[0]; + + // Minimum length for the pendingFlushes stack + private static final int MIN_FLUSHLENGTH = 64; + + // Stack of pending indices to flush + private Object[] pendingFlushes = new Object[MIN_FLUSHLENGTH]; + private int lastFlush = 0; + + private int totalElements = 0; + private Display display; + private int rangeStart; + private int rangeLength; + private boolean updateScheduled; + + public final static class Range { + int start = 0; + int length = 0; + + public Range(int s, int l) { + start = s; + length = l; + } + } + + Runnable uiRunnable = new Runnable() { + public void run() { + synchronized(this) { + updateScheduled = false; + } + updateTable(); + } + }; + + public ConcurrentTableUpdator(IConcurrentTable table, Display display) { + this.table = table; + this.display = display; + } + + public Range getRange() { + synchronized(this) { + return new Range(rangeStart, rangeLength); + } + } + + /** + * Updates all elements in the given range + * + * @param changedElements + * @param rangeStart + * @param rangeLength + * @since 3.1 + */ + public void setElements(Object[] changedElements, int start, int length) { + int len = Math.min(changedElements.length, length); + boolean visibleDirty = false; + + synchronized(this) { + for (int i = 0; i < len; i++) { + int element = i + start; + Object object = changedElements[i]; + + Object oldObject = knownObjects[element]; + + if (oldObject != object && isVisible(element)) { + visibleDirty = true; + } + + knownObjects[element] = object; + } + + if (visibleDirty) { + scheduleUIUpdate(); + } + } + + } + + /** + * @param element + * @return + * @since 3.1 + */ + private boolean isVisible(int element) { + return element >= rangeStart && element < rangeStart + rangeLength; + } + + public void flushCache(Object toFlush) { + synchronized(this) { + int currentIdx = knownIndices.get(toFlush, -1); + + // If we've never heard of this object, bail out. + if (currentIdx == -1) { + return; + } + + knownIndices.remove(toFlush); + knownObjects[currentIdx] = null; + + // If we've sent this object to the UI, schedule a flush + int sentIdx = sentIndices.get(toFlush, -1); + if (sentIdx != -1) { + pushFlush(toFlush); + + sentIndices.remove(toFlush); + sentObjects[sentIdx] = null; + + scheduleUIUpdate(); + } + } + + } + + /** + * Sets the size of the table. Called from a background thread. + * + * @param newTotal + * @since 3.1 + */ + public void setTotalItems(int newTotal) { + synchronized (this) { + if (newTotal != knownObjects.length) { + if (newTotal < knownObjects.length) { + // Flush any objects that are being removed as a result of the resize + for (int i = newTotal; i < knownObjects.length; i++) { + Object toFlush = knownObjects[i]; + + if (toFlush != null) { + flushCache(toFlush); + } + } + } + + int minSize = Math.min(knownObjects.length, newTotal); + + Object[] newKnownObjects = new Object[newTotal]; + System.arraycopy(knownObjects, 0, newKnownObjects, 0, minSize); + knownObjects = newKnownObjects; + + scheduleUIUpdate(); + } + } + } + + /** + * Pushes an object onto the flush stack + * @param toFlush + * @since 3.1 + */ + private void pushFlush(Object toFlush) { + if (lastFlush >= pendingFlushes.length) { + int newCapacity = Math.min(MIN_FLUSHLENGTH, lastFlush * 2); + Object[] newPendingFlushes = new Object[newCapacity]; + System.arraycopy(pendingFlushes, 0, newPendingFlushes, 0, lastFlush); + pendingFlushes = newPendingFlushes; + } + + pendingFlushes[lastFlush++] = toFlush; + } + + /** + * + * @param idx + * @param element + * @since 3.1 + */ + public void update(int idx, Object value) { + // Keep the synchronized block as small as possible, since the UI may + // be waiting on it. + synchronized(this) { + Object oldObject = knownObjects[idx]; + + if (oldObject != value && isVisible(idx)) { + knownObjects[idx] = value; + + scheduleUIUpdate(); + } + } + } + + /** + * Called whenever the set of visible items in the table changes. + * Must be called from the UI thread. Will ensure that the + * set of visible items is up-to-date. + * + * @param start + * @param length + * @since 3.1 + */ + public void setRangeOfInterest(int start, int length) { + synchronized (this) { + if (rangeStart == start && rangeLength == length) { + return; + } + + rangeStart = start; + rangeLength = length; + } + + updateTable(); + } + + /** + * Schedules a UI update + * + * @since 3.1 + */ + private void scheduleUIUpdate() { + synchronized(this) { + if (!updateScheduled) { + updateScheduled = true; + display.asyncExec(uiRunnable); + } + } + } + + private boolean hasPendingFlushes() { + return lastFlush != 0; + } + + /** + * Sends all known items in the given range to the table. Must be called from the + * UI thread. Returns the number of items in the range that haven't been computed yet. + * + * @param start + * @param length + * @since 3.1 + */ + private void updateTable() { + int counter = 0; + + Object[] flushes = null; + int localNumFlushes = 0; + Object[] elementsToSend = null; + int newLength = -1; + int start = 0; + int length = 0; + + // Copy everything to local variables -- don't make any calls to other + // objects while we're inside our synchronized block. + synchronized (this) { + start = rangeStart; + length = rangeLength; + + if (lastFlush > 0) { + localNumFlushes = lastFlush; + flushes = pendingFlushes; + pendingFlushes = new Object[MIN_FLUSHLENGTH]; + lastFlush = 0; + } + + // Check if we need to resize the table + if (knownObjects.length != sentObjects.length) { + newLength = knownObjects.length; + + Object[] newSentObjects = new Object[knownObjects.length]; + System.arraycopy(sentObjects, 0, newSentObjects, 0, + Math.min(knownObjects.length, sentObjects.length)); + sentObjects = newSentObjects; + } + + length = Math.min(length, sentObjects.length - start); + + if (length > 0) { + elementsToSend = new Object[length]; + for (int i = 0; i < elementsToSend.length; i++) { + int element = i + start; + + Object object = knownObjects[element]; + if (object != sentObjects[element]) { + elementsToSend[i] = object; + } + } + } + } + + for (int idx = 0; idx < localNumFlushes; idx++) { + table.flushCache(flushes[idx]); + } + + if (newLength != -1) { + table.setTotalItems(newLength); + } + + for (int idx = 0; idx < length; idx++) { + Object next = elementsToSend[idx]; + if (next != null) { + table.update(idx + start, next); + } + } + } +} Index: src/org/eclipse/jface/viewers/deferred/FastProgressReporter.java =================================================================== RCS file: src/org/eclipse/jface/viewers/deferred/FastProgressReporter.java diff -N src/org/eclipse/jface/viewers/deferred/FastProgressReporter.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/jface/viewers/deferred/FastProgressReporter.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,134 @@ +/******************************************************************************* + * Copyright (c) 2004 IBM Corporation and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Common Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/cpl-v10.html + * + * Contributors: + * IBM Corporation - initial API and implementation + *******************************************************************************/ +package org.eclipse.jface.viewers.deferred; + +import org.eclipse.core.runtime.IProgressMonitor; + +/** + * @since 3.1 + */ +public final class FastProgressReporter { + private IProgressMonitor monitor; + private volatile boolean canceled = false; + private int cancelCheck = 0; + private String taskName; + + private int taskDepth = 0; + private int subTaskSize = 1; + private int totalWork = 1; + private int parentWork = 1; + private int monitorUnitsRemaining; + + private static int CANCEL_CHECK_PERIOD = 40; + + /** + * Constructs a null FastProgressReporter + */ + public FastProgressReporter() { + } + + /** + * Constructs a FastProgressReporter that wraps the given progress monitor + * + * @param taskName + * @param monitor + */ + public FastProgressReporter(IProgressMonitor monitor, int totalProgress) { + this.monitor = monitor; + monitorUnitsRemaining = totalProgress; + canceled = monitor.isCanceled(); + } + +// /** +// * Every call to beginTask must have a corresponding call to endTask, with the +// * same argument. +// * +// * @param totalWork +// * @since 3.1 +// */ +// public void beginTask(int totalWork) { +// +// if (monitor == null) { +// return; +// } +// +// taskDepth++; +// +// if (totalWork == 0) { +// return; +// } +// +// this.totalWork *= totalWork; +// } +// +// public void beginSubTask(int subTaskWork) { +// subTaskSize *= subTaskWork; +// } +// +// public void endSubTask(int subTaskWork) { +// subTaskSize /= subTaskWork; +// } +// +// public void worked(int amount) { +// amount *= subTaskSize; +// +// if (amount > totalWork) { +// amount = totalWork; +// } +// +// int consumed = monitorUnitsRemaining * amount / totalWork; +// +// if (consumed > 0) { +// monitor.worked(consumed); +// monitorUnitsRemaining -= consumed; +// } +// totalWork -= amount; +// } +// +// public void endTask(int totalWork) { +// taskDepth--; +// +// if (taskDepth == 0) { +// if (monitor != null && monitorUnitsRemaining > 0) { +// monitor.worked(monitorUnitsRemaining); +// } +// } +// +// if (totalWork == 0) { +// return; +// } +// +// this.totalWork /= totalWork; +// +// } + + public boolean isCanceled() { + if (monitor == null) { + return canceled; + } + + cancelCheck++; + if (cancelCheck > CANCEL_CHECK_PERIOD) { + canceled = monitor.isCanceled(); + cancelCheck = 0; + } + return canceled; + } + + public void cancel() { + canceled = true; + + if (monitor == null) { + return; + } + monitor.setCanceled(true); + } +} Index: src/org/eclipse/jface/viewers/deferred/IConcurrentContentProvider.java =================================================================== RCS file: src/org/eclipse/jface/viewers/deferred/IConcurrentContentProvider.java diff -N src/org/eclipse/jface/viewers/deferred/IConcurrentContentProvider.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/jface/viewers/deferred/IConcurrentContentProvider.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,33 @@ +/******************************************************************************* + * Copyright (c) 2004 IBM Corporation and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Common Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/cpl-v10.html + * + * Contributors: + * IBM Corporation - initial API and implementation + *******************************************************************************/ +package org.eclipse.jface.viewers.deferred; + + +/** + * @since 3.1 + */ +public interface IConcurrentContentProvider { + + /** + * Called by a listener to request an update. The receiver should call + * the given listener's setContents(...) method at its earliest convenience. + * The receiver is allowed to compute the elements asynchronously. That is, + * it can compute the result in a background thread and call setContents(...) + * once the result is ready. + * + * @param listener + * @since 3.1 + */ + public void requestUpdate(IConcurrentContentProviderListener listener); + + public void addListener(IConcurrentContentProviderListener listener); + public void removeListener(IConcurrentContentProviderListener listener); +} Index: src/org/eclipse/jface/viewers/deferred/IConcurrentContentProviderListener.java =================================================================== RCS file: src/org/eclipse/jface/viewers/deferred/IConcurrentContentProviderListener.java diff -N src/org/eclipse/jface/viewers/deferred/IConcurrentContentProviderListener.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/jface/viewers/deferred/IConcurrentContentProviderListener.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,28 @@ +/******************************************************************************* + * Copyright (c) 2004 IBM Corporation and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Common Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/cpl-v10.html + * + * Contributors: + * IBM Corporation - initial API and implementation + *******************************************************************************/ +package org.eclipse.jface.viewers.deferred; + +/** + * @since 3.1 + */ +public interface IConcurrentContentProviderListener { + public void add(Object[] added); + public void remove(Object[] removed); + public void update(Object[] changed); + + /** + * Sends the complete set of elements in the model. + * + * @param newContents + * @since 3.1 + */ + public void setContents(Object[] newContents); +} Index: src/org/eclipse/jface/viewers/deferred/IConcurrentTable.java =================================================================== RCS file: src/org/eclipse/jface/viewers/deferred/IConcurrentTable.java diff -N src/org/eclipse/jface/viewers/deferred/IConcurrentTable.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/jface/viewers/deferred/IConcurrentTable.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,43 @@ +/******************************************************************************* + * Copyright (c) 2004 IBM Corporation and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Common Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/cpl-v10.html + * + * Contributors: + * IBM Corporation - initial API and implementation + *******************************************************************************/ +package org.eclipse.jface.viewers.deferred; + +/** + * @since 3.1 + */ +public interface IConcurrentTable { + /** + * Tells the receiver that it should remove any cached information about the given + * element. Either the element has changed or is about to be removed. The row + * that was previously occupied by the element will be filled by a subsequent call + * to update(...) + * + * @param element + * @since 3.1 + */ + public void flushCache(Object element); + + /** + * Updates the contents of the item on the itemIndex row. It should be filled + * in using the given element. + * + * The receiver is allowed to cache properties of the given object. If a subsequent + * call to update(...) is made moving the object to a new row, the receiver can + * reuse cached values rather than computing them again. A call to flushCache(...) + * will indicate that cached values may have been changed. + * + * @param itemIndex + * @param element + * @since 3.1 + */ + public void update(int itemIndex, Object element); + public void setTotalItems(int total); +} Index: src/org/eclipse/jface/viewers/deferred/IntHashMap.java =================================================================== RCS file: src/org/eclipse/jface/viewers/deferred/IntHashMap.java diff -N src/org/eclipse/jface/viewers/deferred/IntHashMap.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/jface/viewers/deferred/IntHashMap.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,59 @@ +/******************************************************************************* + * Copyright (c) 2004 IBM Corporation and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Common Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/cpl-v10.html + * + * Contributors: + * IBM Corporation - initial API and implementation + *******************************************************************************/ +package org.eclipse.jface.viewers.deferred; + +import java.util.HashMap; + +/** + * Represents a map of objects onto ints. This is intended for future optimization: + * using the concrete int class would allow for an implementation that doesn't require + * additional object allocations for Integers. However, the current implementation + * simply delegates to the Java HashMap class. + * + * @since 3.1 + */ +public class IntHashMap { + private HashMap map; + + public IntHashMap(int size, float loadFactor) { + map = new HashMap(size, loadFactor); + } + + public IntHashMap() { + map = new HashMap(); + } + + public void remove(Object key) { + map.remove(key); + } + + public void put(Object key, int value) { + map.put(key, new Integer(value)); + } + + public int get(Object key) { + return get(key, 0); + } + + public int get(Object key, int defaultValue) { + Integer result = (Integer)map.get(key); + + if (result != null) { + return result.intValue(); + } + + return defaultValue; + } + + public boolean containsKey(Object key) { + return map.containsKey(key); + } +} Index: src/org/eclipse/jface/viewers/deferred/LazySortedCollection.java =================================================================== RCS file: src/org/eclipse/jface/viewers/deferred/LazySortedCollection.java diff -N src/org/eclipse/jface/viewers/deferred/LazySortedCollection.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/jface/viewers/deferred/LazySortedCollection.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,1482 @@ +/******************************************************************************* + * Copyright (c) 2004 IBM Corporation and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Common Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/cpl-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.core.runtime.IProgressMonitor; +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. + * + *+ * 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. + *
+ *+ * 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. + *
+ * + * @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; + public boolean enableRandomization = true; + + // Cancellation support + private IProgressMonitor progressMonitor = null; + // Normally, we return this cached result when determining if + // we're cancelled. However, periodically (whenever cancelCheckCounter reaches 0) + // we will update the cached value by calling progressMonitor.isCancelled(). + // The rest of these "cancellation + private boolean cancelled = false; + private int cancelCheckCounter = 0; + // Minimum milliseconds between each call to isCancelled + private static final int CANCEL_CHECK_PERIOD = 50; + // Minimum number of elements to process before calling isCancelled + private static final int MIN_CANCEL_CHECK_FREQUENCY = 10; + // Number of bogus checks before a real + private int cancelCheckFrequency = MIN_CANCEL_CHECK_FREQUENCY; + // Timestamp of the last call to isCancelled + private long lastCancelCheckTimestamp = 0; + + + // 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"; + } + }; + + 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 void copy(Edge toCopy) { + startNode = toCopy.startNode; + direction = toCopy.direction; + } + + 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; + } + } + + private void setNextUnsorted(int parent, int next) { + nextUnsorted[parent] = next; + if (next != -1) { + parentTree[next] = parent; + } + recomputeTreeSize(parent); + } + + public LazySortedCollection(Comparator c) { + this.comparator = c; + } + + public void print() { + StringBuffer buf = new StringBuffer(); + System.out.println("----"); + print(0, root); + + System.out.println(buf.toString()); + } + + private String indent(int indent) { + String output = ""; + + for(int i = 0; i < indent; i++) { + output += " "; + } + + return output; + } + + public void print(int indent, int nodeToPrint) { + + String indentString = indent(indent); + if (nodeToPrint == -1) { + System.out.println("null\n"); + return; + } + + if (leftSubTree[nodeToPrint] != -1) { + System.out.println(indentString + "left " + leftSubTree[nodeToPrint]); + print(indent + 1, leftSubTree[nodeToPrint]); + } + + System.out.println(indentString + "value {" + contents[nodeToPrint] + "}"); + int next = nextUnsorted[nodeToPrint]; + while (next != -1) { + System.out.println(indentString + "unsorted " + next + " {" + contents[next] + "}"); + next = nextUnsorted[next]; + } + + if (rightSubTree[nodeToPrint] != -1) { + System.out.println(indentString + "right " + rightSubTree[nodeToPrint]); + print(indent + 1, rightSubTree[nodeToPrint]); + } + } + + public void testInvariants() { + if (enableRandomization) { + 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"); + Assert.isTrue(right == -1, "unsorted nodes shouldn't have a right subtree"); + } + + if (left != -1) { + testInvariants(left); + Assert.isTrue(parentTree[left] == node, "left node has invalid parent pointer"); + } + if (right != -1) { + testInvariants(right); + Assert.isTrue(parentTree[right] == node, "right node has invalid parent pointer"); + } + + 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"); + Assert.isTrue(leftSubTree[unsorted] == -1, "unsorted nodes shouldn't have left subtrees"); + Assert.isTrue(rightSubTree[unsorted] == -1, "unsorted nodes shouldn't have right subtrees"); + Assert.isTrue(parentTree[unsorted] == previous, "unsorted node has invalid parent pointer"); + Assert.isTrue(contents[unsorted] != lazyRemovalFlag, "unsorted nodes should not be lazily removed"); + 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); + + if (treeSize != getSubtreeSize(node)) { + print(); + } + + Assert.isTrue(treeSize == getSubtreeSize(node), "invalid tree size"); + } + + 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 idxToAdd 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; + } + + int addedTreeSize = treeSize[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 (enableRandomization && 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 + * @since 3.1 + */ + 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 cannot be used to reduce the amount of memory used by the collection. + * + * @param newSize + * @since 3.1 + */ + public final void setCapacity(int newSize) { + if (newSize > contents.length) { + setArraySize(newSize); + } + } + + /** + * Adjusts the capacity of the array. + * + * @param newCapacity + * @since 3.1 + */ + 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 + * @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 + * @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; + } + } + } + + /** + * Returns the Edge whose target is the given node + * @param targetNode + * @return + * @since 3.1 + */ + private Edge getEdgeTo(int targetNode) { + int parent = parentTree[targetNode]; + + int direction = DIR_LEFT; + + if (parent == -1) { + if (root == targetNode) { + direction = DIR_ROOT; + } else if (firstUnusedNode == targetNode){ + direction = DIR_UNUSED; + } + } else { + if (leftSubTree[parent] == targetNode) { + direction = DIR_LEFT; + } else if (rightSubTree[parent] == targetNode) { + direction = DIR_RIGHT; + } else if (nextUnsorted[parent] == targetNode) { + direction = DIR_UNSORTED; + } + } + + return new Edge(parent, direction); + } + + 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 toRecompute + * @param stopAtNode + * @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]; + } + } + + /** + * @param subTree + * @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 + * @since 3.1 + */ + public final void add(Object 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. + * + * @param toAdd + * @since 3.1 + */ + public final void addAll(Collection toAdd) { + Iterator iter = toAdd.iterator(); + while (iter.hasNext()) { + add(iter.next()); + } + + testInvariants(); + } + + /** + * Adds all items from the given array to the collection + * @param toAdd + * @since 3.1 + */ + public final void addAll(Object[] toAdd) { + for (int i = 0; i < toAdd.length; i++) { + Object object = toAdd[i]; + + add(object); + } + + testInvariants(); + } + + /** + * Returns true iff the collection is empty + * + * @return + * @since 3.1 + */ + public final boolean isEmpty() { + boolean result = (root == -1); + + testInvariants(); + + return result; + } + + /** + * Removes the given object from the collection + * + * @param toRemove + * @since 3.1 + */ + public final void remove(Object toRemove) { + internalRemove(toRemove); + + pack(); + + testInvariants(); + } + + /** + * @param toRemove + * @since 3.1 + */ + 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(); + } + + public final void removeAll(Collection toRemove, IProgressMonitor mon) throws InterruptedException { + for (Iterator iter = toRemove.iterator(); iter.hasNext();) { + Object next = (Object) iter.next(); + + internalRemove(next); + } + + testInvariants(); + + pack(); + + testInvariants(); + } + + public final void removeAll(Object[] toRemove, IProgressMonitor mon) throws InterruptedException { + for (int i = 0; i < toRemove.length; i++) { + Object object = toRemove[i]; + + internalRemove(object); + } + + testInvariants(); + + pack(); + + testInvariants(); + } + + /** + * Retains the first n 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 toRetain + * @return + * @since 3.1 + */ + public final void retainFirst(int n, FastProgressReporter mon) throws InterruptedException { + int sz = size(); + + if (n >= sz) { + return; + } + + removeRange(n, sz - n, mon); + + testInvariants(); + } + + public final void retainFirst(int n) { + try { + retainFirst(n, new FastProgressReporter()); + } catch (InterruptedException e) { + } + + testInvariants(); + } + + public final void removeRange(int first, int length) { + try { + removeRange(first, length, new FastProgressReporter()); + } catch (InterruptedException e) { + } + + testInvariants(); + } + + public 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 + * @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 + * + * @since 3.1 + */ + public final void clear() { + lastNode = 0; + setArraySize(MIN_CAPACITY); + root = -1; + firstUnusedNode = -1; + objectIndices = null; + + testInvariants(); + } + + public Comparator getComparator() { + return comparator; + } + + /** + * Fills in an array of size n with the n smallest elements from the collection. + * Note that the returned elements are not sorted, however these would be the first + * elements in the list if the collection were sorted. Returns the number of elements + * inserted into the result array (this will always equal the length of the array if + * the array is smaller than the size of the collection). + * + *+ * When returning a sorted array, the algorithm runs in O(s + n * lg (n)) and when returning + * an unsorted array, the algorithm runs in O(s + n) time, where s is the size of the collection + * and n is the size of the output. The partial sort order computed in previous calls to + * this method is remembered and used to speed up subsequent calls. That is, if this method is + * called twice on the same range, its runtime will be closer to O(n) on subsequent calls (regardless + * of sorting). + *
+ * + * @param result + * @since 3.1 + */ + public final int getFirst(Object[] result, boolean sorted, FastProgressReporter mon) throws InterruptedException { + int returnValue = getRange(result, 0, sorted, mon); + + testInvariants(); + + return returnValue; + } + + 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) would fill in myArray starting with the 10th smallest item + * in the collection. + * + *+ * When returning a sorted array, the algorithm runs in O(s + n * lg (n)) and when returning + * an unsorted array, the algorithm runs in O(s + n) time, where s is the size of the collection + * and n is the size of the output. The partial sort order computed in previous calls to + * this method is remembered and used to speed up subsequent calls. That is, if this method is + * called twice on the same range, its runtime will be closer to O(n) on subsequent calls (regardless + * of sorting). + *
+ * + * Returns the number of elements + * inserted into the result array (this will always equal the length of the array if + * the array is smaller than the size of the collection). + * + * @param result + * @since 3.1 + */ + public final int getRange(Object[] result, int rangeStart, boolean sorted, FastProgressReporter mon) throws InterruptedException { + return getRange(result, 0, rangeStart, root, sorted, mon); + } + + 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 + * + * @param index + * @return + * @since 3.1 + */ + 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; + } + + 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; + } + + /** + * @param item + * @return + * @since 3.1 + */ + public boolean contains(Object item) { + boolean returnValue = (getObjectIndex(item) != -1); + + testInvariants(); + + return returnValue; + } +} Index: src/org/eclipse/jface/viewers/deferred/SynchronousTableManager.java =================================================================== RCS file: src/org/eclipse/jface/viewers/deferred/SynchronousTableManager.java diff -N src/org/eclipse/jface/viewers/deferred/SynchronousTableManager.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/jface/viewers/deferred/SynchronousTableManager.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,96 @@ +/******************************************************************************* + * Copyright (c) 2004 IBM Corporation and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Common Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/cpl-v10.html + * + * Contributors: + * IBM Corporation - initial API and implementation + *******************************************************************************/ +package org.eclipse.jface.viewers.deferred; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Comparator; + +import org.eclipse.core.runtime.IProgressMonitor; + +/** + * @since 3.1 + */ +public class SynchronousTableManager extends TableManager { + + private int limit = 100; + private IConcurrentContentProvider content; + private IConcurrentTable table; + private Comparator sortOrder; + private Collection allElement = new ArrayList(); + private Object[] sentElements = new Object[0]; + private int rangeStart = 0; + private int rangeLength = 0; + + public void SynchronousTableManager(IConcurrentTable table, IConcurrentContentProvider contentProvider, Comparator sortOrder) { + content = contentProvider; + this.table = table; + this.sortOrder = sortOrder; + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#add(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor) + */ + public void add(Collection items, IProgressMonitor mon) { + + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#remove(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor) + */ + public void remove(Collection items, IProgressMonitor mon) { + + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#update(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor) + */ + public void update(Collection items, IProgressMonitor mon) { + + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#refresh(org.eclipse.core.runtime.IProgressMonitor) + */ + public void refresh(IProgressMonitor monitor) { + + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#setSortOrder(java.util.Comparator) + */ + public void setSortOrder(Comparator sorter) { + + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#setRangeOfInterest(int, int) + */ + public void setRangeOfInterest(int start, int length) { + rangeStart = start; + rangeLength = length; + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#setLimit(int) + */ + public void setLimit(int maxTableSize) { + + } + + /* (non-Javadoc) + * @see org.eclipse.jface.viewers.deferred.TableManager#getLimit() + */ + public int getLimit() { + return 0; + } + +} Index: src/org/eclipse/jface/viewers/deferred/TableManager.java =================================================================== RCS file: src/org/eclipse/jface/viewers/deferred/TableManager.java diff -N src/org/eclipse/jface/viewers/deferred/TableManager.java --- /dev/null 1 Jan 1970 00:00:00 -0000 +++ src/org/eclipse/jface/viewers/deferred/TableManager.java 1 Jan 1970 00:00:00 -0000 @@ -0,0 +1,32 @@ +/******************************************************************************* + * Copyright (c) 2004 IBM Corporation and others. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Common Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/cpl-v10.html + * + * Contributors: + * IBM Corporation - initial API and implementation + *******************************************************************************/ +package org.eclipse.jface.viewers.deferred; + +import java.util.Collection; +import java.util.Comparator; + +import org.eclipse.core.runtime.IProgressMonitor; + +/** + * + * Not intended to be subclassed by clients + * @since 3.1 + */ +public abstract class TableManager { + public abstract void add(Collection items, IProgressMonitor mon); + public abstract void remove(Collection items, IProgressMonitor mon); + public abstract void update(Collection items, IProgressMonitor mon); + public abstract void refresh(IProgressMonitor monitor); + public abstract void setSortOrder(Comparator sorter); + public abstract void setRangeOfInterest(int start, int length); + public abstract void setLimit(int maxTableSize); + public abstract int getLimit(); +}