blob: 22488ec79f2fdadc70fbedd139c864f9a95800e3 (
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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection.immutable
/** The canonical factory methods for <a href="HashSet.html">immutable HashSet's<la>.
*
* @author Martin Odersky
* @version 2.0, 19/01/2007
*/
object HashSet {
/** The empty set of this type.
*/
def empty[A] = new HashSet[A]
/** The canonical factory for this type
*/
def apply[A](elems: A*) = empty[A] ++ elems
}
/** This class implements immutable sets using a hash table.
*
* @author Martin Odersky
* @version 2.0, 19/01/2007
*/
@serializable
class HashSet[A] extends Set[A] with mutable.FlatHashTable[A] {
protected var later: HashSet[A] = null
protected var changedElem: A = _
protected var deleted: Boolean = _
def empty[C]: Set[C] = new EmptySet[C]
def contains(elem: A): Boolean = synchronized {
var m = this
var cnt = 0
while (m.later != null) {
if (elem == m.changedElem) return m.deleted
cnt += 1
m = m.later
}
if (cnt > logLimit) makeCopy(m)
m.containsEntry(elem)
}
def + (elem: A): Set[A] = synchronized {
makeCopyIfUpdated()
if (containsEntry(elem)) this
else {
markUpdated(elem, false)
later addEntry elem
later
}
}
def - (elem: A): Set[A] = synchronized {
makeCopyIfUpdated()
if (!containsEntry(elem)) this
else {
markUpdated(elem, true)
later removeEntry elem
later
}
}
override def size: Int = synchronized {
var m = this
var cnt = 0
var s = 0
while (m.later != null) {
if (m.deleted) s += 1 else s -= 1
cnt += 1
m = m.later
}
s += tableSize
if (cnt > logLimit) makeCopy(m)
s
}
override def elements = synchronized {
makeCopyIfUpdated()
// note need to cache because (later versions of) set might be mutated while elements are traversed.
val cached = new mutable.ArrayBuffer() ++ super.elements
cached.elements
}
private def logLimit: Int = Math.sqrt(table.length).toInt
private def markUpdated(elem: A, del: Boolean) {
val lv = loadFactor
later = new HashSet[A] {
override def initialSize = 0
override def loadFactor = lv
table = HashSet.this.table
tableSize = HashSet.this.tableSize
threshold = HashSet.this.threshold
}
changedElem = elem
deleted = del
}
private def makeCopy(last: HashSet[A]) {
def undo(m: HashSet[A]) {
if (m ne last) {
undo(m.later)
if (m.deleted) addEntry(m.changedElem)
else removeEntry(m.changedElem)
}
}
table = new Array[AnyRef](last.table.length)
Array.copy(last.table, 0, table, 0, table.length)
tableSize = last.tableSize
threshold = last.threshold
undo(this)
later = null
}
private def makeCopyIfUpdated() {
var m = this
while (m.later != null) m = m.later
if (m ne this) makeCopy(m)
}
}
|
