Scala 2.8 TreeMap and custom Ordering

Question

I'm switching from scala 2.7 and ordered to scala 2.8 and using ordering. It looks quite straight forward but I was wondering could I make it a little less verbose. For example:

scala> case class A(i: Int)
defined class A
scala> object A extends Ordering[A] { def compare(o1: A, o2: A) = o1.i - o2.i}
defined module A

If I then try to create a TreeMap I get an error

scala> new collection.immutable.TreeMap[A, String]()
<console>:10: error: could not find implicit value for parameter ordering: Ordering[A]
       new collection.immutable.TreeMap[A, String]()
       ^

However if I explicitly specify the object A as the ordering it works fine.

scala> new collection.immutable.TreeMap[A, String]()(A)
res34: scala.collection.immutable.TreeMap[A,String] = Map()

Do I always have to explicitly specify the ordering or is there a shorter format?

Thanks

Maupin

WARNING: comparing ints by subtracting them DOES NOT WORK. Also applies to most answers given here. #2729293 – Artieartifact

... iff the ints are big and have opposite signs. The number can then overflow yielding the opposite result since the sign switches. But if you are working with numbers that close to Int.MAX_VALUE, you're already playing with fire, aren't you? I think the subtracting "idiom" is particularly concise/useful in scala since scala doesn't have (ternary) conditional expressions (?:) – Kunstlied

@Kunstlied Scala does have conditional expressions. Syntax is: if( condition ) valueIfTrue else valueIfFalse . Now, if using symbols ? and : instead of "if(" and ") else" is a requirement, then no, Scala doesn't have conditional expressions. – Luminiferous

Answer 1

Notice the word "implicit" in the diagnostic. The parameter is declared implicit meaning the compiler will try to find a suitable value in scope at the point you invoke the constructor. If you make your Ordering an implicit value, it will be eligible for this treatment by the compiler:

scala> implicit object A extends Ordering[A] { def compare(o1: A, o2: A) = o1.i - o2.i}
defined module A

scala> val tm1 = new collection.immutable.TreeMap[A, String]()
tm1: scala.collection.immutable.TreeMap[A,String] = Map()

Edit:

That example works in the REPL because the REPL encloses your code in invisible class definitions. Here's one that works free-standing:

case class A(val i:Int) extends Ordered[A] { def compare(o:A) = i - o.i }

object A { implicit object AOrdering extends Ordering[A] { def compare(o1: A, o2: A) = o1.i - o2.i } }

class B {
    import A.AOrdering

    val tm1 = new collection.immutable.TreeMap[A, String]()
}

Cardboard

If I try that in my code I get told "error: `implicit' modifier cannot be used for top-level objects". So is there a way of doing this for top-level objects? – Maupin

@Dave There isn't, but you can put such an implicit inside a package object for the package that contains A. – Christmann

@Daniel: Did you try? I did but somehow got rebuffed by the compiler. I don't know if I just did it wrong or it's really not allowed. – Cardboard

I didn't try the package object solution. All the rest was ok. – Christmann

@Dave Actually, put the implicit object AOrdering instead the object companion (ie, object A). That seems to work as well. – Christmann

Answer 2

Mind you, there's a slightly less verbose way of creating an Ordering:

implicit val OrderingA = Ordering.by((_: A).i)

The main advantage of Ordering being you can provide many of them for the same class. If your A class is truly Ordered, then you should just extend that. If not, instead of using implicits, you may pass an Ordering explicitly:

new collection.immutable.TreeMap[A, String]()(Ordering.by(_.i))

Christmann

Seems concise, comprehensible, and flexible. – Lawana

Came here again, wanted to upvote/comment but .. I've already been there done that! – Lawana

@Daniel, how would you implement that for key with multiple fileds? E.g. case class A (i : Int, j : Int). It's possible to write ..Ordering.by((_: A).i) or ..Ordering.by((_: A).j) but I can't find any option to use both. There is no thenBy. Tuple doesn't work either... Any suggestions, please? – Anaptyxis

@Anaptyxis Sure there is. There's a orElse that will do what you want. It did not exist at that time. – Christmann

Answer 3

Instead of extending Ordering[A], try extending Ordered[A]. Like so:

scala> case class A(val i:Int) extends Ordered[A] {def compare(o:A) = i-o.i}
defined class A

scala> A(1)<A(2)
res0: Boolean = true

scala> A(1)<A(0)
res1: Boolean = false

scala> new collection.immutable.TreeMap[A, String]()
res3: scala.collection.immutable.TreeMap[A,String] = Map()

Kaylil

The way that works is that a low priority implicit converts the Ordered[A] to Ordering[A] for the TreeMap. Unfortunately we serialize TreeMaps for storage and the class of the ordering is a little volatile (some $$anon$ class). – Maupin