/
LinkedHashSet.scala
177 lines (148 loc) · 4.98 KB
/
LinkedHashSet.scala
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
/*
* Scala (https://www.scala-lang.org)
*
* Copyright EPFL and Lightbend, Inc.
*
* Licensed under Apache License 2.0
* (http://www.apache.org/licenses/LICENSE-2.0).
*
* See the NOTICE file distributed with this work for
* additional information regarding copyright ownership.
*/
package scala
package collection
package mutable
import scala.annotation.nowarn
import scala.collection.generic.DefaultSerializable
/** This class implements mutable sets using a hashtable.
* The iterator and all traversal methods of this class visit elements in the order they were inserted.
*
* @tparam A the type of the elements contained in this set.
*
* @define Coll `LinkedHashSet`
* @define coll linked hash set
* @define mayNotTerminateInf
* @define willNotTerminateInf
* @define orderDependent
* @define orderDependentFold
*/
class LinkedHashSet[A]
extends AbstractSet[A]
with SetOps[A, LinkedHashSet, LinkedHashSet[A]]
with StrictOptimizedIterableOps[A, LinkedHashSet, LinkedHashSet[A]]
with IterableFactoryDefaults[A, LinkedHashSet]
with DefaultSerializable {
override def iterableFactory: IterableFactory[LinkedHashSet] = LinkedHashSet
// stepper is not overridden to use XTableStepper because that stepper would not return the
// elements in insertion order
type Entry = LinkedHashSet.Entry[A]
@transient protected var firstEntry: Entry = null
@transient protected var lastEntry: Entry = null
@transient private[this] var table: HashTable[A, AnyRef, Entry] = newHashTable
// Used by scala-java8-compat (private[mutable] erases to public, so Java code can access it)
private[mutable] def getTable: HashTable[A, AnyRef, Entry] = table
private def newHashTable =
new HashTable[A, AnyRef, Entry] {
def createNewEntry(key: A, value: AnyRef) = {
val e = new Entry(key)
if (firstEntry eq null) firstEntry = e
else { lastEntry.later = e; e.earlier = lastEntry }
lastEntry = e
e
}
override def foreachEntry[U](f: Entry => U): Unit = {
var cur = firstEntry
while (cur ne null) {
f(cur)
cur = cur.later
}
}
}
override def last: A =
if (size > 0) lastEntry.key
else throw new NoSuchElementException("Cannot call .last on empty LinkedHashSet")
override def lastOption: Option[A] =
if (size > 0) Some(lastEntry.key)
else None
override def head: A =
if (size > 0) firstEntry.key
else throw new NoSuchElementException("Cannot call .head on empty LinkedHashSet")
override def headOption: Option[A] =
if (size > 0) Some(firstEntry.key)
else None
override def size: Int = table.tableSize
override def knownSize: Int = size
override def isEmpty: Boolean = size == 0
def contains(elem: A): Boolean = table.findEntry(elem) ne null
def addOne(elem: A): this.type = {
table.findOrAddEntry(elem, null)
this
}
def subtractOne(elem: A): this.type = {
remove(elem)
this
}
override def remove(elem: A): Boolean = {
val e = table.removeEntry(elem)
if (e eq null) false
else {
if (e.earlier eq null) firstEntry = e.later
else e.earlier.later = e.later
if (e.later eq null) lastEntry = e.earlier
else e.later.earlier = e.earlier
e.earlier = null // Null references to prevent nepotism
e.later = null
true
}
}
def iterator: Iterator[A] = new AbstractIterator[A] {
private[this] var cur = firstEntry
def hasNext = cur ne null
def next() =
if (hasNext) { val res = cur.key; cur = cur.later; res }
else Iterator.empty.next()
}
override def foreach[U](f: A => U): Unit = {
var cur = firstEntry
while (cur ne null) {
f(cur.key)
cur = cur.later
}
}
override def clear(): Unit = {
table.clearTable()
firstEntry = null
lastEntry = null
}
private def writeObject(out: java.io.ObjectOutputStream): Unit = {
out.defaultWriteObject()
table.serializeTo(out, { e => out.writeObject(e.key) })
}
private def readObject(in: java.io.ObjectInputStream): Unit = {
in.defaultReadObject()
table = newHashTable
table.init(in, table.createNewEntry(in.readObject().asInstanceOf[A], null))
}
@nowarn("""cat=deprecation&origin=scala\.collection\.Iterable\.stringPrefix""")
override protected[this] def stringPrefix = "LinkedHashSet"
}
/** $factoryInfo
* @define Coll `LinkedHashSet`
* @define coll linked hash set
*/
@SerialVersionUID(3L)
object LinkedHashSet extends IterableFactory[LinkedHashSet] {
override def empty[A]: LinkedHashSet[A] = new LinkedHashSet[A]
def from[E](it: collection.IterableOnce[E]) =
it match {
case lhs: LinkedHashSet[E] => lhs
case _ => Growable.from(empty[E], it)
}
def newBuilder[A] = new GrowableBuilder(empty[A])
/** Class for the linked hash set entry, used internally.
*/
private[mutable] final class Entry[A](val key: A) extends HashEntry[A, Entry[A]] {
var earlier: Entry[A] = null
var later: Entry[A] = null
}
}