Request for NavigableMap instead of SortedMap

[tgrundtvig]

Hi there,
Would it be possible to get a NavigableMap interface to the TreeMaps instead of the SortedMap interface?
We are writing a thesis about data modelling in java and we are considering using JDBM3 for caching the data. The problem is that we need the added functionality of the NavigableMap interface, especially the subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) method, where we can choose wether or not the intervals should be open or not.
Since we are using keys with no natural successor method it is not possible for us to use the subMap method in the SortedMap interface to get all the intervals we need.
How difficult would it be to provide the NavigableMap interface instead of the SortedMap interface?
Should we try to modify the code ourself or do you know of any issues that makes this difficult, so it would be better to look for alternatives?

Best regards
Tobias and Martin.

[jankotek]

Hi,

First, I think you can easily get functionality of subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) by making a few extra 'containsKey' checks.

NavigableMap was introduced in Java 6. JDBM tries to be compatible with Android which is mostly Java 5. NavigableMap was introduced to Android at version 2.3 (which I did not know until now). So I think it is good idea to include it.

For me this has low priority, so it may make it to JDBM somewhere around 3.2 or 3.3 version.
If you would like to write it yourself, you will need three things:

1. Overall unit test for NavigableMap under Apache 2 license. Android class lib, Guava or Apache harmony are good place to start. I wont accept code without this test.

2. Modify BTreeSortedMap (BTree wrapper) to implement this interface instead of SortedSet

3. Modify DB interface to return NavigableMap and NavigableSet interfaces

[ajermakovics]

If you're going to do this I think you should consider ConcurrentNavigableMap instead of NavigableMap. Brings 4 useful concurrency methods

[jankotek]

Cuncurrent interfaces are on my plan.If it is going to be ConcurrentMap+SortedMap or ConcurrentNavigableMap is other problem

[tgrundtvig]

Hi Again,

We have decided to go ahead and modify the code to support the NavigableMap interface.
After reading the code we have come to the conclusion that we will have to make some small changes the BTreeTupleBrowser interface and its implementations:
If we want a clean and readable solution, we need to be able to browse in both directions in a similar way. At the moment the getNext returns the current and then increases the index while getPrevious first decreases the index and then return the new current.
We would suggest something like a getCurrent that do not move the cursor and then a goNext and goPrevious that moves the cursor if possible (returning true if the cursor could be moved). This way it will be much cleaner to make it possible to traverse in both directions in a similar way (which is needed for the NavigableMap interface). Otherwise we have to take care of special cases when traversing backwards in a closed interval.
What are your thoughts about this small change?

Secondly I must admit that I do not know what you mean by: Overall unit test for NavigableMap under Apache 2 license.
Do there exist a standard test of the NavigableMap interface under Apache 2 license? And if so, where could I find this?
I have looked at Android class lib, Guava and Apache harmony without being able to find such a test....

Best regards..

[jankotek]

Hi, I like your dedication. I will write and add NavigableMap soon (~week).

[tgrundtvig]

Hi jankotek,

We have implemented the NavigableMap interface on top of a much smaller and simpler interface that we call BaseMap, so now the task is reduced to implementing the BaseMap interface which looks like this:

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);
}

(The Entry<K,V> is just the java.util.Map.Entry interface, so it can be implemented in any way found suitable)

Our NavigableMap implementation takes care of iterators, submaps etc. It also does modCount and fast fail by throwing ConcurrentModificationException, so the implementation of BaseMap does not need to be concerned with any of this.

As I see it the best implementation would be to have BTree implement BaseMap or we could create a separate class that either extends BTree (I personally do not like this option so much) or contains a BTree and create the implementation here.

We can do this or you can do it if you prefer not having us modifying your existing code, but we are in kind of a hurry since we have an upcoming deadline.

We can email our implementation of NavigableMap and the unit tests we have made and you can put on whatever license you like, as long as we can use the code for our thesis. Must say though that some of the code is heavily inspired by java's TreeMap implementation (read copy-pasted from) which is under the GNU General Public License version 2, and I have no idea if this is compatible with the Apache 2 license. I am not really into that license stuff, sorry.

Hope too hear from you soon.

Best Regards Tobias.

[mv-dk]

Hi Jan,

I am writing the thesis with Tobias.

We have created a test file, NavigableMapInterfaceTest, extending SortedMapInterfaceTest. When we run the test on a regular java.util.TreeMap, the following two tests fail:

• testEntrySetContainsEntryNullKeyMissing
• testEntrySetRemoveNullKeyMissing

We think it would be a good idea to have the TreeMap in JDBM3 behave the same way as java.util.TreeMap, since this is what most people would expect. This only requires small changes like supporting null values (not null keys) and throwing a NullPointerException on entrySet().contains(null) instead of returning false.

Martin

[tgrundtvig]

Hi again,

We began implementing the BaseMap interface in a separate class that contains a BTree, here is the code:

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");
        }

    }

}

As you can see, we still need some implementation.
We had to make BTreeNode.loadNode protected instead of private for this to work. It would be more elegant to move the code into BTreeNode and BTree, but so far we have tried to modify the existing code as little as possible.

Best regards Tobias.

[jankotek]

Hi Tobias,

as I wrote I already started implementing NavigableMap. So please wait with your implementation for couple of days.

[tgrundtvig]

Hi jankotek,

We have nearly finished the implementation and written tests for it, so if you want to, you can just use our implementation and concentrate on other issues. Here is our NavigableMap implementation that uses the BaseMap interface I posted earlier:

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);
        }
    }
}

If you want to use this code, feel free, otherwise we will just wait for your implementation....

Best regards Tobias.

[jankotek]

Hi,
NavigableMap with some tests is now in Git. It still not full implementation, for example descending map does not work. Submaps do not work fully as well. We need to write more unit tests and I will try to integrate your code.

Rather than sending code here, please create fork and use merge requests

[jankotek]

TreeMap now implements ConcurrentNavigableMap interface. It supports all functions except inverted map.