整列済み集合

目次

整列済み集合

整列済み集合(SortedSet)は与えられた順(集合の作成時に自由に選べます)で要素を(iteratorやforeachを使って)返す集合です。 SortedSetのデフォルトの表現は、左の子ツリーの全ての要素が右の子ツリーよりも小さいという不変条件を維持する順序付き二分木です。 こうすると単純に順番に辿っていけばツリーの全ての要素を昇順で返せます。 Scalaのimmutable.TreeSetクラスはこの順序付けの不変条件と同時に木を平衡—木の根から葉までの全てのパスの長さが高々1要素分しか違わないことを示す—に保つために赤黒木[]を実装として使っています。

空のTreeSetを作る場合、最初に希望する順序付けの規定もできます:

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

myOrdering: scala.math.Ordering[String] = ...

そしてその順序付けを使って空のツリーセットを作るには次のようにします:

scala> TreeSet.empty(myOrdering)

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

もしくは順序付けの引数を省略して代わりに要素の型を指定できます。 その場合要素の型のデフォルトの順序付けが使われます。

scala> TreeSet.empty[String]

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

新しい集合をツリーセットから作る場合(例えば連結やフィルタリングで)その集合は元の集合と同じ順序付けを保持します。例えば、

scala> res2 + ("one", "two", "three", "four")

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

整列済み集合は要素の範囲をサポートします。 例えば、rangeメソッドは開始要素から終了要素まで(ただし終了要素を除く)の全ての要素を返します。 他にfromは集合内の開始要素以上の全ての要素を返します。 これらのメソッドの返り値もまた整列済み集合です。 例:

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)

続いては: ビット集合

整列済み集合

目次