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: HashSet.scala 16884 2009-01-09 16:52:09Z cunei $
package scalax.collection.immutable
import generic.{SetTemplate, SetFactory, AddableBuilder}
/** The canonical factory methods for <a href="HashSet.html">immutable HashSet's<la>.
*
* @author Martin Odersky
* @version 2.8
*/
object HashSet extends SetFactory[HashSet] {
/** The empty set of this type.
*/
def empty[A] = new HashSet[A]
}
/** This class implements immutable maps/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.
*
* @author Martin Odersky
* @version 2.0, 19/01/2007
*/
@serializable
class HashSet[A] extends Set[A]
with SetTemplate[HashSet, A]
with mutable.FlatHashTable[A] {
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 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
}
override def newBuilder[B]: generic.Builder[HashSet, B] =
new AddableBuilder[HashSet, B](HashSet.empty)
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)
}
}
|
