lazysortedcollection.java

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

/*******************************************************************************
 * Copyright (c) 2004, 2005 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.jface.viewers.deferred;

import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;

import org.eclipse.jface.util.Assert;

/**
 * This object maintains a collection of elements, sorted by a comparator
 * given in the constructor. The collection is lazily sorted, allowing 
 * more efficient runtimes for most methods. There are several methods on this
 * object that allow objects to be queried by their position in the sorted
 * collection.
 * 
 * <p>
 * This is a modified binary search tree. Each subtree has a value, a left and right subtree, 
 * a count of the number of children, and a set of unsorted children. 
 * Insertion happens lazily. When a new node N is inserted into a subtree T, it is initially 
 * added to the set of unsorted children for T without actually comparing it with the value for T. 
 * </p>
 * <p>
 * The unsorted children will remain in the unsorted set until some subsequent operation requires
 * us to know the exact set of elements in one of the subtrees. At that time, we partition
 * T by comparing all of its unsorted children with T's value and moving them into the left 
 * or right subtrees.
 * </p>
 * 
 * @since 3.1
 */
public class LazySortedCollection {
    private final int MIN_CAPACITY = 8;
    private Object[] contents = new Object[MIN_CAPACITY];
    private int[] leftSubTree = new int[MIN_CAPACITY];
    private int[] rightSubTree = new int[MIN_CAPACITY];
    private int[] nextUnsorted = new int[MIN_CAPACITY];
    private int[] treeSize = new int[MIN_CAPACITY];
    private int[] parentTree = new int[MIN_CAPACITY];
    private int root = -1;
    private int lastNode = 0;
    private int firstUnusedNode = -1;
    
    private static final float loadFactor = 0.75f;
    
    private IntHashMap objectIndices;
    private Comparator comparator;
    private static int counter = 0;
    
    /**
     * Disables randomization and enables additional runtime error checking.
     * Severely degrades performance if set to true. Intended for use in test 
     * suites only.
     */
    public boolean enableDebug = false;
    
    // This object is inserted as the value into any node scheduled for lazy removal
    private Object lazyRemovalFlag = new Object() {
        public String toString() {
            return "Lazy removal flag";  //$NON-NLS-1$
        }
    };
    
    private final static int DIR_LEFT = 0;
    private final static int DIR_RIGHT = 1;
    private final static int DIR_UNSORTED = 2;
    
    // Direction constants indicating root nodes
    private final static int DIR_ROOT = 3;
    private final static int DIR_UNUSED = 4;
       
    private final class Edge {
        private int startNode;
        private int direction;
        
        private Edge() {
            startNode = -1;
            direction = -1;
        }
        
        private Edge(int node, int dir) {
            startNode = node;
            direction = dir;
        }
        
        private int getStart() {
            return startNode;
        }
        
        private int getTarget() {
            if (startNode == -1) {
                if (direction == DIR_UNSORTED) {
                    return firstUnusedNode;
                } else if (direction == DIR_ROOT) {
                    return root;
                }
                return -1;
            }
            
            if (direction == DIR_LEFT) {
                return leftSubTree[startNode];
            }
            if (direction == DIR_RIGHT) {
                return rightSubTree[startNode];
            }
            return nextUnsorted[startNode];
        }
        
        private boolean isNull() {
            return getTarget() == -1;
        }
     
        /**
         * Redirects this edge to a new node
         * @param newNode
         * @since 3.1
         */
        private void setTarget(int newNode) {            
            if (direction == DIR_LEFT) {
    	        leftSubTree[startNode] = newNode;
            } else if (direction == DIR_RIGHT) {
                rightSubTree[startNode] = newNode;
            } else if (direction == DIR_UNSORTED) {
                nextUnsorted[startNode] = newNode;
            } else if (direction == DIR_ROOT) {
                root = newNode;
            } else if (direction == DIR_UNUSED) {
                firstUnusedNode = newNode;
            }
            
	        if (newNode != -1) {
	            parentTree[newNode] = startNode;
	        }
        }
        
        private void advance(int direction) {
            startNode = getTarget();
            this.direction = direction;
        }
    }

    private void setRootNode(int node) {
        root = node;
        if (node != -1) {
            parentTree[node] = -1;
        }
    }
    
    /**
     * Creates a new sorted collection using the given comparator to determine
     * sort order.
     * 
     * @param c comparator that determines the sort order
     */
    public LazySortedCollection(Comparator c) {
        this.comparator = c;
    }
    
    /**
     * Tests if this object's internal state is valid. Throws a runtime
     * exception if the state is invalid, indicating a programming error
     * in this class. This method is intended for use in test
     * suites and should not be called by clients.
     */
    public void testInvariants() {
        if (!enableDebug) {
            return;
        }
        
        testInvariants(root);
    }
    
