treearray.java

非常接近C/S操作方式的Java Ajax框架－ZK 用ZK框架使你的B/S应用程序更漂亮更易操作。 官网：www.zkoss.org

/* TreeArray.java

{{IS_NOTE

	Purpose: Red-black tree based array implementation of List interface.
	Description:
	History:
	 2001/5/9, Tom M. Yeh: Created.

}}IS_NOTE

Copyright (C) 2001 Potix Corporation. All Rights Reserved.

{{IS_RIGHT
	This program is distributed under GPL Version 2.0 in the hope that
	it will be useful, but WITHOUT ANY WARRANTY.
}}IS_RIGHT
*/
package org.zkoss.util;

import java.util.*;

/**
 * Red-black tree based array implementation of List interface.
 * Unlike LinkedList, the random access by index is as fast as log(n).
 * Unlike ArrayList, the insertion is as fast as log(n). It is
 * a great compromise between randown and sequential access.
 *
 * <p>In additions, it extends the features by also implementing
 * ListX.
 *
 * <p>The deriving class might override newEntry if it also
 * extends RbEntry; override insert(RbEntry, RbEntry) for adding element;
 * override delete(RbEntry) for removing element; clear() for
 * clearing the whole list.
 *
 * <p>Also, RbEntry.setElement might be overrided if the deriving class
 * wants to do something when the set method is called.
 *
 * <p>The iterator method is designed such that next() will proceed correctly
 * even if getElement() throws an exception.
 *
 * <p>The original algorithm is invented by Henri Chen.
 *
 * @author tomyeh
 * @see ListX
 */
