scala.collection.mutable.TreeMap vs java.util.TreeMap - searching for a key element w/o traversing whole list

[Eric Peters]

I was porting over some java code that was using java.util.TreeMap and wouldn't quite replicate the same behavior in the scala immutable TreeMap.

One method that was missing from the scala TreeMap is: getHigherEntry(K key): "Gets the entry for the least key greater than the specified key", should be simple to implement.  

However, I can't seem to find any methods in the TreeMap that won't recurse through the whole map!  I would expect that in a TreeMap, I would be able to search for a key using a compare method of what's stored in the tree and just look through the minimum number of branches to reach the leaf.  Instead I'm finding it searching all of the branches.

My testing pseudo code:

object IntOrderingTest extends Ordering[Int] {

def compare(a:Int, b:Int) = { val order = a compare b; println(s"$a compare $b: $order"); order }

}

val m = new TreeMap[Int,Int]()(IntOrderingTest) ++ Map(1 -> 1) ++ Map(2 -> 2) ++ Map(15 -> 15, 13 -> 13, 8 -> 8, 4 -> 4) ++ Map(3 -> 3, 5 -> 5, 6 -> 6, 7 -> 7, 9 -> 9, 10 -> 10, 11 -> 11, 12 -> 12, 14 -> 14)

find:

scala> m.find{ case(k, v) => IntOrderingTest.compare(k, 15) >= 0  }

1 compare 15: -1

2 compare 15: -1

3 compare 15: -1

4 compare 15: -1

5 compare 15: -1

6 compare 15: -1

7 compare 15: -1

8 compare 15: -1

9 compare 15: -1

10 compare 15: -1

11 compare 15: -1

12 compare 15: -1

13 compare 15: -1

14 compare 15: -1

15 compare 15: 0

collectFirst:

scala> m.collectFirst{ case(k,v) if(m.compare(k, 11) >= 0) => v }
1 compare 11: -1
2 compare 11: -1
3 compare 11: -1
4 compare 11: -1
5 compare 11: -1
6 compare 11: -1
7 compare 11: -1
8 compare 11: -1
9 compare 11: -1
10 compare 11: -1
11 compare 11: 0
11 compare 11: 0
res11: Option[Int] = Some(11)

Am I doing something wrong?

Thanks,

Eric

[Som Snytt]

The scaladoc suggests:

scala> (m from 6).take(2).last
5 compare 6: -1
9 compare 6: 1
7 compare 6: 1
6 compare 6: 0
res14: (Int, Int) = (7,7)


scala> (m from 6).tail.head
5 compare 6: -1
9 compare 6: 1
7 compare 6: 1
6 compare 6: 0
6 compare 9: -1
6 compare 7: -1
6 compare 6: 0
res12: (Int, Int) = (7,7)

[Daniel Sobral]

On Mon, Nov 5, 2012 at 7:27 PM, Eric Peters <ericp...@gmail.com> wrote:
> I was porting over some java code that was using java.util.TreeMap and
> wouldn't quite replicate the same behavior in the scala immutable TreeMap.
>
> One method that was missing from the scala TreeMap is: getHigherEntry(K
> key): "Gets the entry for the least key greater than the specified key",
> should be simple to implement.
>
> However, I can't seem to find any methods in the TreeMap that won't recurse
> through the whole map! I would expect that in a TreeMap, I would be able to
> search for a key using a compare method of what's stored in the tree and
> just look through the minimum number of branches to reach the leaf. Instead
> I'm finding it searching all of the branches.

I'm not sure why you think "find" should be able to understand that
your predicate is related to how the tree is ordered, but, to put it
simply, it doesn't. It derives no information from the result of the
predicate other than that's not the element desired, so it needs to
keep looking.

Moreover, find will return the *first* element, according to the
tree's order, so it has to start from the least element and test one
by one from there.

There's really no such method on Scala's TreeMap. You can use "from"
instead, but before Scala 2.10 it is just as inefficient as using
find.

--
Daniel C. Sobral

I travel to the future all the time.

[Rex Kerr]

I think you're misreading--Eric seems to me to just be saying that getHigherEntry is a key method for a sorted map, and Scala doesn't have it.  I don't think he's saying that any particular method should do it, just that some method should exist which does.

And I agree with that.  I've several times had to use Java maps specifically because Scala doesn't have that method.  Using that method is one of the main reasons to favor trees over hash maps.

  --Rex

[Eric Peters]

Just so there is no confusion, +1 for what Rex said.  I knew find/collect/etc *shouldn't* work but I had some naive hope scala would have some magic trick up its sleeve to try it anyhow :)

The earlier post by Som Snytt seems to get me mostly what I want:

scala> m.from(15)

5 compare 15: -1
9 compare 15: -1
13 compare 15: -1
20 compare 15: 1
15 compare 15: 0
14 compare 15: -1

res23: scala.collection.immutable.TreeMap[Int,Int] = Map(15 -> 15, 20 -> 20, 25 -> 25)

(to get the actual result I want, I just throw a .head/headOption)

I just don't know what type of additional work might be going on trying to return the whole tree vs just the one element I care about.

-Eric