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 = nil;      }    // Unlink the remaining nodes of the previous row.    while (parent != nil)      {        Node next = parent.right;        parent.right = nil;        parent = next;      }  }  /**   * Returns the first sorted node in the map, or nil if empty. Package   * visible for use by nested classes.   *   * @return the first node   */  final Node firstNode()  {    // Exploit fact that nil.left == nil.    Node node = root;    while (node.left != nil)      node = node.left;    return node;  }  /**   * Return the TreeMap.Node associated with key, or the nil 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 nil   */  final Node getNode(Object key)  {    Node current = root;    while (current != nil)      {        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 nil, 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 == nil)      return lastNode();    Node last = nil;    Node current = root;    int comparison = 0;    while (current != nil)      {        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 nil.color == BLACK.    while (n.parent.color == RED && n.parent.parent != nil)      {        if (n.parent == n.parent.parent.left)          {            Node uncle = n.parent.parent.right;            // Uncle may be nil, 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 nil, 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 nil if empty.   *   * @return the last node   */  private Node lastNode()  {    // Exploit fact that nil.right == nil.    Node node = root;    while (node.right != nil)      node = node.right;    return node;  }  /**   * Find the "lowest" node which is &gt;= key. If key is nil, return either   * nil 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 nil for nil key   * @return the next node   */  final Node lowestGreaterThan(Object key, boolean first)  {    if (key == nil)      return first ? firstNode() : nil;    Node last = nil;    Node current = root;    int comparison = 0;    while (current != nil)      {        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 nil if there isn't one.   *   * @param node the current node, not nil   * @return the prior node in sorted order   */  private Node predecessor(Node node)  {    if (node.left != nil)      {        node = node.left;        while (node.right != nil)          node = node.right;        return node;      }    Node parent = node.parent;    // Exploit fact that nil.left == nil and node is non-nil.    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 == nil)      {        // Node to be deleted has 0 or 1 children.        splice = node;        child = node.right;      }    else if (node.right == nil)      {        // 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 != nil)          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 != nil)      child.parent = parent;    if (parent == nil)      {        // 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 == nil || child == nil)    //   throw new InternalError();    // Establish node.right link.    node.right = child.left;    if (child.left != nil)      child.left.parent = node;    // Establish child->parent link.    child.parent = node.parent;    if (node.parent != nil)      {        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 == nil || child == nil)    //   throw new InternalError();    // Establish node.left link.    node.left = child.right;    if (child.right != nil)      child.right.parent = node;    // Establish child->parent link.    child.parent = node.parent;    if (node.parent != nil)      {        if (node == node.parent.right)          node.parent.right = child;        else          node.parent.left = child;      }    else      root = child;    // Link n and child.    child.right = node;    node.parent = child;  }  /**   * Return the node following the given one, or nil if there isn't one.   * Package visible for use by nested classes.   *   * @param node the current node, not nil   * @return the next node in sorted order   */  final Node successor(Node node)  {