treemap.java

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

		// Fill each row that is completely full of nodes.
		for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1) {
			Node parent = row;
			Node last = null;
			for (int i = 0; i < rowsize; i += 2) {
				Node left = new Node(null, null, BLACK);
				Node right = new Node(null, null, BLACK);
				left.parent = parent;
				left.right = right;
				right.parent = parent;
				parent.left = left;
				Node next = parent.right;
				parent.right = right;
				parent = next;
				if (last != null)
					last.right = left;
				last = right;
			}
			row = row.left;
		}

		// Now do the partial final row in red.
		int overflow = count - rowsize;
		Node parent = row;
		int i;
		for (i = 0; i < overflow; i += 2) {
			Node left = new Node(null, null, RED);
			Node right = new Node(null, null, RED);
			left.parent = parent;
			right.parent = parent;
			parent.left = left;
			Node next = parent.right;
			parent.right = right;
			parent = next;
		}
		// Add a lone left node if necessary.
		if (i - overflow == 0) {
			Node left = new Node(null, null, RED);
			left.parent = parent;
			parent.left = left;
			parent = parent.right;
			left.parent.right = getNil();
		}
		// Unlink the remaining nodes of the previous row.
		while (parent != getNil()) {
			Node next = parent.right;
			parent.right = getNil();
			parent = next;
		}
	}

	/**
	 * Returns the first sorted node in the map, or getNil() if empty. Package
	 * visible for use by nested classes.
	 *
	 * @return the first node
	 */
	final Node firstNode() {
		// Exploit fact that getNil().left == getNil().
		Node node = root;
		while (node.left != getNil())
			node = node.left;
		return node;
	}

	/**
	 * Return the TreeMap.Node associated with key, or the getNil() node if no such
	 * node exists in the tree. Package visible for use by nested classes.
	 *
	 * @param key the key to search for
	 * @return the node where the key is found, or getNil()
	 */
	final Node getNode(Object key) {
		Node current = root;
		while (current != getNil()) {
			int comparison = compare(key, current.key);
			if (comparison > 0)
				current = current.right;
			else if (comparison < 0)
				current = current.left;
			else
				return current;
		}
		return current;
	}

	/**
	 * Find the "highest" node which is &lt; key. If key is getNil(), return last
	 * node. Package visible for use by nested classes.
	 *
	 * @param key the upper bound, exclusive
	 * @return the previous node
	 */
	final Node highestLessThan(Object key) {
		if (key == getNil())
			return lastNode();

		Node last = getNil();
		Node current = root;
		int comparison = 0;

		while (current != getNil()) {
			last = current;
			comparison = compare(key, current.key);
			if (comparison > 0)
				current = current.right;
			else if (comparison < 0)
				current = current.left;
			else // Exact match.
				return predecessor(last);
		}
		return comparison <= 0 ? predecessor(last) : last;
	}

	/**
	 * Maintain red-black balance after inserting a new node.
	 *
	 * @param n the newly inserted node
	 */
	private void insertFixup(Node n) {
		// Only need to rebalance when parent is a RED node, and while at least
		// 2 levels deep into the tree (ie: node has a grandparent). Remember
		// that getNil().color == BLACK.
		while (n.parent.color == RED && n.parent.parent != getNil()) {
			if (n.parent == n.parent.parent.left) {
				Node uncle = n.parent.parent.right;
				// Uncle may be getNil(), in which case it is BLACK.
				if (uncle.color == RED) {
					// Case 1. Uncle is RED: Change colors of parent, uncle,
					// and grandparent, and move n to grandparent.
					n.parent.color = BLACK;
					uncle.color = BLACK;
					uncle.parent.color = RED;
					n = uncle.parent;
				} else {
					if (n == n.parent.right) {
						// Case 2. Uncle is BLACK and x is right child.
						// Move n to parent, and rotate n left.
						n = n.parent;
						rotateLeft(n);
					}
					// Case 3. Uncle is BLACK and x is left child.
					// Recolor parent, grandparent, and rotate grandparent right.
					n.parent.color = BLACK;
					n.parent.parent.color = RED;
					rotateRight(n.parent.parent);
				}
			} else {
				// Mirror image of above code.
				Node uncle = n.parent.parent.left;
				// Uncle may be getNil(), in which case it is BLACK.
				if (uncle.color == RED) {
					// Case 1. Uncle is RED: Change colors of parent, uncle,
					// and grandparent, and move n to grandparent.
					n.parent.color = BLACK;
					uncle.color = BLACK;
					uncle.parent.color = RED;
					n = uncle.parent;
				} else {
					if (n == n.parent.left) {
						// Case 2. Uncle is BLACK and x is left child.
						// Move n to parent, and rotate n right.
						n = n.parent;
						rotateRight(n);
					}
					// Case 3. Uncle is BLACK and x is right child.
					// Recolor parent, grandparent, and rotate grandparent left.
					n.parent.color = BLACK;
					n.parent.parent.color = RED;
					rotateLeft(n.parent.parent);
				}
			}
		}
		root.color = BLACK;
	}

	/**
	 * Returns the last sorted node in the map, or getNil() if empty.
	 *
	 * @return the last node
	 */
	private Node lastNode() {
		// Exploit fact that getNil().right == getNil().
		Node node = root;
		while (node.right != getNil())
			node = node.right;
		return node;
	}

	/**
	 * Find the "lowest" node which is &gt;= key. If key is getNil(), return either
	 * getNil() or the first node, depending on the parameter first.
	 * Package visible for use by nested classes.
	 *
	 * @param key the lower bound, inclusive
	 * @param first true to return the first element instead of getNil() for getNil() key
	 * @return the next node
	 */
	final Node lowestGreaterThan(Object key, boolean first) {
		if (key == getNil())
			return first ? firstNode() : getNil();

		Node last = getNil();
		Node current = root;
		int comparison = 0;

		while (current != getNil()) {
			last = current;
			comparison = compare(key, current.key);
			if (comparison > 0)
				current = current.right;
			else if (comparison < 0)
				current = current.left;
			else
				return current;
		}
		return comparison > 0 ? successor(last) : last;
	}

	/**
	 * Return the node preceding the given one, or getNil() if there isn't one.
	 *
	 * @param node the current node, not getNil()
	 * @return the prior node in sorted order
	 */
	private Node predecessor(Node node) {
		if (node.left != getNil()) {
			node = node.left;
			while (node.right != getNil())
				node = node.right;
			return node;
		}

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

	/**
	 * Construct a tree from sorted keys in linear time. Package visible for
	 * use by TreeSet.
	 *
	 * @param s the stream to read from
	 * @param count the number of keys to read
	 * @param readValue true to read values, false to insert "" as the value
	 * @throws ClassNotFoundException if the underlying stream fails
	 * @throws IOException if the underlying stream fails
	 * @see #readObject(ObjectInputStream)
	 * @see TreeSet#readObject(ObjectInputStream)
	 */
	final void putFromObjStream(ObjectInputStream s, int count, boolean readValues) throws IOException, ClassNotFoundException {
		fabricateTree(count);
		Node node = firstNode();

		while (--count >= 0) {
			node.key = s.readObject();
			node.value = readValues ? s.readObject() : "";
			node = successor(node);
		}
	}

	/**
	 * Construct a tree from sorted keys in linear time, with values of "".
	 * Package visible for use by TreeSet.
	 *
	 * @param keys the iterator over the sorted keys
	 * @param count the number of nodes to insert
	 * @see TreeSet#TreeSet(SortedSet)
	 */
	final void putKeysLinear(Iterator keys, int count) {
		fabricateTree(count);
		Node node = firstNode();

		while (--count >= 0) {
			node.key = keys.next();
			node.value = "";
			node = successor(node);
		}
	}

	/**
	 * Deserializes this object from the given stream.
	 *
	 * @param s the stream to read from
	 * @throws ClassNotFoundException if the underlying stream fails
	 * @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 readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
		s.defaultReadObject();
		int size = s.readInt();
		putFromObjStream(s, size, true);
	}

	/**
	 * Remove node from tree. This will increment modCount and decrement size.
	 * Node must exist in the tree. Package visible for use by nested classes.
	 *
	 * @param node the node to remove
	 */
	final void removeNode(Node node) {
		Node splice;
		Node child;

		modCount++;
		size--;

		// Find splice, the node at the position to actually remove from the tree.
		if (node.left == getNil()) {
			// Node to be deleted has 0 or 1 children.
			splice = node;
			child = node.right;
		} else if (node.right == getNil()) {
			// Node to be deleted has 1 child.
			splice = node;
			child = node.left;
		} else {
			// Node has 2 children. Splice is node's predecessor, and we swap
			// its contents into node.
			splice = node.left;
			while (splice.right != getNil())
				splice = splice.right;
			child = splice.left;
			node.key = splice.key;
			node.value = splice.value;
		}

		// Unlink splice from the tree.
		Node parent = splice.parent;
		if (child != getNil())
			child.parent = parent;
		if (parent == getNil()) {
			// Special case for 0 or 1 node remaining.
			root = child;
			return;
		}
		if (splice == parent.left)
			parent.left = child;
		else
			parent.right = child;

		if (splice.color == BLACK)
			deleteFixup(child, parent);
	}

	/**
	 * Rotate node n to the left.
	 *
	 * @param node the node to rotate
	 */
	private void rotateLeft(Node node) {
		Node child = node.right;
		// if (node == getNil() || child == getNil())
		//   throw new InternalError();

		// Establish node.right link.
		node.right = child.left;
		if (child.left != getNil())
			child.left.parent = node;

		// Establish child->parent link.
		child.parent = node.parent;
		if (node.parent != getNil()) {
			if (node == node.parent.left)
				node.parent.left = child;
			else
				node.parent.right = child;
		} else
			root = child;

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

	/**
	 * Rotate node n to the right.
	 *
	 * @param node the node to rotate
	 */
	private void rotateRight(Node node) {
		Node child = node.left;
		// if (node == getNil() || child == getNil())
		//   throw new InternalError();

		// Establish node.left link.
		node.left = child.right;
		if (child.right != getNil())
			child.right.parent = node;

		// Establish child->parent link.
		child.parent = node.parent;
		if (node.parent != getNil()) {
			if (node == node.parent.right)
				node.parent.right = child;
			else
				node.parent.left = child;
		} else
			root = child;