blob: 32c3dbc3d2238ec3c2f0af518b52ef70d14b2790 (
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
|
/* NSC -- new Scala compiler
* Copyright 2005-2012 LAMP/EPFL
* @author Martin Odersky
*/
package dotty.tools.dotc.util
object HashSet {
def apply[T >: Null <: AnyRef](): HashSet[T] = this(16)
def apply[T >: Null <: AnyRef](label: String): HashSet[T] = this(label, 16)
def apply[T >: Null <: AnyRef](initialCapacity: Int): HashSet[T] = this("No Label", initialCapacity)
def apply[T >: Null <: AnyRef](label: String, initialCapacity: Int): HashSet[T] =
new HashSet[T](label, initialCapacity)
}
class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) extends Set[T] with scala.collection.generic.Clearable {
private var used = 0
private var table = new Array[AnyRef](initialCapacity)
private def index(x: Int): Int = math.abs(x % table.length)
def hash(x: T): Int = x.hashCode
def size: Int = used
def clear(): Unit = {
used = 0
table = new Array[AnyRef](initialCapacity)
}
def findEntryOrUpdate(x: T): T = {
var h = index(hash(x))
var entry = table(h)
while (entry ne null) {
if (x == entry)
return entry.asInstanceOf[T]
h = index(h + 1)
entry = table(h)
}
addEntryAt(h, x)
}
private def addEntryAt(h: Int, x: T) = {
table(h) = x
used += 1
if (used > (table.length >> 2)) growTable()
x
}
def findEntry(x: T): T = {
var h = index(hash(x))
var entry = table(h)
while ((entry ne null) && x != entry) {
h = index(h + 1)
entry = table(h)
}
entry.asInstanceOf[T]
}
private var rover: Int = -1
protected def findEntryByHash(hashCode: Int): T = {
rover = index(hashCode)
nextEntryByHash(hashCode)
}
protected def nextEntryByHash(hashCode: Int): T = {
var entry = table(rover)
while (entry ne null) {
rover = index(rover + 1)
if (hash(entry.asInstanceOf[T]) == hashCode) return entry.asInstanceOf[T]
entry = table(rover)
}
null
}
protected def addEntryAfterScan(x: T): T = addEntryAt(rover, x)
def addEntry(x: T): Unit = {
var h = index(hash(x))
var entry = table(h)
while (entry ne null) {
if (x == entry) return
h = index(h + 1)
entry = table(h)
}
table(h) = x
used += 1
if (used > (table.length >> 2)) growTable()
}
def addEntries(xs: TraversableOnce[T]): Unit = {
xs foreach addEntry
}
def iterator = new Iterator[T] {
private var i = 0
def hasNext: Boolean = {
while (i < table.length && (table(i) eq null)) i += 1
i < table.length
}
def next(): T =
if (hasNext) { i += 1; table(i - 1).asInstanceOf[T] }
else null
}
private def addOldEntry(x: T): Unit = {
var h = index(hash(x))
var entry = table(h)
while (entry ne null) {
h = index(h + 1)
entry = table(h)
}
table(h) = x
}
private def growTable(): Unit = {
val oldtable = table
val growthFactor =
if (table.length <= initialCapacity) 8
else if (table.length <= (initialCapacity * 8)) 4
else 2
table = new Array[AnyRef](table.length * growthFactor)
var i = 0
while (i < oldtable.length) {
val entry = oldtable(i)
if (entry ne null) addOldEntry(entry.asInstanceOf[T])
i += 1
}
}
override def toString() = "HashSet %s(%d / %d)".format(label, used, table.length)
}
|
