tree.java

一个用Java开发的Web邮局

			System.arraycopy(children, 0, elements, off, children.length);
			System.arraycopy(buffer, 0, elements, off+children.length, len);

			int[] dbuffer = new int[len];
			System.arraycopy(depths, off, dbuffer, 0, len);
			for (int i=off; i<off+children.length; i++)
				depths[i] = depth+1;
			System.arraycopy(dbuffer, 0, depths, off+children.length, len);
			nelements += children.length;

			nchildren[p] += children.length;
		}
	}

	// Returns the depth of an object in the tree
	private int depth(Object object) {
		Object parent = parentOf(object);
		if (parent==null)
			return 1;
		else
			return depth(parent)+1;
	}

	/**
	 * Removes the specified object and all its children from the tree.
	 * Computationally pretty expensive.
	 */
	public void remove(Object object) {
		if (object==null)
			return; // i mean, really...
		synchronized (LOCK) {
			int e = elementIndex(object);
			if (e>-1)
				removeElement(e);
		}
	}

	void removeElement(int e) {
		int len = 0;
        // does this element have children?
		for (int p=0; p<nparents; p++) {
			if (parents[p]==elements[e]) {
				int nc = nchildren[p];
                // remove the children of this parent first
                Object[] pchildren = new Object[nc];
				System.arraycopy(children[p], 0, pchildren, 0, nc);
				for (int c=0; c<nc; c++) {
					int ce = elementIndex(pchildren[c]);
					if (ce>-1)
						removeElement(ce);
				}
                // remove the parent
				if ((len = nparents-p-1)>0) {
					System.arraycopy(parents, p+1, parents, p, len);
					System.arraycopy(children, p+1, children, p, len);
					System.arraycopy(nchildren, p+1, nchildren, p, len);
				}
				nparents--; p--;
			} else {
				// is this element a child of another parent?
				for (int c=0; c<nchildren[p]; c++) {
					if (children[p][c]==elements[e]) {
						// remove this element from the children array
						if ((len = nchildren[p]-c-1)>0) {
							System.arraycopy(children[p], c+1, children[p], c, len);
						}
						nchildren[p]--; c--;
					}
				}
			}
		}
		if ((len = nelements-e-1)>0) {
			System.arraycopy(elements, e+1, elements, e, len);
			System.arraycopy(depths, e+1, depths, e, len);
		}
		nelements--;
	}
	
	/**
	 * Removes the specified objects and all their children from the tree.
	 * @throws NullPointerException if an object does not exist in the tree.
	 */
	public void remove(Object[] objects) {
		for (int i=0; i<objects.length; i++)
			remove(objects[i]);
	}
	
	/**
	 * Recursively removes the specified object's children from the tree.
	 * @throws NullPointerException if the object does not exist in the tree.
	 */
	public void removeChildren(Object parent) {
		synchronized (LOCK) {
			removeChildrenImpl(parent);
		}
	}

	void removeChildrenImpl(Object parent) {
		int p = parentIndex(parent);
		if (p>-1) {
			for (int c=0; c<nchildren[p]; c++)
				removeChildrenImpl(children[p][c]);
			children[p] = new Object[increment];
			nchildren[p] = 0;
		}
	}

	/**
	 * Removes all objects from the tree.
	 */
	public void clear() {
		synchronized (LOCK) {
			parents = new Object[increment];
			nparents = 0;
			nchildren = new int[increment];
			for (int i=0; i<increment; i++)
				nchildren[i] = 0;
			children = new Object[increment][increment];
			elements = new Object[increment];
			depths = new int[increment];
			nelements = 0;
		}
	}

	/**
	 * Returns the depth of the specified object in the tree.
	 * Roots have a depth of 1.
	 */
	public int getDepth(Object object) {
		synchronized (LOCK) {
			int e = elementIndex(object);
			if (e==-1) {
				//System.out.println("Warning: "+object+" not found");
				//new Throwable().printStackTrace();
				return -1;
			}
			return depths[e];
		}
	}

	/**
	 * Returns the roots in this tree.
	 */
	public Object[] getRoots() {
		synchronized (LOCK) {
			Vector v = new Vector();
			for (int i=0; i<nelements; i++) {
				if (depths[i]==1)
					v.addElement(elements[i]);
			}
			Object[] roots = new Object[v.size()];
			v.copyInto(roots);
			return roots;
		}
	}

	/**
	 * Returns the number of roots in this tree.
	 */
	public int getRootCount() {
		synchronized (LOCK) {
			Vector v = new Vector();
			for (int i=0; i<nelements; i++) {
				if (depths[i]==1)
					v.addElement(elements[i]);
			}
			return v.size();
		}
	}

	/**
	 * Returns all the objects in this tree in depth-first order.
	 */
	public Object[] getTree() {
		synchronized (LOCK) {
			Object[] objects = new Object[nelements];
			System.arraycopy(elements, 0, objects, 0, nelements);
			return objects;
		}
	}

	/**
	 * Returns the number of objects in this tree.
	 */
	public int getTreeCount() {
		return nelements;
	}

	/**
	 * Indicates whether there are any children in this tree.
	 */
	public boolean hasChildren() {
		synchronized (LOCK) {
			for (int p=0; p<nparents; p++)
				if (nchildren[p]>0)
					return true;
		}
		return false;
	}
	
	/**
	 * Sorts the objects in the tree according to the specified object collator.
	 * This has no effect if a collator has not been defined.
	 */
	public void sort(ObjectCollator collator) {
		if (collator==null) throw new NullPointerException("null collator");
		synchronized (LOCK) {
			Sorter sorter = this.new Sorter(collator);
			elements = sorter.newelements;
			depths = sorter.newdepths;
		}
	}

	class Sorter {

		Object[] newelements;
		int[] newdepths;
		int count = 0;

		Sorter(ObjectCollator collator) {
			// first sort the roots
			Vector v = new Vector();
			for (int i=0; i<nelements; i++) {
				if (depths[i]==1)
					v.addElement(elements[i]);
			}
			Object[] roots = new Object[v.size()];
			v.copyInto(roots);
			sort(roots, 0, roots.length-1, collator);
			// now sort the children of each parent
			for (int p=0; p<nparents; p++)
				sort(children[p], 0, nchildren[p]-1, collator);
			// now create a new elements array positioning the elements according to the new order
			newelements = new Object[elements.length];
			newdepths = new int[elements.length];
			for (int r=0; r<roots.length; r++) {
				newelements[count] = roots[r];
				newdepths[count] = depths[elementIndex(roots[r])];
				count++;
				appendChildren(roots[r]);
			}
		}

		void appendChildren(Object parent) {
			for (int p=0; p<nparents; p++) {
				if (parent==parents[p]) {
					for (int c=0; c<nchildren[p]; c++) {
						newelements[count] = children[p][c];
						newdepths[count] = getDepth(children[p][c]);
						count++;
						appendChildren(children[p][c]);
					}
					break;
				}
			}
		}
		
	}

	// Quicksort algorithm.
	static void sort(Object[] objects, int first, int last, ObjectCollator collator) {
		int lo = first, hi = last;
		Object mid;
		if (last>first) {
			mid = objects[(first+last)/2];
			while (lo<=hi) {
				while (lo<last && collator.compare(objects[lo], mid)<0)
					lo += 1;
				while (hi>first && collator.compare(objects[hi], mid)>0)
					hi -= 1;
				if (lo<=hi) { // swap
					Object tmp = objects[lo];
					objects[lo] = objects[hi];
					objects[hi] = tmp;
					lo += 1;
					hi -= 1;
				}
			}
			if (first<hi)
				sort(objects, first, hi, collator);
			if (lo<last)
				sort(objects, lo, last, collator);
		}
	}

	public void printArray(String name, Object[] array, int count) {
		System.out.println(name+": length="+array.length+", count="+count);
		for (int i=0; i<count; i++)
			System.out.println("\t"+array[i]);
	}

	public void printElements() {
        System.out.println("elements=");
		for (int i=0; i<nelements; i++) {
			StringBuffer buffer = new StringBuffer();
			buffer.append(Integer.toString(depths[i]));
			for (int j=0; j<depths[i]; j++)
				buffer.append("  ");
			buffer.append(elements[i]);
			System.out.println(buffer.toString());
		}
		System.out.println("tree=");
		for (int p=0; p<nparents; p++) {
			System.out.println(parents[p]);
			for (int c=0; c<nchildren[p]; c++)
				System.out.println("  "+children[p][c]);
		}
	}

	// -- Utility methods --

	public String toString() {
		StringBuffer buffer = new StringBuffer();
		buffer.append(getClass().getName());
		buffer.append("[");
		buffer.append("nelements="+nelements);
		buffer.append(",elements.length="+elements.length);
		buffer.append(",depths.length="+depths.length);
		buffer.append(",nparents="+nparents);
		buffer.append(",parents.length="+parents.length);
		buffer.append("]");
		return buffer.toString();
	}

}