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

    if (node.right != nil)
      {
        node = node.right;
        while (node.left != nil)
          node = node.left;
        return node;
      }

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

  /**
   * Serializes this object to the given stream.
   *
   * @param s the stream to write to
   * @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 writeObject(ObjectOutputStream s) throws IOException
  {
    s.defaultWriteObject();

    Node node = firstNode();
    s.writeInt(size);
    while (node != nil)
      {
        s.writeObject(node.key);
        s.writeObject(node.value);
        node = successor(node);
      }
  }

  /**
   * Iterate over HashMap's entries. This implementation is parameterized
   * to give a sequential view of keys, values, or entries.
   *
   * @author Eric Blake <[e-mail]>
   */
  private final class TreeIterator implements Iterator
  {
    /**
     * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
     * or {@link #ENTRIES}.
     */
    private final int type;
    /** The number of modifications to the backing Map that we know about. */
    private int knownMod = modCount;
    /** The last Entry returned by a next() call. */
    private Node last;
    /** The next entry that should be returned by next(). */
    private Node next;
    /**
     * The last node visible to this iterator. This is used when iterating
     * on a SubMap.
     */
    private final Node max;

    /**
     * Construct a new TreeIterator with the supplied type.
     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
     */
    TreeIterator(int type)
    {
      // FIXME gcj cannot handle this. Bug java/4695
      // this(type, firstNode(), nil);
      this.type = type;
      this.next = firstNode();
      this.max = nil;
    }

    /**
     * Construct a new TreeIterator with the supplied type. Iteration will
     * be from "first" (inclusive) to "max" (exclusive).
     *
     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
     * @param first where to start iteration, nil for empty iterator
     * @param max the cutoff for iteration, nil for all remaining nodes
     */
    TreeIterator(int type, Node first, Node max)
    {
      this.type = type;
      this.next = first;
      this.max = max;
    }

    /**
     * Returns true if the Iterator has more elements.
     * @return true if there are more elements
     * @throws ConcurrentModificationException if the TreeMap was modified
     */
    public boolean hasNext()
    {
      if (knownMod != modCount)
        throw new ConcurrentModificationException();
      return next != max;
    }

    /**
     * Returns the next element in the Iterator's sequential view.
     * @return the next element
     * @throws ConcurrentModificationException if the TreeMap was modified
     * @throws NoSuchElementException if there is none
     */
    public Object next()
    {
      if (knownMod != modCount)
        throw new ConcurrentModificationException();
      if (next == max)
        throw new NoSuchElementException();
      last = next;
      next = successor(last);

      if (type == VALUES)
        return last.value;
      else if (type == KEYS)
        return last.key;
      return last;
    }

    /**
     * Removes from the backing TreeMap the last element which was fetched
     * with the <code>next()</code> method.
     * @throws ConcurrentModificationException if the TreeMap was modified
     * @throws IllegalStateException if called when there is no last element
     */
    public void remove()
    {
      if (last == null)
        throw new IllegalStateException();
      if (knownMod != modCount)
        throw new ConcurrentModificationException();

      removeNode(last);
      last = null;
      knownMod++;
    }
  } // class TreeIterator

  /**
   * Implementation of {@link #subMap(Object, Object)} and other map
   * ranges. This class provides a view of a portion of the original backing
   * map, and throws {@link IllegalArgumentException} for attempts to
   * access beyond that range.
   *
   * @author Eric Blake <[e-mail]>
   */
  private final class SubMap extends AbstractMap implements SortedMap
  {
    /**
     * The lower range of this view, inclusive, or nil for unbounded.
     * Package visible for use by nested classes.
     */
    final Object minKey;

    /**
     * The upper range of this view, exclusive, or nil for unbounded.
     * Package visible for use by nested classes.
     */
    final Object maxKey;

    /**
     * The cache for {@link #entrySet()}.
     */
    private Set entries;

    /**
     * Create a SubMap representing the elements between minKey (inclusive)
     * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound
     * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap).
     *
     * @param minKey the lower bound
     * @param maxKey the upper bound
     * @throws IllegalArgumentException if minKey &gt; maxKey
     */
    SubMap(Object minKey, Object maxKey)
    {
      if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
        throw new IllegalArgumentException("fromKey > toKey");
      this.minKey = minKey;
      this.maxKey = maxKey;
    }

    /**
     * Check if "key" is in within the range bounds for this SubMap. The
     * lower ("from") SubMap range is inclusive, and the upper ("to") bound
     * is exclusive. Package visible for use by nested classes.
     *
     * @param key the key to check
     * @return true if the key is in range
     */
    final boolean keyInRange(Object key)
    {
      return ((minKey == nil || compare(key, minKey) >= 0)
              && (maxKey == nil || compare(key, maxKey) < 0));
    }

    public void clear()
    {
      Node next = lowestGreaterThan(minKey, true);
      Node max = lowestGreaterThan(maxKey, false);
      while (next != max)
        {
          Node current = next;
          next = successor(current);
          removeNode(current);
        }
    }

    public Comparator comparator()
    {
      return comparator;
    }

    public boolean containsKey(Object key)
    {
      return keyInRange(key) && TreeMap.this.containsKey(key);
    }

    public boolean containsValue(Object value)
    {
      Node node = lowestGreaterThan(minKey, true);
      Node max = lowestGreaterThan(maxKey, false);
      while (node != max)
        {
          if (equals(value, node.getValue()))
            return true;
          node = successor(node);
        }
      return false;
    }

    public Set entrySet()
    {
      if (entries == null)
        // Create an AbstractSet with custom implementations of those methods
        // that can be overriden easily and efficiently.
        entries = new AbstractSet()
        {
          public int size()
          {
            return SubMap.this.size();
          }

          public Iterator iterator()
          {
            Node first = lowestGreaterThan(minKey, true);
            Node max = lowestGreaterThan(maxKey, false);
            return new TreeIterator(ENTRIES, first, max);
          }

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

          public boolean contains(Object o)
          {
            if (! (o instanceof Map.Entry))
              return false;
            Map.Entry me = (Map.Entry) o;
            Object key = me.getKey();
            if (! keyInRange(key))
              return false;
            Node n = getNode(key);
            return n != nil && AbstractSet.equals(me.getValue(), n.value);
          }

          public boolean remove(Object o)
          {
            if (! (o instanceof Map.Entry))
              return false;
            Map.Entry me = (Map.Entry) o;
            Object key = me.getKey();
            if (! keyInRange(key))
              return false;
            Node n = getNode(key);
            if (n != nil && AbstractSet.equals(me.getValue(), n.value))
              {
                removeNode(n);
                return true;
              }
            return false;
          }
        };
      return entries;
    }

    public Object firstKey()
    {
      Node node = lowestGreaterThan(minKey, true);
      if (node == nil || ! keyInRange(node.key))
        throw new NoSuchElementException();
      return node.key;
    }

    public Object get(Object key)
    {
      if (keyInRange(key))
        return TreeMap.this.get(key);
      return null;
    }

    public SortedMap headMap(Object toKey)
    {
      if (! keyInRange(toKey))
        throw new IllegalArgumentException("key outside range");
      return new SubMap(minKey, toKey);
    }

    public Set keySet()
    {
      if (this.keys == null)
        // Create an AbstractSet with custom implementations of those methods
        // that can be overriden easily and efficiently.
        this.keys = new AbstractSet()
        {
          public int size()
          {
            return SubMap.this.size();
          }

          public Iterator iterator()
          {
            Node first = lowestGreaterThan(minKey, true);
            Node max = lowestGreaterThan(maxKey, false);
            return new TreeIterator(KEYS, first, max);
          }

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

          public boolean contains(Object o)
          {
            if (! keyInRange(o))
              return false;
            return getNode(o) != nil;
          }

          public boolean remove(Object o)
          {
            if (! keyInRange(o))
              return false;
            Node n = getNode(o);
            if (n != nil)
              {
                removeNode(n);
                return true;
              }
            return false;
          }
        };
      return this.keys;
    }

    public Object lastKey()
    {
      Node node = highestLessThan(maxKey);
      if (node == nil || ! keyInRange(node.key))
        throw new NoSuchElementException();
      return node.key;
    }

    public Object put(Object key, Object value)
    {
      if (! keyInRange(key))
        throw new IllegalArgumentException("Key outside range");
      return TreeMap.this.put(key, value);
    }

    public Object remove(Object key)
    {
      if (keyInRange(key))
        return TreeMap.this.remove(key);
      return null;
    }

    public int size()
    {
      Node node = lowestGreaterThan(minKey, true);
      Node max = lowestGreaterThan(maxKey, false);
      int count = 0;
      while (node != max)
        {
          count++;
          node = successor(node);
        }
      return count;
    }

    public SortedMap subMap(Object fromKey, Object toKey)
    {
      if (! keyInRange(fromKey) || ! keyInRange(toKey))
        throw new IllegalArgumentException("key outside range");
      return new SubMap(fromKey, toKey);
    }

    public SortedMap tailMap(Object fromKey)
    {
      if (! keyInRange(fromKey))
        throw new IllegalArgumentException("key outside range");
      return new SubMap(fromKey, maxKey);
    }

    public Collection values()
    {
      if (this.values == null)
        // Create an AbstractCollection with custom implementations of those
        // methods that can be overriden easily and efficiently.
        this.values = new AbstractCollection()
        {
          public int size()
          {
            return SubMap.this.size();
          }

          public Iterator iterator()
          {
            Node first = lowestGreaterThan(minKey, true);
            Node max = lowestGreaterThan(maxKey, false);
            return new TreeIterator(VALUES, first, max);
          }

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