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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala.collection
package immutable
import annotation.unchecked.{ uncheckedVariance => uV }
import generic._
import collection.parallel.immutable.ParHashSet
/** This class implements immutable sets using a hash trie.
*
* '''Note:''' The builder of this hash set may return specialized representations for small sets.
*
* @tparam A the type of the elements contained in this hash set.
*
* @author Martin Odersky
* @author Tiark Rompf
* @version 2.8
* @since 2.3
* @define Coll `immutable.HashSet`
* @define coll immutable hash set
*/
@SerialVersionUID(2L)
class HashSet[A] extends AbstractSet[A]
with Set[A]
with GenericSetTemplate[A, HashSet]
with SetLike[A, HashSet[A]]
with CustomParallelizable[A, ParHashSet[A]]
with Serializable
{
override def companion: GenericCompanion[HashSet] = HashSet
//class HashSet[A] extends Set[A] with SetLike[A, HashSet[A]] {
override def par = ParHashSet.fromTrie(this)
override def size: Int = 0
override def empty = HashSet.empty[A]
def iterator: Iterator[A] = Iterator.empty
override def foreach[U](f: A => U): Unit = { }
def contains(e: A): Boolean = get0(e, computeHash(e), 0)
override def + (e: A): HashSet[A] = updated0(e, computeHash(e), 0)
override def + (elem1: A, elem2: A, elems: A*): HashSet[A] =
this + elem1 + elem2 ++ elems
// TODO: optimize (might be able to use mutable updates)
def - (e: A): HashSet[A] =
removed0(e, computeHash(e), 0)
protected def elemHashCode(key: A) = key.##
protected final def improve(hcode: Int) = {
var h: Int = hcode + ~(hcode << 9)
h = h ^ (h >>> 14)
h = h + (h << 4)
h ^ (h >>> 10)
}
private[collection] def computeHash(key: A) = improve(elemHashCode(key))
protected def get0(key: A, hash: Int, level: Int): Boolean = false
def updated0(key: A, hash: Int, level: Int): HashSet[A] =
new HashSet.HashSet1(key, hash)
protected def removed0(key: A, hash: Int, level: Int): HashSet[A] = this
protected def writeReplace(): AnyRef = new HashSet.SerializationProxy(this)
}
/** $factoryInfo
* @define Coll `immutable.HashSet`
* @define coll immutable hash set
*
* @author Tiark Rompf
* @since 2.3
* @define Coll `immutable.HashSet`
* @define coll immutable hash set
* @define mayNotTerminateInf
* @define willNotTerminateInf
*/
object HashSet extends ImmutableSetFactory[HashSet] {
/** $setCanBuildFromInfo */
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, HashSet[A]] = setCanBuildFrom[A]
override def empty[A]: HashSet[A] = EmptyHashSet.asInstanceOf[HashSet[A]]
private object EmptyHashSet extends HashSet[Any] { }
// TODO: add HashSet2, HashSet3, ...
class HashSet1[A](private[HashSet] val key: A, private[HashSet] val hash: Int) extends HashSet[A] {
override def size = 1
override def get0(key: A, hash: Int, level: Int): Boolean =
(hash == this.hash && key == this.key)
override def updated0(key: A, hash: Int, level: Int): HashSet[A] =
if (hash == this.hash && key == this.key) this
else {
if (hash != this.hash) {
//new HashTrieSet[A](level+5, this, new HashSet1(key, hash))
val m = new HashTrieSet[A](0,new Array[HashSet[A]](0),0) // TODO: could save array alloc
m.updated0(this.key, this.hash, level).updated0(key, hash, level)
} else {
// 32-bit hash collision (rare, but not impossible)
new HashSetCollision1(hash, ListSet.empty + this.key + key)
}
}
override def removed0(key: A, hash: Int, level: Int): HashSet[A] =
if (hash == this.hash && key == this.key) HashSet.empty[A] else this
override def iterator: Iterator[A] = Iterator(key)
override def foreach[U](f: A => U): Unit = f(key)
}
private[immutable] class HashSetCollision1[A](private[HashSet] val hash: Int, val ks: ListSet[A])
extends HashSet[A] {
override def size = ks.size
override def get0(key: A, hash: Int, level: Int): Boolean =
if (hash == this.hash) ks.contains(key) else false
override def updated0(key: A, hash: Int, level: Int): HashSet[A] =
if (hash == this.hash) new HashSetCollision1(hash, ks + key)
else {
var m: HashSet[A] = new HashTrieSet[A](0,new Array[HashSet[A]](0),0)
// might be able to save some ops here, but it doesn't seem to be worth it
for (k <- ks)
m = m.updated0(k, this.hash, level)
m.updated0(key, hash, level)
}
override def removed0(key: A, hash: Int, level: Int): HashSet[A] =
if (hash == this.hash) {
val ks1 = ks - key
if(ks1.isEmpty)
HashSet.empty[A]
else if(ks1.tail.isEmpty)
new HashSet1(ks1.head, hash)
else
new HashSetCollision1(hash, ks1)
} else this
override def iterator: Iterator[A] = ks.iterator
override def foreach[U](f: A => U): Unit = ks.foreach(f)
private def writeObject(out: java.io.ObjectOutputStream) {
// this cannot work - reading things in might produce different
// hash codes and remove the collision. however this is never called
// because no references to this class are ever handed out to client code
// and HashTrieSet serialization takes care of the situation
sys.error("cannot serialize an immutable.HashSet where all items have the same 32-bit hash code")
//out.writeObject(kvs)
}
private def readObject(in: java.io.ObjectInputStream) {
sys.error("cannot deserialize an immutable.HashSet where all items have the same 32-bit hash code")
//kvs = in.readObject().asInstanceOf[ListSet[A]]
//hash = computeHash(kvs.)
}
}
class HashTrieSet[A](private val bitmap: Int, private[collection] val elems: Array[HashSet[A]], private val size0: Int)
extends HashSet[A] {
override def size = size0
override def get0(key: A, hash: Int, level: Int): Boolean = {
val index = (hash >>> level) & 0x1f
val mask = (1 << index)
if (bitmap == - 1) {
elems(index & 0x1f).get0(key, hash, level + 5)
} else if ((bitmap & mask) != 0) {
val offset = Integer.bitCount(bitmap & (mask-1))
// TODO: might be worth checking if sub is HashTrieSet (-> monomorphic call site)
elems(offset).get0(key, hash, level + 5)
} else
false
}
override def updated0(key: A, hash: Int, level: Int): HashSet[A] = {
val index = (hash >>> level) & 0x1f
val mask = (1 << index)
val offset = Integer.bitCount(bitmap & (mask-1))
if ((bitmap & mask) != 0) {
// TODO: might be worth checking if sub is HashTrieSet (-> monomorphic call site)
val sub = elems(offset)
val subNew = sub.updated0(key, hash, level + 5)
if (sub eq subNew) this
else {
val elemsNew = new Array[HashSet[A]](elems.length)
Array.copy(elems, 0, elemsNew, 0, elems.length)
elemsNew(offset) = subNew
new HashTrieSet(bitmap, elemsNew, size + (subNew.size - sub.size))
}
} else {
val elemsNew = new Array[HashSet[A]](elems.length + 1)
Array.copy(elems, 0, elemsNew, 0, offset)
elemsNew(offset) = new HashSet1(key, hash)
Array.copy(elems, offset, elemsNew, offset + 1, elems.length - offset)
val bitmapNew = bitmap | mask
new HashTrieSet(bitmapNew, elemsNew, size + 1)
}
}
override def removed0(key: A, hash: Int, level: Int): HashSet[A] = {
val index = (hash >>> level) & 0x1f
val mask = (1 << index)
val offset = Integer.bitCount(bitmap & (mask-1))
if ((bitmap & mask) != 0) {
val sub = elems(offset)
// TODO: might be worth checking if sub is HashTrieMap (-> monomorphic call site)
val subNew = sub.removed0(key, hash, level + 5)
if (sub eq subNew) this
else if (subNew.isEmpty) {
val bitmapNew = bitmap ^ mask
if (bitmapNew != 0) {
val elemsNew = new Array[HashSet[A]](elems.length - 1)
Array.copy(elems, 0, elemsNew, 0, offset)
Array.copy(elems, offset + 1, elemsNew, offset, elems.length - offset - 1)
val sizeNew = size - sub.size
// if we have only one child, which is not a HashTrieSet but a self-contained set like
// HashSet1 or HashSetCollision1, return the child instead
if (elemsNew.length == 1 && !elemsNew(0).isInstanceOf[HashTrieSet[_]])
elemsNew(0)
else
new HashTrieSet(bitmapNew, elemsNew, sizeNew)
} else
HashSet.empty[A]
} else {
val elemsNew = new Array[HashSet[A]](elems.length)
Array.copy(elems, 0, elemsNew, 0, elems.length)
elemsNew(offset) = subNew
val sizeNew = size + (subNew.size - sub.size)
new HashTrieSet(bitmap, elemsNew, sizeNew)
}
} else {
this
}
}
override def iterator = new TrieIterator[A](elems.asInstanceOf[Array[Iterable[A]]]) {
final override def getElem(cc: AnyRef): A = cc.asInstanceOf[HashSet1[A]].key
}
/*
def time(block: =>Unit) = { val t0 = System.nanoTime; block; println("elapsed: " + (System.nanoTime - t0)/1000000.0) }
var mOld = OldHashSet.empty[Int]
var mNew = HashSet.empty[Int]
time { for (i <- 0 until 100000) mOld = mOld + i }
time { for (i <- 0 until 100000) mOld = mOld + i }
time { for (i <- 0 until 100000) mOld = mOld + i }
time { for (i <- 0 until 100000) mNew = mNew + i }
time { for (i <- 0 until 100000) mNew = mNew + i }
time { for (i <- 0 until 100000) mNew = mNew + i }
time { mOld.iterator.foreach( p => ()) }
time { mOld.iterator.foreach( p => ()) }
time { mOld.iterator.foreach( p => ()) }
time { mNew.iterator.foreach( p => ()) }
time { mNew.iterator.foreach( p => ()) }
time { mNew.iterator.foreach( p => ()) }
*/
override def foreach[U](f: A => U): Unit = {
var i = 0;
while (i < elems.length) {
elems(i).foreach(f)
i += 1
}
}
}
@SerialVersionUID(2L) private class SerializationProxy[A,B](@transient private var orig: HashSet[A]) extends Serializable {
private def writeObject(out: java.io.ObjectOutputStream) {
val s = orig.size
out.writeInt(s)
for (e <- orig) {
out.writeObject(e)
}
}
private def readObject(in: java.io.ObjectInputStream) {
orig = empty
val s = in.readInt()
for (i <- 0 until s) {
val e = in.readObject().asInstanceOf[A]
orig = orig + e
}
}
private def readResolve(): AnyRef = orig
}
}
|