/*
 * @author Ranides Atterwim <ranides@gmail.com>
 * @copyright Ranides Atterwim
 * @license WTFPL
 * @url http://ranides.net/projects/assira
 */
package net.ranides.assira.collection.lookups;

import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
import net.ranides.assira.collection.iterators.AListIterator;
import java.util.Comparator;
import java.util.ListIterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.SortedMap;
import net.ranides.assira.generic.CompareUtils;

/**
 * A type-specific red-black tree map with primitive int values
 *
 * <P>The iterators provided by the views can be safely cast to a type-specific
 * {@linkplain java.util.ListIterator list iterator}.
 */
@SuppressWarnings({
    "PMD.AvoidReassigningParameters"
})
public final class RBTreeLookup<K> extends ASortedLookup<K> implements java.io.Serializable {

    private static final long serialVersionUID = 1L;
        
    /**
     * A reference to the root entry.
     */
    protected transient Entry<K> tree;
    
    /**
     * Number of entries in this map.
     */
    protected int count;
    
    /**
     * The first key in this map.
     */
    protected transient Entry<K> firstEntry;
    
    /**
     * The last key in this map.
     */
    protected transient Entry<K> lastEntry;
    
    /**
     * This vector remembers the path and the direction followed during the
     * current insertion. It suffices for about 2<sup>32</sup> entries.
     */
    private transient boolean dirPath[];
    private transient Entry<K> nodePath[];


    /**
     * Creates a new empty tree map.
     */
    public RBTreeLookup() {
		this((Comparator<K>)null);
    }

    /**
     * Creates a new empty tree map with the given comparator.
     *
     * @param comparator a (possibly type-specific) comparator.
     */
    public RBTreeLookup(Comparator<? super K> comparator) {
        super(comparator);
		tree = null;
        count = 0;
        allocatePaths();
    }

    /**
     * Creates a new tree map copying a given map.
     *
     * @param values a {@link Map} to be copied into the new tree map.
     */
    public RBTreeLookup(Map<? extends K, ? extends Integer> values) {
        this();
        putAll(values);
    }

    /**
     * Creates a new tree map copying a given sorted map (and its
     * {@link Comparator}).
     *
     * @param values a {@link SortedMap} to be copied into the new tree map.
     */
    public RBTreeLookup(SortedMap<K, Integer> values) {
        this(values.comparator());
        putAll(values);
    }

    /**
     * Creates a new tree map copying a given map.
     *
     * @param values a type-specific map to be copied into the new tree map.
     */
    public RBTreeLookup(Lookup<? extends K> values) {
        this();
        putAll(values);
    }

    /**
     * Creates a new tree map copying a given sorted map (and its
     * {@link Comparator}).
     *
     * @param values a type-specific sorted map to be copied into the new tree map.
     */
    public RBTreeLookup(SortedLookup<K> values) {
        this(values.comparator());
        putAll(values);
    }

    /**
     * Creates a new tree map using the elements of two parallel arrays and the
     * given comparator.
     *
     * @param keys the array of mkeys of the new tree map.
     * @param values the array of corresponding mvalues in the new tree map.
     * @param comparator a (possibly type-specific) comparator.
     * @throws IllegalArgumentException if <code>k</code> and <code>v</code>
     * have different lengths.
     */
    public RBTreeLookup(K[] keys, int values[], Comparator<? super K> comparator) {
        this(comparator);
        if (keys.length != values.length) {
            throw new IllegalArgumentException("The key array and the value array have different lengths (" + keys.length + " and " + values.length + ")");
        }
        for (int i = 0; i < keys.length; i++) {
            this.put(keys[ i], values[ i]);
        }
    }

    /**
     * Creates a new tree map using the elements of two parallel arrays.
     *
     * @param keys the array of mkeys of the new tree map.
     * @param values the array of corresponding mvalues in the new tree map.
     * @throws IllegalArgumentException if <code>k</code> and <code>v</code>
     * have different lengths.
     */
    public RBTreeLookup(K[] keys, int[] values) {
        this(keys, values, null);
    }
    
