BitsetsSetsSorted SetsContents

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

BitsetsSetsSorted SetsContents