forked from typelevel/cats-effect
-
Notifications
You must be signed in to change notification settings - Fork 0
/
LinkedMap.scala
74 lines (62 loc) · 2.56 KB
/
LinkedMap.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
/*
* Copyright (c) 2017-2018 The Typelevel Cats-effect Project Developers
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package cats
package effect
package internals
import scala.collection.immutable.LongMap
/**
* A Map which tracks the insertion order of entries, so that entries may be
* traversed in the order they were inserted. Alternative to `ListMap` that
* has better asymptotic performance at the cost of more memory usage.
*/
private[effect] class LinkedMap[K, +V](
val entries: Map[K, (V, Long)],
private[this] val insertionOrder: LongMap[K],
private[this] val nextId: Long) {
/** Returns `true` if this map is empty, or `false` otherwise. */
def isEmpty: Boolean =
entries.isEmpty
/** Returns a new map with the supplied key/value added. */
def updated[V2 >: V](k: K, v: V2): LinkedMap[K, V2] = {
val insertionOrderOldRemoved = entries.get(k).fold(insertionOrder) { case (_, id) => insertionOrder - id }
new LinkedMap(entries.updated(k, (v, nextId)), insertionOrderOldRemoved.updated(nextId, k), nextId + 1)
}
/** Removes the element at the specified key. */
def -(k: K): LinkedMap[K, V] =
new LinkedMap(entries - k,
entries
.get(k)
.map { case (_, id) => insertionOrder - id }
.getOrElse(insertionOrder),
nextId)
/** The keys in this map, in the order they were added. */
def keys: Iterable[K] = insertionOrder.values
/** The values in this map, in the order they were added. */
def values: Iterable[V] = keys.flatMap(k => entries.get(k).toList.map(_._1))
/** Pulls the first value from this `LinkedMap`, in FIFO order. */
def dequeue: (V, LinkedMap[K, V]) = {
val k = insertionOrder.head._2
(entries(k)._1, this - k)
}
override def toString: String =
keys.zip(values).mkString("LinkedMap(", ", ", ")")
}
private[effect] object LinkedMap {
def empty[K, V]: LinkedMap[K, V] =
emptyRef.asInstanceOf[LinkedMap[K, V]]
private val emptyRef =
new LinkedMap[Nothing, Nothing](Map.empty, LongMap.empty, 0)
}