blob: 13bd8386a32b2cbaf8ca1c6fde7a3342e02ff9d5 (
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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection.immutable
/** The canonical factory methods for <a href="HashSet.html">immutable HashSet's<la>.
*
* @author Martin Odersky
* @version 2.0, 19/01/2007
*/
object HashSet {
/** The empty set of this type.
*/
def empty[A] = new HashSet[A]
/** The canonical factory for this type
*/
def apply[A](elems: A*) = empty[A] ++ elems
}
/** This class implements immutable sets using a hash table.
*
* @author Martin Odersky
* @version 2.0, 19/01/2007
*/
@serializable
class HashSet[A] extends Set[A] with mutable.FlatHashTable[A] {
protected var later: HashSet[A] = null
protected var changedElem: A = _
protected var deleted: Boolean = _
def empty[C]: Set[C] = new EmptySet[C]
def contains(elem: A): Boolean = synchronized {
var m = this
var cnt = 0
while (m.later != null) {
if (elem == m.changedElem) return m.deleted
cnt = cnt + 1
m = m.later
}
if (cnt > logLimit) makeCopy(m)
m.containsEntry(elem)
}
def + (elem: A): Set[A] = synchronized {
makeCopyIfUpdated()
if (containsEntry(elem)) this
else {
markUpdated(elem, false)
later addEntry elem
later
}
}
def - (elem: A): Set[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 = tableSize
while (m.later != null) {
if (m.deleted) s = s + 1 else s = s - 1
cnt = cnt + 1
m = m.later
}
if (cnt > logLimit) makeCopy(m)
s
}
override def elements = synchronized {
makeCopyIfUpdated()
super.elements
}
private def logLimit: Int = Math.sqrt(table.length.toDouble).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 Array[AnyRef](last.table.length)
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)
}
}
|