    @SuppressWarnings("unchecked")
    private void allocatePaths() {
        dirPath = new boolean[64];
        nodePath = new Entry[64];
    }
    
    @Override
    protected Entry<K> findEntry(K key) {
        Entry<K> entry = tree;
        int cmp;
        while (entry != null && (cmp = compare(key, entry.key)) != 0) {
            entry = cmp < 0 ? entry.left() : entry.right();
        }
        return entry;
    }

    @Override
    protected Entry<K> locateEntry(K key) {
        Entry<K> current = tree, last = tree;
        int cmp = 0;
        while (current != null && (cmp = compare(key, current.key)) != 0) {
            last = current;
            current = cmp < 0 ? current.left() : current.right();
        }
        return cmp == 0 ? current : last;
    }

    @Override
    protected LookupEntry<K> firstEntry() {
        if (tree == null) {
            throw new NoSuchElementException();
        }
        return firstEntry;
    }

    @Override
    protected LookupEntry<K> lastEntry() {
        if (tree == null) {
            throw new NoSuchElementException();
        }
        return lastEntry;
    }

	@Override
	protected ListIterator<LookupEntry<K>> entryIterator() {
		return new TreeIterator();
	}

	@Override
	protected ListIterator<LookupEntry<K>> entryIterator(K begin) {
		return new TreeIterator(begin);
	}
    
    @Override
	protected SortedLookup<K> submap(K begin, boolean bottom, K end, boolean top) {
		return new Submap(begin, bottom, end, top);
	}
	
    @SuppressWarnings("PMD")
    @Override
    public int put(K key, int value) {
        modified = false;
        int maxDepth = 0;
        if (tree == null) { // The case of the empty tree is treated separately.
            count++;
            tree = lastEntry = firstEntry = new Entry<>(key, value);
        } else {
            Entry<K> current = tree, next;
            int cmp, i = 0;
            while (true) {
                if ((cmp = compare(key, current.key)) == 0) {
                    final int oldValue = current.value;
                    current.value = value;
                    // We clean up the node path, or we could have stale references later.
                    while (i-- != 0) {
                        nodePath[ i] = null;
                    }
                    return oldValue;
                }
                nodePath[ i] = current;
                if (dirPath[ i++] = cmp > 0) {
                    if (current.succ()) {
                        count++;
                        next = new Entry<>(key, value);
                        if (current.right == null) {
                            lastEntry = next;
                        }
                        next.left = current;
                        next.right = current.right;
                        current.right(next);
                        break;
                    }
                    current = current.right;
                } else {
                    if (current.pred()) {
                        count++;
                        next = new Entry<>(key, value);
                        if (current.left == null) {
                            firstEntry = next;
                        }
                        next.right = current;
                        next.left = current.left;
                        current.left(next);
                        break;
                    }
                    current = current.left;
                }
            }
            modified = true;
            maxDepth = i--;
            while (i > 0 && !nodePath[ i].black()) {
                if (!dirPath[ i - 1]) {
                    Entry<K> node = nodePath[ i - 1].right;
                    if (!nodePath[ i - 1].succ() && !node.black()) {
                        nodePath[ i].black(true);
                        node.black(true);
                        nodePath[ i - 1].black(false);
                        i -= 2;
                    } else {
                        Entry<K> xnode;
                        if (!dirPath[ i]) {
                            node = nodePath[ i];
                        } else {
                            xnode = nodePath[ i];
                            node = xnode.right;
                            xnode.right = node.left;
                            node.left = xnode;
                            nodePath[ i - 1].left = node;
                            if (node.pred()) {
                                node.pred(false);
                                xnode.succ(node);
                            }
                        }
                        xnode = nodePath[ i - 1];
                        xnode.black(false);
                        node.black(true);
                        xnode.left = node.right;
                        node.right = xnode;
                        if (i < 2) {
                            tree = node;
                        } else {
                            if (dirPath[ i - 2]) {
                                nodePath[ i - 2].right = node;
                            } else {
                                nodePath[ i - 2].left = node;
                            }
                        }
                        if (node.succ()) {
                            node.succ(false);
                            xnode.pred(node);
                        }
                        break;
                    }
                } else {
                    Entry<K> nodeY = nodePath[ i - 1].left;
                    if (!nodePath[ i - 1].pred() && !nodeY.black()) {
                        nodePath[ i].black(true);
                        nodeY.black(true);
                        nodePath[ i - 1].black(false);
                        i -= 2;
                    } else {
                        Entry<K> nodeX;
                        if (dirPath[ i]) {
                            nodeY = nodePath[ i];
                        } else {
                            nodeX = nodePath[ i];
                            nodeY = nodeX.left;
                            nodeX.left = nodeY.right;
                            nodeY.right = nodeX;
                            nodePath[ i - 1].right = nodeY;
                            if (nodeY.succ()) {
                                nodeY.succ(false);
                                nodeX.pred(nodeY);
                            }
                        }
                        nodeX = nodePath[ i - 1];
                        nodeX.black(false);
                        nodeY.black(true);
                        nodeX.right = nodeY.left;
                        nodeY.left = nodeX;
                        if (i < 2) {
                            tree = nodeY;
                        } else {
                            if (dirPath[ i - 2]) {
                                nodePath[ i - 2].right = nodeY;
                            } else {
                                nodePath[ i - 2].left = nodeY;
                            }
                        }
                        if (nodeY.pred()) {
                            nodeY.pred(false);
                            nodeX.succ(nodeY);
                        }
                        break;
                    }
                }
            }
        }
        tree.black(true);
        // We clean up the node path, or we could have stale references later.
        while (maxDepth-- != 0) {
            nodePath[ maxDepth] = null;
        }
        return defRetValue;
    }
    