    private void testInvariants(int node) {
        if (node == -1) {
            return;
        }
        
        // Get the current tree size (we will later force the tree size
        // to be recomputed from scratch -- if everything works properly, then
        // there should be no change.
        int treeSize = getSubtreeSize(node);

        int left = leftSubTree[node];
        int right = rightSubTree[node];
        int unsorted = nextUnsorted[node];
        
        if (isUnsorted(node)) {
            Assert.isTrue(left == -1, "unsorted nodes shouldn't have a left subtree"); //$NON-NLS-1$
            Assert.isTrue(right == -1, "unsorted nodes shouldn't have a right subtree"); //$NON-NLS-1$
        }
        
        if (left != -1) {
            testInvariants(left);
            Assert.isTrue(parentTree[left] == node, "left node has invalid parent pointer"); //$NON-NLS-1$
        }
        if (right != -1) {
            testInvariants(right);
            Assert.isTrue(parentTree[right] == node, "right node has invalid parent pointer");             //$NON-NLS-1$
        }

        int previous = node;
        while (unsorted != -1) {
            int oldTreeSize = this.treeSize[unsorted];
            recomputeTreeSize(unsorted);
            
            Assert.isTrue(this.treeSize[unsorted] == oldTreeSize, 
                    "Invalid node size for unsorted node"); //$NON-NLS-1$
            Assert.isTrue(leftSubTree[unsorted] == -1, "unsorted nodes shouldn't have left subtrees"); //$NON-NLS-1$
            Assert.isTrue(rightSubTree[unsorted] == -1, "unsorted nodes shouldn't have right subtrees"); //$NON-NLS-1$
            Assert.isTrue(parentTree[unsorted] == previous, "unsorted node has invalid parent pointer"); //$NON-NLS-1$
            Assert.isTrue(contents[unsorted] != lazyRemovalFlag, "unsorted nodes should not be lazily removed"); //$NON-NLS-1$
            previous = unsorted;
            unsorted = nextUnsorted[unsorted];
        }
        
        // Note that we've already tested that the child sizes are correct... if our size is
        // correct, then recomputing it now should not cause any change.
        recomputeTreeSize(node);
                
        Assert.isTrue(treeSize == getSubtreeSize(node), "invalid tree size"); //$NON-NLS-1$
    }
    
    private boolean isUnsorted(int node) {
        int parent = parentTree[node];
        
        if (parent != -1) {
            return nextUnsorted[parent] == node;
        }
        
        return false;
    }
    
    private final boolean isLess(int element1, int element2) {
        return comparator.compare(contents[element1], contents[element2]) < 0;
    }
    
    /**
     * Adds the given element to the given subtree. Returns the new
     * root of the subtree.
     * 
     * @param subTree index of the subtree to insert elementToAdd into. If -1, 
     *                then a new subtree will be created for elementToAdd
     * @param elementToAdd index of the element to add to the subtree. If -1, this method
     *                 is a NOP.
     * @since 3.1
     */
    private final int addUnsorted(int subTree, int elementToAdd) {
        if (elementToAdd == -1) {
            return subTree;
        }
        
        if (subTree == -1) {
            nextUnsorted[elementToAdd] = -1;
            treeSize[elementToAdd] = 1;
            return elementToAdd;
        }
        
        // If the subTree is empty (ie: it only contains nodes flagged for lazy removal),
        // chop it off.
        if (treeSize[subTree] == 0) {
            removeSubTree(subTree);
            nextUnsorted[elementToAdd] = -1;
            treeSize[elementToAdd] = 1;
            return elementToAdd;
        }
        
        // If neither subtree has any children, add a pseudorandom chance of the
        // newly added element becoming the new pivot for this node. Note: instead
        // of a real pseudorandom generator, we simply use a counter here.
        if (!enableDebug && leftSubTree[subTree] == -1 && rightSubTree[subTree] == -1 
                && leftSubTree[elementToAdd] == -1 && rightSubTree[elementToAdd] == -1) {
	        counter--;
	        
	        if (counter % treeSize[subTree] == 0) {
	            // Make the new node into the new pivot 
	            nextUnsorted[elementToAdd] = subTree;
	            parentTree[elementToAdd] = parentTree[subTree];
	            parentTree[subTree] = elementToAdd;
	            treeSize[elementToAdd] = treeSize[subTree] + 1;
	            return elementToAdd;
	        }
        }
        
        int oldNextUnsorted = nextUnsorted[subTree];
        nextUnsorted[elementToAdd] = oldNextUnsorted;
        
        if (oldNextUnsorted == -1) {
            treeSize[elementToAdd] = 1;
        } else {
            treeSize[elementToAdd] = treeSize[oldNextUnsorted] + 1;
            parentTree[oldNextUnsorted] = elementToAdd;
        }
        
        parentTree[elementToAdd] = subTree;
        
        nextUnsorted[subTree] = elementToAdd;
        treeSize[subTree]++;        
        return subTree;
    }
    
    /**
     * Returns the number of elements in the collection
     * 
     * @return the number of elements in the collection
     */
    public int size() {
        int result = getSubtreeSize(root);
        
        testInvariants();
        
        return result;
    }
    
    /**
     * Given a tree and one of its unsorted children, this sorts the child by moving
     * it into the left or right subtrees. Returns the next unsorted child or -1 if none
     * 
     * @param subTree parent tree
     * @param toMove child (unsorted) subtree
     * @since 3.1
     */
    private final int partition(int subTree, int toMove) {
        int result = nextUnsorted[toMove];
        
        if (isLess(toMove, subTree)) {
            int nextLeft = addUnsorted(leftSubTree[subTree], toMove);
            leftSubTree[subTree] = nextLeft;
            parentTree[nextLeft] = subTree;
        } else {
            int nextRight = addUnsorted(rightSubTree[subTree], toMove);
            rightSubTree[subTree] = nextRight;
            parentTree[nextRight] = subTree;
        }
        
        return result;
    }
    
    /**
     * Partitions the given subtree. Moves all unsorted elements at the given node
     * to either the left or right subtrees. If the node itself was scheduled for
     * lazy removal, this will force the node to be removed immediately. Returns
     * the new subTree.
     * 
     * @param subTree
     * @return the replacement node (this may be different from subTree if the subtree
     * was replaced during the removal)
     * @since 3.1
     */
    private final int partition(int subTree, FastProgressReporter mon) throws InterruptedException {
        if (subTree == -1) {