longtree.java

jive 论坛所有的java源码

/**
 * $RCSfile: LongTree.java,v $
 * $Revision: 1.1.1.1 $
 * $Date: 2002/09/09 13:51:13 $
 *
 * New Jive  from Jdon.com.
 *
 * This software is the proprietary information of CoolServlets, Inc.
 * Use is subject to license terms.
 */

package com.jivesoftware.util;

/**
 * A simple tree structure for long values. It's nowhere near a complete tree
 * implementation since we don't really need one. However, if anyone is
 * interested in finishing this class, or optimizing it, that would be
 * appreciated.<p>
 *
 * The tree uses three arrays to keep the tree structure. It works as in the
 * following example:
 *
 * <pre>
 *   1
 *   |-- 3
 *   |-- |--4
 *   |-- |--6
 *   |-- 5
 *
 * array index:   0 | 1 | 2 | 3 | 4
 *
 * key:           1 | 3 | 4 | 5 | 6
 * leftChild:     1 | 2 |-1 |-1 |-1
 * rightChild    -1 | 3 | 4 |-1 |-1
 * </pre>
 *
 * Where the key array holds key values, and the leftChild and rightChild arrays
 * are pointers to other array indices.<p>
 *
 * The tree holds a maximum of 65534 nodes. It is not intended to be thread-safe.
 * Based on algorithm found in the book "Introduction To Algorithms" by Cormen
 * et all, MIT Press, 1997.
 */
public final class LongTree implements Cacheable {

    long [] keys;
    //char arrays let us address get about 65K nodes.
    char [] leftChildren;
    char [] rightSiblings;

    // Pointer to next available slot.
    char nextIndex = 2;

    /**
     * Constructs a new tree.
     *
     * @param rootKey the value of the root node of the tree.
     * @param size the maximum size of the tree. It cannot grow beyond this size.
     */
    public LongTree(long rootKey, int size) {
        keys = new long[size+1];
        leftChildren = new char[size+1];
        rightSiblings = new char[size+1];

        // New tree, so set the fields to null at root.
        keys[1] = rootKey;
        leftChildren[1] = 0;
        rightSiblings[1] = 0;
    }

    /**
     * Adds a child to the tree.
     *
     * @param parentKey the parent to add the new value to.
     * @param newKey new value to add to the tree.
     */
    public void addChild(long parentKey, long newKey) {
        // Find record for parent
        char parentIndex = findKey(parentKey, (char)1);
        if (parentIndex == 0) {
            throw new IllegalArgumentException("Parent key " + parentKey +
                    " not found when adding child " + newKey + ".");
        }

        // Create record for new key.
        keys[nextIndex] = newKey;
        leftChildren[nextIndex] = 0;
        rightSiblings[nextIndex] = 0;

        // Adjust references. Check to see if the parent has any children.
        if (leftChildren[parentIndex] == 0) {
            // No children, therefore make the new key the first child.
            leftChildren[parentIndex] = nextIndex;
        }
        else {
            // The parent has children, so find the right-most child.
            long siblingIndex = leftChildren[parentIndex];
            while (rightSiblings[new Long(siblingIndex).intValue()] != 0) {
                siblingIndex = rightSiblings[new Long(siblingIndex).intValue()];
            }
            // Add the new entry as a sibling of that last child.
            rightSiblings[new Long(siblingIndex).intValue()] = nextIndex;
        }

        // Finally, increment nextIndex so it's ready for next add.
        nextIndex++;
    }

    /**
     * Returns a parent of <code>childKey</code>.
     */
    public long getParent(long childKey) {
        // If the root key was passed in, return -1;
        if (keys[1] == childKey) {
            return -1;
        }

        // Otherwise, perform a search to find the parent.
        char childIndex = findKey(childKey, (char)1);
        if (childIndex == 0) {
            return -1;
        }

        // Adjust the childIndex pointer until we find the left most sibling of
        // childKey.
        char leftSiblingIndex = getLeftSiblingIndex(childIndex);
        while (leftSiblingIndex != 0) {
            childIndex = leftSiblingIndex;
            leftSiblingIndex = getLeftSiblingIndex(childIndex);
        }

        // Now, search the leftChildren array until we find the parent of
        // childIndex. First, search backwards from childIndex.
        for(int i=childIndex-1; i>=0; i--) {
            if (leftChildren[i] == childIndex) {
                return keys[i];
            }
        }

        // Now, search forward from childIndex.
        for(int i=childIndex+1; i<=leftChildren.length; i++) {
            if (leftChildren[i] == childIndex) {
                return keys[i];
            }
        }

        // We didn't find the parent, so giving up. This shouldn't happen.
        return -1;
    }