    @SuppressWarnings({"PMD","unchecked"})
    @Override
    public int removeInt(Object key) {
        modified = false;
        if (tree == null) {
            return defRetValue;
        }
        Entry<K> current = tree;
        int cmp;
        int i = 0;
        final K kkey = (K) key;
        while (true) {
            if ((cmp = compare(kkey, current.key)) == 0) {
                break;
            }
            dirPath[ i] = cmp > 0;
            nodePath[ i] = current;
            if (dirPath[ i++]) {
                if ((current = current.right()) == null) {
                    // We clean up the node path, or we could have stale references later.
                    while (i-- != 0) {
                        nodePath[ i] = null;
                    }
                    return defRetValue;
                }
            } else {
                if ((current = current.left()) == null) {
                    // We clean up the node path, or we could have stale references later.
                    while (i-- != 0) {
                        nodePath[ i] = null;
                    }
                    return defRetValue;
                }
            }
        }
        if (current.left == null) {
            firstEntry = current.next();
        }
        if (current.right == null) {
            lastEntry = current.prev();
        }
        if (current.succ()) {
            if (current.pred()) {
                if (i == 0) {
                    tree = current.left;
                } else {
                    if (dirPath[ i - 1]) {
                        nodePath[ i - 1].succ(current.right);
                    } else {
                        nodePath[ i - 1].pred(current.left);
                    }
                }
            } else {
                current.prev().right = current.right;
                if (i == 0) {
                    tree = current.left;
                } else {
                    if (dirPath[ i - 1]) {
                        nodePath[ i - 1].right = current.left;
                    } else {
                        nodePath[ i - 1].left = current.left;
                    }
                }
            }
        } else {
            boolean color;
            Entry<K> rnode = current.right;
            if (rnode.pred()) {
                rnode.left = current.left;
                rnode.pred(current.pred());
                if (!rnode.pred()) {
                    rnode.prev().right = rnode;
                }
                if (i == 0) {
                    tree = rnode;
                } else {
                    if (dirPath[ i - 1]) {
                        nodePath[ i - 1].right = rnode;
                    } else {
                        nodePath[ i - 1].left = rnode;
                    }
                }
                color = rnode.black();
                rnode.black(current.black());
                current.black(color);
                dirPath[ i] = true;
                nodePath[ i++] = rnode;
            } else {
                Entry<K> snode;
                int j = i++;
                while (true) {
                    dirPath[ i] = false;
                    nodePath[ i++] = rnode;
                    snode = rnode.left;
                    if (snode.pred()) {
                        break;
                    }
                    rnode = snode;
                }
                dirPath[ j] = true;
                nodePath[ j] = snode;
                if (snode.succ()) {
                    rnode.pred(snode);
                } else {
                    rnode.left = snode.right;
                }
                snode.left = current.left;
                if (!current.pred()) {
                    current.prev().right = snode;
                    snode.pred(false);
                }
                snode.right(current.right);
                color = snode.black();
                snode.black(current.black());
                current.black(color);
                if (j == 0) {
                    tree = snode;
                } else {
                    if (dirPath[ j - 1]) {
                        nodePath[ j - 1].right = snode;
                    } else {
                        nodePath[ j - 1].left = snode;
                    }
                }
            }
        }
        int maxDepth = i;
        if (current.black()) {
            for (; i > 0; i--) {
                if (dirPath[ i - 1] && !nodePath[ i - 1].succ()
                        || !dirPath[ i - 1] && !nodePath[ i - 1].pred()) {
                    Entry<K> xnode = dirPath[ i - 1] ? nodePath[ i - 1].right : nodePath[ i - 1].left;
                    if (!xnode.black()) {
                        xnode.black(true);
                        break;
                    }
                }
                if (!dirPath[ i - 1]) {
                    Entry<K> wnode = nodePath[ i - 1].right;
                    if (!wnode.black()) {
                        wnode.black(true);
                        nodePath[ i - 1].black(false);
                        nodePath[ i - 1].right = wnode.left;
                        wnode.left = nodePath[ i - 1];
                        if (i < 2) {
                            tree = wnode;
                        } else {
                            if (dirPath[ i - 2]) {
                                nodePath[ i - 2].right = wnode;
                            } else {
                                nodePath[ i - 2].left = wnode;
                            }
                        }
                        nodePath[ i] = nodePath[ i - 1];
                        dirPath[ i] = false;
                        nodePath[ i - 1] = wnode;
                        if (maxDepth == i++) {
                            maxDepth++;
                        }
                        wnode = nodePath[ i - 1].right;
                    }
                    if ((wnode.pred() || wnode.left.black())
                            && (wnode.succ() || wnode.right.black())) {
                        wnode.black(false);
                    } else {
                        if (wnode.succ() || wnode.right.black()) {
                            Entry<K> ynode = wnode.left;
                            ynode.black(true);
                            wnode.black(false);
                            wnode.left = ynode.right;
                            ynode.right = wnode;
                            wnode = nodePath[ i - 1].right = ynode;
                            if (wnode.succ()) {
                                wnode.succ(false);
                                wnode.right.pred(wnode);
                            }
                        }
                        wnode.black(nodePath[ i - 1].black());
                        nodePath[ i - 1].black(true);
                        wnode.right.black(true);
                        nodePath[ i - 1].right = wnode.left;
                        wnode.left = nodePath[ i - 1];
                        if (i < 2) {
                            tree = wnode;
                        } else {
                            if (dirPath[ i - 2]) {
                                nodePath[ i - 2].right = wnode;
                            } else {
                                nodePath[ i - 2].left = wnode;
                            }
                        }
                        if (wnode.pred()) {
                            wnode.pred(false);
                            nodePath[ i - 1].succ(wnode);
                        }
                        break;
                    }
                } else {
                    Entry<K> wnode = nodePath[ i - 1].left;
                    if (!wnode.black()) {
                        wnode.black(true);
                        nodePath[ i - 1].black(false);
                        nodePath[ i - 1].left = wnode.right;
                        wnode.right = nodePath[ i - 1];
                        if (i < 2) {
                            tree = wnode;
                        } else {
                            if (dirPath[ i - 2]) {
                                nodePath[ i - 2].right = wnode;
                            } else {
                                nodePath[ i - 2].left = wnode;
                            }
                        }
                        nodePath[ i] = nodePath[ i - 1];
                        dirPath[ i] = true;
                        nodePath[ i - 1] = wnode;
                        if (maxDepth == i++) {
                            maxDepth++;
                        }
                        wnode = nodePath[ i - 1].left;
                    }
                    if ((wnode.pred() || wnode.left.black())
                            && (wnode.succ() || wnode.right.black())) {
                        wnode.black(false);
                    } else {
                        if (wnode.pred() || wnode.left.black()) {
                            Entry<K> ynode = wnode.right;
                            ynode.black(true);
                            wnode.black(false);
                            wnode.right = ynode.left;
                            ynode.left = wnode;
                            wnode = nodePath[ i - 1].left = ynode;
                            if (wnode.pred()) {
                                wnode.pred(false);
                                wnode.left.succ(wnode);
                            }
                        }
                        wnode.black(nodePath[ i - 1].black());
                        nodePath[ i - 1].black(true);
                        wnode.left.black(true);
                        nodePath[ i - 1].left = wnode.right;
                        wnode.right = nodePath[ i - 1];
                        if (i < 2) {
                            tree = wnode;
                        } else {
                            if (dirPath[ i - 2]) {
                                nodePath[ i - 2].right = wnode;
                            } else {
                                nodePath[ i - 2].left = wnode;
                            }
                        }
                        if (wnode.succ()) {
                            wnode.succ(false);
                            nodePath[ i - 1].pred(wnode);
                        }
                        break;
                    }
                }
            }
            if (tree != null) {
                tree.black(true);
            }
        }
        modified = true;
        count--;
        // We clean up the node path, or we could have stale references later.
        while (maxDepth-- != 0) {
            nodePath[ maxDepth] = null;
        }
        return current.value;
    }

