Sorted Sets Contents

## Sorted Sets

A SortedSet is a set that produces its elements (using iterator or foreach) in a given ordering (which can be freely chosen at the time the set is created). The default representation of a SortedSet is an ordered binary tree which maintains the invariant that all elements in the left subtree of a node are smaller than all elements in the right subtree. That way, a simple in order traversal can return all tree elements in increasing order. Scala's class immutable.TreeSet uses a red-black tree implementation[] to maintain this ordering invariant and at the same time keep the tree balanced-meaning that all paths from the root of the tree to a leaf have lengths that differ only by at most one element.

To create an empty TreeSet, you could first specify the desired ordering:

 scala> val myOrdering = Ordering.fromLessThan[String](_ > _) myOrdering: scala.math.Ordering[String] = ...

Then, to create an empty tree set with that ordering, use:

 scala> TreeSet.empty(myOrdering) res1: scala.collection.immutable.TreeSet[String] = TreeSet()

Or you can leave out the ordering argument but give an element type or the empty set. In that case, the default ordering on the element type will be used.

 scala> TreeSet.empty[String] res2: scala.collection.immutable.TreeSet[String] = TreeSet()

If you create new sets from a tree-set (for instance by concatenation or filtering) they will keep the same ordering as the original set. For instance,

 scala> res2 + ("one", "two", "three", "four") res3: scala.collection.immutable.TreeSet[String] = TreeSet(four, one, three, two)

Sorted sets also support ranges of elements. For instance, the range method returns all elements from a starting element up to, but excluding, and end element. Or, the from method returns all elements greater or equal than a starting element in the set's ordering. The result of calls to both methods is again a sorted set. Examples:

 scala> res3 range ("one", "two") res4: scala.collection.immutable.TreeSet[String] = TreeSet(one, three) scala> res3 from "three" res5: scala.collection.immutable.TreeSet[String] = TreeSet(three, two)

Next: Bitsets

 Sorted Sets Contents