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