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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection.immutable
/** The canonical factory of <a href="ListMap.html">ListMap</a>'s */
object ListMap {
/** The empty map of this type
* @deprecated use <code>empty</code> instead
*/
@deprecated
def Empty[A, B] = new ListMap[A, B]
/** The empty map of this type */
def empty[A, B] = new ListMap[A, B]
/** The canonical factory for this type
*/
def apply[A, B](elems: (A, B)*) = empty[A, B] ++ elems
}
/** This class implements immutable maps using a list-based data
* structure. Instances of <code>ListMap</code> represent
* empty maps; they can be either created by calling the constructor
* directly, or by applying the function <code>ListMap.empty</code>.
*
* @author Matthias Zenger
* @author Martin Oderskty
* @version 2.0, 01/01/2007
*/
@serializable
class ListMap[A, +B] extends Map[A, B] {
/** Returns a <code>new ListMap</code> instance mapping keys of the
* same type to values of type <code>C</code>.
*/
def empty[C] = ListMap.empty[A, C]
/** Returns the number of mappings in this map.
*
* @return number of mappings in this map.
*/
def size: Int = 0
/** Checks if this map maps <code>key</code> to a value and return the
* value if it exists.
*
* @param key the key of the mapping of interest
* @return the value of the mapping, if it exists
*/
def get(key: A): Option[B] = None
/** This method allows one to create a new map with an
* additional mapping from <code>key</code>
* to <code>value</code>. If the map contains already a
* mapping for <code>key</code>, it will be overridden by this
* function.
*
* @param key the key element of the updated entry.
* @param value the value element of the updated entry.
*/
def update [B1 >: B](key: A, value: B1): ListMap[A, B1] = new Node(key, value)
/** This creates a new mapping without the given <code>key</code>.
* If the map does not contain a mapping for the given key, the
* method returns the same map.
*
* @param key a map without a mapping for the given key.
*/
def - (key: A): ListMap[A, B] = this
/** Returns an iterator over key-value pairs.
*/
def elements: Iterator[(A,B)] =
new Iterator[(A,B)] {
var self: ListMap[A,B] = ListMap.this
def hasNext = !self.isEmpty
def next: (A,B) =
if (!hasNext) throw new NoSuchElementException("next on empty iterator")
else { val res = (self.key, self.value); self = self.next; res }
}.toList.reverse.elements
protected def key: A = throw new NoSuchElementException("empty map")
protected def value: B = throw new NoSuchElementException("empty map")
protected def next: ListMap[A, B] = throw new NoSuchElementException("empty map")
@serializable
protected class Node[B1 >: B](override protected val key: A,
override protected val value: B1) extends ListMap[A, B1] {
/** Returns the number of mappings in this map.
*
* @return number of mappings.
*/
override def size: Int = next.size + 1
/** Is this an empty map?
*
* @return true, iff the map is empty.
*/
override def isEmpty: Boolean = false
/** Retrieves the value which is associated with the given key. This
* method throws an exception if there is no mapping from the given
* key to a value.
*
* @param key the key
* @return the value associated with the given key.
*/
override def apply(k: A): B1 = if (k == key) value else next(k)
/** Checks if this map maps <code>key</code> to a value and return the
* value if it exists.
*
* @param key the key of the mapping of interest
* @return the value of the mapping, if it exists
*/
override def get(k: A): Option[B1] =
if (k == key) Some(value) else next.get(k)
/** This method allows one to create a new map with an
* additional mapping from <code>key</code>
* to <code>value</code>. If the map contains already a
* mapping for <code>key</code>, it will be overridden by this
* function.
*
* @param k ...
* @param v ...
*/
override def update [B2 >: B1](k: A, v: B2): ListMap[A, B2] = {
val m = if (contains(k)) this - k else this
new m.Node(k, v)
}
/** Creates a new mapping without the given <code>key</code>.
* If the map does not contain a mapping for the given key, the
* method returns the same map.
*
* @param k ...
* @return ...
*/
override def - (k: A): ListMap[A, B1] =
if (k == key)
next
else {
val tail = next - k
if (tail eq next) this
else new tail.Node(key, value)
}
override protected def next: ListMap[A,B1] = ListMap.this
}
}
|
