|
|
|
整列済み集合 | 目次 |
最新版は Scala Documentation に移行しました。
整列済み集合は (SortedSet) は (集合の作成時に指定された) 任意の順序で要素を (iterator や foreach を使って) 返す事ができる集合だ。SortedSet クラスのデフォルトの表現は、左の子ツリー内の全ての要素が右の子ツリーの全ての要素よりも小さいという恒常条件を満たす順序付けされた二分木だ。これにより、通りがけ順 (in-order) で探索するだけで、木の全ての要素を昇順に返すことができる。Scala の immutable.TreeSet クラスは 赤黒木 を使ってこの恒常条件を実装している。また、この木構造は、平衡木であり、ルートから全て葉のまでの長さの違いは最大で一要素しかない。
空の 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) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
続いては、ビット集合
|
|
|
整列済み集合 | 目次 |