lazysortedcollection.java

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

        }
                
        // Find the edges that lead to the next-smallest and
        // next-largest nodes
        Edge nextSmallest = new Edge(subTree, DIR_LEFT);
        while (!nextSmallest.isNull()) {
            nextSmallest.advance(DIR_RIGHT);
        }
        
        Edge nextLargest = new Edge(subTree, DIR_RIGHT);
        while (!nextLargest.isNull()) {
            nextLargest.advance(DIR_LEFT);
        }
        
        // Index of the replacement node
        int replacementNode = -1;
        
        // Count of number of nodes moved to the right
        
        int leftSize = getSubtreeSize(left);
        int rightSize = getSubtreeSize(right);
        
        // Swap with a child from the larger subtree
        if (leftSize > rightSize) {
            replacementNode = nextSmallest.getStart();

            // Move any unsorted nodes that are larger than the replacement node into
            // the left subtree of the next-largest node
            Edge unsorted = new Edge(replacementNode, DIR_UNSORTED);
            while (!unsorted.isNull()) {
                int target = unsorted.getTarget();
                
                if (!isLess(target, replacementNode)) {
                    unsorted.setTarget(nextUnsorted[target]);
                    nextLargest.setTarget(addUnsorted(nextLargest.getTarget(), target));
                } else {
                    unsorted.advance(DIR_UNSORTED);
                }
            }
            
            forceRecomputeTreeSize(unsorted.getStart(), replacementNode);
            forceRecomputeTreeSize(nextLargest.getStart(), subTree);
        } else {
            replacementNode = nextLargest.getStart();

            // Move any unsorted nodes that are smaller than the replacement node into
            // the right subtree of the next-smallest node
            Edge unsorted = new Edge(replacementNode, DIR_UNSORTED);
            while (!unsorted.isNull()) {
                int target = unsorted.getTarget();
                
                if (isLess(target, replacementNode)) {
                    unsorted.setTarget(nextUnsorted[target]);
                    nextSmallest.setTarget(addUnsorted(nextSmallest.getTarget(), target));
                } else {
                    unsorted.advance(DIR_UNSORTED);
                }
            }
            
            forceRecomputeTreeSize(unsorted.getStart(), replacementNode);
            forceRecomputeTreeSize(nextSmallest.getStart(), subTree);
        }
        
        // Now all the affected treeSize[...] elements should be updated to reflect the
        // unsorted nodes that moved. Swap nodes. 
        Object replacementContent = contents[replacementNode];
        contents[replacementNode] = contents[subTree];
        contents[subTree] = replacementContent;
        
        if (objectIndices != null) {
            objectIndices.put(replacementContent, subTree);
            // Note: currently we don't bother updating the index of the replacement
            // node since we're going to remove it immediately afterwards and there's
            // no good reason to search for the index in a method that was given the
            // index as a parameter...
            
            // objectIndices.put(contents[replacementNode], replacementNode)
        }
        
        int replacementParent = parentTree[replacementNode]; 
        
        replaceNode(replacementNode, removeNode(replacementNode));
        //Edge parentEdge = getEdgeTo(replacementNode);
        //parentEdge.setTarget(removeNode(replacementNode));

        forceRecomputeTreeSize(replacementParent, subTree);
        recomputeTreeSize(subTree);
        
        //testInvariants();
        
        return subTree;
    }
   
    /**
     * Removes all elements from the collection
     */
    public final void clear() {
        lastNode = 0;
        setArraySize(MIN_CAPACITY);
        root = -1;
        firstUnusedNode = -1;
        objectIndices = null;
        
        testInvariants();
    }
    
    /**
     * Returns the comparator that is determining the sort order for this collection
     * 
     * @return comparator for this collection
     */
    public Comparator getComparator() {
        return comparator;
    }
    
    /**
     * Fills in an array of size n with the n smallest elements from the collection.
     * Can compute the result in sorted or unsorted order. 
     * 
     * Currently package visible until the implementation of FastProgressReporter is finished.
     * 
     * @param result array to be filled
     * @param sorted if true, the result array will be sorted. If false, the result array
     * may be unsorted. This does not affect which elements appear in the result, only their 
     * order.
     * @param mon monitor used to report progress and check for cancellation
     * @return the number of items inserted into the result array. This will be equal to the minimum
     * of result.length and container.size()
     * @throws InterruptedException if the progress monitor is cancelled
     */
    /* package */ final int getFirst(Object[] result, boolean sorted, FastProgressReporter mon) throws InterruptedException {
        int returnValue = getRange(result, 0, sorted, mon);
        
        testInvariants();
        
        return returnValue;
    }
    
    /**
     * Fills in an array of size n with the n smallest elements from the collection.
     * Can compute the result in sorted or unsorted order. 
     * 
     * @param result array to be filled
     * @param sorted if true, the result array will be sorted. If false, the result array
     * may be unsorted. This does not affect which elements appear in the result. It only
     * affects their order. Computing an unsorted result is asymptotically faster.
     * @return the number of items inserted into the result array. This will be equal to the minimum
     * of result.length and container.size()
     */
    public final int getFirst(Object[] result, boolean sorted) {
        int returnValue = 0;
        
        try {
            returnValue = getFirst(result, sorted, new FastProgressReporter());
        } catch (InterruptedException e) {
        }
        
        testInvariants();
        
        return returnValue;
    }
    
    /**
     * Given a position defined by k and an array of size n, this fills in the array with
     * the kth smallest element through to the (k+n)th smallest element. For example, 
     * getRange(myArray, 10, false) would fill in myArray starting with the 10th smallest item
     * in the collection. The result can be computed in sorted or unsorted order. Computing the
     * result in unsorted order is more efficient.
     * <p>
     * Temporarily set to package visibility until the implementation of FastProgressReporter
     * is finished.
     * </p>
     * 
     * @param result array to be filled in
     * @param rangeStart index of the smallest element to appear in the result
     * @param sorted true iff the result array should be sorted
     * @param mon progress monitor used to cancel the operation
     * @throws InterruptedException if the progress monitor was cancelled in another thread
     */
    /* package */ final int getRange(Object[] result, int rangeStart, boolean sorted, FastProgressReporter mon) throws InterruptedException {
        return getRange(result, 0, rangeStart, root, sorted, mon);
    }
    
    /**
     * Computes the n through n+k items in this collection.
     * Computing the result in unsorted order is more efficient. Sorting the result will
     * not change which elements actually show up in the result. That is, even if the result is
     * unsorted, it will still contain the same elements as would have been at that range in
     * a fully sorted collection. 
     * 
     * @param result array containing the result
     * @param rangeStart index of the first element to be inserted into the result array
     * @param sorted true iff the result will be computed in sorted order
     * @return the number of items actually inserted into the result array (will be the minimum
     * of result.length and this.size())
     */
    public final int getRange(Object[] result, int rangeStart, boolean sorted) {
        int returnValue = 0;
        
        try {
            returnValue = getRange(result, rangeStart, sorted, new FastProgressReporter());
        } catch (InterruptedException e) {
        }
        
        testInvariants();
        
        return returnValue;
    }
    
    /**
     * Returns the item at the given index. Indexes are based on sorted order.
     * 
     * @param index index to test
     * @return the item at the given index
     */
    public final Object getItem(int index) {
        Object[] result = new Object[1];
        try {
            getRange(result, index, false, new FastProgressReporter());
        } catch (InterruptedException e) {
            // shouldn't happen
        }
        Object returnValue = result[0];
        
        testInvariants();
        
        return returnValue;
    }
    
    /**
     * Returns the contents of this collection as a sorted or unsorted
     * array. Computing an unsorted array is more efficient.
     * 
     * @param sorted if true, the result will be in sorted order. If false,
     * the result may be in unsorted order.
     * @return the contents of this collection as an array.
     */
    public final Object[] getItems(boolean sorted) {
        Object[] result = new Object[size()];
        
        getRange(result, 0, sorted);
        
        return result;
    }
    
    private final int getRange(Object[] result, int resultIdx, int rangeStart, int node, boolean sorted, FastProgressReporter mon) throws InterruptedException {
        if (node == -1) {
            return 0;
        }

        int availableSpace = result.length - resultIdx;
        
        // If we're asking for all children of the current node, simply call getChildren
        if (rangeStart == 0) {
            if (treeSize[node] <= availableSpace) {
                return getChildren(result, resultIdx, node, sorted, mon);
            }
        }
        
        node = partition(node, mon);
        if (node == -1) {
            return 0;
        }
        
        int inserted = 0;
        
        int numberLessThanNode = getSubtreeSize(leftSubTree[node]);
                
        if (rangeStart < numberLessThanNode) {
            if (inserted < availableSpace) {
                inserted += getRange(result, resultIdx, rangeStart, leftSubTree[node], sorted, mon);
            }
        }
        
        if (rangeStart <= numberLessThanNode) {
	        if (inserted < availableSpace) {
	            result[resultIdx + inserted] = contents[node];
	            inserted++;
	        }	        
        } 
        
        if (inserted < availableSpace) {
            inserted += getRange(result, resultIdx + inserted,
                Math.max(rangeStart - numberLessThanNode - 1, 0), rightSubTree[node], sorted, mon);
        }
        
        return inserted;
    }
    
    /**
     * Fills in the available space in the given array with all children of the given node.
     * 
     * @param result 
     * @param resultIdx index in the result array where we will begin filling in children
     * @param node
     * @return the number of children added to the array
     * @since 3.1
     */
    private final int getChildren(Object[] result, int resultIdx, int node, boolean sorted, FastProgressReporter mon) throws InterruptedException {
        if (node == -1) {
            return 0;
        }
        
        int tempIdx = resultIdx;
        
        if (sorted) {
            node = partition(node, mon);
            if (node == -1) {
                return 0;
            }
        }
        
        // Add child nodes smaller than this one
        if (tempIdx < result.length) {
            tempIdx += getChildren(result, tempIdx, leftSubTree[node], sorted, mon);
        }
        
        // Add the pivot
        if (tempIdx < result.length) {
            Object value = contents[node];
            if (value != lazyRemovalFlag) {
                result[tempIdx++] = value;
            }
        }
        
        // Add child nodes larger than this one
        if (tempIdx < result.length) {
            tempIdx += getChildren(result, tempIdx, rightSubTree[node], sorted, mon);
        }
        
        // Add unsorted children (should be empty if the sorted flag was true)
        for (int unsortedNode = nextUnsorted[node]; unsortedNode != -1 && tempIdx < result.length; 
        	unsortedNode = nextUnsorted[unsortedNode]) {
            
            result[tempIdx++] = contents[unsortedNode];
        }
        
        return tempIdx - resultIdx;
    }

    /**
     * Returns true iff this collection contains the given item
     * 
     * @param item item to test
     * @return true iff this collection contains the given item
     */
    public boolean contains(Object item) {
    	Assert.isNotNull(item);
        boolean returnValue = (getObjectIndex(item) != -1);
        
        testInvariants();
        
        return returnValue;
    }
}