    @Override
    public int size() {
        return count;
    }

    @Override
    public void clear() {
        count = 0;
        tree = null;
        firstEntry = null;
		lastEntry = null;
    }
    
    private void writeObject(java.io.ObjectOutputStream ostream) throws java.io.IOException {
        int n = count;
        TreeIterator iterator = new TreeIterator();
        ostream.defaultWriteObject();
        while (n-- != 0) {
            Entry<K> entry = iterator.next();
            ostream.writeObject(entry.key);
            ostream.writeInt(entry.value);
        }
    }

    /**
     * Reads the given number of entries from the input stream, returning the
     * corresponding tree.
     *
     * @param s the input istream.
     * @param n the (positive) number of entries to read.
     * @param pred the entry containing the key that preceeds the first key in
     * the tree.
     * @param succ the entry containing the key that follows the last key in the
     * tree.
     */
    @SuppressWarnings("unchecked")
    private Entry<K> readTree(java.io.ObjectInputStream istream, int n, Entry<K> pred, Entry<K> succ) throws java.io.IOException, ClassNotFoundException {
        if (n == 1) {
            final Entry<K> top = new Entry<>((K) istream.readObject(), istream.readInt());
            top.pred(pred);
            top.succ(succ);
            top.black(true);
            return top;
        }
        if (n == 2) {
            /* We handle separately this case so that recursion will
             *always* be on nonempty subtrees. */
            final Entry<K> top = new Entry<>((K) istream.readObject(), istream.readInt());
            top.black(true);
            top.right(new Entry<>((K) istream.readObject(), istream.readInt()));
            top.right.pred(top);
            top.pred(pred);
            top.right.succ(succ);
            return top;
        }
        // The right subtree is the largest one.
        final int rightN = n / 2, leftN = n - rightN - 1;
        final Entry<K> top = new Entry<>();
        top.left(readTree(istream, leftN, pred, top));
        top.key = (K) istream.readObject();
        top.value = istream.readInt();
        top.black(true);
        top.right(readTree(istream, rightN, top, succ));
        if (n + 2 == ((n + 2) & -(n + 2))) {
            top.right.black(false); // Quick test for determining whether n + 2 is a power of 2.
        }
        return top;
    }

