treemap.java

linux下的gcc编译器

  /**
   * 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(nil, 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 == nil)
            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 == nil)
      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 = nil;
    int comparison = 0;

    // Find new node's parent.
    while (current != nil)
      {
        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 == nil)
      {
        // 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 == nil)
      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, nil);
  }

  /**
   * 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 nil
   * @param parent the parent of the node just deleted, never nil
   */
  private void deleteFixup(Node node, Node parent)
  {
    // if (parent == nil)
    //   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 == nil)
            //   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 == nil)
            //   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;

    // 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.