treearray.java

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

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

	protected final RbEntry insert(int index, RbEntry p) {
		checkRangePlus(index); //index==_size is ok
		return insert(index<_size ? getRbEntry(index): null, p);
	}

	private static final void changeAncestorLeftNum(RbEntry p, int diff) {
		for (; p.parent!=null; p=p.parent)
			if (p.parent.left == p)
				p.parent.leftNum += diff;
	}

	/**
	 * All add methods are done thru this method. Override it if necessary.
	 *
	 * <p>Note: p is inserted <b>before</b> insertBefore.
	 */
	protected RbEntry insert(RbEntry insertBefore, final RbEntry p) {
		assert !p.orphan;
		if (_root == null) {
			_root = p;
		} else {
			if (insertBefore != null && insertBefore.left == null) {
				insertBefore.left = p;
			} else {
				insertBefore = insertBefore==null ? _root: insertBefore.left;
				insertBefore = insertBefore.rightMost();
				insertBefore.right = p;
			}
			p.parent = insertBefore;

			changeAncestorLeftNum(p, 1);
		}

		fixAfterInsert(p); //fix up for red-black rule
		incSize();
		return p;
	}

	private final void rotateLeft(RbEntry x) {
		RbEntry y = x.right;
		x.right = y.left;
		if (y.left != null)
			y.left.parent = x;
		y.parent = x.parent;
		if (x.parent == null)
			_root = y;
		else if (x.parent.left == x)
			x.parent.left = y;
		else
			x.parent.right = y;
		y.left = x;
		x.parent = y;

		y.leftNum += x.leftNum+1;
	}

	private final void rotateRight(RbEntry y) {
		RbEntry x = y.left;
		y.left = x.right;
		if (x.right != null)
			x.right.parent = y;
		x.parent = y.parent;
		if (y.parent == null)
			_root = x;
		else if (y.parent.right == y)
			y.parent.right = x;
		else
			y.parent.left = x;
		x.right = y;
		y.parent = x;

		y.leftNum -= x.leftNum+1;
	}

	private final void fixAfterInsert(RbEntry x) {
		x.color = RED;
		while (x!=null && x!=_root && x.parent.color==RED) {
			if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
				RbEntry y = rightOf(parentOf(parentOf(x)));
				if (colorOf(y) == RED) {
					setColor(parentOf(x), BLACK);
					setColor(y, BLACK);
					setColor(parentOf(parentOf(x)), RED);
					x = parentOf(parentOf(x));
				} else {
					if (x == rightOf(parentOf(x))) {
						x = parentOf(x);
						rotateLeft(x);
					}
					setColor(parentOf(x), BLACK);
					setColor(parentOf(parentOf(x)), RED);
					if (parentOf(parentOf(x)) != null)
						rotateRight(parentOf(parentOf(x)));
				}
			} else {
				RbEntry y = leftOf(parentOf(parentOf(x)));
				if (colorOf(y) == RED) {
					setColor(parentOf(x), BLACK);
					setColor(y, BLACK);
					setColor(parentOf(parentOf(x)), RED);
					x = parentOf(parentOf(x));
				} else {
					if (x == leftOf(parentOf(x))) {
						x = parentOf(x);
						rotateRight(x);
					}
					setColor(parentOf(x),  BLACK);
					setColor(parentOf(parentOf(x)), RED);
					if (parentOf(parentOf(x)) != null)
						rotateLeft(parentOf(parentOf(x)));
				}
			}
		}//while
		_root.color = BLACK;
	}

	protected RbEntry delete(int index) {
		RbEntry p = getRbEntry(index);
		delete(p);
		return p;
	}

	/**
	 * All remove methods are done thru this method. Override it if necessary.
	 */
	protected void delete(RbEntry p) {
		assert !p.orphan;
		if (p.left!=null && p.right!=null)
			swapPosition(p.nextEntry(), p);
				//Make sure at least one of left or right is null by
				//swapping with next, whose left is null (right.leftMost)

		changeAncestorLeftNum(p, -1);
		decSize();

		RbEntry replacement = (p.left != null ? p.left : p.right);
		if (replacement != null) {
			replacement.parent = p.parent;
			if (p.parent == null) 
				_root = replacement;
			else if (p == p.parent.left)
				p.parent.left  = replacement;
			else
				p.parent.right = replacement;

			if (p.color == BLACK)
				fixAfterDelete(replacement);
		} else { // No children
			if (p.parent == null) // size==1
				_root = null;
			else if (p == p.parent.left)
					p.parent.left = null;
			else if (p == p.parent.right)
					p.parent.right = null;
		}
		p.setOrphan();
	}

	/**
	 * Swap the linkages of two nodes in a tree. We cannot only swap the
	 * element field because the binding of entry and element have to remain.
	 */
	private final void swapPosition(RbEntry x, RbEntry y) {
		// Save initial values.
		RbEntry px = x.parent, lx = x.left, rx = x.right;
		RbEntry py = y.parent, ly = y.left, ry = y.right;
		boolean xWasLeftChild = px != null && x == px.left;
		boolean yWasLeftChild = py != null && y == py.left;

		// Swap, handling special cases of one being the other's parent.
		if (x == py) {  // x was y's parent
			x.parent = y;
			if (yWasLeftChild) {
				y.left = x;
				y.right = rx;
			} else {
				y.right = x;
				y.left = lx;
			}
		} else {
			x.parent = py;
			if (py != null) {
				if (yWasLeftChild)
					py.left = x;
				else
					py.right = x;
			}
			y.left = lx;
			y.right = rx;
		}

		if (y == px) { // y was x's parent
			y.parent = x;
			if (xWasLeftChild) {
				x.left = y;
				x.right = ry;
			} else {
				x.right = y;
				x.left = ly;
			}
		} else {
			y.parent = px;
			if (px != null) {
				if (xWasLeftChild)
					px.left = y;
				else
					px.right = y;
			}
			x.left = ly;
			x.right = ry;
		}

		// Fix children's parent pointers
		if (x.left != null)
			x.left.parent = x;
		if (x.right != null)
			x.right.parent = x;
		if (y.left != null)
			y.left.parent = y;
		if (y.right != null)
			y.right.parent = y;

		// Swap colors
		boolean c = x.color;
		x.color = y.color;
		y.color = c;

		// Swap leftNum
		int v = x.leftNum;
		x.leftNum = y.leftNum;
		y.leftNum = v;

		// Check if root changed
		if (_root == x)
			_root = y;
		else if (_root == y)
			_root = x;
	}

	private void fixAfterDelete(RbEntry x) {
		while (x != _root && colorOf(x) == BLACK) {
			if (x == leftOf(parentOf(x))) {
				RbEntry sib = rightOf(parentOf(x));

				if (colorOf(sib) == RED) {
					setColor(sib, BLACK);
					setColor(parentOf(x), RED);
					rotateLeft(parentOf(x));
					sib = rightOf(parentOf(x));
				}

				if (colorOf(leftOf(sib))  == BLACK &&
					colorOf(rightOf(sib)) == BLACK) {
					setColor(sib,  RED);
					x = parentOf(x);
				} else {
					if (colorOf(rightOf(sib)) == BLACK) {
						setColor(leftOf(sib), BLACK);
						setColor(sib, RED);
						rotateRight(sib);
						sib = rightOf(parentOf(x));
					}
					setColor(sib, colorOf(parentOf(x)));
					setColor(parentOf(x), BLACK);
					setColor(rightOf(sib), BLACK);
					rotateLeft(parentOf(x));
					x = _root;
				}
			} else { // symmetric
				RbEntry sib = leftOf(parentOf(x));

				if (colorOf(sib) == RED) {
					setColor(sib, BLACK);
					setColor(parentOf(x), RED);
					rotateRight(parentOf(x));
					sib = leftOf(parentOf(x));
				}

				if (colorOf(rightOf(sib)) == BLACK &&
					colorOf(leftOf(sib)) == BLACK) {
					setColor(sib,  RED);
					x = parentOf(x);
				} else {
					if (colorOf(leftOf(sib)) == BLACK) {
						setColor(rightOf(sib), BLACK);
						setColor(sib, RED);
						rotateLeft(sib);
						sib = leftOf(parentOf(x));
					}
					setColor(sib, colorOf(parentOf(x)));
					setColor(parentOf(x), BLACK);
					setColor(leftOf(sib), BLACK);
					rotateRight(parentOf(x));
					x = _root;
				}
			}
		}

		setColor(x, BLACK);
	}

	protected final void incSize() {modCount++; _size++; }
	protected final void decSize() {modCount++; _size--; }

	protected final void checkRange(int index) {
		if (index >= _size || index < 0)
			indexOutOfBounds(index);
	}

	protected final void checkRangePlus(int index) {
		if (index > _size || index < 0)
			indexOutOfBounds(index);
	}

	protected final void indexOutOfBounds(int index) {
		throw new IndexOutOfBoundsException(
				"Index: " + index + ", Size: " + _size);
	}

	/**
	 * Converts and checks whether it is not orphan
	 */
	protected final RbEntry checkNotOrphan(Entry entry) {
		RbEntry p = (RbEntry)entry;
		if (p.orphan)
			throw new IllegalStateException();
		return p;
	}

	private class EntryIter implements ListIterator {
		private RbEntry _cursor;
		private RbEntry _lastRet = null;
		private int _expectedModCount;

		private EntryIter(int index) {
			checkRangePlus(index); //index==_size is ok

			_cursor = index<_size ? getRbEntry(index): null;
			_expectedModCount = modCount;
		}
		
		public final boolean hasNext() {
			checkComodification();
			return _cursor != null;
		}
		public Object next() {
			checkComodification();

			if (_cursor == null)
				throw new NoSuchElementException();

			_lastRet = _cursor;
			Object obj = _cursor;
			_cursor = _cursor.nextEntry();
			return obj;
		}

		public final boolean hasPrevious() {
			checkComodification();
			if (_cursor == null)
				return _size > 0;
			else
				return _cursor.previousEntry() != null;
		}
		public Object previous() {
			checkComodification();

			if (_cursor == null) {
				if (_size == 0)
					throw new NoSuchElementException();
				_cursor = getRbEntry(_size-1);
			} else {
				RbEntry prev = _cursor.previousEntry();
				if (prev == null)
					throw new NoSuchElementException();
				_cursor = prev;
			}
			_lastRet = _cursor;
			return _cursor;
		}

		public final int nextIndex() {
			return _cursor==null ? _size: indexOfEntry(_cursor);
		}
		public final int previousIndex() {
			return _cursor==null ? _size-1: indexOfEntry(_cursor)-1;
		}

		public final void remove() {
			if (_lastRet == null)
				throw new IllegalStateException();

			checkComodification();

			if (_lastRet == _cursor)
				_cursor = _cursor.nextEntry();

			delete(_lastRet);
			_expectedModCount = modCount;
			_lastRet = null;
		}

		public final void set(Object obj) {
			if (_lastRet == null)
				throw new IllegalStateException();

			checkComodification();

			_lastRet.setElement(obj);
			//no need to update _expectdModCount here
		}
		public final Object get() {
			return _lastRet.getElement();
		}

		public final void add(Object obj) {
			checkComodification();

			insert(_cursor, newEntry(obj));
			_expectedModCount = modCount;
		}

		private final void checkComodification() {
			if (modCount != _expectedModCount)
				throw new ConcurrentModificationException();
		}
	}//EntryIter

	private class Iter extends EntryIter {
		private Iter(int index) {
			super(index);
		}
		public final Object next() {
			return ((RbEntry)super.next()).getElement();
		}
		public final Object previous() {
			return ((RbEntry)super.previous()).getElement();
		}
	}//Iter

	//-- cloneable --//
	public Object clone() {
		TreeArray clone;
		try {
			clone = (TreeArray)super.clone();
		}catch(CloneNotSupportedException e) {
			throw new InternalError();
		}

		//Put clone into "virgin" state
		clone._size = 0;
		clone._root = null;
		clone.modCount = 0;

		// Initialize clone with our elements
		for (RbEntry p = first(); p != null; p = p.nextEntry())
		    clone.add(p.getElement());

		return clone;
	}

	//-- Serializable --//
	//NOTE: they must be declared as private
	private synchronized void writeObject(java.io.ObjectOutputStream s)
	throws java.io.IOException {
		s.defaultWriteObject();

        s.writeInt(_size);

		for (RbEntry p = first(); p != null; p = p.nextEntry())
			s.writeObject(p.getElement());
	}

	private synchronized void readObject(java.io.ObjectInputStream s)
	throws java.io.IOException, ClassNotFoundException {
		s.defaultReadObject();

		int size = s.readInt();

		for (int i=0; i<size; i++)
			add(s.readObject());
	}
}