blob: 35ead05b63cb38b4deff90bdf168a52c34100d99 (
plain) (
blame)
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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection.immutable
//import Predef.NoSuchElementException
/** The canonical factory of <a href="ListSet.html">ListSet</a>'s */
object ListSet {
/** constructs an empty ListSet
* @deprecated use <code>empty</code> instead
*/
@deprecated
def Empty[A] = new ListSet[A]
/** The empty set of this type.
*/
def empty[A] = new ListSet[A]
/** The canonical factory for this type
*/
def apply[A, B](elems: A*) = empty[A] ++ elems
}
/** This class implements immutable sets using a list-based data
* structure. Instances of <code>ListSet</code> represent
* empty sets; they can be either created by calling the constructor
* directly, or by applying the function <code>ListSet.empty</code>.
*
* @author Matthias Zenger
* @version 1.0, 09/07/2003
*/
@serializable
class ListSet[A] extends AnyRef with Set[A] {
/** Returns the number of elements in this set.
*
* @return number of set elements.
*/
def size: Int = 0
override def isEmpty: Boolean = true;
def empty[B] = ListSet.empty[B]
/** Checks if this set contains element <code>elem</code>.
*
* @param elem the element to check for membership.
* @return true, iff <code>elem</code> is contained in this set.
*/
def contains(elem: A): Boolean = false
/** This method creates a new set with an additional element.
*/
def +(elem: A): ListSet[A] = new Node(elem)
/** <code>-</code> can be used to remove a single element from
* a set.
*/
def -(elem: A): ListSet[A] = this
/** Creates a new iterator over all elements contained in this set.
*
* @throws Predef.NoSuchElementException
* @return the new iterator
*/
def elements: Iterator[A] = new Iterator[A] {
var that: ListSet[A] = ListSet.this;
def hasNext = !that.isEmpty;
def next: A =
if (!hasNext) throw new NoSuchElementException("next on empty iterator")
else { val res = that.elem; that = that.next; res }
}
/** Compares two sets for equality.
* Two set are equal iff they contain the same elements.
*/
override def equals(obj: Any): Boolean = obj match {
case _: scala.collection.Set[_] =>
val that = obj.asInstanceOf[scala.collection.Set[A]]
(size == that.size) && (toList forall that.contains)
case _ =>
false
}
/**
* @throws Predef.NoSuchElementException
*/
protected def elem: A = throw new NoSuchElementException("Set has no elements");
/**
* @throws Predef.NoSuchElementException
*/
protected def next: ListSet[A] = throw new NoSuchElementException("Next of an empty set");
@serializable
protected class Node(override protected val elem: A) extends ListSet[A] {
/** Returns the number of elements in this set.
*
* @return number of set elements.
*/
override def size = ListSet.this.size + 1
/** Checks if this set is empty.
*
* @return true, iff there is no element in the set.
*/
override def isEmpty: Boolean = false
/** Checks if this set contains element <code>elem</code>.
*
* @param elem the element to check for membership.
* @return true, iff <code>elem</code> is contained in this set.
*/
override def contains(e: A) = (e == elem) || ListSet.this.contains(e)
/** This method creates a new set with an additional element.
*/
override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e)
/** <code>-</code> can be used to remove a single element from
* a set.
*/
override def -(e: A): ListSet[A] = if (e == elem) ListSet.this else {
val tail = ListSet.this - e; new tail.Node(elem)
}
override protected def next: ListSet[A] = ListSet.this
override def stringPrefix = "Set"
}
}
|
