longtree.java

这个是网络上下载的一个struct框架的程序

     */
    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 [] getRecursiveKeys() {
        char startIndex = 1;
        long [] depthKeys = new long[nextIndex-1];
        depthKeys[0] = keys[startIndex];
        int cursor = 1;
        // 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];
        }
        return depthKeys;
    }

    /**
     * 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.
     *
     * @param parentKey the parent key to get children of.
     * @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 getCachedSize() {
        int size = 0;
        size += CacheSizes.sizeOfObject() * 3;
        size += CacheSizes.sizeOfLong() * keys.length;
        size += CacheSizes.sizeOfChar() * keys.length * 2;
        size += CacheSizes.sizeOfChar();
        return size;
    }

    public void writeExternal(ObjectOutput out) throws IOException {
        out.writeObject(keys);
        out.writeObject(leftChildren);
        out.writeObject(rightSiblings);
        out.writeChar(nextIndex);
    }

    public void readExternal(ObjectInput in) throws IOException,
            ClassNotFoundException
    {
        this.keys = (long [])in.readObject();
        this.leftChildren = (char [])in.readObject();
        this.rightSiblings = (char [])in.readObject();
        this.nextIndex = in.readChar();
    }

    /**
     * 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;
    }
}