redblackmap.java

pastry的java实现的2.0b版

   * @return DESCRIBE THE RETURN VALUE
   */
  private static boolean valEquals(Object o1, Object o2) {
    return (o1 == null ? o2 == null : o1.equals(o2));
  }

  /**
   * Balancing operations. Implementations of rebalancings during insertion and
   * deletion are slightly different than the CLR version. Rather than using
   * dummy nilnodes, we use a set of accessors that deal properly with null.
   * They are used to avoid messiness surrounding nullness checks in the main
   * algorithms.
   *
   * @param p DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   */

  private static boolean colorOf(Entry p) {
    return (p == null ? BLACK : p.color);
  }

  /**
   * DESCRIBE THE METHOD
   *
   * @param p DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   */
  private static Entry parentOf(Entry p) {
    return (p == null ? null : p.parent);
  }

  /**
   * DESCRIBE THE METHOD
   *
   * @param p DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   */
  private static Entry leftOf(Entry p) {
    return (p == null) ? null : p.left;
  }

  /**
   * DESCRIBE THE METHOD
   *
   * @param p DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   */
  private static Entry rightOf(Entry p) {
    return (p == null) ? null : p.right;
  }

  /**
   * Recursive "helper method" that does the real work of the of the previous
   * method. Identically named parameters have identical definitions. Additional
   * parameters are documented below. It is assumed that the comparator and size
   * fields of the RedBlackMap are already set prior to calling this method. (It
   * ignores both fields.)
   *
   * @param level the current level of tree. Initial call should be 0.
   * @param lo the first element index of this subtree. Initial should be 0.
   * @param hi the last element index of this subtree. Initial should be size-1.
   * @param redLevel the level at which nodes should be red. Must be equal to
   *      computeRedLevel for tree of this size.
   * @param it DESCRIBE THE PARAMETER
   * @param str DESCRIBE THE PARAMETER
   * @param defaultVal DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   * @exception java.io.IOException DESCRIBE THE EXCEPTION
   * @exception ClassNotFoundException DESCRIBE THE EXCEPTION
   */
  private static Entry buildFromSorted(int level, int lo, int hi,
                                       int redLevel,
                                       Iterator it,
                                       java.io.ObjectInputStream str,
                                       Object defaultVal)
     throws java.io.IOException, ClassNotFoundException {
    /*
     *  Strategy: The root is the middlemost element. To get to it, we
     *  have to first recursively construct the entire left subtree,
     *  so as to grab all of its elements. We can then proceed with right
     *  subtree.
     *
     *  The lo and hi arguments are the minimum and maximum
     *  indices to pull out of the iterator or stream for current subtree.
     *  They are not actually indexed, we just proceed sequentially,
     *  ensuring that items are extracted in corresponding order.
     */
    if (hi < lo) {
      return null;
    }

    int mid = (lo + hi) / 2;

    Entry left = null;
    if (lo < mid) {
      left = buildFromSorted(level + 1, lo, mid - 1, redLevel,
        it, str, defaultVal);
    }

    // extract key and/or value from iterator or stream
    Object key;
    Object value;
    if (it != null) {
      // use iterator
      if (defaultVal == null) {
        Map.Entry entry = (Map.Entry) it.next();
        key = entry.getKey();
        value = entry.getValue();
      } else {
        key = it.next();
        value = defaultVal;
      }
    } else {
      // use stream
      key = str.readObject();
      value = (defaultVal != null ? defaultVal : str.readObject());
    }

    Entry middle = new Entry(key, value, null);

    // color nodes in non-full bottommost level red
    if (level == redLevel) {
      middle.color = RED;
    }

    if (left != null) {
      middle.left = left;
      left.parent = middle;
    }

    if (mid < hi) {
      Entry right = buildFromSorted(level + 1, mid + 1, hi, redLevel,
        it, str, defaultVal);
      middle.right = right;
      right.parent = middle;
    }

    return middle;
  }

  /**
   * Find the level down to which to assign all nodes BLACK. This is the last
   * `full' level of the complete binary tree produced by buildTree. The
   * remaining nodes are colored RED. (This makes a `nice' set of color
   * assignments wrt future insertions.) This level number is computed by
   * finding the number of splits needed to reach the zeroeth node. (The answer
   * is ~lg(N), but in any case must be computed by same quick O(lg(N)) loop.)
   *
   * @param sz DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   */
  private static int computeRedLevel(int sz) {
    int level = 0;
    for (int m = sz - 1; m >= 0; m = m / 2 - 1) {
      level++;
    }
    return level;
  }

  /**
   * DESCRIBE THE CLASS
   *
   * @version $Id: pretty.settings 2305 2005-03-11 20:22:33Z jeffh $
   * @author jeffh
   */
  private class SubMap extends AbstractMap
     implements SortedMap, java.io.Serializable {

    /**
     * fromKey is significant only if fromStart is false. Similarly, toKey is
     * significant only if toStart is false.
     */
    private boolean fromStart = false, toEnd = false;
    private Object fromKey, toKey;

    private transient Set entrySet = new EntrySetView();
    private final static long serialVersionUID = -6520786458950516097L;

    /**
     * Constructor for SubMap.
     *
     * @param fromKey DESCRIBE THE PARAMETER
     * @param toKey DESCRIBE THE PARAMETER
     */
    SubMap(Object fromKey, Object toKey) {
      if (compare(fromKey, toKey) > 0) {
        throw new IllegalArgumentException("fromKey > toKey");
      }
      this.fromKey = fromKey;
      this.toKey = toKey;
    }

    /**
     * Constructor for SubMap.
     *
     * @param key DESCRIBE THE PARAMETER
     * @param headMap DESCRIBE THE PARAMETER
     */
    SubMap(Object key, boolean headMap) {
      compare(key, key);
      // Type-check key

      if (headMap) {
        fromStart = true;
        toKey = key;
      } else {
        toEnd = true;
        fromKey = key;
      }
    }

    /**
     * Constructor for SubMap.
     *
     * @param fromStart DESCRIBE THE PARAMETER
     * @param fromKey DESCRIBE THE PARAMETER
     * @param toEnd DESCRIBE THE PARAMETER
     * @param toKey DESCRIBE THE PARAMETER
     */
    SubMap(boolean fromStart, Object fromKey, boolean toEnd, Object toKey) {
      this.fromStart = fromStart;
      this.fromKey = fromKey;
      this.toEnd = toEnd;
      this.toKey = toKey;
    }

    /**
     * Gets the Empty attribute of the SubMap object
     *
     * @return The Empty value
     */
    public boolean isEmpty() {
      return entrySet.isEmpty();
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param key DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    public Object get(Object key) {
      if (!inRange(key)) {
        return null;
      }
      return RedBlackMap.this.get(key);
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param key DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    public boolean containsKey(Object key) {
      return inRange(key) && RedBlackMap.this.containsKey(key);
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param key DESCRIBE THE PARAMETER
     * @param value DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    public Object put(Object key, Object value) {
      if (!inRange(key)) {
        throw new IllegalArgumentException("key out of range");
      }
      return RedBlackMap.this.put(key, value);
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @return DESCRIBE THE RETURN VALUE
     */
    public Comparator comparator() {
      return comparator;
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @return DESCRIBE THE RETURN VALUE
     */
    public Object firstKey() {
      Object first = key(fromStart ? firstEntry() : getCeilEntry(fromKey));
      if (!toEnd && compare(first, toKey) >= 0) {
        throw (new NoSuchElementException());
      }
      return first;
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @return DESCRIBE THE RETURN VALUE
     */
    public Object lastKey() {
      Object last = key(toEnd ? lastEntry() : getPrecedingEntry(toKey));
      if (!fromStart && compare(last, fromKey) < 0) {
        throw (new NoSuchElementException());
      }
      return last;
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @return DESCRIBE THE RETURN VALUE
     */
    public Set entrySet() {
      return entrySet;
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param key DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    protected Object putInRange(Object key) {
      if ((!fromStart) && (compare(key, fromKey) < 0)) {
        return fromKey;
      } else if ((!toEnd) && (compare(key, toKey) > 0)) {
        return toKey;
      } else {
        return key;
      }
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param fromKey DESCRIBE THE PARAMETER
     * @param toKey DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    public SortedMap subMap(Object fromKey, Object toKey) {
      if (compare(fromKey, toKey) > 0) {
        return new RedBlackMap(this).subMap(fromKey, toKey);
      } else {
        return new SubMap(putInRange(fromKey), putInRange(toKey));
      }
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param toKey DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    public SortedMap headMap(Object toKey) {
      return new SubMap(fromStart, fromKey, false, putInRange(toKey));
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param fromKey DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    public SortedMap tailMap(Object fromKey) {
      return new SubMap(false, putInRange(fromKey), toEnd, toKey);
    }

    /**
     * DESCRIBE THE METHOD
     *
     * @param key DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    private boolean inRange(Object key) {
      return (fromStart || compare(key, fromKey) >= 0) &&
        (toEnd || compare(key, toKey) < 0);
    }

    // This form allows the high endpoint (as well as all legit keys)
    /**
     * DESCRIBE THE METHOD
     *
     * @param key DESCRIBE THE PARAMETER
     * @return DESCRIBE THE RETURN VALUE
     */
    private boolean inRange2(Object key) {
      return (fromStart || compare(key, fromKey) >= 0) &&
        (toEnd || compare(key, toKey) <= 0);
    }

    /**
     * DESCRIBE THE CLASS
     *
     * @version $Id: pretty.settings 2305 2005-03-11 20:22:33Z jeffh $
     * @author jeffh
     */
    private class EntrySetView extends AbstractSet {
      private transient int size = -1, sizeModCount;

      /**
       * Gets the Empty attribute of the EntrySetView object
       *
       * @return The Empty value
       */
      public boolean isEmpty() {
        return !iterator().hasNext();
      }

      /**
       * DESCRIBE THE METHOD
       *
       * @return DESCRIBE THE RETURN VALUE
       */
      public int size() {
        if (size == -1 || sizeModCount != RedBlackMap.this.modCount) {
          size = 0;
          sizeModCount = RedBlackMap.this.modCount;
          Iterator i = iterator();
          while (i.hasNext()) {
            size++;
            i.next();
          }
        }
        return size;
      }

      /**
       * DESCRIBE THE METHOD
       *
       * @param o DESCRIBE THE PARAMETER
       * @return DESCRIBE THE RETURN VALUE
       */