Nearest keys in a SortedMap

Question

Given a key k in a SortedMap, how can I efficiently find the largest key m that is less than or equal to k, and also the smallest key n that is greater than or equal to k. Thank you.

Answer 1

Looking at the source code for 2.9.0, the following code seems about to be the best you can do

def getLessOrEqual[A,B](sm: SortedMap[A,B], bound: A): B = {
  val key = sm.to(x).lastKey
  sm(key)
}

I don't know exactly how the splitting of the RedBlack tree works, but I guess it's something like a O(log n) traversal of the tree/construction of new elements and then a balancing, presumable also O(log n). Then you need to go down the new tree again to get the last key. Unfortunately you can't retrieve the value in the same go. So you have to go down again to fetch the value.

In addition the lastKey might throw an exception and there is no similar method that returns an Option.

I'm waiting for corrections.

Edit and personal comment

The SortedMap area of the std lib seems to be a bit neglected. I'm also missing a mutable SortedMap. And looking through the sources, I noticed that there are some important methods missing (like the one the OP asks for or the ones pointed out in my answer) and also some have bad implementation, like 'last' which is defined by TraversableLike and goes through the complete tree from first to last to obtain the last element.

Edit 2

Now the question is reformulated my answer is not valid anymore (well it wasn't before anyway). I think you have to do the thing I'm describing twice for lessOrEqual and greaterOrEqual. Well you can take a shortcut if you find the equal element.

Answer 2

Scala's SortedSet trait has no method that will give you the closest element to some other element.

It is presently implemented with TreeSet, which is based on RedBlack. The RedBlack tree is not visible through methods on TreeSet, but the protected method tree is protected. Unfortunately, it is basically useless. You'd have to override methods returning TreeSet to return your subclass, but most of them are based on newSet, which is private.

So, in the end, you'd have to duplicate most of TreeSet. On the other hand, it isn't all that much code.

Once you have access to RedBlack, you'd have to implement something similar to RedBlack.Tree's lookup, so you'd have O(logn) performance. That's actually the same complexity of range, though it would certainly do less work.

Alternatively, you'd make a zipper for the tree, so that you could actually navigate through the set in constant time. It would be a lot more work, of course.

Answer 3

Using Scala 2.11.7, the following will give what you want:

scala> val set = SortedSet('a', 'f', 'j', 'z')
set: scala.collection.SortedSet[Char] = TreeSet(a, f, j, z)

scala> val beforeH = set.to('h').last
beforeH: Char = f

scala> val afterH = set.from('h').head
afterH: Char = j

Generally you should use lastOption and headOption as the specified elements may not exist. If you are looking to squeeze a little more efficiency out, you can try replacing from(...).head with keysIteratorFrom(...).head

Answer 4

Sadly, the Scala library only allows to make this type of query efficiently:

and also the smallest key n that is greater than or equal to k.

val n = TreeMap(...).keysIteratorFrom(k).next

You can hack this by keeping two structures, one with normal keys, and one with negated keys. Then you can use the other structure to make the second type of query.

val n = - TreeMap(...).keysIteratorFrom(-k).next