treemap.java

纯java操作系统jnode,安装简单和操作简单的个人使用的Java操作系统

	 * @throws NoSuchElementException if the map is empty
	 */
	public Object firstKey() {
		if (root == getNil())
			throw new NoSuchElementException();
		return firstNode().key;
	}

	/**
	 * Return the value in this TreeMap associated with the supplied key,
	 * or <code>null</code> if the key maps to nothing.  NOTE: Since the value
	 * could also be null, you must use containsKey to see if this key
	 * actually maps to something.
	 *
	 * @param key the key for which to fetch an associated value
	 * @return what the key maps to, if present
	 * @throws ClassCastException if key is not comparable to elements in the map
	 * @throws NullPointerException if key is null but the comparator does not
	 *         tolerate nulls
	 * @see #put(Object, Object)
	 * @see #containsKey(Object)
	 */
	public Object get(Object key) {
		// Exploit fact that getNil().value == null.
		return getNode(key).value;
	}

	/**
	 * Returns a view of this Map including all entries with keys less than
	 * <code>toKey</code>. The returned map is backed by the original, so changes
	 * in one appear in the other. The submap will throw an
	 * {@link IllegalArgumentException} for any attempt to access or add an
	 * element beyond the specified cutoff. The returned map does not include
	 * the endpoint; if you want inclusion, pass the successor element.
	 *
	 * @param toKey the (exclusive) cutoff point
	 * @return a view of the map less than the cutoff
	 * @throws ClassCastException if <code>toKey</code> is not compatible with
	 *         the comparator (or is not Comparable, for natural ordering)
	 * @throws NullPointerException if toKey is null, but the comparator does not
	 *         tolerate null elements
	 */
	public SortedMap headMap(Object toKey) {
		return new SubMap(getNil(), toKey);
	}

	/**
	 * Returns a "set view" of this TreeMap's keys. The set is backed by the
	 * TreeMap, so changes in one show up in the other.  The set supports
	 * element removal, but not element addition.
	 *
	 * @return a set view of the keys
	 * @see #values()
	 * @see #entrySet()
	 */
	public Set keySet() {
		if (keys == null)
			// Create an AbstractSet with custom implementations of those methods
			// that can be overriden easily and efficiently.
			keys = new AbstractSet() {
			public int size() {
				return size;
			}

			public Iterator iterator() {
				return new TreeIterator(KEYS);
			}

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

			public boolean contains(Object o) {
				return containsKey(o);
			}

			public boolean remove(Object key) {
				Node n = getNode(key);
				if (n == getNil())
					return false;
				removeNode(n);
				return true;
			}
		};
		return keys;
	}

	/**
	 * Returns the last (highest) key in the map.
	 *
	 * @return the last key
	 * @throws NoSuchElementException if the map is empty
	 */
	public Object lastKey() {
		if (root == getNil())
			throw new NoSuchElementException("empty");
		return lastNode().key;
	}

	/**
	 * Puts the supplied value into the Map, mapped by the supplied key.
	 * The value may be retrieved by any object which <code>equals()</code>
	 * this key. NOTE: Since the prior value could also be null, you must
	 * first use containsKey if you want to see if you are replacing the
	 * key's mapping.
	 *
	 * @param key the key used to locate the value
	 * @param value the value to be stored in the HashMap
	 * @return the prior mapping of the key, or null if there was none
	 * @throws ClassCastException if key is not comparable to current map keys
	 * @throws NullPointerException if key is null, but the comparator does
	 *         not tolerate nulls
	 * @see #get(Object)
	 * @see Object#equals(Object)
	 */
	public Object put(Object key, Object value) {
		Node current = root;
		Node parent = getNil();
		int comparison = 0;

		// Find new node's parent.
		while (current != getNil()) {
			parent = current;
			comparison = compare(key, current.key);
			if (comparison > 0)
				current = current.right;
			else if (comparison < 0)
				current = current.left;
			else // Key already in tree.
				return current.setValue(value);
		}

		// Set up new node.
		Node n = new Node(key, value, RED);
		n.parent = parent;

		// Insert node in tree.
		modCount++;
		size++;
		if (parent == getNil()) {
			// Special case inserting into an empty tree.
			root = n;
			return null;
		}
		if (comparison > 0)
			parent.right = n;
		else
			parent.left = n;

		// Rebalance after insert.
		insertFixup(n);
		return null;
	}

	/**
	 * Copies all elements of the given map into this hashtable.  If this table
	 * already has a mapping for a key, the new mapping replaces the current
	 * one.
	 *
	 * @param m the map to be hashed into this
	 * @throws ClassCastException if a key in m is not comparable with keys
	 *         in the map
	 * @throws NullPointerException if a key in m is null, and the comparator
	 *         does not tolerate nulls
	 */
	public void putAll(Map m) {
		Iterator itr = m.entrySet().iterator();
		int pos = m.size();
		while (--pos >= 0) {
			Map.Entry e = (Map.Entry) itr.next();
			put(e.getKey(), e.getValue());
		}
	}

	/**
	 * Removes from the TreeMap and returns the value which is mapped by the
	 * supplied key. If the key maps to nothing, then the TreeMap remains
	 * unchanged, and <code>null</code> is returned. NOTE: Since the value
	 * could also be null, you must use containsKey to see if you are
	 * actually removing a mapping.
	 *
	 * @param key the key used to locate the value to remove
	 * @return whatever the key mapped to, if present
	 * @throws ClassCastException if key is not comparable to current map keys
	 * @throws NullPointerException if key is null, but the comparator does
	 *         not tolerate nulls
	 */
	public Object remove(Object key) {
		Node n = getNode(key);
		if (n == getNil())
			return null;
		// Note: removeNode can alter the contents of n, so save value now.
		Object result = n.value;
		removeNode(n);
		return result;
	}

	/**
	 * Returns the number of key-value mappings currently in this Map.
	 *
	 * @return the size
	 */
	public int size() {
		return size;
	}

	/**
	 * Returns a view of this Map including all entries with keys greater or
	 * equal to <code>fromKey</code> and less than <code>toKey</code> (a
	 * half-open interval). The returned map is backed by the original, so
	 * changes in one appear in the other. The submap will throw an
	 * {@link IllegalArgumentException} for any attempt to access or add an
	 * element beyond the specified cutoffs. The returned map includes the low
	 * endpoint but not the high; if you want to reverse this behavior on
	 * either end, pass in the successor element.
	 *
	 * @param fromKey the (inclusive) low cutoff point
	 * @param toKey the (exclusive) high cutoff point
	 * @return a view of the map between the cutoffs
	 * @throws ClassCastException if either cutoff is not compatible with
	 *         the comparator (or is not Comparable, for natural ordering)
	 * @throws NullPointerException if fromKey or toKey is null, but the
	 *         comparator does not tolerate null elements
	 * @throws IllegalArgumentException if fromKey is greater than toKey
	 */
	public SortedMap subMap(Object fromKey, Object toKey) {
		return new SubMap(fromKey, toKey);
	}

	/**
	 * Returns a view of this Map including all entries with keys greater or
	 * equal to <code>fromKey</code>. The returned map is backed by the
	 * original, so changes in one appear in the other. The submap will throw an
	 * {@link IllegalArgumentException} for any attempt to access or add an
	 * element beyond the specified cutoff. The returned map includes the
	 * endpoint; if you want to exclude it, pass in the successor element.
	 *
	 * @param fromKey the (inclusive) low cutoff point
	 * @return a view of the map above the cutoff
	 * @throws ClassCastException if <code>fromKey</code> is not compatible with
	 *         the comparator (or is not Comparable, for natural ordering)
	 * @throws NullPointerException if fromKey is null, but the comparator
	 *         does not tolerate null elements
	 */
	public SortedMap tailMap(Object fromKey) {
		return new SubMap(fromKey, getNil());
	}

	/**
	 * Returns a "collection view" (or "bag view") of this TreeMap's values.
	 * The collection is backed by the TreeMap, so changes in one show up
	 * in the other.  The collection supports element removal, but not element
	 * addition.
	 *
	 * @return a bag view of the values
	 * @see #keySet()
	 * @see #entrySet()
	 */
	public Collection values() {
		if (values == null)
			// We don't bother overriding many of the optional methods, as doing so
			// wouldn't provide any significant performance advantage.
			values = new AbstractCollection() {
			public int size() {
				return size;
			}

			public Iterator iterator() {
				return new TreeIterator(VALUES);
			}

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

	/**
	 * Compares two elements by the set comparator, or by natural ordering.
	 * Package visible for use by nested classes.
	 *
	 * @param o1 the first object
	 * @param o2 the second object
	 * @throws ClassCastException if o1 and o2 are not mutually comparable,
	 *         or are not Comparable with natural ordering
	 * @throws NullPointerException if o1 or o2 is null with natural ordering
	 */
	final int compare(Object o1, Object o2) {
		return (comparator == null ? ((Comparable) o1).compareTo(o2) : comparator.compare(o1, o2));
	}

	/**
	 * Maintain red-black balance after deleting a node.
	 *
	 * @param node the child of the node just deleted, possibly getNil()
	 * @param parent the parent of the node just deleted, never getNil()
	 */
	private void deleteFixup(Node node, Node parent) {
		// if (parent == getNil())
		//   throw new InternalError();
		// If a black node has been removed, we need to rebalance to avoid
		// violating the "same number of black nodes on any path" rule. If
		// node is red, we can simply recolor it black and all is well.
		while (node != root && node.color == BLACK) {
			if (node == parent.left) {
				// Rebalance left side.
				Node sibling = parent.right;
				// if (sibling == getNil())
				//   throw new InternalError();
				if (sibling.color == RED) {
					// Case 1: Sibling is red.
					// Recolor sibling and parent, and rotate parent left.
					sibling.color = BLACK;
					parent.color = RED;
					rotateLeft(parent);
					sibling = parent.right;
				}

				if (sibling.left.color == BLACK && sibling.right.color == BLACK) {
					// Case 2: Sibling has no red children.
					// Recolor sibling, and move to parent.
					sibling.color = RED;
					node = parent;
					parent = parent.parent;
				} else {
					if (sibling.right.color == BLACK) {
						// Case 3: Sibling has red left child.
						// Recolor sibling and left child, rotate sibling right.
						sibling.left.color = BLACK;
						sibling.color = RED;
						rotateRight(sibling);
						sibling = parent.right;
					}
					// Case 4: Sibling has red right child. Recolor sibling,
					// right child, and parent, and rotate parent left.
					sibling.color = parent.color;
					parent.color = BLACK;
					sibling.right.color = BLACK;
					rotateLeft(parent);
					node = root; // Finished.
				}
			} else {
				// Symmetric "mirror" of left-side case.
				Node sibling = parent.left;
				// if (sibling == getNil())
				//   throw new InternalError();
				if (sibling.color == RED) {
					// Case 1: Sibling is red.
					// Recolor sibling and parent, and rotate parent right.
					sibling.color = BLACK;
					parent.color = RED;
					rotateRight(parent);
					sibling = parent.left;
				}

				if (sibling.right.color == BLACK && sibling.left.color == BLACK) {
					// Case 2: Sibling has no red children.
					// Recolor sibling, and move to parent.
					sibling.color = RED;
					node = parent;
					parent = parent.parent;
				} else {
					if (sibling.left.color == BLACK) {
						// Case 3: Sibling has red right child.
						// Recolor sibling and right child, rotate sibling left.
						sibling.right.color = BLACK;
						sibling.color = RED;
						rotateLeft(sibling);
						sibling = parent.left;
					}
					// Case 4: Sibling has red left child. Recolor sibling,
					// left child, and parent, and rotate parent right.
					sibling.color = parent.color;
					parent.color = BLACK;
					sibling.left.color = BLACK;
					rotateRight(parent);
					node = root; // Finished.
				}
			}
		}
		node.color = BLACK;
	}

	/**
	 * Construct a perfectly balanced tree consisting of n "blank" nodes. This
	 * permits a tree to be generated from pre-sorted input in linear time.
	 *
	 * @param count the number of blank nodes, non-negative
	 */
	private void fabricateTree(final int count) {
		if (count == 0)
			return;

		// We color every row of nodes black, except for the overflow nodes.
		// I believe that this is the optimal arrangement. We construct the tree
		// in place by temporarily linking each node to the next node in the row,
		// then updating those links to the children when working on the next row.

		// Make the root node.
		root = new Node(null, null, BLACK);
		size = count;
		Node row = root;
		int rowsize;