Request for NavigableMap instead of SortedMap about jdbm3 HOT 12 CLOSED

public interface BaseMap<K, V>
{
//modifications
public void clear();
public V put(K key, V value);
public void deleteEntry(Entry<K, V> e);

//views
public int size();
public Comparator<? super K> comparator();

//Search for entries all these method should return null if entry does not exist
public Entry<K, V> getFirstEntry();
public Entry<K, V> getLastEntry();

public Entry<K, V> getEntry(Object key);
public Entry<K, V> getFloorEntry(K key);
public Entry<K, V> getCeilingEntry(K key);
public Entry<K, V> getHigherEntry(K key);
public Entry<K, V> getLowerEntry(K key);

//Navigation should return null if there is no next/previous entry 
public Entry<K, V> getNext(Entry<K, V> entry);
public Entry<K, V> getPrev(Entry<K, V> entry);
}

package net.kotek.jdbm;

import java.io.IOError;
import java.io.IOException;
import java.util.Comparator;
import java.util.Map.Entry;

public class BTreeBaseMap<K, V> implements BaseMap<K, V>
{
    private final BTree<K, V> btree;
    private final boolean readonly;

    public BTreeBaseMap(BTree<K, V> btree, boolean readonly)
    {
        this.btree = btree;
        this.readonly = readonly;
    }

    @Override
    public void clear()
    {
        if(readonly) throw new UnsupportedOperationException("readonly");
        throw new UnsupportedOperationException("Not implemented yet");
        // TODO Auto-generated method stub
        // btree.getLock().writeLock().lock();
        // btree.getLock().writeLock().unlock();
    }

    @Override
    public V put(K key, V value)
    {
        if(readonly) throw new UnsupportedOperationException("readonly");
        try
        {
            return btree.insert(key, value, true);
        }
        catch(IOException e)
        {
            throw new IOError(e);
        }
    }

    @Override
    public void deleteEntry(Entry<K, V> e)
    {
        if(readonly) throw new UnsupportedOperationException("readonly");
        try
        {
            btree.remove(e.getKey());
        }
        catch(IOException ex)
        {
            throw new IOError(ex);
        }
    }

    @Override
    public int size()
    {
        return btree.size();
    }

    @Override
    public Comparator<? super K> comparator()
    {
        return btree.getComparator();
    }

    @Override
    public Entry<K, V> getFirstEntry()
    {

        try
        {
            btree.getLock().readLock().lock();
            return findFirst(btree.getRoot());
        }
        catch(IOException e)
        {
            throw new IOError(e);
        }
        finally
        {
            btree.getLock().readLock().unlock();
        }
    }

