lazysortedcollection.java

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

            return -1;
        }
        
        if (contents[subTree] == lazyRemovalFlag) {
            subTree = removeNode(subTree);
            if (subTree == -1) {
                return -1;
            }
        }
        
        for (int idx = nextUnsorted[subTree]; idx != -1;) { 
            idx = partition(subTree, idx);
            nextUnsorted[subTree] = idx;
            if (idx != -1) {
                parentTree[idx] = subTree;
            }
            
            if (mon.isCanceled()) {
                throw new InterruptedException();
            }
        }
        
        // At this point, there are no remaining unsorted nodes in this subtree
        nextUnsorted[subTree] = -1;
        
        return subTree;
    }
    
    private final int getSubtreeSize(int subTree) {
        if (subTree == -1) {
            return 0;
        }
        return treeSize[subTree];
    }
    
    /**
     * Increases the capacity of this collection, if necessary, so that it can hold the 
     * given number of elements. This can be used prior to a sequence of additions to
     * avoid memory reallocation. This cannot be used to reduce the amount 
     * of memory used by the collection.
     *
     * @param newSize capacity for this collection
     */
    public final void setCapacity(int newSize) {
        if (newSize > contents.length) {
            setArraySize(newSize);
        }
    }
    
    /**
     * Adjusts the capacity of the array.
     * 
     * @param newCapacity
     */
    private final void setArraySize(int newCapacity) {
        Object[] newContents = new Object[newCapacity];
        System.arraycopy(contents, 0, newContents, 0, lastNode);
        contents = newContents;
        
        int[] newLeftSubTree = new int[newCapacity];
        System.arraycopy(leftSubTree, 0, newLeftSubTree, 0, lastNode);
        leftSubTree = newLeftSubTree;
        
        int[] newRightSubTree = new int[newCapacity];
        System.arraycopy(rightSubTree, 0, newRightSubTree, 0, lastNode);
        rightSubTree = newRightSubTree;
        
        int[] newNextUnsorted = new int[newCapacity];
        System.arraycopy(nextUnsorted, 0, newNextUnsorted, 0, lastNode);
        nextUnsorted = newNextUnsorted;
        
        int[] newTreeSize = new int[newCapacity];
        System.arraycopy(treeSize, 0, newTreeSize, 0, lastNode);
        treeSize = newTreeSize;
        
        int[] newParentTree = new int[newCapacity];
        System.arraycopy(parentTree, 0, newParentTree, 0, lastNode);
        parentTree = newParentTree;
    }
    
    /**
     * Creates a new node with the given value. Returns the index of the newly
     * created node.
     * 
     * @param value
     * @return the index of the newly created node
     * @since 3.1
     */
    private final int createNode(Object value) {
        int result = -1;

        if (firstUnusedNode == -1) {
            // If there are no unused nodes from prior removals, then 
            // we add a node at the end
            result = lastNode;
            
            // If this would cause the array to overflow, reallocate the array 
            if (contents.length <= lastNode) {
                setCapacity(lastNode * 2);
            }
            
            lastNode++;
        } else {
            // Reuse a node from a prior removal
            result = firstUnusedNode;
            firstUnusedNode = nextUnsorted[result];
        }
        
        contents[result] = value;
        treeSize[result] = 1;
        
        // Clear pointers
        leftSubTree[result] = -1;
        rightSubTree[result] = -1;
        nextUnsorted[result] = -1;
        
        // As long as we have a hash table of values onto tree indices, incrementally
        // update the hash table. Note: the table is only constructed as needed, and it
        // is destroyed whenever the arrays are reallocated instead of reallocating it.
        if (objectIndices != null) {
            objectIndices.put(value, result);
        }
        
        return result;
    }
    
    /**
     * Returns the current tree index for the given object.
     * 
     * @param value
     * @return the current tree index
     * @since 3.1
     */
    private int getObjectIndex(Object value) {
        // If we don't have a map of values onto tree indices, build the map now.
        if (objectIndices == null) {
            int result = -1;
            
            objectIndices = new IntHashMap((int)(contents.length / loadFactor) + 1, loadFactor);
            
            for (int i = 0; i < lastNode; i++) {
                Object element = contents[i];
                
                if (element != null && element != lazyRemovalFlag) {
                    objectIndices.put(element, i);
                    
                    if (value == element) {
                        result = i;
                    }
                }
            }
            
            return result;
        }
        
        // If we have a map of values onto tree indices, return the result by looking it up in
        // the map
        return objectIndices.get(value, -1);
    }
    
    /**
     * Redirects any pointers from the original to the replacement. If the replacement
     * causes a change in the number of elements in the parent tree, the changes are
     * propogated toward the root.
     * 
     * @param nodeToReplace
     * @param replacementNode
     * @since 3.1
     */
    private void replaceNode(int nodeToReplace, int replacementNode) {
        int parent = parentTree[nodeToReplace];
        
        if (parent == -1) {
            if (root == nodeToReplace) {
                setRootNode(replacementNode);
            }
        } else {
            if (leftSubTree[parent] == nodeToReplace) {
                leftSubTree[parent] = replacementNode;
            } else if (rightSubTree[parent] == nodeToReplace) {
                rightSubTree[parent] = replacementNode;
            } else if (nextUnsorted[parent] == nodeToReplace) {
                nextUnsorted[parent] = replacementNode;
            }
            if (replacementNode != -1) {
                parentTree[replacementNode] = parent;
            }
        }
    }
    
    private void recomputeAncestorTreeSizes(int node) {
        while (node != -1) {
            int oldSize = treeSize[node];
            
            recomputeTreeSize(node);
            
            if (treeSize[node] == oldSize) {
                break;
            }
            
            node = parentTree[node];
        }        
    }
    
    /**
     * Recomputes the tree size for the given node.
     * 
     * @param node
     * @since 3.1
     */
    private void recomputeTreeSize(int node) {
        if (node == -1) {
            return;
        }
        treeSize[node] = getSubtreeSize(leftSubTree[node])
    		+ getSubtreeSize(rightSubTree[node])
    		+ getSubtreeSize(nextUnsorted[node])
    		+ (contents[node] == lazyRemovalFlag ? 0 : 1); 
    }
    
    /**
     * 
     * @param toRecompute
     * @param whereToStop
     * @since 3.1
     */
    private void forceRecomputeTreeSize(int toRecompute, int whereToStop) {
        while (toRecompute != -1 && toRecompute != whereToStop) {
	        recomputeTreeSize(toRecompute);
	        
	        toRecompute = parentTree[toRecompute];
        }
    }
    
    /**
     * Destroy the node at the given index in the tree
     * @param nodeToDestroy
     * @since 3.1
     */
    private void destroyNode(int nodeToDestroy) {
        // If we're maintaining a map of values onto tree indices, remove this entry from
        // the map
        if (objectIndices != null) {
            Object oldContents = contents[nodeToDestroy];
            if (oldContents != lazyRemovalFlag) {
                objectIndices.remove(oldContents);
            }
        }
        
        contents[nodeToDestroy] = null;
        leftSubTree[nodeToDestroy] = -1;
        rightSubTree[nodeToDestroy] = -1;
        
        if (firstUnusedNode == -1) {
            treeSize[nodeToDestroy] = 1;
        } else {
            treeSize[nodeToDestroy] = treeSize[firstUnusedNode] + 1;
            parentTree[firstUnusedNode] = nodeToDestroy;
        }
        
        nextUnsorted[nodeToDestroy] = firstUnusedNode;
        
        firstUnusedNode = nodeToDestroy; 
    }
    
    /**
     * Frees up memory by clearing the list of nodes that have been freed up through removals.
     * 
     * @since 3.1
     */
    private final void pack() {
        
        // If there are no unused nodes, then there is nothing to do
        if (firstUnusedNode == -1) {
            return;
        }
        
        int reusableNodes = getSubtreeSize(firstUnusedNode);
        int nonPackableNodes = lastNode - reusableNodes;
        
        // Only pack the array if we're utilizing less than 1/4 of the array (note:
        // this check is important, or it will change the time bounds for removals)
        if (contents.length < MIN_CAPACITY || nonPackableNodes > contents.length / 4) {
            return;
        }
        
        // Rather than update the entire map, just null it out. If it is needed,
        // it will be recreated lazily later. This will save some memory if the
        // map isn't needed, and it takes a similar amount of time to recreate the
        // map as to update all the indices.
        objectIndices = null;
        
        // Maps old index -> new index
        int[] mapNewIdxOntoOld = new int[contents.length];
        int[] mapOldIdxOntoNew = new int[contents.length];
        
        int nextNewIdx = 0;
        // Compute the mapping. Determine the new index for each element 
        for (int oldIdx = 0; oldIdx < lastNode; oldIdx++) {
            if (contents[oldIdx] != null) {
                mapOldIdxOntoNew[oldIdx] = nextNewIdx;
                mapNewIdxOntoOld[nextNewIdx] = oldIdx;
                nextNewIdx++;
            } else {
                mapOldIdxOntoNew[oldIdx] = -1;
            }
        }
        
        // Make the actual array size double the number of nodes to allow
        // for expansion.
        int newNodes = nextNewIdx;
        int newCapacity = Math.max(newNodes * 2, MIN_CAPACITY);
        
        // Allocate new arrays
        Object[] newContents = new Object[newCapacity];
        int[] newTreeSize = new int[newCapacity];
        int[] newNextUnsorted = new int[newCapacity];
        int[] newLeftSubTree = new int[newCapacity];
        int[] newRightSubTree = new int[newCapacity];
        int[] newParentTree = new int[newCapacity];
        
        for (int newIdx = 0; newIdx < newNodes; newIdx++) {
            int oldIdx = mapNewIdxOntoOld[newIdx];
            newContents[newIdx] = contents[oldIdx];
            newTreeSize[newIdx] = treeSize[oldIdx];
            
            int left = leftSubTree[oldIdx];
            if (left == -1) {
                newLeftSubTree[newIdx] = -1;
            } else {
                newLeftSubTree[newIdx] = mapOldIdxOntoNew[left];
            }
            
            int right = rightSubTree[oldIdx];
            if (right == -1) {
                newRightSubTree[newIdx] = -1;                
            } else {
                newRightSubTree[newIdx] = mapOldIdxOntoNew[right];
            }

            int unsorted = nextUnsorted[oldIdx];
            if (unsorted == -1) {
                newNextUnsorted[newIdx] = -1;
            } else {
                newNextUnsorted[newIdx] = mapOldIdxOntoNew[unsorted];
            }
            
            int parent = parentTree[oldIdx];
            if (parent == -1) {
                newParentTree[newIdx] = -1;
            } else {
                newParentTree[newIdx] = mapOldIdxOntoNew[parent];
            }
        }
        
        contents = newContents;
        nextUnsorted = newNextUnsorted;
        treeSize = newTreeSize;
        leftSubTree = newLeftSubTree;