mambo.core.AssociativeArray source code

1 /**
2  * Copyright: Copyright (c) 2008-2012 Jacob Carlborg. All rights reserved.
3  * Authors: Jacob Carlborg
4  * Version: Initial created: 2008
5  * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0)
6  */
7 module mambo.core.AssociativeArray;
8 
9 import tango.core.Exception : NoSuchElementException;
10 
11 import mambo.util.Traits;
12 
13 /**
14  * Returns the value to which the specified key is mapped,
15  * or ($D_CODE null) if this associative array contains no mapping for the key.
16  *
17  * $(P More formally, if the specified associative array contains a mapping from a key
18  * $(D_CODE k) to a value $(D_CODE v) such that $(D_CODE (key==null ? k==null :
19  * key.equals(k))), then this method returns $(D_CODE v); otherwise
20  * it returns $(D_CODE null).  (There can be at most one such mapping.))
21  *
22  * Params:
23  *     aa = the associative array to get the value from
24  *     key = the key whose associated value is to be returned
25  *
26  *
27  * Returns: the value to which the specified key is mapped, or
28  * 			$(D_CODE null) if this map contains no mapping for the key
29  *
30  * Throws: AssertException if any paramter is invalid
31  * 		   NoSuchElementException if the given key could not be found
32  */
33 V get (K, V) (V[K] aa, K key)
34 in
35 {
36 	assert(aa.length > 0, "mambo.collection.AssociativeArray.get: The length of the associative array was 0");
37 }
38 body
39 {
40 	if (key in aa)
41 		return aa[key];
42 
43 	else
44 		throw new NoSuchElementException("The give key could not be found", __FILE__, __LINE__);
45 }
46 
47 /**
48  * Associates the specified value with the specified key in the specified
49  * associative array. If the associative array previously contained a mapping for
50  * the key, the old value is replaced by the specified value.  (An associative array
51  * <tt>aa</tt> is said to contain a mapping for a key <tt>k</tt> if and only
52  * if $(LINK2 #containsKey(Object), m.containsKey(k)) would return
53  * <tt>true</tt>.)
54  *
55  * Params:
56  *     aa = the associative array to add the key/value pair to
57  *     key = key with which the specified value is to be associated
58  *     value = value to be associated with the specified key
59  *
60  * Returns: the previous value associated with <tt>key</tt>, or
61  *          or the newly associated value.
62  */
63 V put (K, V) (V[K] aa, K key, V value)
64 {
65 	if (key in aa)
66 	{
67 		V prevValue = aa[key];
68 		aa[key] = value;
69 
70 		return prevValue;
71 	}
72 
73 	return aa[key] = value;
74 }
75 
76 /**
77  * Associates the specified value with the specified key in the specified
78  * associative array. If the associative array previously contained a mapping for
79  * the key, the existing value associated for the given key will be return and the
80  * associative array is unchanged. (An associative array <tt>aa</tt> is said
81  * to contain a mapping for a key <tt>k</tt> if and only if
82  * $(LINK2 #containsKey(Object), m.containsKey(k)) would return <tt>true</tt>.)
83  *
84  * Params:
85  *     aa = the associative array to add the key/value pair to
86  *     key = key with which the specified value is to be associated
87  *     value = value to be associated with the specified key
88  *
89  * Returns: the previous value associated with <tt>key</tt>, or
90  *          or the newly associated value.
91  */
92 V insert (K, V) (V[K] aa, K key, V value)
93 {
94 	if (key in aa)
95 		return aa[key];
96 
97 	return aa[key] = value;
98 }
99 
100 /**
101  * Associates the specified value with the specified key in the specified
102  * multimap. If the multimap previously contained a mapping for
103  * the key, the existing value associated for the given key will be return and the
104  * multimap is unchanged. (An multimap <tt>mm</tt> is said
105  * to contain a mapping for a key <tt>k</tt> if and only if
106  * $(LINK2 #containsKey(Object), m.containsKey(k)) would return <tt>true</tt>.)
107  *
108  * Params:
109  *     mm = the multimap to add the key/value pair to
110  *     key = key with which the specified value is to be associated
111  *     value = value to be associated with the specified key
112  *
113  * Returns: the previous value associated with <tt>key</tt>, or
114  *          or the newly associated value.
115  */
116 V insert (K, V) (V[][K] mm, K key, V value)
117 {
118 	if (key in aa)
119 		return aa[key];
120 
121 	return aa[key] ~= value;
122 }
123 
124 /**
125  * Removes the mapping for a key from the specified
126  * associative array if it is present. More formally,
127  * if the associative array contains a mapping
128  * from key <tt>k</tt> to value <tt>v</tt> such that
129  * $(D_CODE (key==null ?  k==null : key.equals(k))), that mapping
130  * is removed.  (The associative array can contain at most one such mapping.)
131  *
132  * $(P Returns the value to which the associative array previously associated the key,
133  * or <tt>null</tt> if the map contained no mapping for the key.)
134  *
135  * Params:
136  *     aa = the associative array to remove the key/value pair from
137  *     key = key whose mapping is to be removed from the associative array
138  *
139  * Returns:
140  */
141 V remove (K, V) (V[K] aa, K key)
142 {
143 	if (key in aa)
144 	{
145 		V v = aa[key];
146 		aa.remove(k);
147 
148 		return v;
149 	}
150 
151 	else
152 		throw new NoSuchElementException("The give key could not be found", __FILE__, __LINE__);
153 }
154 
155 /**
156  * Returns <tt>true</tt> if the specified
157  * associative array contains no key-value mappings.
158  *
159  * Params:
160  *     aa = the associative array to check if it's empty
161  *
162  * Returns: <tt>true</tt> if the specified
163  * 			associative array contains no key-value mappings
164  */
165 bool isEmpty (K, V) (V[K] aa)
166 {
167 	return aa.length == 0;
168 }
169 
170 /**
171  * Returns the number of key-value mappings in
172  * the specified associative array
173  *
174  * Params:
175  *     aa = the associative array to get the number of key-value mappings from
176  *
177  * Returns: the number of key-value mappings in the associative array
178  */
179 int size (K, V) (V[K] aa)
180 {
181 	aa.length;
182 }
183 
184 /**
185  * Returns value to lower bound
186  *
187  * associative array. If the associative array previously contained a mapping for
188  *
189  * Returns the value of the key pointing to the first element in the container
190  * whose key does not compare less than key, i.e. it is either equal or greater.
191  *
192  * Params:
193  *     aa = the associative array to get the lower bound of
194  *     key = the key to be compared
195  *
196  * Returns: the value of the key of the first element in the container whose
197  * 			key does not compare less than key.
198  *
199  * Throws: NoSuchElementException if the given key could not be found
200  */
201 V lowerBound (K, V) (V[K] aa, K key)
202 {
203 	foreach (k, v ; aa)
204 		if (!(k < key))
205 			return v;
206 
207 	throw new NoSuchElementException("The give key could not be found", __FILE__, __LINE__);
208 }
209 
210 /**
211  * Returns the bounds of a range that includes all the elements in the
212  * container with a key that compares equal to key.
213  *
214  * In map containers,  where no duplicate keys are allowed, the range
215  * will include one element at most. If key does not match any key in
216  * the container, the range returned has a length of zero.
217  *
218  * Params:
219  *     mm = the multimap to get the range from
220  *     key = the key value to be compared
221  *
222  * Returns: an array containing all the values the matched the key
223  */
224 V[] equalRange (K, V) (V[][K] mm, K key)
225 {
226 	if (key in mm)
227 		return mm[key];
228 
229 	else
230 		return [];
231 }
232 
233 /**
234  * Returns the bounds of a range that includes all the elements in the
235  * container with a key that compares equal to key.
236  *
237  * In map containers,
238  * where no duplicate keys are allowed, the range will include one
239  * element at most. If key does not match any key in the container, the range
240  * returned has a length of zero.
241  *
242  * Params:
243  *     aa = the associative array to get the range from
244  *     key = the key value to be compared
245  *
246  * Returns: an array containing all the values the matched the key
247  */
248 V[] equalRange (K, V) (V[K] aa, K key)
249 {
250 	if (key in aa)
251 		return [aa[key]];
252 
253 	else
254 		return [];
255 }
256 
257 // This is a function private to this package. From some reason it cannot be accessible if
258 // it's marked with "package".
259 bool _anyAA (alias predicate, AA) (AA aa)
260 	if (isAssociativeArray!(AA) && isAssociativeArrayPredicate!(predicate, AA))
261 {
262 	foreach (k, v ; aa)
263 		if (predicate(k, v))
264 			return true;
265 
266 	return false;
267 }
268 
269 // This is a function private to this package. From some reason it cannot be accessible if
270 // it's marked with "package".
271 auto _findAA (alias predicate, AA) (AA aa)
272 	if (isAssociativeArray!(AA) && isAssociativeArrayPredicate!(predicate, AA))
273 {
274 	alias KeyTypeOfAssociativeArray!(AA) K;
275 	alias ValueTypeOfAssociativeArray!(AA) V;
276 	alias KeyValue!(K, V) Pair;
277 
278 	foreach (k, v ; aa)
279 		if (predicate(k, v))
280 			return Pair(k, v, false);
281 
282 	return Pair.init;
283 }
284 
285 struct KeyValue (K, V)
286 {
287 	K key;
288 	V value;
289 	private bool isEmpty_ = true;
290 
291 	alias any this;
292 
293 	@property bool isEmpty ()
294 	{
295 		return isEmpty_;
296 	}
297 
298 	@property bool any ()
299 	{
300 		return !isEmpty;
301 	}
302 }
303 
304 auto _mapAA (alias func, AA) (AA aa) if (isAssociativeArray!(AA))
305 {
306 	alias KeyTypeOfAssociativeArray!(AA) K;
307 	alias ValueTypeOfAssociativeArray!(AA) V;
308 
309 	alias typeof(func(K.init, V.init)) ReturnType;
310 
311 	ReturnType[] result;
312 	result.reserve(aa.length);
313 
314 	foreach (k, v ; aa)
315 		result ~= func(k, v);
316 
317 	return result;
318 }