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).

Answer 1

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.

Answer 2

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.