public class TreeArray extends AbstractList
implements ListX, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 20060622L;

    protected static final boolean RED   = false;
    protected static final boolean BLACK = true;

	/**
	 * Caller shall use AbstractList.Entry instead of RbEntry for
	 * better portability.
	 */
	protected static class RbEntry implements Entry {
		protected Object	element; //use setElement and getElement
		protected int   	leftNum; //# of elements on its left sub-tree
		protected RbEntry	left;
		protected RbEntry	right;
		protected RbEntry	parent;
		protected boolean	color; //a black node
		protected boolean	orphan = false; //not belonging to any list

		protected RbEntry(Object element) {
			this.element = element;
		}

		/**
		 * Override it if you want to something when an element is retrieved.
		 * All other parts that get element must invoke this method
		 */
		public Object getElement() {
			return this.element;
		}

		/**
		 * Override it if you want to do something when an element
		 * is set. All other parts that set element will invoke this method.
		 */
		public void setElement(Object element) {
			this.element = element;
		}

		public final boolean isOrphan() {
			return orphan;
		}

		protected final RbEntry nextEntry() {
			if (right != null)
				return right.leftMost();
			return firstRightAncestor();
		}
		public final Entry next() {
			return nextEntry();
		}
		protected final RbEntry previousEntry() {
			if (left!=null)
				return left.rightMost();
			return firtLeftAncestor();
		}
		public final Entry previous() {
			return previousEntry();
		}

		//-- utilities --/
		/**
		 * Gets the leftmost leaf of the specified subtree.
		 * It is the entry with lowest index in the subtree.
		 */
		protected final RbEntry leftMost() {
			for (RbEntry p=this;; p=p.left)
				if (p.left==null)
					return p;
		}
		/**
		 * Gets the rihtmost leaf of the specified subtree.
		 * It is the entry with highest index in the subtree.
		 */
		protected final RbEntry rightMost() {
			for (RbEntry p=this;; p=p.right)
				if (p.right==null)
					return p;
		}
		/**
		 * Gets the first ancestor at the left of the specified entry.
		 * "At the left" we mean the returned ancesor's right is the entry
		 * or its ancestor. It is also the first parent with lower index.
		 */
		protected final RbEntry firtLeftAncestor() {
			for (RbEntry p=this; p.parent!=null; p=p.parent)
				if (p.parent.right == p)
					return p.parent;
			return null;
		}
		/**
		 * Gets the first parent at the right of the specified entry.
		 * "At the right" we mean the returned ancesor's right is the entry
		 * or its ancestor. It is also the first parent with higer index.
		 */
		protected final RbEntry firstRightAncestor() {
			for (RbEntry p=this; p.parent != null; p = p.parent)
				if (p.parent.left == p)
					return p.parent;
			return null;
		}

		//It doesn't maintain the tree but reset itself as an orphan.
		private final void setOrphan() {
			orphan = true;
			left = right = parent = null;
		}

		/**
		 * Called by TreeArray.clear to do clear recursively.
		 * Since it always be invoked to clear the whole tree,
		 * it doesn't have to maintain leftNum or other tree info.
		 * <p>However, this.element is kept.
		 */
		protected void clear() {
			if (left != null) left.clear();
			if (right != null) right.clear();
			setOrphan();
		}
	}//class RbEntry

	protected transient RbEntry _root = null;
	protected transient int _size = 0;
	protected transient int _hashCode = 0;

	public TreeArray() {
	}

	/** Constructor with a collection.
	 * @param c the collection to add; null to ignore
	 */
	public TreeArray(Collection c) {
		this();
		if (c != null)
			addAll(c);
	}

	//-- its own extension --//
	/**
	 * Adds an element by its natural ordering.
	 * This array must be sorted into ascending order according to
	 * the natural ordering. To sort, either sort
	 * or add all elements by order.
	 * <p>All elements are assumed to implement Comparable.
	 */
	public final void addByOrder(Object element) {
		int j = search(element);
		if (j < 0)
			j = -j-1;
		add(j, element);
	}
	/**
	 * Adds an element by the specified comparator.
	 * This array must be sorted into ascending order according to
	 * the specified comparator. To sort, either sort
	 * or add all elements by order.
	 */
	public final void addByOrder(Object element, Comparator c) {
		int j = search(element, c);
		if (j < 0)
			j = -j-1;
		add(j, element);
	}

	/**
	 * Removes an element by its natural ordering.
	 * This array must be sorted into ascending order according to
	 * the natural ordering. To sort, either sort
	 * or add all elements by order.
	 * <p>All elements are assumed to implement Comparable.
	 */
	public final boolean removeByOrder(Object element) {
		int j = search(element);
		if (j >= 0) {
			remove(j);
			return true;
		}
		return false;
	}
	/**
	 * Removes an element by the specified comparator.
	 * This array must be sorted into ascending order according to
	 * the specified comparator. To sort, either sort
	 * or add all elements by order.
	 */
	public final boolean removeByOrder(Object element, Comparator c) {
		int j = search(element, c);
		if (j >= 0) {
			remove(j);
			return true;
		}
		return false;
	}

	/**
	 * Adds all elements by their natural ordering.
	 * This array must be sorted into ascending order according to
	 * the natural ordering. To sort, either sort
	 * or add all elements by order.
	 * <p>All elements are assumed to implement Comparable.
	 */
	public final void addAllByOrder(Collection cn) {
		for (Iterator it = cn.iterator(); it.hasNext();)
			addByOrder(it.next());
	}
	/**
	 * Adds all elements by the specified comparator.
	 * This array must be sorted into ascending order according to
	 * the specified comparator. To sort, either sort
	 * or add all elements by order.
	 */
	public final void addAllByOrder(Collection cn, Comparator c) {
		for (Iterator it = cn.iterator(); it.hasNext();)
			addByOrder(it.next(), c);
	}

	/**
	 * Searches an element by its natural ordering.
	 * This array must be sorted into ascending order according to
	 * the natural ordering. To sort, either sort
	 * or add all elements by order, {@link #addByOrder(Object)}.
	 *
	 * <p>All elements are assumed to implement Comparable.
	 * Note: the element argument of this method is passed as the argument 
	 * of the compareTo method. Thus, it is OK to pass any kind of object,
	 * as long as the elements stored in this array is able to detect it.
	 *
	 * <p>For example, you might use a String to search the element,
	 * and your element's compareTo shall be implemented as follows.
	 *
	 * <pre><code>public int compareTo(Object o) {
	 *  return o instanceof String ?
	 *		_name.compareTo((String)o):
	 *		_name.compareTo(((YourClass)o).getName());
	 *}
	 */
	public final int search(Object element) {
		return Collections.binarySearch(this, element);
	}
	/**
	 * Searches an element by the specified comparator.
	 * This array must be sorted into ascending order according to
	 * the specified comparator. To sort, either sort
	 * or add all elements by order, {@link #addByOrder(Object, Comparator)}.
	 *
	 * <p>All elements are assumed to implement Comparable.
	 * Note: the element argument of this method is passed as the argument 
	 * of the compareTo method. Thus, it is OK to pass any kind of object,
	 * as long as the elements stored in this array is able to detect it.
	 */
	public final int search(Object element, Comparator c) {
		return Collections.binarySearch(this, element, c);
	}
	/**
	 * Gets an element by its natural ordering.
	 * It is a shortcut of get(search(element)).
	 *
	 * @see #search(Object)
	 * @return null if not found
	 */
	public final Object getByOrder(Object element) {
		int j = search(element);
		return j >= 0 ? get(j): null;
	}
	/**
	 * Gets an element by its natural ordering.
	 * It is a shortcut of get(search(element, c)).
	 *
	 * @see #search(Object, Comparator)
	 * @return null if not found
	 */
	public final Object getByOrder(Object element, Comparator c) {
		int j = search(element, c);
		return j >= 0 ? get(j): null;
	}
	/**
	 * Sorts all elements ascendingly by the natural ordering.
	 * <p>All elements are assumed to implement Comparable.
	 */
	public final void sort() {
		Collections.sort(this);
	}
	/**
	 * Sorts all elements ascendingly by the specified comparator.
	 */
	public final void sort(Comparator c) {
		Collections.sort(this, c);
	}

	//-- overriding AbstractList --//
	public final int size() {
		return _size;
	}

    public final Object get(int index) {
    	return getRbEntry(index).getElement();
    }

	public Object set(int index, Object element) {
		RbEntry p = getRbEntry(index);
		Object old = p.getElement();
		p.setElement(element);
		return old;
	}

	public void add(int index, Object element) {
		addEntry(index, element);
	}

	public Object remove(int index) {
		RbEntry p = getRbEntry(index);
		delete(p);
		return p.getElement();
	}

	public final Iterator iterator() {
		return listIterator();
	}

	public final ListIterator listIterator(int index) {
		return new Iter(index);
	}

	/**
	 * Clears the whole list. Overrides it if the derived class has
	 * other data to clear. Note it doesn't call removeEx.
	 *
	 * <p>Note clear actually invokes RbEntry.clear to do the real
	 * cleanup. Deriving classes might override RbEntry.clear.
	 */
	public void clear() {
		if (_root != null) {
			_root.clear();
			modCount++;
			_size = 0;
			_root = null;
		}
	}

	//-- overriding ListX --//
	protected final RbEntry getRbEntry(int index) {
		checkRange(index);

		int baseIndex = 0;
		RbEntry p = _root;
		do {
			int thisIndex = baseIndex + p.leftNum;
			if (index == thisIndex) {
				return p;
			} else if (index < thisIndex) {
				p = p.left;
			} else {
				baseIndex = thisIndex + 1;
				p = p.right;
			}
		} while (p != null); //it might be modified by someone else
		throw new ConcurrentModificationException();
	}

	public final Entry getEntry(int index) {
		return getRbEntry(index);
	}

	protected final int indexOfEntry(RbEntry p) {
		if (p.orphan)
			return -1;

		int v = p.leftNum;
		RbEntry lowParent = p.firtLeftAncestor();
		if (lowParent != null)
			 v += indexOfEntry(lowParent) + 1;
		return v;
	}	

	public final int indexOfEntry(Entry p) {
		return indexOfEntry((RbEntry)p);
	}

	public int hashCode() {
		if (_hashCode == 0)
			_hashCode = super.hashCode();
		return _hashCode;
	}

	//-- Extra features --//
	public final ListIterator entryIterator(int index) {
		return new EntryIter(index);
	}
	public final ListIterator entryIterator() {
		return new EntryIter(0);
	}

	/**
	 * Creates an instance of RbEntry. Override it if necessary
	 */
	protected RbEntry newEntry(Object element) {
		return new RbEntry(element);
	}

	public final Entry addEntry(Entry insertBefore, Object element) {
		return insert(checkNotOrphan(insertBefore), newEntry(element));
	}

	public final Entry addEntry(int index, Object element) {
		return insert(index, newEntry(element));
	}

	public final Entry addEntry(Object element) {
		return addEntry(_size, element);
	}

	public final void removeEntry(Entry p) {
		delete(checkNotOrphan(p));
	}

	public final Entry removeEntry(int index) {
		return delete(index);
	}

	//-- utilities --/
	/** Returns the first node. */
	protected final RbEntry first() {
		return _root==null ? null: _root.leftMost();
	}

	private static final boolean colorOf(RbEntry p) {
		return (p == null ? BLACK : p.color);
	}

	private static final RbEntry  parentOf(RbEntry p) {
		return (p == null ? null: p.parent);
	}

	private static final void setColor(RbEntry p, boolean c) {
		if (p != null)  p.color = c;
	}

	private static final RbEntry leftOf(RbEntry p) {
		return (p == null)? null: p.left;
	}