abstracttreemap.java

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

                Entry y = x.p.p.left;
                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.left) {
                        x = x.p;
                        rotateRight(x);
                    }
                    x.p.color = BLACK;
                    x.p.p.color = RED;
                    if (x.p.p != NIL) 
                        rotateLeft(x.p.p);
                }
            }
        }
        root.color = BLACK;
    }
    
    protected void fixUpRemove(Entry x) {
        while (x != root && x.color == BLACK) {
            if (x == x.p.left) {
                Entry sib = x.p.right;

                if (sib.color == RED) {
                    sib.color = BLACK;
                    x.p.color = RED;
                    rotateLeft(x.p);
                    sib = x.p.right;
                }

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

                if (sib.color == RED) {
                    sib.color = BLACK;
                    x.p.color = RED;
                    rotateRight(x.p);
                    sib = x.p.left;
                }

                if (sib.right.color == BLACK && 
                    sib.left.color == BLACK) {
                    sib.color =  RED;
                    x = x.p;
                } else {
                    if (sib.left.color == BLACK) {
                        sib.right.color = BLACK;
                        sib.color = RED;
                        rotateLeft(sib);
                        sib = x.p.left;
                    }
                    sib.color = x.p.color;
                    x.p.color = BLACK;
                    sib.left.color = BLACK;
                    rotateRight(x.p);
                    x = root;
                }
            }
        }

        x.color = BLACK; 
    }
    
    protected void remove(Entry z) {
        boolean isUnique = !( z.keyEquals(z.left) || 
            z.keyEquals(z.right) || z.keyEquals(z.p) );
        
        Entry y = ( z.left != NIL && z.right != NIL ? successor(z) : z );
        Entry x = ( y.left != NIL ? y.left : y.right );
        x.p = y.p;
        
        if (y.p == NIL) {
            root = x;
        } else if (y == y.p.left) {
            y.p.left = x;
        } else {
            y.p.right = x;
        }
        
        if (y != z) {
            z.copyFields(y);
        }
        if (y.color == BLACK)
            fixUpRemove(x);
        
        decrementSize(isUnique);
    }
    
    // ========================================================================
    // Inner classes
    
    // ------------------------------------------------------------------------
    // Entry class - represents a Red-Black Tree Node
    
    public static class Entry {
        int val;
        int order; // used to determine ordering for duplicate keys
        
        Entry left = null;
        Entry right = null;
        Entry p;
        boolean color = BLACK;
        
        public Entry(int val) {
            this.val = val;
        }
        
        public Entry(int val, Entry parent, int order) {
            this.val = val;
            this.p = parent;
            this.order = order;
            this.left = NIL;
            this.right = NIL;
        }
        
        public int getIntKey() {
            throw new UnsupportedOperationException("Unsupported");
        }
        
        public long getLongKey() {
            throw new UnsupportedOperationException("Unsupported");
        }
        
        public float getFloatKey() {
            throw new UnsupportedOperationException("Unsupported");
        }
        
        public double getDoubleKey() {
            throw new UnsupportedOperationException("Unsupported");
        }
        
        public Object getKey() {
            return null;
        }

        public int getValue() {
            return val;
        }

        public int getOrder() {
            return order;
        }
        
        public int setValue(int value) {
            int old = val;
            val = value;
            return old;
        }
        
        public boolean keyEquals(Entry e) {
            Object k = getKey();
            return ( k==null ? k==e.getKey() : k.equals(e.getKey()) );
        }
        
        public boolean equals(Object o) {
            if (!(o instanceof Entry))
                return false;
            
            Entry e = (Entry)o;
            
            return (val == e.val && getKey() == e.getKey());
        }

        public int hashCode() {
            int khash = getKey().hashCode();
            int vhash = val;
            return khash^vhash;
        }

        public String toString() {
            return getKey() + "=" + val;
        }
        
        public void copyFields(Entry x) {
            this.val = x.val;
            this.order = x.order;
        }
        
    }
    
    // ------------------------------------------------------------------------
    // Iterators
    
    protected class EntryIterator extends AbstractLiteralIterator {
        private int expectedModCount = AbstractTreeMap.this.modCount;
        private Entry lastReturned = NIL;
        private boolean reverse = false;
        Entry next, end;

        EntryIterator(boolean reverse) {
            next = reverse ? maximum(root) : minimum(root);
            end = NIL;
        }

        EntryIterator(Entry first, Entry last) {
            next = first;
            end = last;
            reverse = first==NIL ? true 
                    : last==NIL ? false 
                    : compare(first,last) > 0;
        }

        public boolean hasNext() {
            return next != end;
        }

        final Entry nextEntry() {
            if (!hasNext())
                throw new NoSuchElementException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            lastReturned = next;
            next = reverse ? predecessor(next) : successor(next);
            /// XXX DEBUG
            if ( lastReturned == NIL ) {
                System.err.println("Encountered NIL in iteration!");
            }
            return lastReturned;
        }

        public Object next() {
            return nextEntry();
        }

        public void remove() {
            if (lastReturned == NIL)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (lastReturned.left != NIL && lastReturned.right != NIL) 
                next = lastReturned; 
            AbstractTreeMap.this.remove(lastReturned);
            ++expectedModCount;
            lastReturned = NIL;
        }
    }

    protected class KeyIterator extends EntryIterator {
        public KeyIterator() {
            super(false);
        }
        public KeyIterator(Entry start, Entry end) {
            super(start, end);
        }
        public Object next() {
            return nextEntry().getKey();
        }
    }

    protected class ValueIterator extends IntIterator {
        EntryIterator m_iter;
        
        public ValueIterator(EntryIterator iter) {
            m_iter = iter;
        }
        public boolean hasNext() {
            return m_iter.hasNext();
        }
        public int nextInt() {
            return m_iter.nextEntry().val;
        }
        public void remove() {
            m_iter.remove();
        }
    }
        
} // end of abstract class AbstractTreeMap