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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection
package immutable
import generic._
/** <p>
* This class implements immutable sets using a hash table.
* </p>
* <p>
* It is optimized for sequential accesses where the last updated table is
* accessed most often. It supports with reasonable efficiency accesses to
* previous versions of the table by keeping a change log that's regularly
* compacted. It needs to synchronize most methods, so it is less suitable
* for highly concurrent accesses.
* </p>
*
* @note the builder of a hash set returns specialized representations EmptySet,Set1,..., Set4
* for sets of size <= 4.
*
* @author Martin Odersky
* @version 2.8
* @since 2.3
*/
@serializable @SerialVersionUID(1L)
class HashSet[A] extends Set[A]
with GenericSetTemplate[A, HashSet]
with SetLike[A, HashSet[A]]
with mutable.FlatHashTable[A] {
override def companion: GenericCompanion[HashSet] = HashSet
@transient protected var later: HashSet[A] = null
@transient protected var changedElem: A = _
@transient protected var deleted: Boolean = _
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): HashSet[A] = synchronized {
makeCopyIfUpdated()
if (containsEntry(elem)) this
else {
markUpdated(elem, false)
later addEntry elem
later
}
}
def - (elem: A): HashSet[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 += m.tableSize
if (cnt > logLimit) makeCopy(m)
s
}
override def iterator = synchronized {
makeCopyIfUpdated()
// note need to cache because (later versions of) set might be mutated while elements are traversed.
val cached = new mutable.ArrayBuffer() ++= super.iterator
cached.iterator
}
private def logLimit: Int = math.sqrt(table.length).toInt
private def markUpdated(elem: A, del: Boolean) {
val lf = loadFactor
later = new HashSet[A] {
override def initialSize = 0
/* We need to do this to avoid a reference to the outer HashMap */
def _newLoadFactor = lf
override def loadFactor = _newLoadFactor
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 scala.Array[AnyRef](last.table.length)
scala.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)
}
private def writeObject(s: java.io.ObjectOutputStream) {
serializeTo(s)
}
private def readObject(in: java.io.ObjectInputStream) {
init(in, x => x)
}
}
/** A factory object for immutable HashSets.
*
* @author Martin Odersky
* @version 2.8
* @since 2.3
*/
object HashSet extends SetFactory[HashSet] {
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, HashSet[A]] = setCanBuildFrom[A]
override def empty[A]: HashSet[A] = new HashSet
}
|
