lazysortedcollection.java

jfa2ce 源码帮助开发人员更好的理解运用

        rightSubTree = newRightSubTree;
        parentTree = newParentTree;
        
        if (root != -1) {
            root = mapOldIdxOntoNew[root];
        }
        
        // All unused nodes have been removed
        firstUnusedNode = -1;
        lastNode = newNodes;
    }
    
    /**
     * Adds the given object to the collection. Runs in O(1) amortized time.
     * 
     * @param toAdd object to add
     */
    public final void add(Object toAdd) {
    	Assert.isNotNull(toAdd);
        // Create the new node
        int newIdx = createNode(toAdd);
        
        // Insert the new node into the root tree
        setRootNode(addUnsorted(root, newIdx));
        
        testInvariants();
    }
    
    /**
     * Adds all items from the given collection to this collection 
     * 
     * @param toAdd objects to add
     */
    public final void addAll(Collection toAdd) {
    	Assert.isNotNull(toAdd);
        Iterator iter = toAdd.iterator();
        while (iter.hasNext()) {
            add(iter.next());
        }
        
        testInvariants();
    }
    
    /**
     * Adds all items from the given array to the collection
     * 
     * @param toAdd objects to add
     */
    public final void addAll(Object[] toAdd) {
    	Assert.isNotNull(toAdd);
        for (int i = 0; i < toAdd.length; i++) {
            Object object = toAdd[i];
            
            add(object);
        }
        
        testInvariants();
    }
    
    /**
     * Returns true iff the collection is empty
     * 
     * @return true iff the collection contains no elements
     */
    public final boolean isEmpty() {
        boolean result = (root == -1);
        
        testInvariants();
        
        return result;
    }
    
    /**
     * Removes the given object from the collection. Has no effect if
     * the element does not exist in this collection.
     * 
     * @param toRemove element to remove
     */
    public final void remove(Object toRemove) {
        internalRemove(toRemove);
        
        pack();
        
        testInvariants();
    }
    
    /**
     * Internal implementation of remove. Removes the given element but does not
     * pack the container after the removal.
     * 
     * @param toRemove element to remove
     */
    private void internalRemove(Object toRemove) {
        int objectIndex = getObjectIndex(toRemove);
        
        if (objectIndex != -1) {
            int parent = parentTree[objectIndex];
            lazyRemoveNode(objectIndex);
            //Edge parentEdge = getEdgeTo(objectIndex);
            //parentEdge.setTarget(lazyRemoveNode(objectIndex));
            recomputeAncestorTreeSizes(parent);
        }
        
        //testInvariants();
    }
    
    /**
     * Removes all elements in the given array from this collection.
     * 
     * @param toRemove elements to remove 
     */
    public final void removeAll(Object[] toRemove) {
    	Assert.isNotNull(toRemove);
    	
        for (int i = 0; i < toRemove.length; i++) {
            Object object = toRemove[i];
            
            internalRemove(object);
        }
    	pack();
    }
    
    /**
     * Retains the n smallest items in the collection, removing the rest. When
     * this method returns, the size of the collection will be n. Note that
     * this is a no-op if n > the current size of the collection.
     * 
     * Temporarily package visibility until the implementation of FastProgressReporter
     * is finished.
     * 
     * @param n number of items to retain
     * @param mon progress monitor
     * @throws InterruptedException if the progress monitor is cancelled in another thread
     */
    /* package */ final void retainFirst(int n, FastProgressReporter mon) throws InterruptedException {
        int sz = size();
        
        if (n >= sz) {
            return;
        }
        
        removeRange(n, sz - n, mon);
        
        testInvariants();
    }
    
    /**
     * Retains the n smallest items in the collection, removing the rest. When
     * this method returns, the size of the collection will be n. Note that
     * this is a no-op if n > the current size of the collection.
     * 
     * @param n number of items to retain
     */
    public final void retainFirst(int n) {
        try {
            retainFirst(n, new FastProgressReporter());
        } catch (InterruptedException e) {
        }
        
        testInvariants();
    }
    
    /**
     * Removes all elements in the given range from this collection.
     * For example, removeRange(10, 3) would remove the 11th through 13th
     * smallest items from the collection.
     * 
     * @param first 0-based index of the smallest item to remove
     * @param length number of items to remove
     */
    public final void removeRange(int first, int length) {
        try {
            removeRange(first, length, new FastProgressReporter());
        } catch (InterruptedException e) {
        }
        
        testInvariants();
    }
    
    /**
     * Removes all elements in the given range from this collection.
     * For example, removeRange(10, 3) would remove the 11th through 13th
     * smallest items from the collection.
     * 
     * Temporarily package visiblity until the implementation of FastProgressReporter is
     * finished.
     * 
     * @param first 0-based index of the smallest item to remove
     * @param length number of items to remove
     * @param mon progress monitor
     * @throws InterruptedException if the progress monitor is cancelled in another thread
     */
    /* package */ final void removeRange(int first, int length, FastProgressReporter mon) throws InterruptedException {
    	removeRange(root, first, length, mon);
    	
    	pack();
    	
    	testInvariants();
    }
    
    private final void removeRange(int node, int rangeStart, int rangeLength, FastProgressReporter mon) throws InterruptedException {
    	if (rangeLength == 0) {
    		return;
    	}
    	
    	int size = getSubtreeSize(node);
    	
    	if (size <= rangeStart) {
    		return;
    	}
    	
    	// If we can chop off this entire subtree without any sorting, do so.
    	if (rangeStart == 0 && rangeLength >= size) {
    		removeSubTree(node);
    		return;
    	}
    	try {
	    	// Partition any unsorted nodes
    	    node = partition(node, mon);
	    	
	    	int left = leftSubTree[node];
	    	int leftSize = getSubtreeSize(left);
	    	
	    	int toRemoveFromLeft = Math.min(leftSize - rangeStart, rangeLength);
	    	
	    	// If we're removing anything from the left node
	    	if (toRemoveFromLeft >= 0) {
	    		removeRange(leftSubTree[node], rangeStart, toRemoveFromLeft, mon);
	    		
	    		// Check if we're removing from both sides
	    		int toRemoveFromRight = rangeStart + rangeLength - leftSize - 1;
	    		
	    		if (toRemoveFromRight >= 0) {
	    			// Remove from right subtree
	    			removeRange(rightSubTree[node], 0, toRemoveFromRight, mon);
	    			
	    			// ... removing from both sides means we need to remove the node itself too
	    			removeNode(node);
	    			return;
	    		}
	    	} else {
	    		// If removing from the right side only
	    		removeRange(rightSubTree[node], rangeStart - leftSize - 1, rangeLength, mon);
	    	}
    	} finally {
    	    recomputeTreeSize(node);
    	}
    }
    
    /**
     * Prunes the given subtree (and all child nodes, sorted or unsorted).
     * 
     * @param subTree
     * @since 3.1
     */
    private final void removeSubTree(int subTree) {
        if (subTree == -1) {
            return;
        }
        
        // Destroy all unsorted nodes
        for (int next = nextUnsorted[subTree]; next != -1;) {
            int current = next;
            next = nextUnsorted[next];
            
            // Destroy this unsorted node
            destroyNode(current);
        }
        
        // Destroy left subtree
        removeSubTree(leftSubTree[subTree]);
        
        // Destroy right subtree
        removeSubTree(rightSubTree[subTree]);
        
        replaceNode(subTree, -1);
        // Destroy pivot node
        destroyNode(subTree);
    }
    
    /**
     * Schedules the node for removal. If the node can be removed in constant time,
     * it is removed immediately.
     * 
     * @param subTree
     * @return the replacement node
     * @since 3.1
     */
    private final int lazyRemoveNode(int subTree) {
        int left = leftSubTree[subTree];
        int right = rightSubTree[subTree];

        // If this is a leaf node, remove it immediately
        if (left == -1 && right == -1) {
            int result = nextUnsorted[subTree];
            replaceNode(subTree, result);
            destroyNode(subTree);
            return result;
        }
        
        // Otherwise, flag it for future removal
        Object value = contents[subTree];
        contents[subTree] = lazyRemovalFlag;
        treeSize[subTree]--;
        if (objectIndices != null) {
            objectIndices.remove(value);
        }
        
        return subTree;
    }
    
    /**
     * Removes the given subtree, replacing it with one of its children.
     * Returns the new root of the subtree
     * 
     * @param subTree
     * @return the index of the new root
     * @since 3.1
     */
    private final int removeNode(int subTree) {
        int left = leftSubTree[subTree];
        int right = rightSubTree[subTree];
        
        if (left == -1 || right == -1) {
            int result = -1;
            
            if (left == -1 && right == -1) {
                // If this is a leaf node, replace it with its first unsorted child
                result = nextUnsorted[subTree];
            } else {
                // Either the left or right child is missing -- replace with the remaining child  
                if (left == -1) {
                    result = right;
                } else {
                    result = left;
                }

                try {
                    result = partition(result, new FastProgressReporter());
                } catch (InterruptedException e) {
                    
                }
                if (result == -1) {
                    result = nextUnsorted[subTree];
                } else {
	                int unsorted = nextUnsorted[subTree];
	                nextUnsorted[result] = unsorted;
	                int additionalNodes = 0;
	                if (unsorted != -1) {
	                    parentTree[unsorted] = result;
	                    additionalNodes = treeSize[unsorted];
	                }
	                treeSize[result] += additionalNodes;
                }
            }
            
            replaceNode(subTree, result);
            destroyNode(subTree);
            return result;