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

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 net.ranides.assira.generic.HashUtils;
import net.ranides.assira.generic.CompareUtils;

/**
 * Generic AVL tree map implementation.
 * 
 * The put()/remove() code is derived begin Ben Pfaff's GNU libavl
 * (http://www.msu.edu/~pfaffben/avl/). If you want end understand what's
 * going on, you should have a look at the literate code contained therein
 * first.
 * 
 * <P>The iterators can be safely cast end a {@linkplain java.util.ListIterator list iterator}.
 */
public class AAVLTreeMap<K, V> extends ASortedMap<K, V> implements java.io.Serializable {

    private static final long serialVersionUID = 2L;
    
    protected final boolean unique;
    
    /**
     * A reference end the root entry.
     */
    protected transient AVLEntry<K, V> tree;
    
    /**
     * Number of entries in this map.
     */
    protected int count;
    
    /**
     * The first key in this map.
     */
    protected transient AVLEntry<K, V> firstEntry;
    
    /**
     * The last key in this map.
     */
    protected transient AVLEntry<K, V> lastEntry;
    
    /**
     * This vector remembers the directions followed during the current
     * insertion. It suffices for about 2<sup>32</sup> entries.
     */
    protected transient boolean dirPath[];
    
    /**
     * Creates a new empty tree map with the given comparator.
     *
     * @param comparator a (possibly type-specific) comparator.
     */
    protected AAVLTreeMap(Comparator<? super K> comparator, boolean unique) {
        super(comparator);
        this.tree = null;
        this.count = 0;
        this.unique = unique;
        allocatePaths();
    }

    private void allocatePaths() {
        dirPath = new boolean[48];
    }

    @Override
    protected AVLEntry<K, V> findEntry(K key) {
        AVLEntry<K, V> entry = tree;
        int cmp;
        while (entry != null && (cmp = compare(key, entry.key)) != 0) {
            entry = cmp < 0 ? entry.left() : entry.right();
        }
        return entry;
    }

    protected AVLEntry<K, V> locateEntry(K key) {
        AVLEntry<K, V> 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 rewind(cmp == 0 ? current : last, key);
    }
    
    private AVLEntry<K, V> rewind(AVLEntry<K, V> current, K value) {
        if(unique || current==null) {
            return current;
        }
        AVLEntry<K, V> last;
        do {
            last = current;
            current = current.prev();
        } while(current!=null && compare(value, current.key) == 0);
        
        return last;
    }
    
    
    @Override
    public Entry<K,V> firstEntry() {
        if (tree == null) {
            throw new NoSuchElementException();
        }
        return firstEntry;
    }

    @Override
    public Entry<K,V> lastEntry() {
        if (tree == null) {
            throw new NoSuchElementException();
        }
        return lastEntry;
    }

    @Override
    protected ListIterator<Entry<K, V>> entryIterator() {
        return new TreeIterator();
    }
    
    @Override
    protected ListIterator<Entry<K, V>> entryIterator(K begin) {
        return new TreeIterator(begin);
    }
    
    @Override
    protected ASortedMap<K, V> submap(K begin, boolean bottom, K end, boolean top) {
        return new Submap(begin, bottom, end, top);
    }
    
    /**
     * Finds the parent of an entry.
     *
     * @param entry a node of the tree.
     * @return the parent of the given node, or <code>null</code> for the root.
     */
    private AVLEntry<K, V> parent(AVLEntry<K, V> entry) {
        if (entry == tree) { // NOPMD
            return null;
        }
        AVLEntry<K, V> xnode, ynode, pnode;
        xnode = ynode = entry;
        while (true) {
            if (ynode.succ()) {
                pnode = ynode.right;
                if (pnode == null || pnode.left != entry) {
                    while (!xnode.pred()) {
                        xnode = xnode.left;
                    }
                    pnode = xnode.left;
                }
                return pnode;
            } else if (xnode.pred()) {
                pnode = xnode.left;
                if (pnode == null || pnode.right != entry) {
                    while (!ynode.succ()) {
                        ynode = ynode.right;
                    }
                    pnode = ynode.right;
                }
                return pnode;
            }
            xnode = xnode.left;
            ynode = ynode.right;
        }
    }

