redblackmap.java

pastry的java实现的2.0b版

  /**
   * Returns the first Entry in the RedBlackMap (according to the RedBlackMap's
   * key-sort function). Returns null if the RedBlackMap is empty.
   *
   * @return DESCRIBE THE RETURN VALUE
   */
  private Entry firstEntry() {
    Entry p = root;
    if (p != null) {
      while (p.left != null) {
        p = p.left;
      }
    }
    return p;
  }

  /**
   * Returns the last Entry in the RedBlackMap (according to the RedBlackMap's
   * key-sort function). Returns null if the RedBlackMap is empty.
   *
   * @return DESCRIBE THE RETURN VALUE
   */
  private Entry lastEntry() {
    Entry p = root;
    if (p != null) {
      while (p.right != null) {
        p = p.right;
      }
    }
    return p;
  }

  /**
   * Returns the successor of the specified Entry, or null if no such.
   *
   * @param t DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   */
  private Entry successor(Entry t) {
    if (t == null) {
      return null;
    } else if (t.deleted) {
      return getCeilEntry(t.key);
    } else if (t.right != null) {
      Entry p = t.right;
      while (p.left != null) {
        p = p.left;
      }
      return p;
    } else {
      Entry p = t.parent;
      Entry ch = t;
      while (p != null && ch == p.right) {
        ch = p;
        p = p.parent;
      }
      return p;
    }
  }

  /**
   * From CLR *
   *
   * @param p DESCRIBE THE PARAMETER
   */
  private void rotateLeft(Entry p) {
    Entry r = p.right;
    p.right = r.left;
    if (r.left != null) {
      r.left.parent = p;
    }
    r.parent = p.parent;
    if (p.parent == null) {
      root = r;
    } else if (p.parent.left == p) {
      p.parent.left = r;
    } else {
      p.parent.right = r;
    }
    r.left = p;
    p.parent = r;
  }

  /**
   * From CLR *
   *
   * @param p DESCRIBE THE PARAMETER
   */
  private void rotateRight(Entry p) {
    Entry l = p.left;
    p.left = l.right;
    if (l.right != null) {
      l.right.parent = p;
    }
    l.parent = p.parent;
    if (p.parent == null) {
      root = l;
    } else if (p.parent.right == p) {
      p.parent.right = l;
    } else {
      p.parent.left = l;
    }
    l.right = p;
    p.parent = l;
  }


  /**
   * From CLR *
   *
   * @param x DESCRIBE THE PARAMETER
   */
  private void fixAfterInsertion(Entry x) {
    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {
      if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
        Entry y = rightOf(parentOf(parentOf(x)));
        if (colorOf(y) == RED) {
          setColor(parentOf(x), BLACK);
          setColor(y, BLACK);
          setColor(parentOf(parentOf(x)), RED);
          x = parentOf(parentOf(x));
        } else {
          if (x == rightOf(parentOf(x))) {
            x = parentOf(x);
            rotateLeft(x);
          }
          setColor(parentOf(x), BLACK);
          setColor(parentOf(parentOf(x)), RED);
          if (parentOf(parentOf(x)) != null) {
            rotateRight(parentOf(parentOf(x)));
          }
        }
      } else {
        Entry y = leftOf(parentOf(parentOf(x)));
        if (colorOf(y) == RED) {
          setColor(parentOf(x), BLACK);
          setColor(y, BLACK);
          setColor(parentOf(parentOf(x)), RED);
          x = parentOf(parentOf(x));
        } else {
          if (x == leftOf(parentOf(x))) {
            x = parentOf(x);
            rotateRight(x);
          }
          setColor(parentOf(x), BLACK);
          setColor(parentOf(parentOf(x)), RED);
          if (parentOf(parentOf(x)) != null) {
            rotateLeft(parentOf(parentOf(x)));
          }
        }
      }
    }
    root.color = BLACK;
  }

  /**
   * Delete node p, and then rebalance the tree.
   *
   * @param p DESCRIBE THE PARAMETER
   */

  private void deleteEntry(Entry p) {
    decrementSize();

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    if (p.left != null && p.right != null) {
      Entry s = successor(p);
      p.key = s.key;
      p.value = s.value;
      p = s;
    }
    // p has 2 children

    // Start fixup at replacement node, if it exists.
    Entry replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
      // Link replacement to parent
      replacement.parent = p.parent;
      if (p.parent == null) {
        root = replacement;
      } else if (p == p.parent.left) {
        p.parent.left = replacement;
      } else {
        p.parent.right = replacement;
      }

      // Null out links so they are OK to use by fixAfterDeletion.
      p.left = p.right = p.parent = null;

      // Fix replacement
      if (p.color == BLACK) {
        fixAfterDeletion(replacement);
      }
    } else if (p.parent == null) {
      // return if we are the only node.
      root = null;
    } else {
      //  No children. Use self as phantom replacement and unlink.
      if (p.color == BLACK) {
        fixAfterDeletion(p);
      }

      if (p.parent != null) {
        if (p == p.parent.left) {
          p.parent.left = null;
        } else if (p == p.parent.right) {
          p.parent.right = null;
        }
        p.parent = null;
      }
    }

    p.deleted = true;
  }

  /**
   * From CLR *
   *
   * @param x DESCRIBE THE PARAMETER
   */
  private void fixAfterDeletion(Entry x) {
    while (x != root && colorOf(x) == BLACK) {
      if (x == leftOf(parentOf(x))) {
        Entry sib = rightOf(parentOf(x));

        if (colorOf(sib) == RED) {
          setColor(sib, BLACK);
          setColor(parentOf(x), RED);
          rotateLeft(parentOf(x));
          sib = rightOf(parentOf(x));
        }

        if (colorOf(leftOf(sib)) == BLACK &&
          colorOf(rightOf(sib)) == BLACK) {
          setColor(sib, RED);
          x = parentOf(x);
        } else {
          if (colorOf(rightOf(sib)) == BLACK) {
            setColor(leftOf(sib), BLACK);
            setColor(sib, RED);
            rotateRight(sib);
            sib = rightOf(parentOf(x));
          }
          setColor(sib, colorOf(parentOf(x)));
          setColor(parentOf(x), BLACK);
          setColor(rightOf(sib), BLACK);
          rotateLeft(parentOf(x));
          x = root;
        }
      } else {
        // symmetric
        Entry sib = leftOf(parentOf(x));

        if (colorOf(sib) == RED) {
          setColor(sib, BLACK);
          setColor(parentOf(x), RED);
          rotateRight(parentOf(x));
          sib = leftOf(parentOf(x));
        }

        if (colorOf(rightOf(sib)) == BLACK &&
          colorOf(leftOf(sib)) == BLACK) {
          setColor(sib, RED);
          x = parentOf(x);
        } else {
          if (colorOf(leftOf(sib)) == BLACK) {
            setColor(rightOf(sib), BLACK);
            setColor(sib, RED);
            rotateLeft(sib);
            sib = leftOf(parentOf(x));
          }
          setColor(sib, colorOf(parentOf(x)));
          setColor(parentOf(x), BLACK);
          setColor(leftOf(sib), BLACK);
          rotateRight(parentOf(x));
          x = root;
        }
      }
    }

    setColor(x, BLACK);
  }

  /**
   * Save the state of the <tt>RedBlackMap</tt> instance to a stream (i.e.,
   * serialize it).
   *
   * @param s DESCRIBE THE PARAMETER
   * @exception java.io.IOException DESCRIBE THE EXCEPTION
   * @serialData The <i>size</i> of the RedBlackMap (the number of key-value
   *      mappings) is emitted (int), followed by the key (Object) and value
   *      (Object) for each key-value mapping represented by the RedBlackMap.
   *      The key-value mappings are emitted in key-order (as determined by the
   *      RedBlackMap's Comparator, or by the keys' natural ordering if the
   *      RedBlackMap has no Comparator).
   */
  private void writeObject(java.io.ObjectOutputStream s)
     throws java.io.IOException {
    // Write out the Comparator and any hidden stuff
    s.defaultWriteObject();

    // Write out size (number of Mappings)
    s.writeInt(size);

    // Write out keys and values (alternating)
    for (Iterator i = entrySet().iterator(); i.hasNext(); ) {
      Entry e = (Entry) i.next();
      s.writeObject(e.key);
      s.writeObject(e.value);
    }
  }


  /**
   * Reconstitute the <tt>RedBlackMap</tt> instance from a stream (i.e.,
   * deserialize it).
   *
   * @param s DESCRIBE THE PARAMETER
   * @exception java.io.IOException DESCRIBE THE EXCEPTION
   * @exception ClassNotFoundException DESCRIBE THE EXCEPTION
   */
  private void readObject(final java.io.ObjectInputStream s)
     throws java.io.IOException, ClassNotFoundException {
    // Read in the Comparator and any hidden stuff
    s.defaultReadObject();

    // Read in size
    int size = s.readInt();

    buildFromSorted(size, null, s, null);
  }

  /**
   * Intended to be called only from TreeSet.readObject *
   *
   * @param size DESCRIBE THE PARAMETER
   * @param s DESCRIBE THE PARAMETER
   * @param defaultVal DESCRIBE THE PARAMETER
   * @exception java.io.IOException DESCRIBE THE EXCEPTION
   * @exception ClassNotFoundException DESCRIBE THE EXCEPTION
   */
  void readTreeSet(int size, java.io.ObjectInputStream s, Object defaultVal)
     throws java.io.IOException, ClassNotFoundException {
    buildFromSorted(size, null, s, defaultVal);
  }

  /**
   * Intended to be called only from TreeSet.addAll *
   *
   * @param set The feature to be added to the AllForTreeSet attribute
   * @param defaultVal The feature to be added to the AllForTreeSet attribute
   */
  void addAllForTreeSet(SortedSet set, Object defaultVal) {
    try {
      buildFromSorted(set.size(), set.iterator(), null, defaultVal);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
  }


  /**
   * Linear time tree building algorithm from sorted data. Can accept keys
   * and/or values from iterator or stream. This leads to too many parameters,
   * but seems better than alternatives. The four formats that this method
   * accepts are: 1) An iterator of Map.Entries. (it != null, defaultVal ==
   * null). 2) An iterator of keys. (it != null, defaultVal != null). 3) A
   * stream of alternating serialized keys and values. (it == null, defaultVal
   * == null). 4) A stream of serialized keys. (it == null, defaultVal != null).
   * It is assumed that the comparator of the RedBlackMap is already set prior
   * to calling this method.
   *
   * @param size the number of keys (or key-value pairs) to be read from the
   *      iterator or stream.
   * @param it If non-null, new entries are created from entries or keys read
   *      from this iterator.
   * @param defaultVal if non-null, this default value is used for each value in
   *      the map. If null, each value is read from iterator or stream, as
   *      described above.
   * @param str DESCRIBE THE PARAMETER
   * @exception java.io.IOException DESCRIBE THE EXCEPTION
   * @throws IOException propagated from stream reads. This cannot occur if str
   *      is null.
   * @throws ClassNotFoundException propagated from readObject. This cannot
   *      occur if str is null.
   */
  private void buildFromSorted(int size, Iterator it,
                               java.io.ObjectInputStream str,
                               Object defaultVal)
     throws java.io.IOException, ClassNotFoundException {
    this.size = size;
    root = buildFromSorted(0, 0, size - 1, computeRedLevel(size),
      it, str, defaultVal);
  }

  /**
   * Sets the Color attribute of the RedBlackMap class
   *
   * @param p The new Color value
   * @param c The new Color value
   */
  private static void setColor(Entry p, boolean c) {
    if (p != null) {
      p.color = c;
    }
  }

  /**
   * Returns the key corresonding to the specified Entry. Throw
   * NoSuchElementException if the Entry is <tt>null</tt> .
   *
   * @param e DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   */
  private static Object key(Entry e) {
    if (e == null) {
      throw new NoSuchElementException();
    }
    return e.key;
  }

  /**
   * Test two values for equality. Differs from o1.equals(o2) only in that it
   * copes with with <tt>null</tt> o1 properly.
   *
   * @param o1 DESCRIBE THE PARAMETER
   * @param o2 DESCRIBE THE PARAMETER