// Link n and child.
		child.right = node;
		node.parent = child;
	}

	/**
	 * Return the node following the given one, or getNil() if there isn't one.
	 * Package visible for use by nested classes.
	 *
	 * @param node the current node, not getNil()
	 * @return the next node in sorted order
	 */
	final Node successor(Node node) {
		if (node.right != getNil()) {
			node = node.right;
			while (node.left != getNil())
				node = node.left;
			return node;
		}

		Node parent = node.parent;
		// Exploit fact that getNil().right == getNil() and node is non-getNil().
		while (node == parent.right) {
			node = parent;
			parent = parent.parent;
		}
		return parent;
	}

	/**
	 * Serializes this object to the given stream.
	 *
	 * @param s the stream to write to
	 * @throws IOException if the underlying stream fails
	 * @serialData the <i>size</i> (int), followed by key (Object) and value
	 *             (Object) pairs in sorted order
	 */
	private void writeObject(ObjectOutputStream s) throws IOException {
		s.defaultWriteObject();

		Node node = firstNode();
		s.writeInt(size);
		while (node != getNil()) {
			s.writeObject(node.key);
			s.writeObject(node.value);
			node = successor(node);
		}
	}

	/**
	 * Iterate over HashMap's entries. This implementation is parameterized
	 * to give a sequential view of keys, values, or entries.
	 *
	 * @author Eric Blake <ebb9@email.byu.edu>
	 */
	private final class TreeIterator implements Iterator {
		/**
		 * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
		 * or {@link #ENTRIES}.
		 */
		private final int type;
		/** The number of modifications to the backing Map that we know about. */
		private int knownMod = modCount;
		/** The last Entry returned by a next() call. */
		private Node last;
		/** The next entry that should be returned by next(). */
		private Node next;
		/**
		 * The last node visible to this iterator. This is used when iterating
		 * on a SubMap.
		 */
		private final Node max;

		/**
		 * Construct a new TreeIterator with the supplied type.
		 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
		 */
		TreeIterator(int type) {
			// FIXME gcj cannot handle this. Bug java/4695
			// this(type, firstNode(), getNil());
			this.type = type;
			this.next = firstNode();
			this.max = getNil();
		}

		/**
		 * Construct a new TreeIterator with the supplied type. Iteration will
		 * be from "first" (inclusive) to "max" (exclusive).
		 *
		 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
		 * @param first where to start iteration, getNil() for empty iterator
		 * @param max the cutoff for iteration, getNil() for all remaining nodes
		 */
		TreeIterator(int type, Node first, Node max) {
			this.type = type;
			this.next = first;
			this.max = max;
		}

		/**
		 * Returns true if the Iterator has more elements.
		 * @return true if there are more elements
		 * @throws ConcurrentModificationException if the TreeMap was modified
		 */
		public boolean hasNext() {
			if (knownMod != modCount)
				throw new ConcurrentModificationException();
			return next != max;
		}

		/**
		 * Returns the next element in the Iterator's sequential view.
		 * @return the next element
		 * @throws ConcurrentModificationException if the TreeMap was modified
		 * @throws NoSuchElementException if there is none
		 */
		public Object next() {
			if (knownMod != modCount)
				throw new ConcurrentModificationException();
			if (next == max)
				throw new NoSuchElementException();
			last = next;
			next = successor(last);

			if (type == VALUES)
				return last.value;
			else if (type == KEYS)
				return last.key;
			return last;
		}

		/**
		 * Removes from the backing TreeMap the last element which was fetched
		 * with the <code>next()</code> method.
		 * @throws ConcurrentModificationException if the TreeMap was modified
		 * @throws IllegalStateException if called when there is no last element
		 */
		public void remove() {
			if (last == null)
				throw new IllegalStateException();
			if (knownMod != modCount)
				throw new ConcurrentModificationException();

			removeNode(last);
			last = null;
			knownMod++;
		}
	} // class TreeIterator

	/**
	 * Implementation of {@link #subMap(Object, Object)} and other map
	 * ranges. This class provides a view of a portion of the original backing
	 * map, and throws {@link IllegalArgumentException} for attempts to
	 * access beyond that range.
	 *
	 * @author Eric Blake <ebb9@email.byu.edu>
	 */
	private final class SubMap extends AbstractMap implements SortedMap {
		/**
		 * The lower range of this view, inclusive, or getNil() for unbounded.
		 * Package visible for use by nested classes.
		 */
		final Object minKey;

		/**
		 * The upper range of this view, exclusive, or getNil() for unbounded.
		 * Package visible for use by nested classes.
		 */
		final Object maxKey;

		/**
		 * The cache for {@link #entrySet()}.
		 */
		private Set entries;

		/**
		 * Create a SubMap representing the elements between minKey (inclusive)
		 * and maxKey (exclusive). If minKey is getNil(), SubMap has no lower bound
		 * (headMap). If maxKey is getNil(), the SubMap has no upper bound (tailMap).
		 *
		 * @param minKey the lower bound
		 * @param maxKey the upper bound
		 * @throws IllegalArgumentException if minKey &gt; maxKey
		 */
		SubMap(Object minKey, Object maxKey) {
			if (minKey != getNil() && maxKey != getNil() && compare(minKey, maxKey) > 0)
				throw new IllegalArgumentException("fromKey > toKey");
			this.minKey = minKey;
			this.maxKey = maxKey;
		}

		/**
		 * Check if "key" is in within the range bounds for this SubMap. The
		 * lower ("from") SubMap range is inclusive, and the upper ("to") bound
		 * is exclusive. Package visible for use by nested classes.
		 *
		 * @param key the key to check
		 * @return true if the key is in range
		 */
		final boolean keyInRange(Object key) {
			return ((minKey == getNil() || compare(key, minKey) >= 0) && (maxKey == getNil() || compare(key, maxKey) < 0));
		}

		public void clear() {
			Node next = lowestGreaterThan(minKey, true);
			Node max = lowestGreaterThan(maxKey, false);
			while (next != max) {
				Node current = next;
				next = successor(current);
				removeNode(current);
			}
		}

		public Comparator comparator() {
			return comparator;
		}

		public boolean containsKey(Object key) {
			return keyInRange(key) && TreeMap.this.containsKey(key);
		}

		public boolean containsValue(Object value) {
			Node node = lowestGreaterThan(minKey, true);
			Node max = lowestGreaterThan(maxKey, false);
			while (node != max) {
				if (equals(value, node.getValue()))
					return true;
				node = successor(node);
			}
			return false;
		}

		public Set entrySet() {
			if (entries == null)
				// Create an AbstractSet with custom implementations of those methods
				// that can be overriden easily and efficiently.
				entries = new AbstractSet() {
				public int size() {
					return SubMap.this.size();
				}

				public Iterator iterator() {
					Node first = lowestGreaterThan(minKey, true);
					Node max = lowestGreaterThan(maxKey, false);
					return new TreeIterator(ENTRIES, first, max);
				}

				public void clear() {
					SubMap.this.clear();
				}

				public boolean contains(Object o) {
					if (!(o instanceof Map.Entry))
						return false;
					Map.Entry me = (Map.Entry) o;
					Object key = me.getKey();
					if (!keyInRange(key))
						return false;
					Node n = getNode(key);
					return n != getNil() && AbstractSet.equals(me.getValue(), n.value);
				}

				public boolean remove(Object o) {
					if (!(o instanceof Map.Entry))
						return false;
					Map.Entry me = (Map.Entry) o;
					Object key = me.getKey();
					if (!keyInRange(key))
						return false;
					Node n = getNode(key);
					if (n != getNil() && AbstractSet.equals(me.getValue(), n.value)) {
						removeNode(n);
						return true;
					}
					return false;
				}
			};
			return entries;
		}

		public Object firstKey() {
			Node node = lowestGreaterThan(minKey, true);
			if (node == getNil() || !keyInRange(node.key))
				throw new NoSuchElementException();
			return node.key;
		}

		public Object get(Object key) {
			if (keyInRange(key))
				return TreeMap.this.get(key);
			return null;
		}

		public SortedMap headMap(Object toKey) {
			if (!keyInRange(toKey))
				throw new IllegalArgumentException("key outside range");
			return new SubMap(minKey, toKey);
		}

		public Set keySet() {
			if (this.keys == null)
				// Create an AbstractSet with custom implementations of those methods
				// that can be overriden easily and efficiently.
				this.keys = new AbstractSet() {
				public int size() {
					return SubMap.this.size();
				}

				public Iterator iterator() {
					Node first = lowestGreaterThan(minKey, true);
					Node max = lowestGreaterThan(maxKey, false);
					return new TreeIterator(KEYS, first, max);
				}

				public void clear() {
					SubMap.this.clear();
				}

				public boolean contains(Object o) {
					if (!keyInRange(o))
						return false;
					return getNode(o) != getNil();
				}

				public boolean remove(Object o) {
					if (!keyInRange(o))
						return false;
					Node n = getNode(o);
					if (n != getNil()) {
						removeNode(n);
						return true;
					}
					return false;
				}
			};
			return this.keys;
		}

		public Object lastKey() {
			Node node = highestLessThan(maxKey);
			if (node == getNil() || !keyInRange(node.key))
				throw new NoSuchElementException();
			return node.key;
		}

		public Object put(Object key, Object value) {
			if (!keyInRange(key))
				throw new IllegalArgumentException("Key outside range");
			return TreeMap.this.put(key, value);
		}

		public Object remove(Object key) {
			if (keyInRange(key))
				return TreeMap.this.remove(key);
			return null;
		}

		public int size() {
			Node node = lowestGreaterThan(minKey, true);
			Node max = lowestGreaterThan(maxKey, false);
			int count = 0;
			while (node != max) {
				count++;
				node = successor(node);
			}
			return count;
		}

		public SortedMap subMap(Object fromKey, Object toKey) {
			if (!keyInRange(fromKey) || !keyInRange(toKey))
				throw new IllegalArgumentException("key outside range");
			return new SubMap(fromKey, toKey);
		}

		public SortedMap tailMap(Object fromKey) {
			if (!keyInRange(fromKey))
				throw new IllegalArgumentException("key outside range");
			return new SubMap(fromKey, maxKey);
		}

		public Collection values() {
			if (this.values == null)
				// Create an AbstractCollection with custom implementations of those
				// methods that can be overriden easily and efficiently.
				this.values = new AbstractCollection() {
				public int size() {
					return SubMap.this.size();
				}

				public Iterator iterator() {
					Node first = lowestGreaterThan(minKey, true);
					Node max = lowestGreaterThan(maxKey, false);
					return new TreeIterator(VALUES, first, max);
				}

				public void clear() {
					SubMap.this.clear();
				}
			};
			return this.values;
		}
	} // class SubMap  
} // class TreeMap