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

WARNING: comparing ints by subtracting them DOES NOT WORK. Also applies to most answers given here. http://stackoverflow.com/questions/2728793/java-integer-what-is-faster-comparison-or-subtraction — jcsahnwaldt Reinstate Monica, Mar 19 '12 at 20:17
... *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 (?:) — kornfridge, Dec 13 '12 at 15:54
@kornfridge 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. — Mario Rossi, Jul 07 '19 at 22:56

score 14 · Answer 1 · answered Apr 21 '10 at 22:54

14

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

answered Apr 21 '10 at 22:54

Daniel C. Sobral

295,120
86
501
681

Seems concise, comprehensible, and flexible. – WestCoastProjects May 15 '14 at 02:26
Came here again, wanted to upvote/comment but .. I've already been there done that! – WestCoastProjects Oct 17 '14 at 21:26
@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? – Dan Feb 09 '22 at 19:39
1

@Dan Sure there is. There's a `orElse` that will do what you want. It did not exist at that time. – Daniel C. Sobral Feb 10 '22 at 20:50

Randall Schulz · Accepted Answer · 2010-04-21T19:53:55.873

11

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]()
}

edited Apr 21 '10 at 19:53

answered Apr 21 '10 at 14:49

Randall Schulz

26,420
4
61
81

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? – David Apr 21 '10 at 15:25
@Dave There isn't, but you can put such an implicit inside a package object for the package that contains `A`. – Daniel C. Sobral Apr 21 '10 at 22:51
@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. – Randall Schulz Apr 21 '10 at 23:09
I didn't try the package object solution. All the rest was ok. – Daniel C. Sobral Apr 22 '10 at 13:20
1

@Dave Actually, put the `implicit object AOrdering` instead the object companion (ie, `object A`). That seems to work as well. – Daniel C. Sobral Apr 22 '10 at 13:25

score 5 · Answer 3 · answered Apr 21 '10 at 19:30

5

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

answered Apr 21 '10 at 19:30

Elazar Leibovich

32,750
33
122
169

1

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). – David Apr 22 '10 at 09:09

Scala 2.8 TreeMap and custom Ordering

3 Answers3

Linked