1 /*
2  * Hunt - A refined core library for D programming language.
3  *
4  * Copyright (C) 2018-2019 HuntLabs
5  *
6  * Website: https://www.huntlabs.net/
7  *
8  * Licensed under the Apache-2.0 License.
9  *
10  */
11 
12 module hunt.collection.Map;
13 
14 import hunt.collection.Collection;
15 import hunt.collection.Set;
16 import hunt.Exceptions;
17 import hunt.Functions;
18 import hunt.Object;
19 import hunt.util.Common;
20 
21 import std.range.interfaces : InputRange;
22 
23 
24 /**
25 */
26 interface Map(K,V) : Iterable!(K,V), IObject, Cloneable {
27     // Query Operations
28 
29     /**
30      * Returns the number of key-value mappings in this map.  If the
31      * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
32      * <tt>Integer.MAX_VALUE</tt>.
33      *
34      * @return the number of key-value mappings in this map
35      */
36     int size();
37 
38     /**
39      * Returns <tt>true</tt> if this map contains no key-value mappings.
40      *
41      * @return <tt>true</tt> if this map contains no key-value mappings
42      */
43     bool isEmpty();
44 
45     /**
46      * Returns <tt>true</tt> if this map contains a mapping for the specified
47      * key.  More formally, returns <tt>true</tt> if and only if
48      * this map contains a mapping for a key <tt>k</tt> such that
49      * <tt>(key==null ? k==null : key.equals(k))</tt>.  (There can be
50      * at most one such mapping.)
51      *
52      * @param key key whose presence in this map is to be tested
53      * @return <tt>true</tt> if this map contains a mapping for the specified
54      *         key
55      * @throws ClassCastException if the key is of an inappropriate type for
56      *         this map
57      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
58      * @throws NullPointerException if the specified key is null and this map
59      *         does not permit null keys
60      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
61      */
62     bool containsKey(K key);
63 
64     /**
65      * Returns <tt>true</tt> if this map maps one or more keys to the
66      * specified value.  More formally, returns <tt>true</tt> if and only if
67      * this map contains at least one mapping to a value <tt>v</tt> such that
68      * <tt>(value==null ? v==null : value.equals(v))</tt>.  This operation
69      * will probably require time linear in the map size for most
70      * implementations of the <tt>Map</tt> interface.
71      *
72      * @param value value whose presence in this map is to be tested
73      * @return <tt>true</tt> if this map maps one or more keys to the
74      *         specified value
75      * @throws ClassCastException if the value is of an inappropriate type for
76      *         this map
77      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
78      * @throws NullPointerException if the specified value is null and this
79      *         map does not permit null values
80      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
81      */
82     bool containsValue(V value);
83 
84     /**
85      * Returns the value to which the specified key is mapped,
86      * or {@code null} if this map contains no mapping for the key.
87      *
88      * <p>More formally, if this map contains a mapping from a key
89      * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
90      * key.equals(k))}, then this method returns {@code v}; otherwise
91      * it returns {@code null}.  (There can be at most one such mapping.)
92      *
93      * <p>If this map permits null values, then a return value of
94      * {@code null} does not <i>necessarily</i> indicate that the map
95      * contains no mapping for the key; it's also possible that the map
96      * explicitly maps the key to {@code null}.  The {@link #containsKey
97      * containsKey} operation may be used to distinguish these two cases.
98      *
99      * @param key the key whose associated value is to be returned
100      * @return the value to which the specified key is mapped, or
101      *         {@code null} if this map contains no mapping for the key
102      * @throws ClassCastException if the key is of an inappropriate type for
103      *         this map
104      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
105      * @throws NullPointerException if the specified key is null and this map
106      *         does not permit null keys
107      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
108      */
109     V get(K key);
110 
111     V opIndex(K key);
112 
113     // Modification Operations
114 
115     /**
116      * Associates the specified value with the specified key in this map
117      * (optional operation).  If the map previously contained a mapping for
118      * the key, the old value is replaced by the specified value.  (A map
119      * <tt>m</tt> is said to contain a mapping for a key <tt>k</tt> if and only
120      * if {@link #containsKey(Object) m.containsKey(k)} would return
121      * <tt>true</tt>.)
122      *
123      * @param key key with which the specified value is to be associated
124      * @param value value to be associated with the specified key
125      * @return the previous value associated with <tt>key</tt>, or
126      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
127      *         (A <tt>null</tt> return can also indicate that the map
128      *         previously associated <tt>null</tt> with <tt>key</tt>,
129      *         if the implementation supports <tt>null</tt> values.)
130      * @throws UnsupportedOperationException if the <tt>put</tt> operation
131      *         is not supported by this map
132      * @throws ClassCastException if the class of the specified key or value
133      *         prevents it from being stored in this map
134      * @throws NullPointerException if the specified key or value is null
135      *         and this map does not permit null keys or values
136      * @throws IllegalArgumentException if some property of the specified key
137      *         or value prevents it from being stored in this map
138      */
139     V put(K key, V value);
140 
141     /**
142      * Removes the mapping for a key from this map if it is present
143      * (optional operation).   More formally, if this map contains a mapping
144      * from key <tt>k</tt> to value <tt>v</tt> such that
145      * <code>(key==null ?  k==null : key.equals(k))</code>, that mapping
146      * is removed.  (The map can contain at most one such mapping.)
147      *
148      * <p>Returns the value to which this map previously associated the key,
149      * or <tt>null</tt> if the map contained no mapping for the key.
150      *
151      * <p>If this map permits null values, then a return value of
152      * <tt>null</tt> does not <i>necessarily</i> indicate that the map
153      * contained no mapping for the key; it's also possible that the map
154      * explicitly mapped the key to <tt>null</tt>.
155      *
156      * <p>The map will not contain a mapping for the specified key once the
157      * call returns.
158      *
159      * @param key key whose mapping is to be removed from the map
160      * @return the previous value associated with <tt>key</tt>, or
161      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
162      * @throws UnsupportedOperationException if the <tt>remove</tt> operation
163      *         is not supported by this map
164      * @throws ClassCastException if the key is of an inappropriate type for
165      *         this map
166      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
167      * @throws NullPointerException if the specified key is null and this
168      *         map does not permit null keys
169      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
170      */
171     V remove(K key);
172 
173 
174     // Bulk Operations
175 
176     /**
177      * Copies all of the mappings from the specified map to this map
178      * (optional operation).  The effect of this call is equivalent to that
179      * of calling {@link #put(Object,Object) put(k, v)} on this map once
180      * for each mapping from key <tt>k</tt> to value <tt>v</tt> in the
181      * specified map.  The behavior of this operation is undefined if the
182      * specified map is modified while the operation is in progress.
183      *
184      * @param m mappings to be stored in this map
185      * @throws UnsupportedOperationException if the <tt>putAll</tt> operation
186      *         is not supported by this map
187      * @throws ClassCastException if the class of a key or value in the
188      *         specified map prevents it from being stored in this map
189      * @throws NullPointerException if the specified map is null, or if
190      *         this map does not permit null keys or values, and the
191      *         specified map contains null keys or values
192      * @throws IllegalArgumentException if some property of a key or value in
193      *         the specified map prevents it from being stored in this map
194      */
195     void putAll(Map!(K, V) m);
196 
197     /**
198      * Removes all of the mappings from this map (optional operation).
199      * The map will be empty after this call returns.
200      *
201      * @throws UnsupportedOperationException if the <tt>clear</tt> operation
202      *         is not supported by this map
203      */
204     void clear();
205 
206     // Views
207 
208     /**
209      * Returns a {@link Collection} view of the values contained in this map.
210      * The collection is backed by the map, so changes to the map are
211      * reflected in the collection, and vice-versa.  If the map is
212      * modified while an iteration over the collection is in progress
213      * (except through the iterator's own <tt>remove</tt> operation),
214      * the results of the iteration are undefined.  The collection
215      * supports element removal, which removes the corresponding
216      * mapping from the map, via the <tt>Iterator.remove</tt>,
217      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
218      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
219      * support the <tt>add</tt> or <tt>addAll</tt> operations.
220      *
221      * @return a collection view of the values contained in this map
222      */
223     // Collection!V values();
224     V[] values();
225 
226     string toString();
227 
228     
229     // Comparison and hashing
230 
231     /**
232      * Compares the specified object with this map for equality.  Returns
233      * <tt>true</tt> if the given object is also a map and the two maps
234      * represent the same mappings.  More formally, two maps <tt>m1</tt> and
235      * <tt>m2</tt> represent the same mappings if
236      * <tt>m1.entrySet().equals(m2.entrySet())</tt>.  This ensures that the
237      * <tt>equals</tt> method works properly across different implementations
238      * of the <tt>Map</tt> interface.
239      *
240      * @param o object to be compared for equality with this map
241      * @return <tt>true</tt> if the specified object is equal to this map
242      */
243     // bool opEquals(Object o);
244 
245     /**
246      * Returns the hash code value for this map.  The hash code of a map is
247      * defined to be the sum of the hash codes of each entry in the map's
248      * <tt>entrySet()</tt> view.  This ensures that <tt>m1.equals(m2)</tt>
249      * implies that <tt>m1.toHash()==m2.toHash()</tt> for any two maps
250      * <tt>m1</tt> and <tt>m2</tt>, as required by the general contract of
251      * {@link Object#toHash}.
252      *
253      * @return the hash code value for this map
254      * @see MapEntry#toHash()
255      * @see Object#equals(Object)
256      * @see #equals(Object)
257      */
258     size_t toHash() @trusted nothrow;
259 
260     // Defaultable methods
261 
262     /**
263      * Returns the value to which the specified key is mapped, or
264      * {@code defaultValue} if this map contains no mapping for the key.
265      *
266      * @implSpec
267      * The final implementation makes no guarantees about synchronization
268      * or atomicity properties of this method. Any implementation providing
269      * atomicity guarantees must override this method and document its
270      * concurrency properties.
271      *
272      * @param key the key whose associated value is to be returned
273      * @param defaultValue the final mapping of the key
274      * @return the value to which the specified key is mapped, or
275      * {@code defaultValue} if this map contains no mapping for the key
276      * @throws ClassCastException if the key is of an inappropriate type for
277      * this map
278      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
279      * @throws NullPointerException if the specified key is null and this map
280      * does not permit null keys
281      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
282      */
283     // final V getOrDefault(K key, V defaultValue) {
284     //     V v;
285     //     static if(is(V == class))
286     //     {            
287     //         return (((v = get(key)) !is null) || containsKey(key))
288     //             ? v
289     //             : defaultValue;
290     //     }
291     //     else
292     //     {
293     //         return containsKey(key) ? v : defaultValue;
294     //     }
295     // }
296 
297     /**
298      * Performs the given action for each entry in this map until all entries
299      * have been processed or the action throws an exception.   Unless
300      * otherwise specified by the implementing class, actions are performed in
301      * the order of entry set iteration (if an iteration order is specified.)
302      * Exceptions thrown by the action are relayed to the caller.
303      *
304      * @implSpec
305      * The final implementation is equivalent to, for this {@code map}:
306      * <pre> {@code
307      * for (MapEntry<K, V> entry : map.entrySet())
308      *     action.accept(entry.getKey(), entry.getValue());
309      * }</pre>
310      *
311      * The final implementation makes no guarantees about synchronization
312      * or atomicity properties of this method. Any implementation providing
313      * atomicity guarantees must override this method and document its
314      * concurrency properties.
315      *
316      * @param action The action to be performed for each entry
317      * @throws NullPointerException if the specified action is null
318      * @throws ConcurrentModificationException if an entry is found to be
319      * removed during iteration
320      */
321     int opApply(scope int delegate(ref K, ref V) dg);
322 
323     /// ditto
324     int opApply(scope int delegate(MapEntry!(K, V) entry) dg);
325 
326     InputRange!K byKey();
327 
328     InputRange!V byValue();
329 
330     /**
331      * Replaces each entry's value with the result of invoking the given
332      * function on that entry until all entries have been processed or the
333      * function throws an exception.  Exceptions thrown by the function are
334      * relayed to the caller.
335      *
336      * @implSpec
337      * <p>The final implementation is equivalent to, for this {@code map}:
338      * <pre> {@code
339      * for (MapEntry<K, V> entry : map.entrySet())
340      *     entry.setValue(function.apply(entry.getKey(), entry.getValue()));
341      * }</pre>
342      *
343      * <p>The final implementation makes no guarantees about synchronization
344      * or atomicity properties of this method. Any implementation providing
345      * atomicity guarantees must override this method and document its
346      * concurrency properties.
347      *
348      * @param function the function to apply to each entry
349      * @throws UnsupportedOperationException if the {@code set} operation
350      * is not supported by this map's entry set iterator.
351      * @throws ClassCastException if the class of a replacement value
352      * prevents it from being stored in this map
353      * @throws NullPointerException if the specified function is null, or the
354      * specified replacement value is null, and this map does not permit null
355      * values
356      * @throws ClassCastException if a replacement value is of an inappropriate
357      *         type for this map
358      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
359      * @throws NullPointerException if function or a replacement value is null,
360      *         and this map does not permit null keys or values
361      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
362      * @throws IllegalArgumentException if some property of a replacement value
363      *         prevents it from being stored in this map
364      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
365      * @throws ConcurrentModificationException if an entry is found to be
366      * removed during iteration
367      */
368     // final void replaceAll(BiFunction<K, V, V> function) {
369     //     Objects.requireNonNull(function);
370     //     for (MapEntry<K, V> entry : entrySet()) {
371     //         K k;
372     //         V v;
373     //         try {
374     //             k = entry.getKey();
375     //             v = entry.getValue();
376     //         } catch(IllegalStateException ise) {
377     //             // this usually means the entry is no longer in the map.
378     //             throw new ConcurrentModificationException(ise);
379     //         }
380 
381     //         // ise thrown from function is not a cme.
382     //         v = function.apply(k, v);
383 
384     //         try {
385     //             entry.setValue(v);
386     //         } catch(IllegalStateException ise) {
387     //             // this usually means the entry is no longer in the map.
388     //             throw new ConcurrentModificationException(ise);
389     //         }
390     //     }
391     // }
392 
393     /**
394      * If the specified key is not already associated with a value (or is mapped
395      * to {@code null}) associates it with the given value and returns
396      * {@code null}, else returns the current value.
397      *
398      * @implSpec
399      * The final implementation is equivalent to, for this {@code
400      * map}:
401      *
402      * <pre> {@code
403      * V v = map.get(key);
404      * if (v is null)
405      *     v = map.put(key, value);
406      *
407      * return v;
408      * }</pre>
409      *
410      * <p>The final implementation makes no guarantees about synchronization
411      * or atomicity properties of this method. Any implementation providing
412      * atomicity guarantees must override this method and document its
413      * concurrency properties.
414      *
415      * @param key key with which the specified value is to be associated
416      * @param value value to be associated with the specified key
417      * @return the previous value associated with the specified key, or
418      *         {@code null} if there was no mapping for the key.
419      *         (A {@code null} return can also indicate that the map
420      *         previously associated {@code null} with the key,
421      *         if the implementation supports null values.)
422      * @throws UnsupportedOperationException if the {@code put} operation
423      *         is not supported by this map
424      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
425      * @throws ClassCastException if the key or value is of an inappropriate
426      *         type for this map
427      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
428      * @throws NullPointerException if the specified key or value is null,
429      *         and this map does not permit null keys or values
430      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
431      * @throws IllegalArgumentException if some property of the specified key
432      *         or value prevents it from being stored in this map
433      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
434      */
435     V putIfAbsent(K key, V value);
436 
437     /**
438      * Removes the entry for the specified key only if it is currently
439      * mapped to the specified value.
440      *
441      * @implSpec
442      * The final implementation is equivalent to, for this {@code map}:
443      *
444      * <pre> {@code
445      * if (map.containsKey(key) && Objects.equals(map.get(key), value)) {
446      *     map.remove(key);
447      *     return true;
448      * } else
449      *     return false;
450      * }</pre>
451      *
452      * <p>The final implementation makes no guarantees about synchronization
453      * or atomicity properties of this method. Any implementation providing
454      * atomicity guarantees must override this method and document its
455      * concurrency properties.
456      *
457      * @param key key with which the specified value is associated
458      * @param value value expected to be associated with the specified key
459      * @return {@code true} if the value was removed
460      * @throws UnsupportedOperationException if the {@code remove} operation
461      *         is not supported by this map
462      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
463      * @throws ClassCastException if the key or value is of an inappropriate
464      *         type for this map
465      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
466      * @throws NullPointerException if the specified key or value is null,
467      *         and this map does not permit null keys or values
468      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
469      */
470     bool remove(K key, V value);
471 
472 
473     /**
474      * Replaces the entry for the specified key only if currently
475      * mapped to the specified value.
476      *
477      * @implSpec
478      * The final implementation is equivalent to, for this {@code map}:
479      *
480      * <pre> {@code
481      * if (map.containsKey(key) && Objects.equals(map.get(key), value)) {
482      *     map.put(key, newValue);
483      *     return true;
484      * } else
485      *     return false;
486      * }</pre>
487      *
488      * The final implementation does not throw NullPointerException
489      * for maps that do not support null values if oldValue is null unless
490      * newValue is also null.
491      *
492      * <p>The final implementation makes no guarantees about synchronization
493      * or atomicity properties of this method. Any implementation providing
494      * atomicity guarantees must override this method and document its
495      * concurrency properties.
496      *
497      * @param key key with which the specified value is associated
498      * @param oldValue value expected to be associated with the specified key
499      * @param newValue value to be associated with the specified key
500      * @return {@code true} if the value was replaced
501      * @throws UnsupportedOperationException if the {@code put} operation
502      *         is not supported by this map
503      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
504      * @throws ClassCastException if the class of a specified key or value
505      *         prevents it from being stored in this map
506      * @throws NullPointerException if a specified key or newValue is null,
507      *         and this map does not permit null keys or values
508      * @throws NullPointerException if oldValue is null and this map does not
509      *         permit null values
510      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
511      * @throws IllegalArgumentException if some property of a specified key
512      *         or value prevents it from being stored in this map
513      */
514     bool replace(K key, V oldValue, V newValue);
515 
516     /**
517      * Replaces the entry for the specified key only if it is
518      * currently mapped to some value.
519      *
520      * @implSpec
521      * The final implementation is equivalent to, for this {@code map}:
522      *
523      * <pre> {@code
524      * if (map.containsKey(key)) {
525      *     return map.put(key, value);
526      * } else
527      *     return null;
528      * }</pre>
529      *
530      * <p>The final implementation makes no guarantees about synchronization
531      * or atomicity properties of this method. Any implementation providing
532      * atomicity guarantees must override this method and document its
533      * concurrency properties.
534       *
535      * @param key key with which the specified value is associated
536      * @param value value to be associated with the specified key
537      * @return the previous value associated with the specified key, or
538      *         {@code null} if there was no mapping for the key.
539      *         (A {@code null} return can also indicate that the map
540      *         previously associated {@code null} with the key,
541      *         if the implementation supports null values.)
542      * @throws UnsupportedOperationException if the {@code put} operation
543      *         is not supported by this map
544      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
545      * @throws ClassCastException if the class of the specified key or value
546      *         prevents it from being stored in this map
547      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
548      * @throws NullPointerException if the specified key or value is null,
549      *         and this map does not permit null keys or values
550      * @throws IllegalArgumentException if some property of the specified key
551      *         or value prevents it from being stored in this map
552      */
553     V replace(K key, V value);
554 
555     /**
556      * If the specified key is not already associated with a value (or is mapped
557      * to {@code null}), attempts to compute its value using the given mapping
558      * function and enters it into this map unless {@code null}.
559      *
560      * <p>If the function returns {@code null} no mapping is recorded. If
561      * the function itself throws an (unchecked) exception, the
562      * exception is rethrown, and no mapping is recorded.  The most
563      * common usage is to construct a new object serving as an initial
564      * mapped value or memoized result, as in:
565      *
566      * <pre> {@code
567      * map.computeIfAbsent(key, k -> new Value(f(k)));
568      * }</pre>
569      *
570      * <p>Or to implement a multi-value map, {@code Map<K,Collection!V>},
571      * supporting multiple values per key:
572      *
573      * <pre> {@code
574      * map.computeIfAbsent(key, k -> new HashSet!V()).add(v);
575      * }</pre>
576      *
577      *
578      * @implSpec
579      * The final implementation is equivalent to the following steps for this
580      * {@code map}, then returning the current value or {@code null} if now
581      * absent:
582      *
583      * <pre> {@code
584      * if (map.get(key) is null) {
585      *     V newValue = mappingFunction.apply(key);
586      *     if (newValue !is null)
587      *         map.put(key, newValue);
588      * }
589      * }</pre>
590      *
591      * <p>The final implementation makes no guarantees about synchronization
592      * or atomicity properties of this method. Any implementation providing
593      * atomicity guarantees must override this method and document its
594      * concurrency properties. In particular, all implementations of
595      * subinterface {@link hunt.concurrency.ConcurrentMap} must document
596      * whether the function is applied once atomically only if the value is not
597      * present.
598      *
599      * @param key key with which the specified value is to be associated
600      * @param mappingFunction the function to compute a value
601      * @return the current (existing or computed) value associated with
602      *         the specified key, or null if the computed value is null
603      * @throws NullPointerException if the specified key is null and
604      *         this map does not support null keys, or the mappingFunction
605      *         is null
606      * @throws UnsupportedOperationException if the {@code put} operation
607      *         is not supported by this map
608      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
609      * @throws ClassCastException if the class of the specified key or value
610      *         prevents it from being stored in this map
611      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
612      */
613 
614     final V computeIfAbsent(K key, Function!(K, V) mappingFunction) {
615         assert(mappingFunction !is null);
616         
617         if (containsKey(key)) {
618             return get(key);
619         }
620         else {
621             V newValue = mappingFunction(key);
622             static if(is(V == class))
623             {
624                 if (newValue !is null) {
625                     put(key, newValue);
626                     return newValue;
627                 }
628                 else
629                     return V.init;
630             }
631             else
632             {
633                 put(key, newValue);
634                 return newValue;
635             }
636         }
637     }
638 
639 
640     /**
641      * If the value for the specified key is present and non-null, attempts to
642      * compute a new mapping given the key and its current mapped value.
643      *
644      * <p>If the function returns {@code null}, the mapping is removed.  If the
645      * function itself throws an (unchecked) exception, the exception is
646      * rethrown, and the current mapping is left unchanged.
647     *
648      * @implSpec
649      * The final implementation is equivalent to performing the following
650      * steps for this {@code map}, then returning the current value or
651      * {@code null} if now absent:
652      *
653      * <pre> {@code
654      * if (map.get(key) !is null) {
655      *     V oldValue = map.get(key);
656      *     V newValue = remappingFunction.apply(key, oldValue);
657      *     if (newValue !is null)
658      *         map.put(key, newValue);
659      *     else
660      *         map.remove(key);
661      * }
662      * }</pre>
663      *
664      * <p>The final implementation makes no guarantees about synchronization
665      * or atomicity properties of this method. Any implementation providing
666      * atomicity guarantees must override this method and document its
667      * concurrency properties. In particular, all implementations of
668      * subinterface {@link hunt.concurrency.ConcurrentMap} must document
669      * whether the function is applied once atomically only if the value is not
670      * present.
671      *
672      * @param key key with which the specified value is to be associated
673      * @param remappingFunction the function to compute a value
674      * @return the new value associated with the specified key, or null if none
675      * @throws NullPointerException if the specified key is null and
676      *         this map does not support null keys, or the
677      *         remappingFunction is null
678      * @throws UnsupportedOperationException if the {@code put} operation
679      *         is not supported by this map
680      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
681      * @throws ClassCastException if the class of the specified key or value
682      *         prevents it from being stored in this map
683      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
684      */
685     // final V computeIfPresent(K key,
686     //         BiFunction<K, V, V> remappingFunction) {
687     //     Objects.requireNonNull(remappingFunction);
688     //     V oldValue;
689     //     if ((oldValue = get(key)) !is null) {
690     //         V newValue = remappingFunction.apply(key, oldValue);
691     //         if (newValue !is null) {
692     //             put(key, newValue);
693     //             return newValue;
694     //         } else {
695     //             remove(key);
696     //             return null;
697     //         }
698     //     } else {
699     //         return null;
700     //     }
701     // }
702 
703     /**
704      * Attempts to compute a mapping for the specified key and its current
705      * mapped value (or {@code null} if there is no current mapping). For
706      * example, to either create or append a {@code string} msg to a value
707      * mapping:
708      *
709      * <pre> {@code
710      * map.compute(key, (k, v) -> (v is null) ? msg : v.concat(msg))}</pre>
711      * (Method {@link #merge merge()} is often simpler to use for such purposes.)
712      *
713      * <p>If the function returns {@code null}, the mapping is removed (or
714      * remains absent if initially absent).  If the function itself throws an
715      * (unchecked) exception, the exception is rethrown, and the current mapping
716      * is left unchanged.
717      *
718      * @implSpec
719      * The final implementation is equivalent to performing the following
720      * steps for this {@code map}, then returning the current value or
721      * {@code null} if absent:
722      *
723      * <pre> {@code
724      * V oldValue = map.get(key);
725      * V newValue = remappingFunction.apply(key, oldValue);
726      * if (oldValue !is null ) {
727      *    if (newValue !is null)
728      *       map.put(key, newValue);
729      *    else
730      *       map.remove(key);
731      * } else {
732      *    if (newValue !is null)
733      *       map.put(key, newValue);
734      *    else
735      *       return null;
736      * }
737      * }</pre>
738      *
739      * <p>The final implementation makes no guarantees about synchronization
740      * or atomicity properties of this method. Any implementation providing
741      * atomicity guarantees must override this method and document its
742      * concurrency properties. In particular, all implementations of
743      * subinterface {@link hunt.concurrency.ConcurrentMap} must document
744      * whether the function is applied once atomically only if the value is not
745      * present.
746      *
747      * @param key key with which the specified value is to be associated
748      * @param remappingFunction the function to compute a value
749      * @return the new value associated with the specified key, or null if none
750      * @throws NullPointerException if the specified key is null and
751      *         this map does not support null keys, or the
752      *         remappingFunction is null
753      * @throws UnsupportedOperationException if the {@code put} operation
754      *         is not supported by this map
755      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
756      * @throws ClassCastException if the class of the specified key or value
757      *         prevents it from being stored in this map
758      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
759      */
760     // final V compute(K key,
761     //         BiFunction<K, V, V> remappingFunction) {
762     //     Objects.requireNonNull(remappingFunction);
763     //     V oldValue = get(key);
764 
765     //     V newValue = remappingFunction.apply(key, oldValue);
766     //     if (newValue is null) {
767     //         // delete mapping
768     //         if (oldValue !is null || containsKey(key)) {
769     //             // something to remove
770     //             remove(key);
771     //             return null;
772     //         } else {
773     //             // nothing to do. Leave things as they were.
774     //             return null;
775     //         }
776     //     } else {
777     //         // add or replace old mapping
778     //         put(key, newValue);
779     //         return newValue;
780     //     }
781     // }
782 
783     /**
784      * If the specified key is not already associated with a value or is
785      * associated with null, associates it with the given non-null value.
786      * Otherwise, replaces the associated value with the results of the given
787      * remapping function, or removes if the result is {@code null}. This
788      * method may be of use when combining multiple mapped values for a key.
789      * For example, to either create or append a {@code string msg} to a
790      * value mapping:
791      *
792      * <pre> {@code
793      * map.merge(key, msg, string::concat)
794      * }</pre>
795      *
796      * <p>If the function returns {@code null} the mapping is removed.  If the
797      * function itself throws an (unchecked) exception, the exception is
798      * rethrown, and the current mapping is left unchanged.
799      *
800      * @implSpec
801      * The final implementation is equivalent to performing the following
802      * steps for this {@code map}, then returning the current value or
803      * {@code null} if absent:
804      *
805      * <pre> {@code
806      * V oldValue = map.get(key);
807      * V newValue = (oldValue is null) ? value :
808      *              remappingFunction.apply(oldValue, value);
809      * if (newValue is null)
810      *     map.remove(key);
811      * else
812      *     map.put(key, newValue);
813      * }</pre>
814      *
815      * <p>The final implementation makes no guarantees about synchronization
816      * or atomicity properties of this method. Any implementation providing
817      * atomicity guarantees must override this method and document its
818      * concurrency properties. In particular, all implementations of
819      * subinterface {@link hunt.concurrency.ConcurrentMap} must document
820      * whether the function is applied once atomically only if the value is not
821      * present.
822      *
823      * @param key key with which the resulting value is to be associated
824      * @param value the non-null value to be merged with the existing value
825      *        associated with the key or, if no existing value or a null value
826      *        is associated with the key, to be associated with the key
827      * @param remappingFunction the function to recompute a value if present
828      * @return the new value associated with the specified key, or null if no
829      *         value is associated with the key
830      * @throws UnsupportedOperationException if the {@code put} operation
831      *         is not supported by this map
832      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
833      * @throws ClassCastException if the class of the specified key or value
834      *         prevents it from being stored in this map
835      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
836      * @throws NullPointerException if the specified key is null and this map
837      *         does not support null keys or the value or remappingFunction is
838      *         null
839      */
840     // final V merge(K key, V value,
841     //         BiFunction<V, V, V> remappingFunction) {
842     //     Objects.requireNonNull(remappingFunction);
843     //     Objects.requireNonNull(value);
844     //     V oldValue = get(key);
845     //     V newValue = (oldValue is null) ? value :
846     //                remappingFunction.apply(oldValue, value);
847     //     if(newValue is null) {
848     //         remove(key);
849     //     } else {
850     //         put(key, newValue);
851     //     }
852     //     return newValue;
853     // }
854 }
855 
856 
857 /* A map entry (key-value pair).  The <tt>Map.entrySet</tt> method returns
858  * a collection-view of the map, whose elements are of this class.  The
859  * <i>only</i> way to obtain a reference to a map entry is from the
860  * iterator of this collection-view.  These <tt>MapEntry</tt> objects are
861  * valid <i>only</i> for the duration of the iteration; more formally,
862  * the behavior of a map entry is undefined if the backing map has been
863  * modified after the entry was returned by the iterator, except through
864  * the <tt>setValue</tt> operation on the map entry.
865  *
866  * @see Map#entrySet()
867  */
868 interface MapEntry(K,V) : IObject, Comparable!(MapEntry!(K,V)) {
869     /**
870      * Returns the key corresponding to this entry.
871      *
872      * @return the key corresponding to this entry
873      * @throws IllegalStateException implementations may, but are not
874      *         required to, throw this exception if the entry has been
875      *         removed from the backing map.
876      */
877     K getKey();
878 
879     /**
880      * Returns the value corresponding to this entry.  If the mapping
881      * has been removed from the backing map (by the iterator's
882      * <tt>remove</tt> operation), the results of this call are undefined.
883      *
884      * @return the value corresponding to this entry
885      * @throws IllegalStateException implementations may, but are not
886      *         required to, throw this exception if the entry has been
887      *         removed from the backing map.
888      */
889     V getValue();
890 
891     /**
892      * Replaces the value corresponding to this entry with the specified
893      * value (optional operation).  (Writes through to the map.)  The
894      * behavior of this call is undefined if the mapping has already been
895      * removed from the map (by the iterator's <tt>remove</tt> operation).
896      *
897      * @param value new value to be stored in this entry
898      * @return old value corresponding to the entry
899      * @throws UnsupportedOperationException if the <tt>put</tt> operation
900      *         is not supported by the backing map
901      * @throws ClassCastException if the class of the specified value
902      *         prevents it from being stored in the backing map
903      * @throws NullPointerException if the backing map does not permit
904      *         null values, and the specified value is null
905      * @throws IllegalArgumentException if some property of this value
906      *         prevents it from being stored in the backing map
907      * @throws IllegalStateException implementations may, but are not
908      *         required to, throw this exception if the entry has been
909      *         removed from the backing map.
910      */
911     V setValue(V value);
912 
913     /**
914      * Compares the specified object with this entry for equality.
915      * Returns <tt>true</tt> if the given object is also a map entry and
916      * the two entries represent the same mapping.  More formally, two
917      * entries <tt>e1</tt> and <tt>e2</tt> represent the same mapping
918      * if<pre>
919      *     (e1.getKey()==null ?
920      *      e2.getKey()==null : e1.getKey().equals(e2.getKey()))  &amp;&amp;
921      *     (e1.getValue()==null ?
922      *      e2.getValue()==null : e1.getValue().equals(e2.getValue()))
923      * </pre>
924      * This ensures that the <tt>equals</tt> method works properly across
925      * different implementations of the <tt>MapEntry</tt> interface.
926      *
927      * @param o object to be compared for equality with this map entry
928      * @return <tt>true</tt> if the specified object is equal to this map
929      *         entry
930      */
931     // bool opEquals(MapEntry!(K,V) o);
932 
933     /**
934      * Returns the hash code value for this map entry.  The hash code
935      * of a map entry <tt>e</tt> is defined to be: <pre>
936      *     (e.getKey()==null   ? 0 : e.getKey().hashCode()) ^
937      *     (e.getValue()==null ? 0 : e.getValue().hashCode())
938      * </pre>
939      * This ensures that <tt>e1.equals(e2)</tt> implies that
940      * <tt>e1.hashCode()==e2.hashCode()</tt> for any two Entries
941      * <tt>e1</tt> and <tt>e2</tt>, as required by the general
942      * contract of <tt>Object.hashCode</tt>.
943      *
944      * @return the hash code value for this map entry
945      * @see Object#hashCode()
946      * @see Object#equals(Object)
947      * @see #equals(Object)
948      */
949     // size_t toHash() @trusted nothrow;
950 
951     /**
952      * Returns a comparator that compares {@link MapEntry} in natural order on key.
953      *
954      * <p>The returned comparator is serializable and throws {@link
955      * NullPointerException} when comparing an entry with a null key.
956      *
957      * @param  !K the {@link Comparable} type of then map keys
958      * @param  !V the type of the map values
959      * @return a comparator that compares {@link MapEntry} in natural order on key.
960      * @see Comparable
961      */
962     // public static <K extends Comparable<K>, V> Comparator<MapEntry!(K,V)> comparingByKey() {
963     //     return (Comparator<MapEntry<K, V>> & Serializable)
964     //         (c1, c2) -> c1.getKey().compareTo(c2.getKey());
965     // }
966 
967     /**
968      * Returns a comparator that compares {@link MapEntry} in natural order on value.
969      *
970      * <p>The returned comparator is serializable and throws {@link
971      * NullPointerException} when comparing an entry with null values.
972      *
973      * @param !K the type of the map keys
974      * @param !V the {@link Comparable} type of the map values
975      * @return a comparator that compares {@link MapEntry} in natural order on value.
976      * @see Comparable
977      */
978     // public static <K, V extends Comparable<V>> Comparator<MapEntry!(K,V)> comparingByValue() {
979     //     return (Comparator<MapEntry<K, V>> & Serializable)
980     //         (c1, c2) -> c1.getValue().compareTo(c2.getValue());
981     // }
982 
983     /**
984      * Returns a comparator that compares {@link MapEntry} by key using the given
985      * {@link Comparator}.
986      *
987      * <p>The returned comparator is serializable if the specified comparator
988      * is also serializable.
989      *
990      * @param  !K the type of the map keys
991      * @param  !V the type of the map values
992      * @param  cmp the key {@link Comparator}
993      * @return a comparator that compares {@link MapEntry} by the key.
994      */
995     // public static <K, V> Comparator<MapEntry<K, V>> comparingByKey(Comparator<K> cmp) {
996     //     Objects.requireNonNull(cmp);
997     //     return (Comparator<MapEntry<K, V>> & Serializable)
998     //         (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
999     // }
1000 
1001     /**
1002      * Returns a comparator that compares {@link MapEntry} by value using the given
1003      * {@link Comparator}.
1004      *
1005      * <p>The returned comparator is serializable if the specified comparator
1006      * is also serializable.
1007      *
1008      * @param  !K the type of the map keys
1009      * @param  !V the type of the map values
1010      * @param  cmp the value {@link Comparator}
1011      * @return a comparator that compares {@link MapEntry} by the value.
1012      */
1013     // public static <K, V> Comparator<MapEntry<K, V>> comparingByValue(Comparator<V> cmp) {
1014     //     Objects.requireNonNull(cmp);
1015     //     return (Comparator<MapEntry<K, V>> & Serializable)
1016     //         (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
1017     // }
1018 }
1019 
1020 import std.conv;
1021 abstract class AbstractMapEntry(K, V) : MapEntry!(K,V) {
1022     
1023     package K key;
1024     package V value;
1025 
1026     this(K key, V value) {
1027         this.key = key;
1028         this.value = value;
1029     }
1030 
1031     /**
1032     * Returns the key.
1033     *
1034     * @return the key
1035     */
1036     K getKey() {
1037         return key;
1038     }
1039 
1040     /**
1041     * Returns the value associated with the key.
1042     *
1043     * @return the value associated with the key
1044     */
1045     V getValue() {
1046         return value;
1047     }
1048 
1049     /**
1050     * Replaces the value currently associated with the key with the given
1051     * value.
1052     *
1053     * @return the value associated with the key before this method was
1054     *         called
1055     */
1056     V setValue(V value) {
1057         V oldValue = this.value;
1058         this.value = value;
1059         return oldValue;
1060     }
1061 
1062     /**
1063     * Returns a string representation of this map entry.  This
1064     * implementation returns the string representation of this
1065     * entry's key followed by the equals character ("<tt>=</tt>")
1066     * followed by the string representation of this entry's value.
1067     *
1068     * @return a string representation of this map entry
1069     */
1070     override string toString() {
1071         return key.to!string() ~ "=" ~ value.to!string();
1072     }
1073 
1074     /**
1075     * Compares the specified object with this entry for equality.
1076     * Returns {@code true} if the given object is also a map entry and
1077     * the two entries represent the same mapping.  More formally, two
1078     * entries {@code e1} and {@code e2} represent the same mapping
1079     * if<pre>
1080     *   (e1.getKey()==null ?
1081     *    e2.getKey()==null :
1082     *    e1.getKey().equals(e2.getKey()))
1083     *   &amp;&amp;
1084     *   (e1.getValue()==null ?
1085     *    e2.getValue()==null :
1086     *    e1.getValue().equals(e2.getValue()))</pre>
1087     * This ensures that the {@code equals} method works properly across
1088     * different implementations of the {@code MapEntry} interface.
1089     *
1090     * @param o object to be compared for equality with this map entry
1091     * @return {@code true} if the specified object is equal to this map
1092     *         entry
1093     * @see    #toHash
1094     */
1095     bool opEquals(IObject o) {
1096         return opEquals(cast(Object) o);
1097     }
1098 
1099     override bool opEquals(Object o) {
1100         if (o is this)
1101             return true;
1102             
1103         MapEntry!(K, V) e = cast(MapEntry!(K, V))o;
1104         if (e !is null) {
1105             if (key == e.getKey() && value == e.getValue())
1106                 return true;
1107         }
1108         return false;
1109     }
1110 
1111     int opCmp(MapEntry!(K, V) o) {
1112         throw new NotImplementedException("opCmp");
1113     }
1114 
1115     alias opCmp = Object.opCmp;
1116 
1117 
1118     override size_t toHash() @trusted nothrow {
1119         return hashOf(key) ^ hashOf(value);
1120     }
1121 }