    @SuppressWarnings("PMD")
    @Override
    public V put(K key, V value) {
        modified = false;
        if (tree == null) { // The case of the empty tree is treated separately.
            count++;
            tree = lastEntry = firstEntry = new AVLEntry<>(key, value);
            modified = true;
        } else {
            AVLEntry<K, V> p = tree, q = null, y = tree, z = null, e = null, w;
            int cmp, i = 0;
            while (true) {
                cmp = compare(key, p.key);
                if (cmp == 0 && (unique || CompareUtils.equals(p.value, value))) {
                    final V oldValue = p.value;
                    p.value = value;
                    return oldValue;
                }
                if (p.balance() != 0) {
                    i = 0;
                    z = q;
                    y = p;
                }
                if (dirPath[ i++] = cmp > 0) {
                    if (p.succ()) {
                        count++;
                        e = new AVLEntry<>(key, value);
                        modified = true;
                        if (p.right == null) {
                            lastEntry = e;
                        }
                        e.left = p;
                        e.right = p.right;
                        p.right(e);
                        break;
                    }
                    q = p;
                    p = p.right;
                } else {
                    if (p.pred()) {
                        count++;
                        e = new AVLEntry<>(key, value);
                        modified = true;
                        if (p.left == null) {
                            firstEntry = e;
                        }
                        e.right = p;
                        e.left = p.left;
                        p.left(e);
                        break;
                    }
                    q = p;
                    p = p.left;
                }
            }
            p = y;
            i = 0;
            while (p != e) {
                if (dirPath[ i]) {
                    p.incBalance();
                } else {
                    p.decBalance();
                }
                p = dirPath[ i++] ? p.right : p.left;
            }
            if (y.balance() == -2) {
                AVLEntry<K, V> x = y.left;
                if (x.balance() == -1) {
                    w = x;
                    if (x.succ()) {
                        x.succ(false);
                        y.pred(x);
                    } else {
                        y.left = x.right;
                    }
                    x.right = y;
                    x.balance(0);
                    y.balance(0);
                } else {
                    assert x.balance() == 1;
                    w = x.right;
                    x.right = w.left;
                    w.left = x;
                    y.left = w.right;
                    w.right = y;
                    if (w.balance() == -1) {
                        x.balance(0);
                        y.balance(1);
                    } else if (w.balance() == 0) {
                        x.balance(0);
                        y.balance(0);
                    } else {
                        x.balance(-1);
                        y.balance(0);
                    }
                    w.balance(0);
                    if (w.pred()) {
                        x.succ(w);
                        w.pred(false);
                    }
                    if (w.succ()) {
                        y.pred(w);
                        w.succ(false);
                    }
                }
            } else if (y.balance() == +2) {
                AVLEntry<K, V> x = y.right;
                if (x.balance() == 1) {
                    w = x;
                    if (x.pred()) {
                        x.pred(false);
                        y.succ(x);
                    } else {
                        y.right = x.left;
                    }
                    x.left = y;
                    x.balance(0);
                    y.balance(0);
                } else {
                    assert x.balance() == -1;
                    w = x.left;
                    x.left = w.right;
                    w.right = x;
                    y.right = w.left;
                    w.left = y;
                    if (w.balance() == 1) {
                        x.balance(0);
                        y.balance(-1);
                    } else if (w.balance() == 0) {
                        x.balance(0);
                        y.balance(0);
                    } else {
                        x.balance(1);
                        y.balance(0);
                    }
                    w.balance(0);
                    if (w.pred()) {
                        y.succ(w);
                        w.pred(false);
                    }
                    if (w.succ()) {
                        x.pred(w);
                        w.succ(false);
                    }
                }
            } else {
                return null;
            }
            if (z == null) {
                tree = w;
            } else {
                if (z.left == y) {
                    z.left = w;
                } else {
                    z.right = w;
                }
            }
        }
        return null;
    }