    /**
     * Returns a child of <code>parentKey</code> at index <code>index</code>.
     */
    public long getChild(long parentKey, int index) {
        char parentIndex = findKey(parentKey, (char)1);
        if (parentIndex == 0) {
            return -1;
        }

        char siblingIndex = leftChildren[parentIndex];
        if (siblingIndex == -1) {
            return -1;
        }
        int i = index;
        while (i > 0) {
            siblingIndex = rightSiblings[siblingIndex];
            if (siblingIndex == 0) {
                return -1;
            }
            i--;
        }
        return keys[siblingIndex];
    }

    /**
     * Returns the number of children of <code>parentKey</code>.
     */
    public int getChildCount(long parentKey) {
        int count = 0;
        char parentIndex = findKey(parentKey, (char)1);
        if (parentIndex == 0) {
            return 0;
        }
        char siblingIndex = leftChildren[parentIndex];
        while (siblingIndex != 0) {
            count++;
            siblingIndex = rightSiblings[siblingIndex];
        }
        return count;
    }

    /**
     * Returns an array of the children of the parentKey, or an empty array
     * if there are no children or the parent key is not in the tree.
     *
     * @param parentKey the parent to get the children of.
     * @return the children of parentKey
     */
    public long [] getChildren(long parentKey) {
        int childCount = getChildCount(parentKey);
        if (childCount == 0) {
            return new long [0];
        }

        long [] children = new long[childCount];

        int i = 0;
        char parentIndex = findKey(parentKey, (char)1);
        char siblingIndex = leftChildren[parentIndex];
        while (siblingIndex != 0) {
            children[i] = keys[siblingIndex];
            i++;
            siblingIndex = rightSiblings[siblingIndex];
        }
        return children;
    }

    /**
     * Returns the index of <code>childKey</code> in <code>parentKey</code> or
     * -1 if <code>childKey</code> is not a child of <code>parentKey</code>.
     */
    public int getIndexOfChild(long parentKey, long childKey) {
        int parentIndex = findKey(parentKey, (char)1);

        int index = 0;

        char siblingIndex = leftChildren[new Long(parentIndex).intValue()];
        if (siblingIndex == 0) {
            return -1;
        }
        while (keys[siblingIndex] != childKey) {
            index++;
            siblingIndex = rightSiblings[siblingIndex];
            if (siblingIndex == 0) {
                return -1;
            }
        }
        return index;
    }

    /**
     * Returns the depth in the tree that the element can be found at or -1
     * if the element is not in the tree. For example, the root element is
     * depth 0, direct children of the root element are depth 1, etc.
     *
     * @param key the key to find the depth for.
     * @return the depth of <tt>key</tt> in the tree hiearchy.
     */
    public int getDepth(long key) {
        int [] depth = { 0 };
        if (findDepth(key, (char)1, depth) == 0) {
            return -1;
        }
        return depth[0];
    }

    /**
     * Returns the keys in the in the tree in depth-first order. For example,
     * give the tree:
     *
     * <pre>
     *   1
     *   |-- 3
     *   |-- |-- 4
     *   |-- |-- |-- 7
     *   |-- |-- 6
     *   |-- 5
     * </pre>
     *
     * Then this method would return the sequence: 1, 3, 4, 7, 6, 5.
     *
     * @return the keys of the tree in depth-first order.
     */
    public long[] getRecursiveChildren(long parentKey) {
        char startIndex = findKey(parentKey, (char)1);
        long [] depthKeys = new long[nextIndex-1];
        int cursor = 0;
        // Iterate through each sibling, filling the depthKeys array up.
        char siblingIndex = leftChildren[startIndex];
        while (siblingIndex != 0) {
            cursor = fillDepthKeys(siblingIndex, depthKeys, cursor);
            // Move to next sibling
            siblingIndex = rightSiblings[siblingIndex];
        }
        // The cursor variable represents how many keys were actually copied
        // into the depth key buffer. Create a new array of the correct size.
        long [] dKeys = new long[cursor];
        for (int i=0; i<cursor; i++) {
            dKeys[i] = depthKeys[i];
        }
        return dKeys;
    }

