1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2013, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala
package collection
package immutable
import generic._
import immutable.{RedBlackTree => RB}
import mutable.{ Builder, SetBuilder }
/** $factoryInfo
* @define Coll `immutable.TreeSet`
* @define coll immutable tree set
*/
object TreeSet extends ImmutableSortedSetFactory[TreeSet] {
implicit def implicitBuilder[A](implicit ordering: Ordering[A]): Builder[A, TreeSet[A]] = newBuilder[A](ordering)
override def newBuilder[A](implicit ordering: Ordering[A]): Builder[A, TreeSet[A]] =
new SetBuilder(empty[A](ordering))
/** The empty set of this type
*/
def empty[A](implicit ordering: Ordering[A]) = new TreeSet[A]
}
/** This class implements immutable sets using a tree.
*
* @tparam A the type of the elements contained in this tree set
* @param ordering the implicit ordering used to compare objects of type `A`
*
* @author Martin Odersky
* @version 2.0, 02/01/2007
* @since 1
* @see [[http://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes.html#redblack_trees "Scala's Collection Library overview"]]
* section on `Red-Black Trees` for more information.
*
* @define Coll `immutable.TreeSet`
* @define coll immutable tree set
* @define orderDependent
* @define orderDependentFold
* @define mayNotTerminateInf
* @define willNotTerminateInf
*/
@SerialVersionUID(-5685982407650748405L)
final class TreeSet[A] private (tree: RB.Tree[A, Unit])(implicit val ordering: Ordering[A])
extends SortedSet[A] with SortedSetLike[A, TreeSet[A]] with Serializable {
if (ordering eq null)
throw new NullPointerException("ordering must not be null")
override def stringPrefix = "TreeSet"
override def size = RB.count(tree)
override def head = RB.smallest(tree).key
override def headOption = if (RB.isEmpty(tree)) None else Some(head)
override def last = RB.greatest(tree).key
override def lastOption = if (RB.isEmpty(tree)) None else Some(last)
override def tail = new TreeSet(RB.delete(tree, firstKey))
override def init = new TreeSet(RB.delete(tree, lastKey))
override def drop(n: Int) = {
if (n <= 0) this
else if (n >= size) empty
else newSet(RB.drop(tree, n))
}
override def take(n: Int) = {
if (n <= 0) empty
else if (n >= size) this
else newSet(RB.take(tree, n))
}
override def slice(from: Int, until: Int) = {
if (until <= from) empty
else if (from <= 0) take(until)
else if (until >= size) drop(from)
else newSet(RB.slice(tree, from, until))
}
override def dropRight(n: Int) = take(size - math.max(n, 0))
override def takeRight(n: Int) = drop(size - math.max(n, 0))
override def splitAt(n: Int) = (take(n), drop(n))
private[this] def countWhile(p: A => Boolean): Int = {
var result = 0
val it = iterator
while (it.hasNext && p(it.next())) result += 1
result
}
override def dropWhile(p: A => Boolean) = drop(countWhile(p))
override def takeWhile(p: A => Boolean) = take(countWhile(p))
override def span(p: A => Boolean) = splitAt(countWhile(p))
def this()(implicit ordering: Ordering[A]) = this(null)(ordering)
private def newSet(t: RB.Tree[A, Unit]) = new TreeSet[A](t)
/** A factory to create empty sets of the same type of keys.
*/
override def empty = TreeSet.empty
/** Creates a new `TreeSet` with the entry added.
*
* @param elem a new element to add.
* @return a new $coll containing `elem` and all the elements of this $coll.
*/
def + (elem: A): TreeSet[A] = newSet(RB.update(tree, elem, (), overwrite = false))
/** A new `TreeSet` with the entry added is returned,
* assuming that elem is <em>not</em> in the TreeSet.
*
* @param elem a new element to add.
* @return a new $coll containing `elem` and all the elements of this $coll.
*/
def insert(elem: A): TreeSet[A] = {
assert(!RB.contains(tree, elem))
newSet(RB.update(tree, elem, (), overwrite = false))
}
/** Creates a new `TreeSet` with the entry removed.
*
* @param elem a new element to add.
* @return a new $coll containing all the elements of this $coll except `elem`.
*/
def - (elem:A): TreeSet[A] =
if (!RB.contains(tree, elem)) this
else newSet(RB.delete(tree, elem))
/** Checks if this set contains element `elem`.
*
* @param elem the element to check for membership.
* @return true, iff `elem` is contained in this set.
*/
def contains(elem: A): Boolean = RB.contains(tree, elem)
/** Creates a new iterator over all elements contained in this
* object.
*
* @return the new iterator
*/
def iterator: Iterator[A] = RB.keysIterator(tree)
override def keysIteratorFrom(start: A): Iterator[A] = RB.keysIterator(tree, Some(start))
override def foreach[U](f: A => U) = RB.foreachKey(tree, f)
override def rangeImpl(from: Option[A], until: Option[A]): TreeSet[A] = newSet(RB.rangeImpl(tree, from, until))
override def range(from: A, until: A): TreeSet[A] = newSet(RB.range(tree, from, until))
override def from(from: A): TreeSet[A] = newSet(RB.from(tree, from))
override def to(to: A): TreeSet[A] = newSet(RB.to(tree, to))
override def until(until: A): TreeSet[A] = newSet(RB.until(tree, until))
override def firstKey = head
override def lastKey = last
}
|
