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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2013, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala
package collection
package immutable
import generic._
import scala.annotation.tailrec
/**
* $factoryInfo
*
* Note that each element insertion takes O(n) time, which means that creating a list set with
* n elements will take O(n^2^) time. This makes the builder suitable only for a small number of
* elements.
*
* @since 1
* @define Coll ListSet
* @define coll list set
*/
object ListSet extends ImmutableSetFactory[ListSet] {
/**
* $setCanBuildFromInfo
*/
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, ListSet[A]] =
setCanBuildFrom[A]
@SerialVersionUID(5010379588739277132L)
private object EmptyListSet extends ListSet[Any]
private[collection] def emptyInstance: ListSet[Any] = EmptyListSet
}
/**
* This class implements immutable sets using a list-based data structure. List set iterators and
* traversal methods visit elements in the order whey were first inserted.
*
* Elements are stored internally in reversed insertion order, which means the newest element is at
* the head of the list. As such, methods such as `head` and `tail` are O(n), while `last` and
* `init` are O(1). Other operations, such as inserting or removing entries, are also O(n), which
* makes this collection suitable only for a small number of elements.
*
* Instances of `ListSet` represent empty sets; they can be either created by calling the
* constructor directly, or by applying the function `ListSet.empty`.
*
* @tparam A the type of the elements contained in this list set
*
* @author Matthias Zenger
* @version 1.0, 09/07/2003
* @since 1
* @define Coll ListSet
* @define coll list set
* @define mayNotTerminateInf
* @define willNotTerminateInf
*/
@SerialVersionUID(-8417059026623606218L)
sealed class ListSet[A] extends AbstractSet[A]
with Set[A]
with GenericSetTemplate[A, ListSet]
with SetLike[A, ListSet[A]]
with Serializable {
override def companion: GenericCompanion[ListSet] = ListSet
override def size: Int = 0
override def isEmpty: Boolean = true
def contains(elem: A): Boolean = false
def +(elem: A): ListSet[A] = new Node(elem)
def -(elem: A): ListSet[A] = this
override def ++(xs: GenTraversableOnce[A]): ListSet[A] =
if (xs.isEmpty) this
else (repr /: xs) (_ + _)
def iterator: Iterator[A] = {
def reverseList = {
var curr: ListSet[A] = this
var res: List[A] = Nil
while (!curr.isEmpty) {
res = curr.elem :: res
curr = curr.next
}
res
}
reverseList.iterator
}
protected def elem: A = throw new NoSuchElementException("elem of empty set")
protected def next: ListSet[A] = throw new NoSuchElementException("next of empty set")
override def toSet[B >: A]: Set[B] = this.asInstanceOf[ListSet[B]]
override def stringPrefix = "ListSet"
/**
* Represents an entry in the `ListSet`.
*/
@SerialVersionUID(-787710309854855049L)
protected class Node(override protected val elem: A) extends ListSet[A] with Serializable {
override def size = sizeInternal(this, 0)
@tailrec private[this] def sizeInternal(n: ListSet[A], acc: Int): Int =
if (n.isEmpty) acc
else sizeInternal(n.next, acc + 1)
override def isEmpty: Boolean = false
override def contains(e: A) = containsInternal(this, e)
@tailrec private[this] def containsInternal(n: ListSet[A], e: A): Boolean =
!n.isEmpty && (n.elem == e || containsInternal(n.next, e))
override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e)
override def -(e: A): ListSet[A] = removeInternal(e, this, Nil)
@tailrec private[this] def removeInternal(k: A, cur: ListSet[A], acc: List[ListSet[A]]): ListSet[A] =
if (cur.isEmpty) acc.last
else if (k == cur.elem) (cur.next /: acc) { case (t, h) => new t.Node(h.elem) }
else removeInternal(k, cur.next, cur :: acc)
override protected def next: ListSet[A] = ListSet.this
override def last: A = elem
override def init: ListSet[A] = next
}
}
|
