Support for NavigableMap in Long2ObjectAVLTreeMap and the like is missing

[cheusov]

This is not an issue but a feature request. It would be nice to have functions from NavigableMap interface in RBTree and AVLTree-based maps and sets classes. For example, {ceiling,floor,higher,lower}{Entry,Key} functions. See here https://docs.oracle.com/javase/8/docs/api/java/util/NavigableMap.html for the reference.

[Speiger]

If this was implemented it would make SortedPools at least makeable with FastUtil. Right now you are forced to use java Implementations because its impossible with fastUtil.

[rwperrott]

Why the lack of support for obviously needed floor keyed methods in SortedMap?

These are essential for efficiently finding things in a sparse array of things and finding the floor thing of varying sized things, in a non-sparse array.

I note that in java.util.NavigableMap, has these methods:

• K floorKey()
• Map.Entry<K,​V> floorEntry​(K key) // To avoid redundant cost, of calling floorKey(), then get()

.. but annoyingly omits these obvious methods:

• SortedMap<K,​V> floorMap() // To avoid redundant cost, of calling floorKey(), lastKey(), then subMap()
• SortedMap<K,​V> floorMap(K toKey) // To avoid redundant cost, of calling floorKey(), then subMap()

I appreciate that you may not want to implement NavigableMap, but maybe should, however please at least add at least a typed version of floorKey (e.g. floorIntKey) to the typed *SortedMap interfaces and their implementations, to avoid the inefficiency of having to call subMap when only the floorKey, and possibly the value are needed.

[vigna]

You lost me at "stupid".

[rwperrott]

I updated, it to make more sense, .. but I have already switched to using parallel arrays of ordered key and value, resized by your array functions, with binarySearch to find the exact key or floor key.

[incaseoftrouble]

Just some questions:

• What is floorKey()? Should be floorKey(K key), right? Anyway, this shouldn't be that hard to implement I guess, especially since there are straightforward "default" implementations. Feel free to submit a MR :-)
• What is floorMap()? And how is floorMap(K key) different from headMap(K key)? (key does not need to element of the map)

[rwperrott]

From the NavigableMap JavaDoc:

floorKey(K key)
Returns the greatest key less than or equal to the given key, or null if there is no such key.

Indeed it should be easy to add floor* methods for a data structure with ordered keys.

As revealed by SortedMap JavaDoc excerpt below, headMap(toKey) is useless for this because it won't return the equivalent of subMap(floorKey(key), toKey), instead subMap(firstKey(), key) for exclusive key:

headMap(K toKey)
Returns a view of the portion of this map whose keys are  strictly less than toKey.

[incaseoftrouble]

What I was asking is a semantic description of floorMap() / floorMap(K key).

• I am guessing that this is supposed to be equivalent to headMap(floorKey(toKey))?
• Or is map.floorMap().get(k) supposed to yield map.get(map.floorKey(k))? In that case this can be directly emulated with floorValue (and potentially headMap), no need for a separate method. Also, its not possible to have such a floorMap to satisfy the contracts of the collections API. For example, iterators and size() don't make sense, since they depend on the key type

[rwperrott]

The 1st suggestion is useless if you need to specify both a lower and higher key, like a floorMap(fromKey, toKey). I originally thought I needed.

A major reason why this library appears to exists are to provide better typed support for primitive key and/or value data structures, so the comment about iterators and size() is puzzling.

After further work on my approach, now using ordered key and data arrays, with binarySearch(array, 0, size, key) of the key array (miss return = -(insertion_point - 1), aka floor): I know that a floorKey(key) functionality is critical to get the start value key and calculate the start offset to the relevant start value part, and also to find an inclusive end floor key, to get the inclusive end value key and to calculate the length of the relevant end value part. I don't see floorValue(key) as useful at all; a floorEntry(key) maybe useful, to get both the actual key and value, when only one entry is needed.

Anyhow, my approach works, so I doubt that I'll comment any further on this issue.

[incaseoftrouble]

I still don't know what floorMap is even supposed to do :-) We can't implement functionality which is not specified.

[rwperrott]

I was mistaken about the need for a floorMap method, only a floorKey method is useful, because I now see no benefit in creating a view of the map for offset key range use.

[Speiger]

It can be useful if you want to have somewhat of a savestate of iteration. because you could iterate and save the key that you were on and then continue later.

[rwperrott]

It can be useful if you want to have somewhat of a savestate of iteration. because you could iterate and save the key that you were on and then continue later.

A floorMap could be derived by something like:

1. calling floorKey with the desired start key value, to get the found start key.
2. calling floorKey with the desired end key value, to get the found end key value.
3. if found end key equals desired end key, then found last key is key before found end key, else found last key is found end key.
4. calling a subMap like method with the found start key and the inclusive found last key.

• I'm not sure about 3. and 4.

To do bounded navigation, it is necessary to detect when at the found start key or the found last key, of the sub-map, to adjust the offset and limit the length of the view of the found first value, or limit the length of the view of the found last value, possibly both, if the mapped found last key equals the found first key. I did this, not via a map view, but more cheaply via a forEach like method, calling a method accepting adjusted key/value, of a provided functional object, in first to last key/value order, or last to first key/value order. A Iterator or a Stream could be provided, but at greater object creation cost.