Is there a Scala version of NavigableMap?

Question

In Java 1.6, the NavigableMap (and the NavigableSet) interfaces were introduced and TreeMap was updated to implement the new interface. Among other things, NavigableMap is useful for asking questions like "Which element in the collection is closest to X? (see this excellent blog post by François Sarradin for an example and discussion).

I was hoping to find something similar in Scala 2.8's TreeMap implementation, but alas, it doesn't appear to be so (at least, it isn't obvious). Is there another Scala class or trait which is similar to Java's NavigableMap? If not, are there some simple Scala idioms which can be used to achieve something similar?

I realize I can use Java's TreeMap, but I'd like to stay within the Scala collections framework (if only for simplicity).

score 2 · Accepted Answer · edited May 23 '17 at 12:24

2

On immutable collections, having the back references makes it impossible to make the collection persistent. So, instead, people use zippers to navigate through such structures. Anti-xml has a nice example of using zippers when working with XML.

edited May 23 '17 at 12:24

Community

1
1

answered Aug 29 '11 at 19:37

Daniel C. Sobral

295,120
86
501
681

It's pretty clear how a zipper might help with modifying (copying) the tree, but it's less clear how a zipper would be used to answer questions like "Which element in the collection is closest to X?". I know we are talking mostly theory here (since zippers appear to be mostly experimental), but can you describe how a zipper might answer the previously mentioned question? – Jim Hurne Aug 30 '11 at 16:09
@Jim Zippers are not experimental at all. Zippers have two kinds of operation: inspect/update and navigate. So, if you have a zipper at X, its navigation operations will naturally give you the closest elements. – Daniel C. Sobral Aug 30 '11 at 17:55
Ah I see now! Thanks. The question you linked to about zippers is what gave me the impression zippers were experimental. Glad to hear they are readily available. – Jim Hurne Aug 31 '11 at 08:49
@Jim Zippers is a way to manipulate data. There may be readily available zippers for some data structures, but you can _write_ zippers for anything you want. – Daniel C. Sobral Aug 31 '11 at 16:11

score 1 · Answer 2 · answered Aug 29 '11 at 01:37

Here's a thread on this topic

It seems SortedMap might be able to get you part of the way there, but what I've tested so far I'm not sure if it's O(log(n)) the way a search ought to be:

def searchMap(m: SortedMap[Int,_], k: Int) = {
    val left  = m to(k) lastKey
    val right = m from(k) take(2) lastKey

    if (k - left < right - k)
        left
    else
        right
}

Based on the definitions of from and to in terms of rangeImpl it looks like this could be O(log(n)), but based on actually timing it, it appears to grow linearly for all plausible values of n.

So I'm not sure.

Why not, but the functions to and from are creating two new maps, which might not be desirable. — Mikaël Mayer, Jun 14 '13 at 13:31

Is there a Scala version of NavigableMap?

2 Answers2