Whats a good way to sort a List in Scala using more than one sort key, e.g. primary, secondary?

[Alex Black]

In C# (gasp!) they have this nice feature:

items.orderBy( item => item.foo ).thenBy ( item => item.bar )

Is there a good way to do this in Scala? E.g. sort my items first by
"foo", if they tie on "foo" then sort them by "bar"?

I end up writing this code:

items.sort { case (item1,item2) =>
if ( item1.foo == item2.foo )
item1.bar > item2.bar
else
item1.foo > item2.foo
}

which gets much worse if you have a third sort key.

[Daniel Spiewak]

I believe the #sort function is stable.  So you should be able to emulate your C# example in the following way:

items sort { _.bar < _.bar } sort { _.foo < _.foo }

Daniel

[Alex Cruise]

Tuples are also comparable in the expected way, so you can also do this:

items sortBy { x => (x.bar, x.foo) }

-0xe1a

[Alex Black]

I could be missing something, but I think that will return the same result as items.sortBy { _.foo }, ie it will only sort on the secondary index.

I think C# Linq does something like build up an expression out of the orderBy and thenBy calls, and then sort the list once for you.

[Jason Zaugg]

On Thu, Feb 24, 2011 at 9:54 PM, Alex Black <al...@alexblack.ca> wrote:
> Thanks Alex, that looks really good.
> Hmm, say I wanted to sort ascending by bar and descending by foo?  If they
> are numbers, I could use positive or negative, what about if they are
> strings?

Here's one way.

scala> case class Reverse[T](t: T)
defined class Reverse

scala> implicit def ReverseOrdering[T: Ordering]: Ordering[Reverse[T]]
= Ordering[T].reverse.on(_.t)
ReverseOrdering: [T](implicit evidence$1: Ordering[T])Ordering[Reverse[T]]

scala> ps.sortBy(p => (p.last, Reverse(p.first)))
res21: List[Person] = List(Person(Smith,Bob), Person(Smith,Bill))

-jason

[Alex Cruise]

On Thu, Feb 24, 2011 at 1:10 PM, Jason Zaugg <jza...@gmail.com> wrote:

Here's one way.

scala> case class Reverse[T](t: T)
defined class Reverse

scala> implicit def ReverseOrdering[T: Ordering]: Ordering[Reverse[T]]
= Ordering[T].reverse.on(_.t)
ReverseOrdering: [T](implicit evidence$1: Ordering[T])Ordering[Reverse[T]]

scala> ps.sortBy(p => (p.last, Reverse(p.first)))
res21: List[Person] = List(Person(Smith,Bob), Person(Smith,Bill))

This is awesome, should be in the library.

-0xe1a

[Jason Zaugg]

On Thu, Feb 24, 2011 at 9:34 PM, Alex Black <al...@alexblack.ca> wrote:
> In C# (gasp!) they have this nice feature:
>
> items.orderBy( item => item.foo ).thenBy ( item => item.bar )
>
> Is there a good way to do this in Scala? E.g. sort my items first by
> "foo", if they tie on "foo" then sort them by "bar"?

scala> case class Person(last: String, first: String)
defined class Person

scala> val ps = List(Person("Smith", "Bob"), Person("Smith", "Bill"))
ps: List[Person] = List(Person(Smith,Bob), Person(Smith,Bill))

scala> ps.sortBy(p => (p.last, p.first))
res15: List[Person] = List(Person(Smith,Bill), Person(Smith,Bob))

scala> implicit val o = Ordering.by((p: Person) => (p.last, p.first))
o: scala.math.Ordering[Person] = scala.math.Ordering$$anon$6@6aa27760

scala> ps.sorted
res16: List[Person] = List(Person(Smith,Bill), Person(Smith,Bob))

[Nicholas Sterling]

That would be handy.  Also, it would be nice if Reverse(Reverse(x)) yielded x.

Nicholas

[Alex Black]

Thanks Alex, that looks really good.

Hmm, say I wanted to sort ascending by bar and descending by foo?  If they are numbers, I could use positive or negative, what about if they are strings?

[Seth Tisue]

>>>>> "Jason" == Jason Zaugg <jza...@gmail.com> writes:

scala> implicit val o = Ordering.by((p: Person) => (p.last, p.first))

Darnit. Why didn't I think of that?

Now I can throw away this code:

def multiSort[T](xs: Seq[T])(orderings: Ordering[T]*) =
xs.sorted(orderings.reduceLeft(combine))
def combine[T](o1: Ordering[T], o2: Ordering[T]) = new Ordering[T] {
def compare(x: T, y: T) =
o1.compare(x, y) match {
case 0 => o2.compare(x, y)
case n => n
}
}

multiSort(people)(Ordering.by(_.last),
Ordering.by(_.first),

--
Seth Tisue @ Northwestern University | http://tisue.net
lead developer, NetLogo: http://ccl.northwestern.edu/netlogo/

[Jim Balter]

You're missing that foo is (as you specified it) the primary index --
bar is the secondary index. Since a stable sort retains the order for
equal keys, sorting by the secondary index first retains the secondary
ordering among keys with the same primary index. Of course, this
method requires two sorts rather than one and requires that sort be
stable, but it does work under that assumption

-- Jim

[Alex Black]

Very cool, I never thought of that, thanks Jim and Daniel.

[Jim Balter]

Not really; the test grows linearly if coded as:

items.sortWith { case(a,b) =>
if( a.k1 < b.k1 ) true
else if( a.k1 > b.k1 ) false
else if( a.k2 < b.k2 ) true
else if( a.k2 > b.k2 ) false
else a.k3 < b.k3
}

-- Jim

[Vlad Patryshev]

 if( a.k1 < b.k1 ) true
 else if( a.k1 > b.k1 ) false
 else if( a.k2 < b.k2 ) true
 else if( a.k2 > b.k2 ) false
 else a.k3 < b.k3

amounts to 

 (a.k1 <  b.k1) || 

((a.k1 == b.k1) && ((a.k2 < b.k2) ||

                   ((a.k2 == b.k2) && (a.k3 < b.k3))))

(add or remove parentheses to your taste... I believe mixing ifs and logical constants is not a good taste)

2011/2/24 Jim Balter <J...@balter.name>

--
Thanks,
-Vlad

[Jim Balter]

And I believe that there's no substance or reason to that objection.
Your version does indeed get much worse as the number of keys
increases, whereas mine has a very simple replicated pattern.

-- Jim