    private void readObject(java.io.ObjectInputStream istream) throws java.io.IOException, ClassNotFoundException {
        istream.defaultReadObject();
        allocatePaths();
        if (count != 0) {
            tree = readTree(istream, count, null, null);
            Entry<K> entry = tree;
            while (entry.left() != null) {
                entry = entry.left();
            }
            firstEntry = entry;
            entry = tree;
            while (entry.right() != null) {
                entry = entry.right();
            }
            lastEntry = entry;
        }
    }

    /**
     * This class represent an entry in a tree map.
     *
     * <P>We use the only "metadata", i.e., {@link Entry#info}, to store
     * information about color, predecessor status and successor status.
     *
     * <P>Note that since the class is recursive, it can be considered
     * equivalently a tree.
     */
    private static final class Entry<K> implements LookupEntry<K> {

        /**
         * The the bit in this mask is true, the node is black.
         */
        private final static int BLACK_MASK = 1;
        /**
         * If the bit in this mask is true, {@link #right} points to a
         * successor.
         */
        private final static int SUCC_MASK = 1 << 31;
        /**
         * If the bit in this mask is true, {@link #left} points to a
         * predecessor.
         */
        private final static int PRED_MASK = 1 << 30;
        /**
         * The key of this entry.
         */
        K key;
        /**
         * The value of this entry.
         */
        int value;
        /**
         * The pointers to the left and right subtrees.
         */
        Entry<K> left, right;
        /**
         * This integers holds different information in different bits (see
         * {@link #SUCC_MASK} and {@link #PRED_MASK}.
         */
        int info;

