* algorithms.     */    private static boolean colorOf(Entry p) {        return (p == null ? BLACK : p.color);    }    private static Entry  parentOf(Entry p) {         return (p == null ? null: p.parent);    }    private static void setColor(Entry p, boolean c) {         if (p != null)  p.color = c;     }    private static Entry  leftOf(Entry p) {         return (p == null)? null: p.left;     }    private static Entry  rightOf(Entry p) {         return (p == null)? null: p.right;     }    /** From CLR **/    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 **/    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 **/    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.     */    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;            }        }    }    /** From CLR **/    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);     }    private static final long serialVersionUID = 919286545866124006L;    /**     * Save the state of the <tt>TreeMap</tt> instance to a stream (i.e.,     * serialize it).     *     * @serialData The <i>size</i> of the TreeMap (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 TreeMap. The key-value mappings are emitted in     *             key-order (as determined by the TreeMap's Comparator,     *             or by the keys' natural ordering if the TreeMap 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>TreeMap</tt> instance from a stream (i.e.,     * deserialize it).     */    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 **/    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 **/    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 TreeMap 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 it If non-null, new entries are created from keys and     *        possibly values read from this stream in serialized form.     *        Exactly one of it and str should be non-null.     * @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.     * @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);    }    /**     * 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 TreeMap 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.     */    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.)     */    private static int computeRedLevel(int sz) {        int level = 0;        for (int m = sz - 1; m >= 0; m = m / 2 - 1)             level++;        return level;    }}