    /**
     * Returns true if the tree node is a leaf.
     *
     * @return true if <code>key</code> has no children.
     */
    public boolean isLeaf(long key) {
        int keyIndex = findKey(key, (char)1);
        if (keyIndex == 0) {
            return false;
        }
        return (leftChildren[keyIndex] == 0);
    }

    /**
     * Returns the keys in the tree.
     */
    public long[] keys() {
        long [] k = new long[nextIndex-1];
        for (int i=0; i<k.length; i++) {
            k[i] = keys[i];
        }
        return k;
    }

    public int getSize() {
        int size = 0;
        size += CacheSizes.sizeOfObject() * 3;
        size += CacheSizes.sizeOfLong() * keys.length;
        size += CacheSizes.sizeOfChar() * keys.length * 2;
        size += CacheSizes.sizeOfChar();
        return size;
    }

    /**
     * Returns the index of the specified value, or 0 if the key could not be
     * found. Tail recursion was removed, but not the other recursive step.
     * Using a stack instead often isn't even faster under Java.
     *
     * @param value the key to search for.
     * @param startIndex the index in the tree to start searching at. Pass in
     *      the root index to search the entire tree.
     */
    private char findKey(long value, char startIndex) {
        if (startIndex == 0) {
            return 0;
        }

        if (keys[startIndex] == value) {
            return startIndex;
        }

        char siblingIndex = leftChildren[startIndex];
        while (siblingIndex != 0) {
            char recursiveIndex = findKey(value, siblingIndex);
            if (recursiveIndex != 0) {
                return recursiveIndex;
            }
            else {
                siblingIndex = rightSiblings[siblingIndex];
            }
        }
        return 0;
    }

    /**
     * Identical to the findKey method, but it also keeps track of the
     * depth.
     */
    private char findDepth(long value, char startIndex, int [] depth) {
        if (startIndex == 0) {
            return 0;
        }

        if (keys[startIndex] == value) {
            return startIndex;
        }

        char siblingIndex = leftChildren[startIndex];
        while (siblingIndex != 0) {
            depth[0]++;
            char recursiveIndex = findDepth(value, siblingIndex, depth);
            if (recursiveIndex != 0) {
                return recursiveIndex;
            }
            else {
                depth[0]--;
                siblingIndex = rightSiblings[siblingIndex];
            }
        }
        return 0;
    }

    /**
     * Recursive method that fills the depthKeys array with all the child keys in
     * the tree in depth first order.
     *
     * @param startIndex the starting index for the current recursive iteration.
     * @param depthKeys the array of depth-first keys that is being filled.
     * @param cursor the current index in the depthKeys array.
     * @return the new cursor value after a recursive run.
     */
    private int fillDepthKeys(char startIndex, long [] depthKeys, int cursor) {
        depthKeys[cursor] = keys[startIndex];
        cursor++;
        char siblingIndex = leftChildren[startIndex];
        while (siblingIndex != 0) {
            cursor = fillDepthKeys(siblingIndex, depthKeys, cursor);
            // Move to next sibling
            siblingIndex = rightSiblings[siblingIndex];
        }
        return cursor;
    }

    /**
     * Returs the left sibling index of index. There is no easy way to find a
     * left sibling. Therefore, we are forced to linearly scan the rightSiblings
     * array until we encounter a reference to index. We'll make the assumption
     * that entries are added in order since that assumption can yield big
     * performance gain if it's true (and no real performance hit otherwise).
     */
    private char getLeftSiblingIndex(char index) {
        //First, search backwards throw rightSiblings array
        for (int i=index-1; i>=0; i--) {
            if (rightSiblings[i] == index) {
                return (char)i;
            }
        }

        //Now, search forwards
        for (int i=index+1; i<rightSiblings.length; i++) {
            if (rightSiblings[i] == index) {
                return (char)i;
            }
        }

        //No sibling found, give up.
        return (char)0;
    }
}