        Entry() {
        }

        /**
         * Creates a new entry with the given key and value.
         *
         * @param key a key.
         * @param value a value.
         */
        Entry(K key, int value) {
            this.key = key;
            this.value = value;
            info = SUCC_MASK | PRED_MASK;
        }

        /**
         * Returns the left subtree.
         *
         * @return the left subtree (<code>null</code> if the left subtree is
         * empty).
         */
        Entry<K> left() {
            return (info & PRED_MASK) != 0 ? null : left;
        }

        /**
         * Returns the right subtree.
         *
         * @return the right subtree (<code>null</code> if the right subtree is
         * empty).
         */
        Entry<K> right() {
            return (info & SUCC_MASK) != 0 ? null : right;
        }

        /**
         * Checks whether the left pointer is really a predecessor.
         *
         * @return true if the left pointer is a predecessor.
         */
        boolean pred() {
            return (info & PRED_MASK) != 0;
        }

        /**
         * Checks whether the right pointer is really a successor.
         *
         * @return true if the right pointer is a successor.
         */
        boolean succ() {
            return (info & SUCC_MASK) != 0;
        }

        /**
         * Sets whether the left pointer is really a predecessor.
         *
         * @param pred if true then the left pointer will be considered a
         * predecessor.
         */
        void pred(boolean pred) {
            if (pred) {
                info |= PRED_MASK;
            } else {
                info &= ~PRED_MASK;
            }
        }

        /**
         * Sets whether the right pointer is really a successor.
         *
         * @param succ if true then the right pointer will be considered a
         * successor.
         */
        void succ(boolean succ) {
            if (succ) {
                info |= SUCC_MASK;
            } else {
                info &= ~SUCC_MASK;
            }
        }

        /**
         * Sets the left pointer to a predecessor.
         *
         * @param pred the predecessr.
         */
        void pred(Entry<K> pred) {
            info |= PRED_MASK;
            left = pred;
        }

        /**
         * Sets the right pointer to a successor.
         *
         * @param succ the successor.
         */
        void succ(Entry<K> succ) {
            info |= SUCC_MASK;
            right = succ;
        }

        /**
         * Sets the left pointer to the given subtree.
         *
         * @param left the new left subtree.
         */
        void left(Entry<K> left) {
            info &= ~PRED_MASK;
            this.left = left;
        }

