tree.java

一个用Java开发的Web邮局

/*
 * Tree.java
 * Copyright (C) 1999 dog <[e-mail]>
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * 
 * You may retrieve the latest version of this library from
 * http://www.dog.net.uk/knife/
 */

package dog.util;

import java.util.Vector;

/**
 * A utility class for manipulating objects in a tree structure.
 * <p>
 * This class provides a way to associate arbitrary objects with one another in a hierarchy.
 *
 * @author [e-mail]
 * @version 1.0
 */
public final class Tree {

	int nparents = 0;
	Object[] parents;
	int[] nchildren;
	Object[][] children;
	int nelements = 0;
	Object[] elements;
	int[] depths;

	int increment;
	Object LOCK = new Object();

	/**
	 * Constructs an empty tree.
	 */
	public Tree() {
		this(10);
	}
	
	/**
	 * Constructs an empty tree with the specified capacity increment.
	 * @param increment the amount by which the capacity is increased when an array overflows.
	 */
	public Tree(int increment) {
		super();
		this.increment = (increment>0) ? increment : 1;
		clear();
	}

	// Returns the elements index of the specified object, or -1 if no such element exists.
	private int elementIndex(Object object) {
		for (int i=0; i<nelements; i++)
			if (elements[i]==object)
				return i;
		return -1;
	}

	// Returns the parents index of the specified object, or -1 if no such parent exists.
	private int parentIndex(Object object) {
		for (int i=0; i<nparents; i++)
			if (parents[i]==object)
				return i;
		return -1;
	}

	/**
	 * Returns the parent of the specified object,
	 * or null if the object is a root or not a child in the tree.
	 */
	public Object getParent(Object child) {
		synchronized (LOCK) {
			return parentOf(child);
		}
	}

	private Object parentOf(Object child) {
		for (int p = 0; p<nparents; p++) {
			for (int c = 0; c<nchildren[p]; c++)
				if (children[p][c]==child)
					return parents[p];
		}
		return null;
	}

	/**
	 * Returns an array of children of the specified object,
	 * or an empty array if the object is not a parent in the tree.
	 */
	public Object[] getChildren(Object parent) {
		synchronized (LOCK) {
			int p = parentIndex(parent);
			if (p>-1) {
				Object[] c = new Object[nchildren[p]];
				System.arraycopy(children[p], 0, c, 0, nchildren[p]);
				return c;
			}
		}
		return new Object[0];
	}

	/**
	 * Returns the number of children of the specified object.
	 */
	public int getChildCount(Object parent) {
		synchronized (LOCK) {
			int p = parentIndex(parent);
			if (p>-1)
				return nchildren[p];
		}
		return 0;
	}

	/**
	 * Indicates whether the specified object is contained in the tree.
	 */
	public boolean contains(Object object) {
		synchronized (LOCK) {
			return (elementIndex(object)>-1);
		}
	}

	private void ensureRootCapacity(int amount) {
		// calculate the amount by which to increase arrays
		int block = ((int)(Math.max(Math.ceil((double)amount/(double)increment), 1)))*increment;
		// ensure capacity of elements
		if (elements.length<nelements+amount) {
			int len = elements.length;
			Object[] newelements = new Object[len+block];
			System.arraycopy(elements, 0, newelements, 0, nelements);
			elements = newelements;
			int[] newdepths = new int[len+block];
			System.arraycopy(depths, 0, newdepths, 0, nelements);
			depths = newdepths;
		}
	}

	private void ensureParentCapacity(int amount) {
		// calculate the amount by which to increase arrays
		int block = ((int)(Math.max(Math.ceil((double)amount/(double)increment), 1)))*increment;
		// ensure capacity of parents (and hence children in parent dimension)
		if (parents.length<nparents+1) {
			Object[] newparents = new Object[parents.length+increment];
			System.arraycopy(parents, 0, newparents, 0, nparents);
			parents = newparents;
			Object[][] newchildren = new Object[parents.length+increment][];
			System.arraycopy(children, 0, newchildren, 0, nparents);
			children = newchildren;
			int[] newnchildren = new int[parents.length+increment];
			System.arraycopy(nchildren, 0, newnchildren, 0, nparents);
			nchildren = newnchildren;
		}
		// ensure capacity of elements
		if (elements.length<nelements+amount) {
			int len = elements.length;
			Object[] newelements = new Object[len+block];
			System.arraycopy(elements, 0, newelements, 0, nelements);
			elements = newelements;
			int[] newdepths = new int[len+block];
			System.arraycopy(depths, 0, newdepths, 0, nelements);
			depths = newdepths;
		}
	}