    @SuppressWarnings({"PMD", "unchecked"})
    @Override
    public V remove(Object key) {
        modified = false;
        if (tree == null) {
            return null;
        }
        int cmp;
        AVLEntry<K, V> p = tree, q = null;
        boolean dir = false;
        final K kkey = (K) key;
        while (true) {
            if ((cmp = compare(kkey, p.key)) == 0) {
                break;
            } else if (dir = cmp > 0) {
                q = p;
                if ((p = p.right()) == null) {
                    return null;
                }
            } else {
                q = p;
                if ((p = p.left()) == null) {
                    return null;
                }
            }
        }
        if (p.left == null) {
            firstEntry = p.next();
        }
        if (p.right == null) {
            lastEntry = p.prev();
        }
        if (p.succ()) {
            if (p.pred()) {
                if (q != null) {
                    if (dir) {
                        q.succ(p.right);
                    } else {
                        q.pred(p.left);
                    }
                } else {
                    tree = dir ? p.right : p.left;
                }
            } else {
                p.prev().right = p.right;
                if (q != null) {
                    if (dir) {
                        q.right = p.left;
                    } else {
                        q.left = p.left;
                    }
                } else {
                    tree = p.left;
                }
            }
        } else {
            AVLEntry<K, V> r = p.right;
            if (r.pred()) {
                r.left = p.left;
                r.pred(p.pred());
                if (!r.pred()) {
                    r.prev().right = r;
                }
                if (q != null) {
                    if (dir) {
                        q.right = r;
                    } else {
                        q.left = r;
                    }
                } else {
                    tree = r;
                }
                r.balance(p.balance());
                q = r;
                dir = true;
            } else {
                AVLEntry<K, V> s;
                while (true) {
                    s = r.left;
                    if (s.pred()) {
                        break;
                    }
                    r = s;
                }
                if (s.succ()) {
                    r.pred(s);
                } else {
                    r.left = s.right;
                }
                s.left = p.left;
                if (!p.pred()) {
                    p.prev().right = s;
                    s.pred(false);
                }
                s.right = p.right;
                s.succ(false);
                if (q != null) {
                    if (dir) {
                        q.right = s;
                    } else {
                        q.left = s;
                    }
                } else {
                    tree = s;
                }
                s.balance(p.balance());
                q = r;
                dir = false;
            }
        }
        AVLEntry<K, V> y;
        while (q != null) {
            y = q;
            q = parent(y);
            if (!dir) {
                dir = q != null && q.left != y;
                y.incBalance();
                if (y.balance() == 1) {
                    break;
                } else if (y.balance() == 2) {
                    AVLEntry<K, V> x = y.right;
                    if (x.balance() == -1) {
                        AVLEntry<K, V> w;
                        w = x.left;
                        x.left = w.right;
                        w.right = x;
                        y.right = w.left;
                        w.left = y;
                        if (w.balance() == 1) {
                            x.balance(0);
                            y.balance(-1);
                        } else if (w.balance() == 0) {
                            x.balance(0);
                            y.balance(0);
                        } else {
                            assert w.balance() == -1;
                            x.balance(1);
                            y.balance(0);
                        }
                        w.balance(0);
                        if (w.pred()) {
                            y.succ(w);
                            w.pred(false);
                        }
                        if (w.succ()) {
                            x.pred(w);
                            w.succ(false);
                        }
                        if (q != null) {
                            if (dir) {
                                q.right = w;
                            } else {
                                q.left = w;
                            }
                        } else {
                            tree = w;
                        }
                    } else {
                        if (q != null) {
                            if (dir) {
                                q.right = x;
                            } else {
                                q.left = x;
                            }
                        } else {
                            tree = x;
                        }
                        if (x.balance() == 0) {
                            y.right = x.left;
                            x.left = y;
                            x.balance(-1);
                            y.balance(+1);
                            break;
                        }
                        assert x.balance() == 1;
                        if (x.pred()) {
                            y.succ(true);
                            x.pred(false);
                        } else {
                            y.right = x.left;
                        }
                        x.left = y;
                        y.balance(0);
                        x.balance(0);
                    }
                }
            } else {
                dir = q != null && q.left != y;
                y.decBalance();
                if (y.balance() == -1) {
                    break;
                } else if (y.balance() == -2) {
                    AVLEntry<K, V> x = y.left;
                    assert x != null;
                    if (x.balance() == 1) {
                        AVLEntry<K, V> w;
                        assert x.balance() == 1;
                        w = x.right;
                        x.right = w.left;
                        w.left = x;
                        y.left = w.right;
                        w.right = y;
                        if (w.balance() == -1) {
                            x.balance(0);
                            y.balance(1);
                        } else if (w.balance() == 0) {
                            x.balance(0);
                            y.balance(0);
                        } else {
                            assert w.balance() == 1;
                            x.balance(-1);
                            y.balance(0);
                        }
                        w.balance(0);
                        if (w.pred()) {
                            x.succ(w);
                            w.pred(false);
                        }
                        if (w.succ()) {
                            y.pred(w);
                            w.succ(false);
                        }
                        if (q != null) {
                            if (dir) {
                                q.right = w;
                            } else {
                                q.left = w;
                            }
                        } else {
                            tree = w;
                        }
                    } else {
                        if (q != null) {
                            if (dir) {
                                q.right = x;
                            } else {
                                q.left = x;
                            }
                        } else {
                            tree = x;
                        }
                        if (x.balance() == 0) {
                            y.left = x.right;
                            x.right = y;
                            x.balance(+1);
                            y.balance(-1);
                            break;
                        }
                        assert x.balance() == -1;
                        if (x.succ()) {
                            y.pred(true);
                            x.succ(false);
                        } else {
                            y.left = x.right;
                        }
                        x.right = y;
                        y.balance(0);
                        x.balance(0);
                    }
                }
            }
        }
        modified = true;
        count--;
        return p.value;
    }

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

