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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection.immutable
import generic._
/** This class implements immutable sets using a hash table.
* 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.
*
* @note the builder of a hash set returns specialized representations EmptySet,Set1,..., Set4
* for sets of size <= 4.
*
* @author Martin Odersky
* @version 2.8
*/
@serializable
class HashSet[A] extends Set[A]
with SetClass[A, HashSet]
with SetTemplate[A, HashSet[A]]
with mutable.FlatHashTable[A] {
override def companion: Companion[HashSet] = HashSet
protected var later: HashSet[A] = null
protected var changedElem: A = _
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 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 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)
}
}
/** A factory object for immutable HashSets
*
* @author Martin Odersky
* @version 2.8
*/
object HashSet extends SetFactory[HashSet] {
implicit def builderFactory[A]: BuilderFactory[A, HashSet[A], Coll] = setBuilderFactory[A]
override def empty[A]: HashSet[A] = new HashSet
}
|