    @Override
    public Entry<K, V> getLastEntry()
    {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public Entry<K, V> getEntry(Object key)
    {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public Entry<K, V> getFloorEntry(K key)
    {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public Entry<K, V> getCeilingEntry(K key)
    {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public Entry<K, V> getHigherEntry(K key)
    {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public Entry<K, V> getLowerEntry(K key)
    {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public Entry<K, V> getNext(Entry<K, V> entry)
    {
        try
        {
            return ((BTreeEntry) entry).getNext();
        }
        catch(IOException e)
        {
            throw new IOError(e);
        }
    }

    @Override
    public Entry<K, V> getPrev(Entry<K, V> entry)
    {
        try
        {
            return ((BTreeEntry) entry).getPrev();
        }
        catch(IOException e)
        {
            throw new IOError(e);
        }
    }

    private BTreeEntry findFirst(BTreeNode<K, V> node) throws IOException
    {
        if(node._isLeaf){ return new BTreeEntry(node, node._first); }
        BTreeNode<K, V> child = node.loadNode(node._children[node._first]);
        return findFirst(child);
    }

    private final class BTreeEntry implements Entry<K, V>
    {
        private final BTreeNode<K, V> _node;
        private final byte _index;
        private final int expectedModCount;
        private final K key;
        private final V value;

        @SuppressWarnings("unchecked")
        public BTreeEntry(BTreeNode<K, V> _node, byte _index)
        {
            this.expectedModCount = btree.modCount;
            this._node = _node;
            this._index = _index;
            this.key = _node._keys[_index];
            if(_node._values[_index] instanceof BTreeLazyRecord) value =
                                ((BTreeLazyRecord<V>) _node._values[_index]).get();
            else value = (V) _node._values[_index];
        }

        public Entry<K, V> getNext() throws IOException
        {
            if(expectedModCount != btree.modCount){ return getHigherEntry(key); }
            byte nextIndex = _index;
            BTreeNode<K, V> nextNode = _node;
            ++nextIndex;
            if(nextIndex < BTree.DEFAULT_SIZE)
            {
                if(_node._keys[nextIndex] == null)
                {
                    // reached end of the tree.
                    return null;
                }
            }
            else if(_node._next != 0)
            {
                // move to next node
                nextNode = _node.loadNode(_node._next);
                nextIndex = _node._first;
            }
            return new BTreeEntry(nextNode, nextIndex);
        }

        public Entry<K, V> getPrev() throws IOException
        {
            if(expectedModCount != btree.modCount){ return getLowerEntry(key); }
            byte prevIndex = _index;
            BTreeNode<K, V> prevNode = _node;
            --prevIndex;
            if(prevIndex < _node._first)
            {
                if(_node._previous != 0)
                {
                    prevNode = _node.loadNode(_node._previous);
                    prevIndex = BTree.DEFAULT_SIZE;
                }
                else
                {
                    return null;
                }
            }
            return new BTreeEntry(prevNode, prevIndex);
        }

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

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

        @Override
        public V setValue(V value)
        {
            throw new UnsupportedOperationException("Entries are readonly");
        }

    }

}

package net.kotek.jdbm;

import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NavigableMap;
import java.util.NavigableSet;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;

public class NavMap<K, V> extends AbstractMap<K, V> implements
        NavigableMap<K, V>
{
    private final BaseMap<K, V> baseMap;
    private int modCount;
    private EntrySet entrySet;
    private KeySet<K> navigableKeySet;
    private NavigableMap<K, V> descendingMap;

    public NavMap(BaseMap<K, V> baseMap)
    {
        super();
        this.baseMap = baseMap;
        this.modCount = 0;
        this.entrySet = null;
        this.navigableKeySet = null;
        this.descendingMap = null;
    }

    public V put(K key, V value)
    {
        ++modCount;
        return baseMap.put(key, value);
    }

    public void clear()
    {
        ++modCount;
        baseMap.clear();
    }

    public void deleteEntry(Entry<K, V> e)
    {
        ++modCount;
        baseMap.deleteEntry(e);
    }

    public int size()
    {
        return baseMap.size();
    }

    public Comparator<? super K> comparator()
    {
        return baseMap.comparator();
    }

    public boolean containsKey(Object key)
    {
        return baseMap.getEntry(key) != null;
    }

    public boolean containsValue(Object value)
    {
        Iterator<Entry<K, V>> it = getForwardIteratorFromStart();
        while(it.hasNext())
        {
            Entry<K, V> e = it.next();
            if(valEquals(value, e.getValue())) return true;
        }
        return false;
    }

    public V get(Object key)
    {
        Entry<K, V> e = baseMap.getEntry(key);
        return (e == null ? null : e.getValue());
    }

    public K firstKey()
    {
        return key(baseMap.getFirstEntry());
    }

    public K lastKey()
    {
        return key(baseMap.getLastEntry());
    }

    public V remove(Object key)
    {
        Entry<K, V> e = baseMap.getEntry(key);
        if(e == null) return null;
        V oldValue = e.getValue();
        deleteEntry(e);
        return oldValue;
    }

    public Entry<K, V> firstEntry()
    {
        return baseMap.getFirstEntry();
    }

    public Entry<K, V> lastEntry()
    {
        return baseMap.getLastEntry();
    }

    public Entry<K, V> pollFirstEntry()
    {
        Entry<K, V> e = baseMap.getFirstEntry();
        if(e == null) return null;
        Entry<K, V> res = copyEntry(e);
        deleteEntry(e);
        return res;
    }

    public Entry<K, V> pollLastEntry()
    {
        Entry<K, V> e = baseMap.getLastEntry();
        if(e == null) return null;
        Entry<K, V> res = copyEntry(e);
        deleteEntry(e);
        return res;
    }

    public Entry<K, V> lowerEntry(K key)
    {
        return baseMap.getLowerEntry(key);
    }

    public K lowerKey(K key)
    {
        return keyOrNull(baseMap.getLowerEntry(key));
    }

    public Entry<K, V> floorEntry(K key)
    {
        return baseMap.getFloorEntry(key);
    }

    public K floorKey(K key)
    {
        return keyOrNull(baseMap.getFloorEntry(key));
    }

    public Entry<K, V> ceilingEntry(K key)
    {
        return baseMap.getCeilingEntry(key);
    }

    public K ceilingKey(K key)
    {
        return keyOrNull(baseMap.getCeilingEntry(key));
    }

    public Entry<K, V> higherEntry(K key)
    {
        return baseMap.getHigherEntry(key);
    }

    public K higherKey(K key)
    {
        return keyOrNull(baseMap.getHigherEntry(key));
    }

    public Set<K> keySet()
    {
        return navigableKeySet();
    }

    @SuppressWarnings({ "unchecked", "rawtypes" })
    public NavigableSet<K> navigableKeySet()
    {
        KeySet<K> nks = navigableKeySet;
        return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
    }

    public NavigableSet<K> descendingKeySet()
    {
        return descendingMap().navigableKeySet();
    }

    public Set<Entry<K, V>> entrySet()
    {
        EntrySet es = entrySet;
        return (es != null) ? es : (entrySet = new EntrySet());
    }

    public NavigableMap<K, V> descendingMap()
    {
        NavigableMap<K, V> km = descendingMap;
        return (km != null) ? km
                : (descendingMap = new DescendingSubMap(true,
                                                        null,
                                                        true,
                                                        true,
                                                        null,
                                                        true));
    }

    public NavigableMap<K, V> subMap(   K fromKey,
                                        boolean fromInclusive,
                                        K toKey,
                                        boolean toInclusive)
    {
        return new AscendingSubMap( false,
                                    fromKey,
                                    fromInclusive,
                                    false,
                                    toKey,
                                    toInclusive);
    }

    public NavigableMap<K, V> headMap(K toKey, boolean inclusive)
    {
        return new AscendingSubMap(true, null, true, false, toKey, inclusive);
    }

    public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive)
    {
        return new AscendingSubMap(false, fromKey, inclusive, true, null, true);
    }

    public SortedMap<K, V> subMap(K fromKey, K toKey)
    {
        return subMap(fromKey, true, toKey, false);
    }

    public SortedMap<K, V> headMap(K toKey)
    {
        return headMap(toKey, false);
    }

    public SortedMap<K, V> tailMap(K fromKey)
    {
        return tailMap(fromKey, true);
    }

    // View class support

    class Values extends AbstractCollection<V>
    {
        public Iterator<V> iterator()
        {
            return new ValueIterator(getForwardIteratorFromStart());
        }

        public int size()
        {
            return baseMap.size();
        }

        public boolean contains(Object o)
        {
            return NavMap.this.containsValue(o);
        }

        public boolean remove(Object o)
        {
            Iterator<Entry<K, V>> it = getForwardIteratorFromStart();
            while(it.hasNext())
            {
                Entry<K, V> e = it.next();
                if(valEquals(e.getValue(), o))
                {
                    baseMap.deleteEntry(e);
                    return true;
                }
            }
            return false;
        }

        public void clear()
        {
            baseMap.clear();
        }
    }

    class EntrySet extends AbstractSet<Entry<K, V>>
    {
        public Iterator<Entry<K, V>> iterator()
        {
            return getForwardIteratorFromStart();
        }

        public boolean contains(Object o)
        {
            if(!(o instanceof Entry)) return false;
            @SuppressWarnings("unchecked")
            Entry<K, V> entry = (Entry<K, V>) o;
            if(entry.getKey() == null) return false;
            V value = entry.getValue();
            Entry<K, V> e = baseMap.getEntry(entry.getKey());
            return e != null && valEquals(e.getValue(), value);
        }

        public boolean remove(Object o)
        {
            if(!(o instanceof Entry)) return false;
            @SuppressWarnings("unchecked")
            Entry<K, V> entry = (Entry<K, V>) o;
            V value = entry.getValue();
            Entry<K, V> e = baseMap.getEntry(entry.getKey());
            if(e != null && valEquals(e.getValue(), value))
            {
                deleteEntry(e);
                return true;
            }
            return false;
        }

        public int size()
        {
            return baseMap.size();
        }

        public void clear()
        {
            baseMap.clear();
        }
    }

    Iterator<K> keyIterator()
    {
        return new KeyIterator(getForwardIteratorFromStart());
    }

    Iterator<K> descendingKeyIterator()
    {
        return new KeyIterator(getBackwardIteratorFromEnd());
    }


    //Also used by submaps. Therefore static.
    static final class KeySet<K> extends AbstractSet<K> implements
            NavigableSet<K>
    {
        private final NavigableMap<K, Object> m;

        KeySet(NavigableMap<K, Object> map)
        {
            m = map;
        }

        @SuppressWarnings({ "unchecked", "rawtypes" })
        public Iterator<K> iterator()
        {
            if(m instanceof NavMap) return (Iterator<K>) ((NavMap) m).keyIterator();
            else return (Iterator<K>) (((NavMap.NavigableSubMap) m).keyIterator());
        }

        @SuppressWarnings({ "unchecked", "rawtypes" })
        public Iterator<K> descendingIterator()
        {
            if(m instanceof NavMap) return ((NavMap<K, Object>) m).descendingKeyIterator();
            else return (Iterator<K>) (((NavMap.NavigableSubMap) m).descendingKeyIterator());
        }

        public int size()
        {
            return m.size();
        }

        public boolean isEmpty()
        {
            return m.isEmpty();
        }

        public boolean contains(Object o)
        {
            return m.containsKey(o);
        }

        public void clear()
        {
            m.clear();
        }

        public K lower(K e)
        {
            return m.lowerKey(e);
        }

        public K floor(K e)
        {
            return m.floorKey(e);
        }

        public K ceiling(K e)
        {
            return m.ceilingKey(e);
        }

        public K higher(K e)
        {
            return m.higherKey(e);
        }

        public K first()
        {
            return m.firstKey();
        }

        public K last()
        {
            return m.lastKey();
        }

        public Comparator<? super K> comparator()
        {
            return m.comparator();
        }

        public K pollFirst()
        {
            Entry<K, Object> e = m.pollFirstEntry();
            return (e == null) ? null : e.getKey();
        }

        public K pollLast()
        {
            Entry<K, Object> e = m.pollLastEntry();
            return (e == null) ? null : e.getKey();
        }

        public boolean remove(Object o)
        {
            int oldSize = size();
            m.remove(o);
            return size() != oldSize;
        }

        public NavigableSet<K> subSet(  K fromElement,
                                        boolean fromInclusive,
                                        K toElement,
                                        boolean toInclusive)
        {
            return new KeySet<>(m.subMap(   fromElement,
                                            fromInclusive,
                                            toElement,
                                            toInclusive));
        }

        public NavigableSet<K> headSet(K toElement, boolean inclusive)
        {
            return new KeySet<>(m.headMap(toElement, inclusive));
        }

        public NavigableSet<K> tailSet(K fromElement, boolean inclusive)
        {
            return new KeySet<>(m.tailMap(fromElement, inclusive));
        }

        public SortedSet<K> subSet(K fromElement, K toElement)
        {
            return subSet(fromElement, true, toElement, false);
        }

        public SortedSet<K> headSet(K toElement)
        {
            return headSet(toElement, false);
        }

        public SortedSet<K> tailSet(K fromElement)
        {
            return tailSet(fromElement, true);
        }

        @SuppressWarnings({ "unchecked", "rawtypes" })
        public NavigableSet<K> descendingSet()
        {
            return new KeySet(m.descendingMap());
        }
    }

    public Iterator<Entry<K, V>> getForwardIteratorFromStart()
    {
        return new ForwardIterator(baseMap.getFirstEntry());
    }

    public Iterator<Entry<K, V>> getForwardIteratorFrom(K key, boolean inclusive)
    {
        Entry<K, V> start = inclusive ? baseMap.getCeilingEntry(key)
                : baseMap.getHigherEntry(key);
        return new ForwardIterator(start);
    }

    public Iterator<Entry<K, V>> getBackwardIteratorFromEnd()
    {
        return new BackwardIterator(baseMap.getLastEntry());
    }

    public Iterator<Entry<K, V>> getBackwardIteratorFrom(   K key,
                                                            boolean inclusive)
    {
        Entry<K, V> start = inclusive ? baseMap.getFloorEntry(key)
                : baseMap.getLowerEntry(key);
        return new BackwardIterator(start);
    }

    private abstract class EntryIterator implements Iterator<Entry<K, V>>
    {
        private Entry<K, V> next;
        private Entry<K, V> lastReturned;

        public EntryIterator(Entry<K, V> start)
        {
            this.next = start;
            this.lastReturned = null;
        }

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

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

        @Override
        public void remove()
        {
            if(lastReturned == null) throw new IllegalStateException();
            deleteEntry(lastReturned);
        }

        public abstract Entry<K, V> getNextEntry(Entry<K, V> current);
    }

    private class ForwardIterator extends EntryIterator
    {
        public ForwardIterator(Entry<K, V> start)
        {
            super(start);
        }

        @Override
        public Entry<K, V> getNextEntry(Entry<K, V> current)
        {
            return baseMap.getNext(current);
        }
    }

    private class BackwardIterator extends EntryIterator
    {
        public BackwardIterator(Entry<K, V> start)
        {
            super(start);
        }

        @Override
        public Entry<K, V> getNextEntry(Entry<K, V> current)
        {
            return baseMap.getPrev(current);
        }
    }

    abstract class PrivateEntryIterator<T> implements Iterator<T>
    {
        private final Iterator<Entry<K, V>> it;

        public PrivateEntryIterator(Iterator<Entry<K, V>> it)
        {
            this.it = it;
        }

        @Override
        public boolean hasNext()
        {
            return it.hasNext();
        }

        @Override
        public void remove()
        {
            it.remove();
        }

        public Entry<K, V> nextEntry()
        {
            return it.next();
        }

    }

    final class ValueIterator extends PrivateEntryIterator<V>
    {
        ValueIterator(Iterator<Entry<K, V>> it)
        {
            super(it);
        }

        public V next()
        {
            return nextEntry().getValue();
        }
    }

    final class KeyIterator extends PrivateEntryIterator<K>
    {
        KeyIterator(Iterator<Entry<K, V>> it)
        {
            super(it);
        }

        public K next()
        {
            return nextEntry().getKey();
        }
    }

    @SuppressWarnings("unchecked")
    private int compare(Object k1, Object k2)
    {
        Comparator<? super K> comparator = baseMap.comparator();
        return comparator == null ? ((Comparable<? super K>) k1).compareTo((K) k2)
                : comparator.compare((K) k1, (K) k2);
    }

    private static final boolean valEquals(Object o1, Object o2)
    {
        return (o1 == null ? o2 == null : o1.equals(o2));
    }

    private static <K, V> Entry<K, V> copyEntry(Entry<K, V> e)
    {
        return (e == null) ? null : new AbstractMap.SimpleImmutableEntry<>(e);
    }

    private static <K, V> K keyOrNull(Entry<K, V> e)
    {
        return (e == null) ? null : e.getKey();
    }

    private static <K> K key(Entry<K, ?> e)
    {
        if(e == null) throw new NoSuchElementException();
        return e.getKey();
    }

    // SubMaps

    private static final Object UNBOUNDED = new Object();

    abstract class NavigableSubMap extends AbstractMap<K, V> implements
            NavigableMap<K, V>
    {
        protected final K lo, hi;
        protected final boolean fromStart, toEnd;
        protected final boolean loInclusive, hiInclusive;
        protected NavigableMap<K, V> descendingMapView = null;
        protected EntrySetView entrySetView = null;
        protected KeySet<K> navigableKeySetView = null;

        NavigableSubMap(boolean fromStart,
                        K lo,
                        boolean loInclusive,
                        boolean toEnd,
                        K hi,
                        boolean hiInclusive)
        {
            if(!fromStart && !toEnd)
            {
                if(compare(lo, hi) > 0) throw new IllegalArgumentException("fromKey > toKey");
            }
            else
            {
                if(!fromStart) // type check
                compare(lo, lo);
                if(!toEnd) compare(hi, hi);
            }

            this.fromStart = fromStart;
            this.lo = lo;
            this.loInclusive = loInclusive;
            this.toEnd = toEnd;
            this.hi = hi;
            this.hiInclusive = hiInclusive;
        }


        private final boolean tooLow(Object key)
        {
            if(!fromStart)
            {
                int c = compare(key, lo);
                if(c < 0 || (c == 0 && !loInclusive)) return true;
            }
            return false;
        }

        private final boolean tooHigh(Object key)
        {
            if(!toEnd)
            {
                int c = compare(key, hi);
                if(c > 0 || (c == 0 && !hiInclusive)) return true;
            }
            return false;
        }

        private final boolean inRange(Object key)
        {
            return !tooLow(key) && !tooHigh(key);
        }

        private final boolean inClosedRange(Object key)
        {
            return (fromStart || compare(key, lo) >= 0)
                    && (toEnd || compare(hi, key) >= 0);
        }

        protected final boolean inRange(Object key, boolean inclusive)
        {
            return inclusive ? inRange(key) : inClosedRange(key);
        }

        protected final Iterator<Entry<K, V>> absForward()
        {
            if(fromStart) return getForwardIteratorFromStart();
            return getForwardIteratorFrom(lo, loInclusive);
        }

        protected final Iterator<Entry<K, V>> absBackward()
        {
            if(toEnd) return getBackwardIteratorFromEnd();
            return getBackwardIteratorFrom(hi, hiInclusive);
        }

        protected final Entry<K, V> absLowest()
        {
            Entry<K, V> e = (fromStart ? baseMap.getFirstEntry()
                    : (loInclusive ? baseMap.getCeilingEntry(lo)
                            : baseMap.getHigherEntry(lo)));
            return (e == null || tooHigh(e.getKey())) ? null : e;
        }

        protected final Entry<K, V> absHighest()
        {
            Entry<K, V> e = (toEnd ? baseMap.getLastEntry()
                    : (hiInclusive ? baseMap.getFloorEntry(hi)
                            : baseMap.getLowerEntry(hi)));
            return (e == null || tooLow(e.getKey())) ? null : e;
        }

        protected final Entry<K, V> absCeiling(K key)
        {
            if(tooLow(key)) return absLowest();
            Entry<K, V> e = baseMap.getCeilingEntry(key);
            return (e == null || tooHigh(e.getKey())) ? null : e;
        }

        protected final Entry<K, V> absHigher(K key)
        {
            if(tooLow(key)) return absLowest();
            Entry<K, V> e = baseMap.getHigherEntry(key);
            return (e == null || tooHigh(e.getKey())) ? null : e;
        }

        protected final Entry<K, V> absFloor(K key)
        {
            if(tooHigh(key)) return absHighest();
            Entry<K, V> e = baseMap.getFloorEntry(key);
            return (e == null || tooLow(e.getKey())) ? null : e;
        }

        protected final Entry<K, V> absLower(K key)
        {
            if(tooHigh(key)) return absHighest();
            Entry<K, V> e = baseMap.getLowerEntry(key);
            return (e == null || tooLow(e.getKey())) ? null : e;
        }

        /** Returns the absolute high fence for ascending traversal */
        protected final Entry<K, V> absHighFence()
        {
            return (toEnd ? null : (hiInclusive ? baseMap.getHigherEntry(hi)
                    : baseMap.getCeilingEntry(hi)));
        }

        /** Return the absolute low fence for descending traversal */
        protected final Entry<K, V> absLowFence()
        {
            return (fromStart ? null : (loInclusive ? baseMap.getLowerEntry(lo)
                    : baseMap.getFloorEntry(lo)));
        }

        // Abstract methods defined in ascending vs descending classes
        // These relay to the appropriate absolute versions

        abstract Entry<K, V> subLowest();

        abstract Entry<K, V> subHighest();

        abstract Entry<K, V> subCeiling(K key);

        abstract Entry<K, V> subHigher(K key);

        abstract Entry<K, V> subFloor(K key);

        abstract Entry<K, V> subLower(K key);

        /** Returns ascending iterator from the perspective of this submap */
        abstract Iterator<K> keyIterator();

        /** Returns descending iterator from the perspective of this submap */
        abstract Iterator<K> descendingKeyIterator();

        // public methods

        public boolean isEmpty()
        {
            return (fromStart && toEnd) ? NavMap.this.isEmpty()
                    : entrySet().isEmpty();
        }

        public int size()
        {
            return (fromStart && toEnd) ? baseMap.size() : entrySet().size();
        }

        public final boolean containsKey(Object key)
        {
            return inRange(key) && NavMap.this.containsKey(key);
        }

        public final V put(K key, V value)
        {
            if(!inRange(key)) throw new IllegalArgumentException("key out of range");
            return NavMap.this.put(key, value);
        }

        public final V get(Object key)
        {
            return !inRange(key) ? null : NavMap.this.get(key);
        }

        public final V remove(Object key)
        {
            return !inRange(key) ? null : NavMap.this.remove(key);
        }

        public final Entry<K, V> ceilingEntry(K key)
        {
            return subCeiling(key);
        }

        public final K ceilingKey(K key)
        {
            return keyOrNull(subCeiling(key));
        }

        public final Entry<K, V> higherEntry(K key)
        {
            return subHigher(key);
        }

        public final K higherKey(K key)
        {
            return keyOrNull(subHigher(key));
        }

        public final Entry<K, V> floorEntry(K key)
        {
            return subFloor(key);
        }

        public final K floorKey(K key)
        {
            return keyOrNull(subFloor(key));
        }

        public final Entry<K, V> lowerEntry(K key)
        {
            return subLower(key);
        }

        public final K lowerKey(K key)
        {
            return keyOrNull(subLower(key));
        }

        public final K firstKey()
        {
            return key(subLowest());
        }

        public final K lastKey()
        {
            return key(subHighest());
        }

        public final Entry<K, V> firstEntry()
        {
            return subLowest();
        }

        public final Entry<K, V> lastEntry()
        {
            return subHighest();
        }

        public final Entry<K, V> pollFirstEntry()
        {
            Entry<K, V> e = subLowest();
            if(e == null) return null;
            Entry<K, V> res = copyEntry(e);
            NavMap.this.deleteEntry(e);
            return res;
        }

        public final Entry<K, V> pollLastEntry()
        {
            Entry<K, V> e = subHighest();
            if(e == null) return null;
            Entry<K, V> res = copyEntry(e);
            NavMap.this.deleteEntry(e);
            return res;
        }

        @SuppressWarnings({ "rawtypes", "unchecked" })
        public final NavigableSet<K> navigableKeySet()
        {
            KeySet<K> nksv = navigableKeySetView;
            return (nksv != null) ? nksv
                    : (navigableKeySetView = new NavMap.KeySet(this));
        }

        public final Set<K> keySet()
        {
            return navigableKeySet();
        }

        public NavigableSet<K> descendingKeySet()
        {
            return descendingMap().navigableKeySet();
        }

        public final SortedMap<K, V> subMap(K fromKey, K toKey)
        {
            return subMap(fromKey, true, toKey, false);
        }

        public final SortedMap<K, V> headMap(K toKey)
        {
            return headMap(toKey, false);
        }

        public final SortedMap<K, V> tailMap(K fromKey)
        {
            return tailMap(fromKey, true);
        }

        abstract class EntrySetView extends AbstractSet<Entry<K, V>>
        {
            private transient int size = -1, sizeModCount;

            public int size()
            {
                if(fromStart && toEnd) return NavMap.this.size();
                if(size == -1 || sizeModCount != NavMap.this.modCount)
                {
                    sizeModCount = NavMap.this.modCount;
                    size = 0;
                    Iterator<Entry<K, V>> i = iterator();
                    while(i.hasNext())
                    {
                        size++;
                        i.next();
                    }
                }
                return size;
            }

            public boolean isEmpty()
            {
                Entry<K, V> n = absLowest();
                return n == null || tooHigh(n.getKey());
            }

            public boolean contains(Object o)
            {
                if(!(o instanceof Entry)) return false;
                @SuppressWarnings("unchecked")
                Entry<K, V> entry = (Entry<K, V>) o;
                K key = entry.getKey();
                if(!inRange(key)) return false;
                Entry<K, V> e = baseMap.getEntry(key);
                return e != null && valEquals(e.getValue(), entry.getValue());
            }

            public boolean remove(Object o)
            {
                if(!(o instanceof Entry)) return false;
                @SuppressWarnings("unchecked")
                Entry<K, V> entry = (Entry<K, V>) o;
                K key = entry.getKey();
                if(!inRange(key)) return false;
                Entry<K, V> e = baseMap.getEntry(key);
                if(e != null && valEquals(e.getValue(), entry.getValue()))
                {
                    NavMap.this.deleteEntry(e);
                    return true;
                }
                return false;
            }
        }

        abstract class SubMapIterator<T> implements Iterator<T>
        {
            Iterator<Entry<K, V>> it;
            Entry<K, V> lastReturned;
            Entry<K, V> next;
            final Object fenceKey;
            int expectedModCount;

            SubMapIterator(Iterator<Entry<K, V>> it, Entry<K, V> fence)
            {
                this.it = it;
                fenceKey = (fence == null) ? UNBOUNDED : fence.getKey();
                expectedModCount = NavMap.this.modCount;
                lastReturned = null;
                next = null;
                if(it.hasNext())
                {
                    next = it.next();
                }
            }

            public final boolean hasNext()
            {
                return next != null && next.getKey() != fenceKey;
            }

            final Entry<K, V> nextEntry()
            {
                Entry<K, V> e = next;
                if(e == null || e.getKey() == fenceKey) throw new NoSuchElementException();
                if(NavMap.this.modCount != expectedModCount) throw new ConcurrentModificationException();
                if(it.hasNext())
                {
                    next = it.next();
                }
                else
                {
                    next = null;
                }
                lastReturned = e;
                return e;
            }

            public final void remove()
            {
                if(lastReturned == null) throw new IllegalStateException();
                if(NavMap.this.modCount != expectedModCount) throw new ConcurrentModificationException();
                NavMap.this.deleteEntry(lastReturned);
                lastReturned = null;
                expectedModCount = NavMap.this.modCount;
            }
        }

        final class SubMapEntryIterator extends SubMapIterator<Entry<K, V>>
        {
            SubMapEntryIterator(Iterator<Entry<K, V>> it, Entry<K, V> fence)
            {
                super(it, fence);
            }

            public Entry<K, V> next()
            {
                return nextEntry();
            }
        }

        final class SubMapKeyIterator extends SubMapIterator<K>
        {
            SubMapKeyIterator(Iterator<Entry<K, V>> it, Entry<K, V> fence)
            {
                super(it, fence);
            }

            public K next()
            {
                return nextEntry().getKey();
            }
        }
    }

    final class AscendingSubMap extends NavigableSubMap
    {
        AscendingSubMap(boolean fromStart,
                        K lo,
                        boolean loInclusive,
                        boolean toEnd,
                        K hi,
                        boolean hiInclusive)
        {
            super(fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
        }

        public Comparator<? super K> comparator()
        {
            return baseMap.comparator();
        }

        public NavigableMap<K, V> subMap(   K fromKey,
                                            boolean fromInclusive,
                                            K toKey,
                                            boolean toInclusive)
        {
            if(!inRange(fromKey, fromInclusive)) throw new IllegalArgumentException("fromKey out of range");
            if(!inRange(toKey, toInclusive)) throw new IllegalArgumentException("toKey out of range");
            return new AscendingSubMap( false,
                                        fromKey,
                                        fromInclusive,
                                        false,
                                        toKey,
                                        toInclusive);
        }

        public NavigableMap<K, V> headMap(K toKey, boolean inclusive)
        {
            if(!inRange(toKey, inclusive)) throw new IllegalArgumentException("toKey out of range");
            return new AscendingSubMap( fromStart,
                                        lo,
                                        loInclusive,
                                        false,
                                        toKey,
                                        inclusive);
        }

        public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive)
        {
            if(!inRange(fromKey, inclusive)) throw new IllegalArgumentException("fromKey out of range");
            return new AscendingSubMap( false,
                                        fromKey,
                                        inclusive,
                                        toEnd,
                                        hi,
                                        hiInclusive);
        }

        public NavigableMap<K, V> descendingMap()
        {
            NavigableMap<K, V> mv = descendingMapView;
            return (mv != null) ? mv
                    : (descendingMapView = new DescendingSubMap(fromStart,
                                                                lo,
                                                                loInclusive,
                                                                toEnd,
                                                                hi,
                                                                hiInclusive));
        }

        Iterator<K> keyIterator()
        {
            return new SubMapKeyIterator(absForward(), absHighFence());
        }

        Iterator<K> descendingKeyIterator()
        {
            return new SubMapKeyIterator(absBackward(), absLowFence());
        }

        final class AscendingEntrySetView extends EntrySetView
        {
            public Iterator<Entry<K, V>> iterator()
            {
                return new SubMapEntryIterator(absForward(), absHighFence());
            }
        }

        public Set<Entry<K, V>> entrySet()
        {
            EntrySetView es = entrySetView;
            return (es != null) ? es : new AscendingEntrySetView();
        }

        Entry<K, V> subLowest()
        {
            return absLowest();
        }

        Entry<K, V> subHighest()
        {
            return absHighest();
        }

        Entry<K, V> subCeiling(K key)
        {
            return absCeiling(key);
        }

        Entry<K, V> subHigher(K key)
        {
            return absHigher(key);
        }

        Entry<K, V> subFloor(K key)
        {
            return absFloor(key);
        }

        Entry<K, V> subLower(K key)
        {
            return absLower(key);
        }
    }

    /**
     * @serial include
     */
    final class DescendingSubMap extends NavigableSubMap
    {
        DescendingSubMap(   boolean fromStart,
                            K lo,
                            boolean loInclusive,
                            boolean toEnd,
                            K hi,
                            boolean hiInclusive)
        {
            super(fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
        }

        private final Comparator<? super K> reverseComparator = Collections.reverseOrder(baseMap.comparator());

        public Comparator<? super K> comparator()
        {
            return reverseComparator;
        }

        public NavigableMap<K, V> subMap(   K fromKey,
                                            boolean fromInclusive,
                                            K toKey,
                                            boolean toInclusive)
        {
            if(!inRange(fromKey, fromInclusive)) throw new IllegalArgumentException("fromKey out of range");
            if(!inRange(toKey, toInclusive)) throw new IllegalArgumentException("toKey out of range");
            return new DescendingSubMap(false,
                                        toKey,
                                        toInclusive,
                                        false,
                                        fromKey,
                                        fromInclusive);
        }

        public NavigableMap<K, V> headMap(K toKey, boolean inclusive)
        {
            if(!inRange(toKey, inclusive)) throw new IllegalArgumentException("toKey out of range");
            return new DescendingSubMap(false,
                                        toKey,
                                        inclusive,
                                        toEnd,
                                        hi,
                                        hiInclusive);
        }

        public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive)
        {
            if(!inRange(fromKey, inclusive)) throw new IllegalArgumentException("fromKey out of range");
            return new DescendingSubMap(fromStart,
                                        lo,
                                        loInclusive,
                                        false,
                                        fromKey,
                                        inclusive);
        }

        public NavigableMap<K, V> descendingMap()
        {
            NavigableMap<K, V> mv = descendingMapView;
            return (mv != null) ? mv
                    : (descendingMapView = new AscendingSubMap( fromStart,
                                                                lo,
                                                                loInclusive,
                                                                toEnd,
                                                                hi,
                                                                hiInclusive));
        }

        Iterator<K> keyIterator()
        {
            return new SubMapKeyIterator(absBackward(), absLowFence());
        }

        Iterator<K> descendingKeyIterator()
        {
            return new SubMapKeyIterator(absForward(), absHighFence());
        }

        final class DescendingEntrySetView extends EntrySetView
        {
            public Iterator<Entry<K, V>> iterator()
            {
                return new SubMapEntryIterator(absBackward(), absLowFence());
            }
        }

        public Set<Entry<K, V>> entrySet()
        {
            EntrySetView es = entrySetView;
            return (es != null) ? es : new DescendingEntrySetView();
        }

        Entry<K, V> subLowest()
        {
            return absHighest();
        }

        Entry<K, V> subHighest()
        {
            return absLowest();
        }

        Entry<K, V> subCeiling(K key)
        {
            return absFloor(key);
        }

        Entry<K, V> subHigher(K key)
        {
            return absLower(key);
        }

        Entry<K, V> subFloor(K key)
        {
            return absCeiling(key);
        }

        Entry<K, V> subLower(K key)
        {
            return absHigher(key);
        }
    }
}