        /**
         * Sets the right pointer to the given subtree.
         *
         * @param right the new right subtree.
         */
        void right(Entry<K> right) {
            info &= ~SUCC_MASK;
            this.right = right;
        }

        /**
         * Returns whether this node is black.
         *
         * @return true iff this node is black.
         */
        boolean black() {
            return (info & BLACK_MASK) != 0;
        }

        /**
         * Sets whether this node is black.
         *
         * @param black if true, then this node becomes black; otherwise, it
         * becomes red..
         */
        void black(boolean black) {
            if (black) {
                info |= BLACK_MASK;
            } else {
                info &= ~BLACK_MASK;
            }
        }

        /**
         * Computes the next entry in the set order.
         *
         * @return the next entry (<code>null</code>) if this is the last
         * entry).
         */
        Entry<K> next() {
            Entry<K> next = this.right;
            if ((info & SUCC_MASK) == 0) {
                while ((next.info & PRED_MASK) == 0) {
                    next = next.left;
                }
            }
            return next;
        }

        /**
         * Computes the previous entry in the set order.
         *
         * @return the previous entry (<code>null</code>) if this is the first
         * entry).
         */
        Entry<K> prev() {
            Entry<K> prev = this.left;
            if ((info & PRED_MASK) == 0) {
                while ((prev.info & SUCC_MASK) == 0) {
                    prev = prev.right;
                }
            }
            return prev;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public Integer getValue() {
            return value;
        }

        @Override
        public int getIntValue() {
            return value;
        }

        @Override
        public int setValue(int value) {
            final int oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        @Override
        public Integer setValue(Integer value) {
            return setValue(value.intValue());
        }

        @SuppressWarnings("unchecked")
        @Override
        public boolean equals(Object object) {
            if (!(object instanceof Map.Entry)) {
                return false;
            }
            Map.Entry<K, Integer> entry = (Map.Entry<K, Integer>) object;
            return CompareUtils.equals(key, entry.getKey()) && CompareUtils.equals(value, entry.getValue());
        }

        @Override
        public int hashCode() {
            return ((key) == null ? 0 : (key).hashCode()) ^ (value);
        }

        @Override
        public String toString() {
            return key + "=>" + value;
        }
        
    }
    
    /**
     * An abstract iterator on the whole range.
     *
     * <P>This class can iterate in both directions on a threaded tree.
     */
    private class TreeIterator extends AListIterator<LookupEntry<K>> {

        /**
         * The entry that will be returned by the next call to
         * {@link java.util.ListIterator#previous()} (or
         * <code>null</code> if no previous entry exists).
         */
        Entry<K> prev;
        /**
         * The entry that will be returned by the next call to
         * {@link java.util.ListIterator#next()} (or
         * <code>null</code> if no next entry exists).
         */
        Entry<K> next;
        /**
         * The last entry that was returned (or
         * <code>null</code> if we did not iterate or used {@link #remove()}).
         */
        Entry<K> curr;
        /**
         * The current index (in the sense of a {@link java.util.ListIterator}).
         * Note that this value is not meaningful when this {@link TreeIterator}
         * has been created using the nonempty constructor.
         */
        int index = 0;

        TreeIterator() {
            next = firstEntry;
        }

        TreeIterator(K key) {
            if ((next = locateEntry(key)) != null) {
                if (compare(next.key, key) <= 0) {
                    prev = next;
                    next = next.next();
                } else {
                    prev = next.prev();
                }
            }
        }

        @Override
        public boolean hasNext() {
            return next != null;
        }

        @Override
        public boolean hasPrevious() {
            return prev != null;
        }

        void updateNext() {
            next = next.next();
        }

        @Override
        public Entry<K> next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            curr = prev = next;
            index++;
            updateNext();
            return curr;
        }

        void updatePrevious() {
            prev = prev.prev();
        }

        @Override
        public Entry<K> previous() {
            if (!hasPrevious()) {
                throw new NoSuchElementException();
            }
            curr = next = prev;
            index--;
            updatePrevious();
            return curr;
        }

        @Override
        public int nextIndex() {
            return index;
        }

        @Override
        public int previousIndex() {
            return index - 1;
        }

        @Override
        public void remove() {
            if (curr == null) {
                throw new IllegalStateException();
            }
            /* If the last operation was a next(), we are removing an entry that preceeds
             the current index, and thus we must decrement it. */
            if (curr == prev) { //NOPMD
                index--;
            }
            next = prev = curr;
            updatePrevious();
            updateNext();
            RBTreeLookup.this.removeInt(curr.key);
            curr = null;
        }

    }

