redblackmap.java

pastry的java实现的2.0b版

  /**
   * Copies all of the mappings from the specified map to this map. These
   * mappings replace any mappings that this map had for any of the keys
   * currently in the specified map.
   *
   * @param map mappings to be stored in this map.
   * @throws ClassCastException class of a key or value in the specified map
   *      prevents it from being stored in this map.
   * @throws NullPointerException if the given map is <tt>null</tt> or this map
   *      does not permit <tt>null</tt> keys and a key in the specified map is
   *      <tt>null</tt> .
   */
  public synchronized void putAll(Map map) {
    int mapSize = map.size();
    if (size == 0 && mapSize != 0 && map instanceof SortedMap) {
      Comparator c = ((SortedMap) map).comparator();
      if (c == comparator || (c != null && c.equals(comparator))) {
        ++modCount;
        try {
          buildFromSorted(mapSize, map.entrySet().iterator(),
            null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
        return;
      }
    }
    super.putAll(map);
  }

  /**
   * Associates the specified value with the specified key in this map. If the
   * map previously contained a mapping for this key, the old value is replaced.
   *
   * @param key key with which the specified value is to be associated.
   * @param value value to be associated with the specified key.
   * @return previous value associated with specified key, or <tt>null</tt> if
   *      there was no mapping for key. A <tt>null</tt> return can also indicate
   *      that the map previously associated <tt>null</tt> with the specified
   *      key.
   * @throws ClassCastException key cannot be compared with the keys currently
   *      in the map.
   * @throws NullPointerException key is <tt>null</tt> and this map uses natural
   *      order, or its comparator does not tolerate <tt>null</tt> keys.
   */
  public synchronized Object put(Object key, Object value) {
    Entry t = root;

    if (t == null) {
      incrementSize();
      root = new Entry(key, value, null);
      return null;
    }

    while (true) {
      int cmp = compare(key, t.key);
      if (cmp == 0) {
        return t.setValue(value);
      } else if (cmp < 0) {
        if (t.left != null) {
          t = t.left;
        } else {
          incrementSize();
          t.left = new Entry(key, value, t);
          fixAfterInsertion(t.left);
          return null;
        }
      } else {
        // cmp > 0
        if (t.right != null) {
          t = t.right;
        } else {
          incrementSize();
          t.right = new Entry(key, value, t);
          fixAfterInsertion(t.right);
          return null;
        }
      }
    }
  }

  /**
   * Removes the mapping for this key from this RedBlackMap if present.
   *
   * @param key key for which mapping should be removed
   * @return previous value associated with specified key, or <tt>null</tt> if
   *      there was no mapping for key. A <tt>null</tt> return can also indicate
   *      that the map previously associated <tt>null</tt> with the specified
   *      key.
   * @throws ClassCastException key cannot be compared with the keys currently
   *      in the map.
   * @throws NullPointerException key is <tt>null</tt> and this map uses natural
   *      order, or its comparator does not tolerate <tt>null</tt> keys.
   */
  public synchronized Object remove(Object key) {
    Entry p = getEntry(key);
    if (p == null) {
      return null;
    }

    Object oldValue = p.value;
    deleteEntry(p);
    return oldValue;
  }

  /**
   * Removes all mappings from this RedBlackMap.
   */
  public synchronized void clear() {
    modCount++;
    size = 0;
    root = null;
  }

  /**
   * Returns a shallow copy of this <tt>RedBlackMap</tt> instance. (The keys and
   * values themselves are not cloned.)
   *
   * @return a shallow copy of this Map.
   */
  public synchronized Object clone() {
    RedBlackMap clone = null;
    try {
      clone = (RedBlackMap) super.clone();
    } catch (CloneNotSupportedException e) {
      throw new InternalError();
    }

    // Put clone into "virgin" state (except for comparator)
    clone.root = null;
    clone.size = 0;
    clone.modCount = 0;
    clone.entrySet = null;

    // Initialize clone with our mappings
    try {
      clone.buildFromSorted(size, entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }

    return clone;
  }

  /**
   * Returns a Set view of the keys contained in this map. The set's iterator
   * will return the keys in ascending order. The map is backed by this <tt>
   * RedBlackMap</tt> instance, so changes to this map are reflected in the Set,
   * and vice-versa. The Set supports element removal, which removes the
   * corresponding mapping from the map, via the <tt>Iterator.remove</tt> , <tt>
   * Set.remove</tt> , <tt>removeAll</tt> , <tt>retainAll</tt> , and <tt>clear
   * </tt> operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
   * operations.
   *
   * @return a set view of the keys contained in this RedBlackMap.
   */
  public Set keySet() {
    if (keySet == null) {
      keySet =
        new AbstractSet() {
          public Iterator iterator() {
            return new KeyIterator();
          }

          public int size() {
            return RedBlackMap.this.size();
          }

          public boolean contains(Object o) {
            return containsKey(o);
          }

          public boolean remove(Object o) {
            int oldSize = size;
            RedBlackMap.this.remove(o);
            return size != oldSize;
          }

          public void clear() {
            RedBlackMap.this.clear();
          }
        };
    }
    return keySet;
  }

  /**
   * Returns a collection view of the values contained in this map. The
   * collection's iterator will return the values in the order that their
   * corresponding keys appear in the tree. The collection is backed by this
   * <tt>RedBlackMap</tt> instance, so changes to this map are reflected in the
   * collection, and vice-versa. The collection supports element removal, which
   * removes the corresponding mapping from the map through the <tt>
   * Iterator.remove</tt> , <tt>Collection.remove</tt> , <tt>removeAll</tt> ,
   * <tt>retainAll</tt> , and <tt>clear</tt> operations. It does not support the
   * <tt>add</tt> or <tt>addAll</tt> operations.
   *
   * @return a collection view of the values contained in this map.
   */
  public Collection values() {
    if (values == null) {
      values =
        new AbstractCollection() {
          public Iterator iterator() {
            return new ValueIterator();
          }

          public int size() {
            return RedBlackMap.this.size();
          }

          public boolean contains(Object o) {
            for (Entry e = firstEntry(); e != null; e = successor(e)) {
              if (valEquals(e.getValue(), o)) {
                return true;
              }
            }
            return false;
          }

          public boolean remove(Object o) {
            for (Entry e = firstEntry(); e != null; e = successor(e)) {
              if (valEquals(e.getValue(), o)) {
                deleteEntry(e);
                return true;
              }
            }
            return false;
          }

          public void clear() {
            RedBlackMap.this.clear();
          }
        };
    }
    return values;
  }

  /**
   * Returns a set view of the mappings contained in this map. The set's
   * iterator returns the mappings in ascending key order. Each element in the
   * returned set is a <tt>Map.Entry</tt> . The set is backed by this map, so
   * changes to this map are reflected in the set, and vice-versa. The set
   * supports element removal, which removes the corresponding mapping from the
   * RedBlackMap, through the <tt>Iterator.remove</tt> , <tt>Set.remove</tt> ,
   * <tt>removeAll</tt> , <tt>retainAll</tt> and <tt>clear</tt> operations. It
   * does not support the <tt>add</tt> or <tt>addAll</tt> operations.
   *
   * @return a set view of the mappings contained in this map.
   * @see Map.Entry
   */
  public Set entrySet() {
    if (entrySet == null) {
      entrySet =
        new AbstractSet() {
          public Iterator iterator() {
            return new EntryIterator();
          }

          public boolean contains(Object o) {
            if (!(o instanceof Map.Entry)) {
              return false;
            }

            Map.Entry entry = (Map.Entry) o;
            Object value = entry.getValue();
            Entry p = getEntry(entry.getKey());
            return p != null && valEquals(p.getValue(), value);
          }

          public boolean remove(Object o) {
            if (!(o instanceof Map.Entry)) {
              return false;
            }

            Map.Entry entry = (Map.Entry) o;
            Object value = entry.getValue();
            Entry p = getEntry(entry.getKey());
            if (p != null && valEquals(p.getValue(), value)) {
              deleteEntry(p);
              return true;
            }
            return false;
          }

          public int size() {
            return RedBlackMap.this.size();
          }

          public void clear() {
            RedBlackMap.this.clear();
          }
        };
    }
    return entrySet;
  }

  /**
   * Returns a view of the portion of this map whose keys range from <tt>fromKey
   * </tt>, inclusive, to <tt>toKey</tt> , exclusive. (If <tt>fromKey</tt> and
   * <tt>toKey</tt> are equal, the returned sorted map is empty.) The returned
   * sorted map is backed by this map, so changes in the returned sorted map are
   * reflected in this map, and vice-versa. The returned sorted map supports all
   * optional map operations.<p>
   *
   * The sorted map returned by this method will throw an <tt>
   * IllegalArgumentException</tt> if the user attempts to insert a key less
   * than <tt>fromKey</tt> or greater than or equal to <tt>toKey</tt> .<p>
   *
   * Note: this method always returns a <i>half-open range</i> (which includes
   * its low endpoint but not its high endpoint). If you need a <i>closed range
   * </i> (which includes both endpoints), and the key type allows for
   * calculation of the successor a given key, merely request the subrange from
   * <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt> . For example,
   * suppose that <tt>m</tt> is a sorted map whose keys are strings. The
   * following idiom obtains a view containing all of the key-value mappings in
   * <tt>m</tt> whose keys are between <tt>low</tt> and <tt>high</tt> ,
   * inclusive: <pre>    SortedMap sub = m.submap(low, high+"\0");</pre> A
   * similar technique can be used to generate an <i>open range</i> (which
   * contains neither endpoint). The following idiom obtains a view containing
   * all of the key-value mappings in <tt>m</tt> whose keys are between <tt>low
   * </tt> and <tt>high</tt> , exclusive: <pre>    SortedMap sub = m.subMap(low+"\0", high);</pre>
   *
   * @param fromKey low endpoint (inclusive) of the subMap.
   * @param toKey high endpoint (exclusive) of the subMap.
   * @return a view of the portion of this map whose keys range from <tt>fromKey
   *      </tt>, inclusive, to <tt>toKey</tt> , exclusive.
   * @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt> cannot be
   *      compared to one another using this map's comparator (or, if the map
   *      has no comparator, using natural ordering).
   * @throws IllegalArgumentException if <tt>fromKey</tt> is greater than <tt>
   *      toKey</tt> .
   * @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is <tt>
   *      null</tt> and this map uses natural order, or its comparator does not
   *      tolerate <tt>null</tt> keys.
   */
  public SortedMap subMap(Object fromKey, Object toKey) {
    if (compare(fromKey, toKey) <= 0) {
      return new SubMap(fromKey, toKey);
    } else {
      return new SubWrappedMap(fromKey, toKey);
    }
  }

  /**
   * Returns a view of the portion of this map whose keys are strictly less than
   * <tt>toKey</tt> . The returned sorted map is backed by this map, so changes
   * in the returned sorted map are reflected in this map, and vice-versa. The
   * returned sorted map supports all optional map operations.<p>
   *
   * The sorted map returned by this method will throw an <tt>
   * IllegalArgumentException</tt> if the user attempts to insert a key greater
   * than or equal to <tt>toKey</tt> .<p>
   *
   * Note: this method always returns a view that does not contain its (high)
   * endpoint. If you need a view that does contain this endpoint, and the key
   * type allows for calculation of the successor a given key, merely request a
   * headMap bounded by <tt>successor(highEndpoint)</tt> . For example, suppose
   * that suppose that <tt>m</tt> is a sorted map whose keys are strings. The
   * following idiom obtains a view containing all of the key-value mappings in
   * <tt>m</tt> whose keys are less than or equal to <tt>high</tt> : <pre>
   *     SortedMap head = m.headMap(high+"\0");
   * </pre>
   *
   * @param toKey high endpoint (exclusive) of the headMap.
   * @return a view of the portion of this map whose keys are strictly less than
   *      <tt>toKey</tt> .
   * @throws ClassCastException if <tt>toKey</tt> is not compatible with this
   *      map's comparator (or, if the map has no comparator, if <tt>toKey</tt>
   *      does not implement <tt>Comparable</tt> ).
   * @throws IllegalArgumentException if this map is itself a subMap, headMap,
   *      or tailMap, and <tt>toKey</tt> is not within the specified range of
   *      the subMap, headMap, or tailMap.
   * @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and this
   *      map uses natural order, or its comparator does not tolerate <tt>null
   *      </tt> keys.
   */
  public SortedMap headMap(Object toKey) {
    return new SubMap(toKey, true);
  }

  /**
   * Returns a view of the portion of this map whose keys are greater than or
   * equal to <tt>fromKey</tt> . The returned sorted map is backed by this map,
   * so changes in the returned sorted map are reflected in this map, and
   * vice-versa. The returned sorted map supports all optional map operations.
   * <p>
   *
   * The sorted map returned by this method will throw an <tt>
   * IllegalArgumentException</tt> if the user attempts to insert a key less
   * than <tt>fromKey</tt> .<p>
   *
   * Note: this method always returns a view that contains its (low) endpoint.
   * If you need a view that does not contain this endpoint, and the element
   * type allows for calculation of the successor a given value, merely request
   * a tailMap bounded by <tt>successor(lowEndpoint)</tt> . For For example,
   * suppose that suppose that <tt>m</tt> is a sorted map whose keys are
   * strings. The following idiom obtains a view containing all of the key-value
   * mappings in <tt>m</tt> whose keys are strictly greater than <tt>low</tt> :
   * <pre>
   *     SortedMap tail = m.tailMap(low+"\0");
   * </pre>
   *
   * @param fromKey low endpoint (inclusive) of the tailMap.
   * @return a view of the portion of this map whose keys are greater than or
   *      equal to <tt>fromKey</tt> .
   * @throws ClassCastException if <tt>fromKey</tt> is not compatible with this
   *      map's comparator (or, if the map has no comparator, if <tt>fromKey
   *      </tt> does not implement <tt>Comparable</tt> ).
   * @throws IllegalArgumentException if this map is itself a subMap, headMap,
   *      or tailMap, and <tt>fromKey</tt> is not within the specified range of
   *      the subMap, headMap, or tailMap.
   * @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> and this
   *      map uses natural order, or its comparator does not tolerate <tt>null
   *      </tt> keys.
   */
  public SortedMap tailMap(Object fromKey) {
    return new SubMap(fromKey, false);
  }

  /**
   * Compares two keys using the correct comparison method for this RedBlackMap.
   *
   * @param k1 DESCRIBE THE PARAMETER
   * @param k2 DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   */
  private int compare(Object k1, Object k2) {
    return (comparator == null ? ((Comparable) k1).compareTo(k2)
      : comparator.compare(k1, k2));
  }