longtree.java

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

/**
 * $RCSfile: LongTree.java,v $
 * $Revision: 1.6 $
 * $Date: 2003/03/03 21:33:45 $
 *
 * Copyright (C) 1999-2001 CoolServlets, Inc. All rights reserved.
 *
 * This software is the proprietary information of CoolServlets, Inc.
 * Use is subject to license terms.
 */

package com.struts2.framework.util;

import java.io.Externalizable;
import java.io.ObjectOutput;
import java.io.IOException;
import java.io.ObjectInput;

/**
 * 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.
 *
 * @author Matt Tucker
 */
public final class LongTree implements Cacheable, Externalizable {

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

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

    /**
     * Creates a new tree.
     *
     * @param rootKey the value of the root node of the tree.
     * @param initialCapacity the maximum initial capacity of the tree.
     */
    public LongTree(long rootKey, int initialCapacity) {
        keys = new long[initialCapacity+1];
        leftChildren = new char[initialCapacity+1];
        rightSiblings = new char[initialCapacity+1];

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

    /**
     * Constructor for use with the Externalizable interface. Normal users
     * of this class <b>should not</b> call this constructor.
     */
    public LongTree() {
        // do nothing
    }

    /**
     * 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 + ".");
        }

        // Expand the arrays if we've run out of room.
        if (nextIndex == keys.length) {
            // Can't grow above 2^16 elements.
            if (keys.length == 65536) {
                throw new IllegalStateException("Tree has exceeded max size and cannot grow!");
            }
            int oldSize = keys.length;
            // Reserve room for new elements.
            int newSize = (int)Math.ceil(oldSize * 1.5);
            // Max size is 2^16 since the child arrrays use chars.
            if (newSize > 65536) {
                newSize = 65536;
            }
            // Grow keys array.
            long [] newKeys = new long[newSize];
            System.arraycopy(keys, 0, newKeys, 0, oldSize);
            keys = newKeys;
            // Grow left children array.
            char [] newLeftChildren = new char[newSize];
            System.arraycopy(leftChildren, 0, newLeftChildren, 0, oldSize);
            leftChildren = newLeftChildren;
            // Grow right children array.
            char [] newRightSiblings = new char[newSize];
            System.arraycopy(rightSiblings, 0, newRightSiblings, 0, oldSize);
            rightSiblings = newRightSiblings;
        }

        // 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>.