    @SuppressFBWarnings("SE_INNER_CLASS")
    private final class Submap extends ASubmap implements java.io.Serializable {

        private static final long serialVersionUID = 2L;
         
        public Submap(K begin, boolean bottom, K end, boolean top) {
			super(begin, bottom, end, top);
        }

		@Override
		protected ListIterator<LookupEntry<K>> entryIterator() {
			return new STreeIterator();
		}

		@Override
		protected ListIterator<LookupEntry<K>> entryIterator(K begin) {
			return new STreeIterator(begin);
		}

		@Override
		protected SortedLookup<K> ssubmap(K begin, boolean bottom, K end, boolean top) {
			return new Submap(begin, bottom, end, top);
		}
		
		@Override
		protected LookupEntry<K> findEntry(K key) {
			if( !inside(key) ) {
				return null;
			}
			return RBTreeLookup.this.findEntry(key);
		}
		
		@Override
        protected RBTreeLookup.Entry<K> locateEntry(K key) {
            return RBTreeLookup.this.locateEntry(key);
        }

        @Override
        public RBTreeLookup.Entry<K> firstEntry() {
            if (tree == null) {
                return null;
            }
            // If this submap goes to -infinity, we return the main map first entry; otherwise, we locate the start of the map.
            RBTreeLookup.Entry<K> entry;
            if (bottom) {
                entry = firstEntry;
            } else {
                entry = locateEntry(begin);
                // If we find either the start or something greater we're OK.
                if (entry!=null && compare(entry.key, begin) < 0) {
                    entry = entry.next();
                }
            }
            // Finally, if this submap doesn't go to infinity, we check that the resulting key isn't greater than the end.
            if (entry == null || !top && compare(entry.key, end) >= 0) {
                return null;
            }
            return entry;
        }

        @Override
        public RBTreeLookup.Entry<K> lastEntry() {
            if (tree == null) {
                return null;
            }
            // If this submap goes to infinity, we return the main map last entry; otherwise, we locate the end of the map.
            RBTreeLookup.Entry<K> entry;
            if (top) {
                entry = lastEntry;
            } else {
                entry = locateEntry(end);
                // If we find something smaller than the end we're OK.
                if (compare(entry.key, end) >= 0) {
                    entry = entry.prev();
                }
            }
            // Finally, if this submap doesn't go to -infinity, we check that the resulting key isn't smaller than the start.
            if (entry == null || !bottom && compare(entry.key, begin) < 0) {
                return null;
            }
            return entry;
        }

        private class STreeIterator extends TreeIterator {

            STreeIterator() {
                next = firstEntry();
            }

            STreeIterator(K key) {
                this();
                if (next != null) {
                    if (!bottom && compare(key, next.key) < 0) {
                        prev = null;
                    } else if (!top && compare(key, (prev = lastEntry()).key) >= 0) {
                        next = null;
                    } else {
                        next = locateEntry(key);
                        if (compare(next.key, key) <= 0) {
                            prev = next;
                            next = next.next();
                        } else {
                            prev = next.prev();
                        }
                    }
                }
            }

            @Override
            void updatePrevious() {
                prev = prev.prev();
                if (!bottom && prev != null && compare(prev.key, begin) < 0) {
                    prev = null;
                }
            }

            @Override
            void updateNext() {
                next = next.next();
                if (!top && next != null && compare(next.key, end) >= 0) {
                    next = null;
                }
            }
        }

    }

}
