treemap.java

this gcc-g++-3.3.1.tar.gz is a source file of gcc, you can learn more about gcc through this codes f

    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)
  {