How to use sortable Sets in Scala (SortedSet, TreeSet, LinkedHashSet)

This is an excerpt from the 1st Edition of the Scala Cookbook ^(#ad) (partially modified for the internet). This is Recipe 11.28, “How to Use Sortable Sets in Scala”

Problem

You want to be able to store and retrieve items from a Set in a sorted order.

Solution: Scala sortable sets

To retrieve values from a set in sorted order, use a SortedSet. To retrieve elements from a set in the order in which elements were inserted, use a LinkedHashSet.

A SortedSet returns elements in a sorted order:

scala> val s = scala.collection.SortedSet(10, 4, 8, 2)
s: scala.collection.SortedSet[Int] = TreeSet(2, 4, 8, 10)

scala> val s = scala.collection.SortedSet("cherry", "kiwi", "apple")
s: scala.collection.SortedSet[String] = TreeSet(apple, cherry, kiwi)

A LinkedHashSet saves elements in the order in which they were inserted:

scala> val s = scala.collection.mutable.LinkedHashSet(10, 4, 8, 2)
s: scala.collection.mutable.LinkedHashSet[Int] = Set(10, 4, 8, 2)

Discussion

The SortedSet is available only in an immutable version. If you need a mutable version, use the java.util.TreeSet. The LinkedHashSet is available only as a mutable collection.

The examples shown in the Solution work because the types used in the sets have an implicit Ordering. Custom types won’t work unless you also provide an implicit Ordering. For example, the following code won’t work because the Person class is just a basic class:

class Person (var name: String)
import scala.collection.SortedSet
val aleka = new Person("Aleka")
val christina = new Person("Christina")
val molly = new Person("Molly")
val tyler = new Person("Tyler")

// this won't work
val s = SortedSet(molly, tyler, christina, aleka)

In the REPL, the last line of code fails with this error:

scala> val s = SortedSet(molly, tyler, christina, aleka)
<console>:17: error: No implicit Ordering defined for Person.
       val s = SortedSet(molly, tyler, christina, aleka)
                        ^

To solve this problem, modify the Person class to extend the Ordered trait, and implement a compare method:

class Person (var name: String) extends Ordered [Person] {
    override def toString = name
    // return 0 if the same, negative if this < that, positive if this > that
    def compare (that: Person) = {
        if (this.name == that.name)
            0
        else if (this.name > that.name)
            1
        else
            −1
    }
}

With this new Person class definition, sorting works as desired:

scala> val s = SortedSet(molly, tyler, christina, aleka)
s: scala.collection.SortedSet[Person] = TreeSet(Aleka, Christina, Molly, Tyler)

For more information about the Ordered and Ordering traits, see Recipe 10.28, “Sorting a Collection” and the links in the See Also section.