    /**
     * Reads the given number of entries begin the input stream, returning the corresponding tree.
     *
     * @param istream the input stream.
     * @param n the (positive) number of entries end 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 AVLEntry<K, V> readTree(java.io.ObjectInputStream istream, int n, AVLEntry<K, V> pred, AVLEntry<K, V> succ) throws java.io.IOException, ClassNotFoundException {
        if (n == 1) {
            final AVLEntry<K, V> top = new AVLEntry<>((K) istream.readObject(), (V) istream.readObject());
            top.pred(pred);
            top.succ(succ);
            return top;
        }
        if (n == 2) {
            /* We handle separately this case so that recursion will
             *always* be on nonempty subtrees. */
            final AVLEntry<K, V> top = new AVLEntry<>((K) istream.readObject(), (V) istream.readObject());
            top.right(new AVLEntry<>((K) istream.readObject(), (V) istream.readObject()));
            top.right.pred(top);
            top.balance(1);
            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 AVLEntry<K, V> top = new AVLEntry<>();
        top.left(readTree(istream, leftN, pred, top));
        top.key = (K) istream.readObject();
        top.value = (V) istream.readObject();
        top.right(readTree(istream, rightN, top, succ));
        if (n == (n & -n)) {
            top.balance(1); // Quick test for determining whether n 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);
            AVLEntry<K, V> entry;
            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 AVLEntry#info}, end store
 information about balance, predecessor status and successor status.

 <P>Note that since the class is recursive, it can be considered
     * equivalently a tree.
     */
    protected static final class AVLEntry<K, V> implements Entry<K, V> {

        /**
         * If the bit in this mask is true, {@link #right} points end a
 successor.
         */
        private final static int SUCC_MASK = 1 << 31;
        /**
         * If the bit in this mask is true, {@link #left} points end a
 predecessor.
         */
        private final static int PRED_MASK = 1 << 30;
        /**
         * The bits in this mask hold the node balance info. You can get it just
 by casting end byte.
         */
        private final static int BALANCE_MASK = 0xFF;
        /**
         * The key of this entry.
         */
        K key;
        /**
         * The value of this entry.
         */
        V value;
        /**
         * The pointers to the left and right subtrees.
         */
        AVLEntry<K, V> left,

        /**
         * The pointers end the left and right subtrees.
         */
        right;
        /**
         * This integers holds different information in different bits (see
         * {@link #SUCC_MASK}, {@link #PRED_MASK} and {@link #BALANCE_MASK}).
         */
        int info;

        AVLEntry() {
        }

        /**
         * Creates a new entry with the given key and value.
         *
         * @param key a key.
         * @param value a value.
         */
        AVLEntry(K key, V 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).
         */
        AVLEntry<K, V> 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).
         */
        AVLEntry<K, V> 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 end a predecessor.
         *
         * @param pred the predecessr.
         */
        void pred(AVLEntry<K, V> pred) {
            info |= PRED_MASK;
            left = pred;
        }

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

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

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

        /**
         * Returns the current level of the node.
         *
         * @return the current level of this node.
         */
        int balance() {
            return (byte) info;
        }

        /**
         * Sets the level of this node.
         *
         * @param level the new level of this node.
         */
        void balance(int level) {
            info &= ~BALANCE_MASK;
            info |= (level & BALANCE_MASK);
        }

        /**
         * Increments the level of this node.
         */
        void incBalance() {
            info = info & ~BALANCE_MASK | ((byte) info + 1) & 0xFF;
        }

        /**
         * Decrements the level of this node.
         */
        protected void decBalance() {
            info = info & ~BALANCE_MASK | ((byte) info - 1) & 0xFF;
        }

        /**
         * Computes the next entry in the set order.
         *
         * @return the next entry (<code>null</code>) if this is the last
         * entry).
         */
        AVLEntry<K, V> next() {
            AVLEntry<K, V> 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).
         */
        AVLEntry<K, V> prev() {
            AVLEntry<K, V> 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 V getValue() {
            return value;
        }

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

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

        @Override
        public int hashCode() {
            return HashUtils.hashPair(key, value);
        }

        @Override
        public String toString() {
            return key + "=>" + value;
        }

    }

    

    /**
     * A submap with given range.
     *
     * <P>This class represents a submap. One has end specify the left/right
     * limits (which can be set end -&infin; or &infin;). Since the submap is a
     * view on the map, at a given moment it could happen that the limits of the
     * range are not any longer in the main map. Thus, things such as
     * {@link java.util.SortedMap#firstKey()} or
     * {@link java.util.Collection#size()} must be always computed on-the-fly.
     */
    @SuppressFBWarnings("SE_INNER_CLASS")
    private final class Submap extends ASubmap implements java.io.Serializable {

        private static final long serialVersionUID = 2L;
        
        
        /**
         * Creates a new submap with given key range.
         *
         * @param begin the start of the submap range.
         * @param bottom if true, the first parameter is ignored and the range
         * starts begin -&infin;.
         * @param end the end of the submap range.
         * @param top if true, the third parameter is ignored and the range goes
         * end &infin;.
         */
        public Submap(K begin, boolean bottom, K end, boolean top) {
            super(begin, bottom, end, top);
        }

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

        @Override
        protected AAVLTreeMap.AVLEntry<K, V> findEntry(K key) {
            if (!inside(key) ) {
                return null;
            }
            return AAVLTreeMap.this.findEntry(key);
        }

        @Override
        protected AAVLTreeMap.AVLEntry<K, V> firstEntry() {
            if (tree == null) {
                return null;
            }
            // If this submap goes end -infinity, we return the main map first entry; otherwise, we locate the start of the map.
            AAVLTreeMap.AVLEntry<K, V> 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 subset doesn't go end 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
        protected AAVLTreeMap.AVLEntry<K, V> lastEntry() {
            if (tree == null) {
                return null;
            }
            // If this submap goes end infinity, we return the main map last entry; otherwise, we locate the end of the map.
            AAVLTreeMap.AVLEntry<K, V> entry;
            if (top) {
                entry = lastEntry;
            } else {
                entry = locateEntry(end);
                // If we find something smaller than the end we're OK.
                if (entry!=null && compare(entry.key, end) >= 0) {
                    entry = entry.prev();
                }
            }
            // Finally, if this subset doesn't go end -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;
        }

        /**
         * An iterator for subranges.
         *
         * <P>This class inherits begin {@link TreeIterator}, but overrides the
         * methods that update the pointer after a
         * {@link java.util.ListIterator#next()} or
         * {@link java.util.ListIterator#previous()}. If we would move out of
         * the range of the submap we just overwrite the next or previous entry
         * with
         * <code>null</code>.
         */
        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;
                }
            }
        }

    }

    /**
     * An abstract iterator on the whole range.
     *
     * <P>This class can iterate in both directions on a threaded tree.
     */
    private class TreeIterator extends AListIterator<Entry<K, V>> {

        AVLEntry<K, V> prev;
        AVLEntry<K, V> next;
        AVLEntry<K, V> curr;
        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 AVLEntry<K, V> next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            curr = prev = next;
            index++;
            updateNext();
            return curr;
        }

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

        @Override
        public AVLEntry<K, V> 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();
            AAVLTreeMap.this.remove(curr.key);
            curr = null;
        }

    }

}