	private void ensureChildCapacity(int amount, int parent) {
		// calculate the amount by which to increase arrays
		int block = ((int)(Math.max(Math.ceil((double)amount/(double)increment), 1)))*increment;
		// ensure capacity of children for this parent
		if (children[parent].length<nchildren[parent]+amount) {
			Object[] newchildren = new Object[children[parent].length+block];
			System.arraycopy(children[parent], 0, newchildren, 0, nchildren[parent]);
			children[parent] = newchildren;
		}
		// ensure capacity of elements
		if (elements.length<nelements+amount) {
			int len = elements.length;
			Object[] newelements = new Object[len+block];
			System.arraycopy(elements, 0, newelements, 0, nelements);
			elements = newelements;
			int[] newdepths = new int[len+block];
			System.arraycopy(depths, 0, newdepths, 0, nelements);
			depths = newdepths;
		}
	}

	/**
	 * Adds a root to the tree.
	 * Returns the root if it was added.
	 */
	public void add(Object object) {
		if (object==null)
			throw new NullPointerException("cannot add null to a tree");
		synchronized (LOCK) {
			int e;
			if ((e = elementIndex(object))>-1) // if we already have the object
				removeElement(e); // remove it
			ensureRootCapacity(1);
			elements[nelements] = object;
			depths[nelements] = 1;
			nelements++;
		}
	}

	/**
	 * Adds roots to the tree.
	 */
	public void add(Object[] objects) {
		synchronized (LOCK) {
			for (int i=0; i<objects.length; i++) {
				if (objects[i]==null)
					throw new NullPointerException("cannot add null to a tree");
				int e;
				if ((e = elementIndex(objects[i]))>-1) // if we already have the object
					removeElement(e); // remove it
			}
			ensureRootCapacity(objects.length);
			System.arraycopy(objects, 0, elements, nelements, objects.length);
			for (int i=nelements; i<nelements+objects.length; i++)
				depths[i] = 1;
			nelements += objects.length;
		}
	}

	/**
	 * Adds a child to the specified parent in the tree.
	 * @throws IllegalArgumentException if the parent does not exist in the tree or the child is the parent.
	 */
	public void add(Object parent, Object child) {
		if (parent==null)
			throw new NullPointerException("null parent specified");
		if (child==null)
			throw new NullPointerException("cannot add null to a tree");
		if (child==parent)
			throw new IllegalArgumentException("cannot add child to itself");
		synchronized (LOCK) {
			int p = parentIndex(parent), pe = -1;
			if (p<0) { // does it exist in the tree?
				if ((pe = elementIndex(parent))<0)
					throw new IllegalArgumentException("parent does not exist");
			} // so we'll add it to parents
			int e;
			if ((e = elementIndex(child))>-1) // if the child is already an element
				removeElement(e);

			if (p<0) { // add the parent to parents
				p = nparents;
				ensureParentCapacity(1);
				parents[p] = parent;
				children[p] = new Object[increment];
				nchildren[p] = 0;
				nparents++;
			}
			ensureChildCapacity(1, p);
			children[p][nchildren[p]] = child;

			// insert the child into elements and set its depth
			int depth = depth(parent);
			int off = pe+nchildren[p]+1;
			int len = nelements-off;
			Object[] buffer = new Object[len];
			System.arraycopy(elements, off, buffer, 0, len);
			elements[off] = child;
			System.arraycopy(buffer, 0, elements, off+1, len);
			int[] dbuffer = new int[len];
			System.arraycopy(depths, off, dbuffer, 0, len);
			depths[off] = depth+1;
			System.arraycopy(dbuffer, 0, depths, off+1, len);
			nelements++;

			nchildren[p]++;
		}
	}

	/**
	 * Adds children to the specified parent in the tree.
	 * @throws IllegalArgumentException if the parent does not exist in the tree or one of the children is the parent.
	 */
	public void add(Object parent, Object[] children) {
		if (parent==null)
			throw new NullPointerException("null parent specified");
		synchronized (LOCK) {
			int p = parentIndex(parent), pe = -1;
			if (p<0) { // does it exist in the tree?
				if ((pe = elementIndex(parent))<0)
					throw new IllegalArgumentException("parent does not exist");
			} // so we'll add it to parents
			for (int i=0; i<children.length; i++) {
				if (children[i]==null)
					throw new NullPointerException("cannot add null to a tree");
				if (children[i]==parent)
					throw new IllegalArgumentException("cannot add child to itself");
				int e;
				if ((e = elementIndex(children[i]))>-1) // if we already have the object
					removeElement(e); // remove it
			}
			if (p<0) { // add the parent to parents
				p = nparents;
				ensureParentCapacity(1);
				parents[p] = parent;
				this.children[p] = new Object[Math.max(increment, (children.length/increment)*increment)];
				nchildren[p] = 0;
				nparents++;
			}
			ensureChildCapacity(children.length, p);
			System.arraycopy(children, 0, this.children[p], nchildren[p], children.length);

			// insert the children into elements and set their depths
			int depth = depth(parent);
			int off = pe+nchildren[p]+1;
			int len = nelements-off;
			Object[] buffer = new Object[len];
			System.arraycopy(elements, off, buffer, 0, len);