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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2013, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala
package collection
package immutable
import generic._
import scala.annotation.tailrec
/**
* $factoryInfo
*
* Note that each element insertion takes O(n) time, which means that creating a list map with
* n elements will take O(n^2^) time. This makes the builder suitable only for a small number of
* elements.
*
* @see [[http://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes.html#list_maps "Scala's Collection Library overview"]]
* section on `List Maps` for more information.
* @since 1
* @define Coll ListMap
* @define coll list map
*/
object ListMap extends ImmutableMapFactory[ListMap] {
/**
* $mapCanBuildFromInfo
*/
implicit def canBuildFrom[A, B]: CanBuildFrom[Coll, (A, B), ListMap[A, B]] =
new MapCanBuildFrom[A, B]
def empty[A, B]: ListMap[A, B] = EmptyListMap.asInstanceOf[ListMap[A, B]]
@SerialVersionUID(-8256686706655863282L)
private object EmptyListMap extends ListMap[Any, Nothing]
}
/**
* This class implements immutable maps using a list-based data structure. List map iterators and
* traversal methods visit key-value pairs in the order whey were first inserted.
*
* Entries are stored internally in reversed insertion order, which means the newest key is at the
* head of the list. As such, methods such as `head` and `tail` are O(n), while `last` and `init`
* are O(1). Other operations, such as inserting or removing entries, are also O(n), which makes
* this collection suitable only for a small number of elements.
*
* Instances of `ListMap` represent empty maps; they can be either created by calling the
* constructor directly, or by applying the function `ListMap.empty`.
*
* @tparam A the type of the keys contained in this list map
* @tparam B the type of the values associated with the keys
*
* @author Matthias Zenger
* @author Martin Odersky
* @version 2.0, 01/01/2007
* @since 1
* @define Coll ListMap
* @define coll list map
* @define mayNotTerminateInf
* @define willNotTerminateInf
*/
@SerialVersionUID(301002838095710379L)
sealed class ListMap[A, +B] extends AbstractMap[A, B]
with Map[A, B]
with MapLike[A, B, ListMap[A, B]]
with Serializable {
override def empty = ListMap.empty
override def size: Int = 0
override def isEmpty: Boolean = true
def get(key: A): Option[B] = None
override def updated[B1 >: B](key: A, value: B1): ListMap[A, B1] = new Node[B1](key, value)
def +[B1 >: B](kv: (A, B1)): ListMap[A, B1] = new Node[B1](kv._1, kv._2)
def -(key: A): ListMap[A, B] = this
override def ++[B1 >: B](xs: GenTraversableOnce[(A, B1)]): ListMap[A, B1] =
if (xs.isEmpty) this
else ((repr: ListMap[A, B1]) /: xs) (_ + _)
def iterator: Iterator[(A, B)] = {
def reverseList = {
var curr: ListMap[A, B] = this
var res: List[(A, B)] = Nil
while (!curr.isEmpty) {
res = (curr.key, curr.value) :: res
curr = curr.next
}
res
}
reverseList.iterator
}
protected def key: A = throw new NoSuchElementException("key of empty map")
protected def value: B = throw new NoSuchElementException("value of empty map")
protected def next: ListMap[A, B] = throw new NoSuchElementException("next of empty map")
override def stringPrefix = "ListMap"
/**
* Represents an entry in the `ListMap`.
*/
@SerialVersionUID(-6453056603889598734L)
protected class Node[B1 >: B](override protected val key: A,
override protected val value: B1) extends ListMap[A, B1] with Serializable {
override def size: Int = sizeInternal(this, 0)
@tailrec private[this] def sizeInternal(cur: ListMap[A, B1], acc: Int): Int =
if (cur.isEmpty) acc
else sizeInternal(cur.next, acc + 1)
override def isEmpty: Boolean = false
override def apply(k: A): B1 = applyInternal(this, k)
@tailrec private[this] def applyInternal(cur: ListMap[A, B1], k: A): B1 =
if (cur.isEmpty) throw new NoSuchElementException("key not found: " + k)
else if (k == cur.key) cur.value
else applyInternal(cur.next, k)
override def get(k: A): Option[B1] = getInternal(this, k)
@tailrec private[this] def getInternal(cur: ListMap[A, B1], k: A): Option[B1] =
if (cur.isEmpty) None
else if (k == cur.key) Some(cur.value)
else getInternal(cur.next, k)
override def contains(k: A): Boolean = containsInternal(this, k)
@tailrec private[this] def containsInternal(cur: ListMap[A, B1], k: A): Boolean =
if(cur.isEmpty) false
else if (k == cur.key) true
else containsInternal(cur.next, k)
override def updated[B2 >: B1](k: A, v: B2): ListMap[A, B2] = {
val m = this - k
new m.Node[B2](k, v)
}
override def +[B2 >: B1](kv: (A, B2)): ListMap[A, B2] = {
val m = this - kv._1
new m.Node[B2](kv._1, kv._2)
}
override def -(k: A): ListMap[A, B1] = removeInternal(k, this, Nil)
@tailrec private[this] def removeInternal(k: A, cur: ListMap[A, B1], acc: List[ListMap[A, B1]]): ListMap[A, B1] =
if (cur.isEmpty) acc.last
else if (k == cur.key) (cur.next /: acc) { case (t, h) => new t.Node(h.key, h.value) }
else removeInternal(k, cur.next, cur :: acc)
override protected def next: ListMap[A, B1] = ListMap.this
override def last: (A, B1) = (key, value)
override def init: ListMap[A, B1] = next
}
}
|
