abstracttreemap.java

来自「用applet实现很多应用小程序」· Java 代码 · 共 578 行 · 第 1/2 页

package prefuse.util.collections;

import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.NoSuchElementException;


/**
 * Abstract base class for red-black trees that map a key value to
 * an int value.
 * 
 * @author <a href="http://jheer.org">jeffrey heer</a>
 */
public abstract class AbstractTreeMap implements IntSortedMap {

    protected static final boolean RED   = false;
    protected static final boolean BLACK = true;
    
    protected static final Entry NIL = new Entry(Integer.MIN_VALUE);
    static {
        NIL.left = NIL.right = NIL.p = NIL;
    }
    
    protected LiteralComparator cmp = null;
    protected Entry root = NIL;
    
    protected boolean allowDuplicates;
    protected int size = 0;
    protected int unique = 0;
    protected int modCount = 0;
    protected int lastOrder = 0;
    
    // ------------------------------------------------------------------------
    // Constructors

    public AbstractTreeMap(LiteralComparator comparator, 
                               boolean allowDuplicates)
    {
        this.cmp = comparator==null ? DefaultLiteralComparator.getInstance()
                                    : comparator;
        this.allowDuplicates = allowDuplicates;
    }

    // ------------------------------------------------------------------------
    // Accessor Methods
    
    public boolean isAllowDuplicates() {
        return allowDuplicates;
    }
    
    /**
     * @see java.util.Map#size()
     */
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return root == NIL;
    }
    
    /**
     * @see java.util.SortedMap#comparator()
     */
    public Comparator comparator() {
        return cmp;
    }
    
    // ------------------------------------------------------------------------
    // SortedMap Methods
    
    /**
     * @see java.util.Map#clear()
     */
    public void clear() {
        ++modCount;
        size = 0;
        root = NIL;
    }

    public int getMinimum() {
        return minimum(root).getValue();
    }
    
    public int getMaximum() {
        return maximum(root).getValue();
    }
    
    public int getMedian() {
        Entry e = minimum(root);
        for ( int i=0; i<size/2; ++i, e=successor(e) );
        return e.getValue();
    }
    
    public int getUniqueCount() {
        return unique;
    }
    
    /**
     * @see java.util.Map#containsValue(java.lang.Object)
     */
    public boolean containsValue(int value) {
        return (root == NIL ? false : containsValue(root, value));
    }
    
    private boolean containsValue(Entry e, int value) {
        if ( e.val == value ) {
            return true;
        } else {
            return (e.left  != NIL && containsValue(e.left,  value)) ||
                   (e.right != NIL && containsValue(e.right, value));
        }
    }
    
    // -- Collection view methods ---------------------------------------------
    
    public IntIterator valueIterator(boolean ascend) {
        return new ValueIterator(new EntryIterator(!ascend));
    }
    
    // ------------------------------------------------------------------------
    // Internal update methods
    
    protected void incrementSize(boolean isUnique) {
        ++size; ++modCount;
        if ( isUnique ) ++unique;
    }
    
    protected void decrementSize(boolean isUnique) {
        --size; ++modCount;
        if ( isUnique ) --unique;
    }
    
    // ------------------------------------------------------------------------
    // Internal Binary Search Tree / Red-Black Tree methods
    // Adapted from Cormen, Leiserson, and Rivest's Introduction to Algorithms
    
    protected abstract int compare(Entry e1, Entry e2);
    
    protected Entry find(Entry x) {
        Entry y = root;
        while (y != NIL) {
            int cmp = compare(x, y);
            if (cmp == 0)
                return y;
            else if (cmp < 0)
                y = y.left;
            else
                y = y.right;
        }
        return y;
    }
    
    protected Entry findPredecessor(Entry x) {
        Entry y = root;
        while (y != NIL) {
            int cmp = compare(x, y);
            if (cmp > 0) {
                if ( y.right == NIL )
                    return y;
                y = y.right;
            } else {
                if ( y.left != NIL ) {
                    y = y.left;
                } else {
                    Entry up = y.p, c = y;
                    for ( ; up != NIL && c == up.left; c = up, up = up.p );
                    return up;
                }
            }
        }
        return y;
    }
    
    protected Entry findCeiling(Entry x) {
        Entry y = root;

        while ( y != NIL ) {
            int cmp = compare(x, y);
            if (cmp == 0) {
                return y;
            } else if (cmp < 0) {
                if (y.left != NIL)
                    y = y.left;
                else
                    return y;
            } else {
                if (y.right != NIL) {
                    y = y.right;
                } else {
                    Entry up = y.p, c = y;
                    for ( ; up != NIL && c == up.right; c = up, up = up.p );
                    return up;
                }
            }
        }
        return y;
    }
    
    protected Entry minimum(Entry x) {
        for ( ; x.left != NIL; x = x.left );
        return x;
    }
    
    protected Entry maximum(Entry x) {
        for ( ; x.right != NIL; x = x.right );
        return x;
    }
    
    protected Entry successor(Entry x) {
        // easy case - just traverse to the right
        if ( x.right != NIL ) return minimum(x.right);
        
        // else have to climb up
        Entry y = x.p;
        while ( y != NIL && x == y.right ) {
            x = y;
            y = y.p;
        }
        return y;
    }
    
    protected Entry predecessor(Entry x) {
        // easy case - just traverse to the left
        if ( x.left != NIL ) return maximum(x.left);
        
        // else have to climb up
        Entry y = x.p;
        while ( y != NIL && x == y.left ) {
            x = y;
            y = y.p;
        }
        return y;
    }
    
    protected void rotateLeft(Entry x) {
        Entry y = x.right;
        x.right = y.left;
        if (y.left != NIL)
            y.left.p = x;
        y.p = x.p;
        if (x.p == NIL)
            root = y;
        else if (x.p.left == x)
            x.p.left = y;
        else
            x.p.right = y;
        y.left = x;
        x.p = y;
    }

    protected void rotateRight(Entry x) {
        Entry y = x.left;
        x.left = y.right;
        if (y.right != NIL)
            y.right.p = x;
        y.p = x.p;
        if (x.p == NIL)
            root = y;
        else if (x.p.right == x)
            x.p.right = y;
        else x.p.left = y;
        y.right = x;
        x.p = y;
    }

    protected void fixUpInsert(Entry x) {
        x.color = RED;

        while (x != NIL && x != root && x.p.color == RED) {
            if (x.p == x.p.p.left) {
                Entry y = x.p.p.right;
                if (y.color == RED) {
                    x.p.color = BLACK;
                    y.color = BLACK;
                    x.p.p.color = RED;
                    x = x.p.p;
                } else {
                    if (x == x.p.right) {
                        x = x.p;
                        rotateLeft(x);
                    }
                    x.p.color = BLACK;
                    x.p.p.color = RED;
                    if (x.p.p != NIL) 
                        rotateRight(x.p.p);
                }
            } else {
                // mirror image case