001/*
002 * Copyright (C) 2002-2015 Sebastiano Vigna
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 *     http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016package squidpony.squidmath;
017
018import squidpony.annotation.GwtIncompatible;
019
020import java.io.Serializable;
021import java.util.*;
022
023/**
024 * An int-key and int-value insertion-ordered hash map with with a fast implementation, originally from fastutil as
025 * Object2ObjectLinkedOpenHashMap but modified (in {@link OrderedMap}) to support constant-time indexed access of keys,
026 * values, and entries, and reordering. Deletion is slower with this algorithm (O(n) because the array used to keep
027 * track of ordering and indexing only allows linear-time deletion, instead of a linked-list approach allowing
028 * constant-time deletion but not helping at all with indexed access), and insertion sometimes takes longer than an
029 * ordered map using a linked-list for order because rehashing is more expensive. The benefits from constant-time access
030 * by index are numerous, especially for games, since fetching a random element becomes O(1) instead of O(n), and the
031 * index can be used to store extra info for no cost.
032 * <br>
033 * An older version of this class didn't support the useful {@link #keyAt(int)} and {@link #getAt(int)} operations,
034 * among many others, and a refactor of the class has made it much closer to {@link IntIntOrderedMap} and to some extent
035 * {@link OrderedMap}, making order control a priority. Some method names have changed; if you used code like
036 * {@code putAndMoveToFirst(k, v)}, that should be replaced with {@code putAt(k, v, 0)}. The API for the data structures
037 * returned by {@link #keySet()} and {@link #values()} has changed in some places; you should use
038 * {@link #keysAsArray()} and {@link #valuesAsArray()} instead of creating a key set or values collection and calling
039 * toArray() on that, as you had to before. The usage of this class should now be similar to the rest of the library.
040 * <br>
041 * Instances of this class use a hash table to represent a map. The table is filled up to a specified <em>load factor</em>, and then doubled in size to accommodate new entries. If the table is
042 * emptied below <em>one fourth</em> of the load factor, it is halved in size. However, halving is not performed when deleting entries from an iterator, as it would interfere with the iteration
043 * process.
044 * <br>
045 * Note that {@link #clear()} does not modify the hash table size. Rather, a family of {@linkplain #trim() trimming methods} lets you control the size of the table; this is particularly useful if
046 * you reuse instances of this class.
047 * <br>
048 * Iterators generated by this map will enumerate pairs in the same order in which they have been added to the map (addition of pairs whose key is already present in the set does not change the
049 * iteration order). Note that this order has nothing in common with the natural order of the keys. The order is kept by means of a int-specialized list, {@link IntVLA}, and is modifiable with this
050 * class' {@link #reorder(int...)} and {@link #shuffle(IRNG)} methods, among other tools. It may be preferable to avoid instantiating an Iterator object and instead
051 * use a normal int-based for loop with {@link #getAt(int)} called in each iteration. Though this doesn't allow easy deletion of items during iteration, it may be the
052 * fastest way to iterate through an OrderedMap.
053 * <br>
054 * This class allows approximately constant-time lookup of keys or values by their index in the ordering, which can
055 * allow some novel usage of the data structure. {@link OrderedSet} can be used like a list of unique elements, keeping
056 * order like a list does but also allowing rapid checks for whether an item exists in the OrderedSet, and OrderedMap
057 * can be used like that but with values associated as well (where OrderedSet uses contains(), OrderedMap uses
058 * containsKey()). You can also set the key and value at a position with {@link #putAt(int, double, int)}, or alter
059 * the key while keeping its value and index the same with {@link #alter(int, int)}. Reordering works here too,
060 * both with completely random orders from {@link #shuffle(IRNG)} or with a previously-generated ordering from
061 * {@link #reorder(int...)} (you can produce such an ordering for a given size and reuse it across multiple Ordered data
062 * structures with {@link IRNG#randomOrdering(int)}). Note that putAt() and {@link #removeAt(int)} do not run in constant
063 * time, and depending on the point of insertion/removal, they are likely to run in linear time (but also note that most
064 * insertion-ordered Maps and Sets don't allow insertion or removal at anywhere but the beginning or end of the order).
065 * <br>
066 * This doesn't allow custom IHashers because IHasher expects an Object to hash, and that would box the keys every time.
067 * <br>
068 * Thank you, Sebastiano Vigna, for making FastUtil available to the public with such high quality.
069 * <br>
070 * See https://github.com/vigna/fastutil for the original library.
071 * @author Sebastiano Vigna (responsible for all the hard parts)
072 * @author Tommy Ettinger (mostly responsible for squashing several layers of parent classes into one monster class)
073 */
074public class IntDoubleOrderedMap implements Serializable, Cloneable {
075    private static final long serialVersionUID = 0L;
076    /**
077     * The array of keys.
078     */
079    protected int[] key;
080    /**
081     * The array of values.
082     */
083    protected double[] value;
084    /**
085     * The mask for wrapping a position counter.
086     */
087    protected int mask;
088    /**
089     * Whether this set contains the key zero.
090     */
091    protected boolean containsNullKey;
092    /**
093     * An IntVLA (variable-length int sequence) that stores the positions in the key array of specific keys, with the
094     * positions in insertion order. The order can be changed with {@link #reorder(int...)} and other methods.
095     */
096    protected IntVLA order;
097    /**
098     * The current table size.
099     */
100    protected int n;
101    /**
102     * Threshold after which we rehash. It must be the table size times {@link #f}.
103     */
104    protected int maxFill;
105    /**
106     * Number of entries in the set (including the key zero, if present).
107     */
108    protected int size;
109    /**
110     * The acceptable load factor.
111     */
112    public final float f;
113    /**
114     * Cached set of entries.
115     */
116    protected volatile MapEntrySet entries;
117    /**
118     * Cached set of keys.
119     */
120    protected volatile KeySet keys;
121    /**
122     * Cached collection of values.
123     */
124    protected volatile ValueCollection values;
125    /**
126     * Default return value.
127     */
128    protected double defRetValue = Double.NaN;
129
130    /**
131     * The initial default size of a hash table.
132     */
133    public static final int DEFAULT_INITIAL_SIZE = 16;
134    /**
135     * The default load factor of a hash table.
136     */
137    public static final float DEFAULT_LOAD_FACTOR = .25f; // .1875f; // .75f;
138    /**
139     * The load factor for a (usually small) table that is meant to be particularly fast.
140     */
141    public static final float FAST_LOAD_FACTOR = .5f;
142    /**
143     * The load factor for a (usually very small) table that is meant to be extremely fast.
144     */
145    public static final float VERY_FAST_LOAD_FACTOR = .25f;
146
147    public void defaultReturnValue(final double rv) {
148        defRetValue = rv;
149    }
150
151    public double defaultReturnValue() {
152        return defRetValue;
153    }
154
155    /**
156     * Creates a new OrderedMap.
157     * <p>
158     * <p>The actual table size will be the least power of two greater than <code>expected</code>/<code>f</code>.
159     *
160     * @param expected the expected number of elements in the hash set.
161     * @param f        the load factor.
162     */
163
164    public IntDoubleOrderedMap(final int expected, final float f) {
165        if (f <= 0 || f > 1)
166            throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than or equal to 1");
167        if (expected < 0) throw new IllegalArgumentException("The expected number of elements must be nonnegative");
168        this.f = f;
169        n = arraySize(expected, f);
170        mask = n - 1;
171        maxFill = maxFill(n, f);
172        key = new int[n + 1];
173        value = new double[n + 1];
174        //link = new long[n + 1];
175        order = new IntVLA(expected);
176    }
177
178    /**
179     * Creates a new OrderedMap with 0.75f as load factor.
180     *
181     * @param expected the expected number of elements in the OrderedMap.
182     */
183    public IntDoubleOrderedMap(final int expected) {
184        this(expected, DEFAULT_LOAD_FACTOR);
185    }
186
187    /**
188     * Creates a new OrderedMap with initial expected 16 entries and 0.75f as load factor.
189     */
190    public IntDoubleOrderedMap() {
191        this(DEFAULT_INITIAL_SIZE, DEFAULT_LOAD_FACTOR);
192    }
193
194    /**
195     * Creates a new OrderedMap copying a given one.
196     *
197     * @param m a {@link Map} to be copied into the new OrderedMap.
198     * @param f the load factor.
199     */
200    public IntDoubleOrderedMap(final IntDoubleOrderedMap m, final float f) {
201        this(m.size(), f);
202        putAll(m);
203    }
204
205    /**
206     * Creates a new OrderedMap with 0.75f as load factor copying a given one.
207     *
208     * @param m a {@link Map} to be copied into the new OrderedMap.
209     */
210    public IntDoubleOrderedMap(final IntDoubleOrderedMap m) {
211        this(m, m.f);
212    }
213
214    /**
215     * Creates a new OrderedMap using the elements of two parallel arrays.
216     *
217     * @param keyArray the array of keys of the new OrderedMap.
218     * @param valueArray the array of corresponding values in the new OrderedMap.
219     * @param f the load factor.
220     * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths.
221     */
222    public IntDoubleOrderedMap(final int[] keyArray, final double[] valueArray, final float f) {
223        this(keyArray.length, f);
224        if (keyArray.length != valueArray.length)
225            throw new IllegalArgumentException("The key array and the value array have different lengths (" + keyArray.length + " and " + valueArray.length + ")");
226        for (int i = 0; i < keyArray.length; i++)
227            put(keyArray[i], valueArray[i]);
228    }
229
230    /**
231     * Creates a new OrderedMap with 0.75f as load factor using the elements of two parallel arrays.
232     *
233     * @param keyArray the array of keys of the new OrderedMap.
234     * @param valueArray the array of corresponding values in the new OrderedMap.
235     * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths.
236     */
237    public IntDoubleOrderedMap(final int[] keyArray, final double[] valueArray) {
238        this(keyArray, valueArray, DEFAULT_LOAD_FACTOR);
239    }
240    private int realSize() {
241        return containsNullKey ? size - 1 : size;
242    }
243    private void ensureCapacity(final int capacity) {
244        final int needed = arraySize(capacity, f);
245        if (needed > n)
246            rehash(needed);
247    }
248    private void tryCapacity(final long capacity) {
249        final int needed = (int) Math.min(
250                1 << 30,
251                Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(capacity
252                        / f))));
253        if (needed > n)
254            rehash(needed);
255    }
256    private double removeEntry(final int pos) {
257        final double oldValue = value[pos];
258        size--;
259        fixOrder(pos);
260        shiftKeys(pos);
261        if (size < (maxFill >> 2) && n > DEFAULT_INITIAL_SIZE)
262            rehash(n >> 1);
263        return oldValue;
264    }
265    private double removeNullEntry() {
266        containsNullKey = false;
267        final double oldValue = value[n];
268        size--;
269        fixOrder(n);
270        if (size < (maxFill >> 2) && n > DEFAULT_INITIAL_SIZE)
271            rehash(n >> 1);
272        return oldValue;
273    }
274
275    /**
276     * Puts the first key in keyArray with the first value in valueArray, then the second in each and so on.
277     * The entries are all appended to the end of the iteration order, unless a key was already present. Then,
278     * its value is changed at the existing position in the iteration order.
279     * If the lengths of the two arrays are not equal, this puts a number of entries equal to the lesser length.
280     * If either array is null, this returns without performing any changes.
281     * @param keyArray an array of int keys that should usually have the same length as valueArray
282     * @param valueArray an array of int values that should usually have the same length as keyArray
283     */
284    public void putAll(final int[] keyArray, final double[] valueArray)
285    {
286        if(keyArray == null || valueArray == null)
287            return;
288        for (int i = 0; i < keyArray.length && i < valueArray.length; i++)
289            put(keyArray[i], valueArray[i]);
290
291    }
292
293    /**
294     * Puts all key-value pairs in the Map m into this OrderedMap.
295     * The entries are all appended to the end of the iteration order, unless a key was already present. Then,
296     * its value is changed at the existing position in the iteration order. This can take any kind of Map,
297     * including unordered HashMap objects; if the Map does not have stable ordering, the order in which entries
298     * will be appended is not stable either. For this reason, OrderedMap, LinkedHashMap, and TreeMap (or other
299     * SortedMap implementations) will work best when order matters.
300     * @param m an IntIntOrderedMap to add into this
301     */
302    public void putAll(IntDoubleOrderedMap m) {
303        if (f <= .5)
304            ensureCapacity(m.size()); // The resulting map will be sized for m.size() elements
305        else
306            tryCapacity(size() + m.size()); // The resulting map will be size() +  m.size() elements
307        int n = m.size();
308        for (int i = 0; i < n; i++) {             
309            put(m.keyAt(i), m.getAt(i));
310        }
311    }
312    private int insert(final int k, final double v) {
313        int pos;
314        if (k == 0) {
315            if (containsNullKey)
316                return n;
317            containsNullKey = true;
318            pos = n;
319        } else {
320            int curr;
321            final int[] key = this.key;
322            // The starting point.
323            if ((curr = key[pos = (HashCommon.mix(k)) & mask]) != 0) {
324                if (curr == k)
325                    return pos;
326                while ((curr = key[pos = (pos + 1) & mask]) != 0)
327                    if (curr == k)
328                        return pos;
329            }
330        }
331        key[pos] = k;
332        value[pos] = v;
333        order.add(pos);
334        if (size++ >= maxFill)
335            rehash(arraySize(size + 1, f));
336        return -1;
337    }
338    private int insertAt(final int k, final double v, final int idx) {
339        int pos;
340        if (k == 0) {
341            if (containsNullKey)
342            {
343                fixOrder(n);
344                order.insert(idx, n);
345                return n;
346            }
347            containsNullKey = true;
348            pos = n;
349        } else {
350            int curr;
351            final int[] key = this.key;
352            // The starting point.
353            if ((curr = key[pos = (HashCommon.mix(k)) & mask]) != 0) {
354                if (curr == k)
355                {
356                    fixOrder(pos);
357                    order.insert(idx, pos);
358                    return pos;
359                }
360                while ((curr = key[pos = (pos + 1) & mask]) != 0)
361                    if (curr == k)
362                    {
363                        fixOrder(pos);
364                        order.insert(idx, pos);
365                        return pos;
366                    }
367            }
368        }
369        key[pos] = k;
370        value[pos] = v;
371        order.insert(idx, pos);
372        if (size++ >= maxFill)
373            rehash(arraySize(size + 1, f));
374        return -1;
375    }
376    public double put(final int k, final double v) {
377        final int pos = insert(k, v);
378        if (pos < 0)
379            return defRetValue;
380        final double oldValue = value[pos];
381        value[pos] = v;
382        return oldValue;
383    }
384    public double putAt(final int k, final double v, final int idx) {
385        final int pos = insertAt(k, v, idx);
386        if (pos < 0)
387            return defRetValue;
388        final double oldValue = value[pos];
389        value[pos] = v;
390        return oldValue;
391    }
392    /**
393     * Shifts left entries with the specified hash code, starting at the
394     * specified position, and empties the resulting free entry.
395     *
396     * @param pos
397     *            a starting position.
398     */
399    protected final void shiftKeys(int pos) {
400        // Shift entries with the same hash.
401        int last, slot;
402        int curr;
403        final int[] key = this.key;
404        for (;;) {
405            pos = ((last = pos) + 1) & mask;
406            for (;;) {
407                if ((curr = key[pos]) == 0) {
408                    key[last] = 0;
409                    return;
410                }
411                slot = (HashCommon.mix(curr))
412                        & mask;
413                if (last <= pos ? last >= slot || slot > pos : last >= slot
414                        && slot > pos)
415                    break;
416                pos = (pos + 1) & mask;
417            }
418            key[last] = curr;
419            value[last] = value[pos];
420            fixOrder(pos, last);
421        }
422    }
423    public double remove(final int k) {
424        if (k == 0) {
425            if (containsNullKey)
426                return removeNullEntry();
427            return defRetValue;
428        }
429        int curr;
430        final int[] key = this.key;
431        int pos;
432        // The starting point.
433        if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0)
434            return defRetValue;
435        if (k == curr)
436            return removeEntry(pos);
437        while (true) {
438            if ((curr = key[pos = (pos + 1) & mask]) == 0)
439                return defRetValue;
440            if (k == curr)
441                return removeEntry(pos);
442        }
443    }
444    private double setValue(final int pos, final double v) {
445        final double oldValue = value[pos];
446        value[pos] = v;
447        return oldValue;
448    }
449    /**
450     * Removes the mapping associated with the first key in iteration order.
451     *
452     * @return the value previously associated with the first key in iteration
453     *         order.
454     * @throws NoSuchElementException
455     *             is this map is empty.
456     */
457    public double removeFirst() {
458        return removeAt(0);
459    }
460    /**
461     * Removes the mapping associated with the last key in iteration order.
462     *
463     * @return the value previously associated with the last key in iteration
464     *         order.
465     * @throws NoSuchElementException
466     *             is this map is empty.
467     */
468    public double removeLast() {
469        return removeAt(size-1);
470    }
471    public double get(final int k) {
472        if (k == 0)
473            return containsNullKey ? value[n] : defRetValue;
474        int curr;
475        final int[] key = this.key;
476        int pos;
477        // The starting point.
478        if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0)
479            return defRetValue;
480        if (k == curr)
481            return value[pos];
482        // There's always an unused entry.
483        while (true) {
484            if ((curr = key[pos = (pos + 1) & mask]) == 0)
485                return defRetValue;
486            if (k == curr)
487                return value[pos];
488        }
489    }
490
491
492    public double getOrDefault(final int k, final double defaultValue) {
493        if (k == 0)
494            return containsNullKey ? value[n] : defaultValue;
495        int curr;
496        final int[] key = this.key;
497        int pos;
498        // The starting point.
499        if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0)
500            return defaultValue;
501        if (k == curr)
502            return value[pos];
503        // There's always an unused entry.
504        while (true) {
505            if ((curr = key[pos = (pos + 1) & mask]) == 0)
506                return defaultValue;
507            if (k == curr)
508                return value[pos];
509        }
510    }
511
512    protected int positionOf(final int k) {
513        if (k == 0)
514        {
515            if(containsNullKey)
516                return n;
517            else
518                return -1;
519        }
520        int curr;
521        final int[] key = this.key;
522        int pos;
523        // The starting point.
524        if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0)
525            return -1;
526        if (k == curr)
527            return pos;
528        // There's always an unused entry.
529        while (true) {
530            if ((curr = key[pos = pos + 1 & mask]) == 0)
531                return -1;
532            if (k == curr)
533                return pos;
534        }
535    }
536
537    /**
538     * Gets the position in the ordering of the given key, though not as efficiently as some data structures can do it
539     * (e.g. {@link Arrangement} can access ordering position very quickly but doesn't store other values on its own).
540     * Returns a value that is at least 0 if it found k, or -1 if k was not present.
541     * @param k a key or possible key that this should find the index of
542     * @return the index of k, if present, or -1 if it is not present in this OrderedMap
543     */
544    public int indexOf(final int k)
545    {
546        int pos = positionOf(k);
547        return (pos < 0) ? -1 : order.indexOf(pos);
548    }
549
550    /**
551     * Swaps the positions in the ordering for the given items, if they are both present. Returns true if the ordering
552     * changed as a result of this call, or false if it stayed the same (which can be because left or right was not
553     * present, or because left and right are the same reference (so swapping would do nothing)).
554     * @param left an item that should be present in this OrderedMap
555     * @param right an item that should be present in this OrderedMap
556     * @return true if this OrderedMap changed in ordering as a result of this call, or false otherwise
557     */
558    public boolean swap(final int left, final int right)
559    {
560        if(left == right) return false;
561        int l = indexOf(left);
562        if(l < 0) return false;
563        int r = indexOf(right);
564        if(r < 0) return false;
565        order.swap(l, r);
566        return true;
567    }
568    /**
569     * Swaps the given indices in the ordering, if they are both valid int indices. Returns true if the ordering
570     * changed as a result of this call, or false if it stayed the same (which can be because left or right referred to
571     * an out-of-bounds index, or because left and right are equal (so swapping would do nothing)).
572     * @param left an index of an item in this OrderedMap, at least 0 and less than {@link #size()}
573     * @param right an index of an item in this OrderedMap, at least 0 and less than {@link #size()}
574     * @return true if this OrderedMap changed in ordering as a result of this call, or false otherwise
575     */
576    public boolean swapIndices(final int left, final int right)
577    {
578        if(left < 0 || right < 0 || left >= order.size || right >= order.size || left == right) return false;
579        order.swap(left, right);
580        return true;
581    }
582
583
584    public boolean containsKey(final int k) {
585        if (k == 0)
586            return containsNullKey;
587        int curr;
588        final int[] key = this.key;
589        int pos;
590        // The starting point.
591        if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0)
592            return false;
593        if (k == curr)
594            return true;
595        // There's always an unused entry.
596        while (true) {
597            if ((curr = key[pos = (pos + 1) & mask]) == 0)
598                return false;
599            if (k == curr)
600                return true;
601        }
602    }
603    public boolean containsValue(final double v) {
604        final double[] value = this.value;
605        final int[] key = this.key;
606        if (containsNullKey && value[n] == v)
607            return true;
608        for (int i = n; i-- != 0;)
609            if (key[i] != 0 && value[i] == v)
610                return true;
611        return false;
612    }
613    /*
614     * Removes all elements from this map.
615     *
616     * <P>To increase object reuse, this method does not change the table size.
617     * If you want to reduce the table size, you must use {@link #trim()}.
618     */
619    public void clear() {
620        if (size == 0)
621            return;
622        size = 0;
623        containsNullKey = false;
624        Arrays.fill(key, 0);
625        order.clear();
626    }
627
628    public int size() {
629        return size;
630    }
631
632    public boolean isEmpty() {
633        return size == 0;
634    }
635
636    /**
637     * Looks up the key {@code k} in this map, remembers the associated value (which will be
638     * {@link #defaultReturnValue()} if k wasn't found), adds {@code increment} to the actual associated value in the
639     * map, and returns the remembered value.
640     * @param k a key to look up
641     * @param increment a double to add to the value associated with {@code k}
642     * @return the previous value associated with k, or {@link #defaultReturnValue()} if k wasn't found
643     */
644    public double getAndIncrement(int k, double increment) {
645        if (k == 0) {
646            if (containsNullKey) {
647                double got = value[n];
648                value[n] += increment;
649                return got;
650            } else {
651                value[n] = defRetValue + increment;
652                return defRetValue;
653            }
654        }
655        int curr;
656        final int[] key = this.key;
657        int pos;
658        // The starting point.
659        if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0)
660        {
661            put(k, defRetValue + increment);
662            return defRetValue;
663        }
664        if (k == curr)
665        {
666            double got = value[pos];
667            value[pos] += increment;
668            return got;
669        }
670        // There's always an unused entry.
671        while (true) {
672            if ((curr = key[pos = (pos + 1) & mask]) == 0)
673            {
674                put(k, defRetValue + increment);
675                return defRetValue;
676            }
677            if (k == curr)
678            {
679                double got = value[pos];
680                value[pos] += increment;
681                return got;
682            }
683        }
684    }
685
686    /**
687     * The entry class for a OrderedMap does not record key and value, but rather the position in the hash table of the corresponding entry. This is necessary so that calls to
688     * {@link MapEntry#setValue(double)} are reflected in the map
689     */
690    public final class MapEntry {
691        // The table index this entry refers to, or -1 if this entry has been
692        // deleted.
693        int index;
694        MapEntry(final int index) {
695            this.index = index;
696        }
697        MapEntry() {
698        }
699        public int getKey() {
700            return key[index];
701        }
702        public double getValue() {
703            return value[index];
704        }
705        public double setValue(final double v) {
706            final double oldValue = value[index];
707            value[index] = v;
708            return oldValue;
709        }
710        public boolean equals(final Object o) {
711            if (!(o instanceof MapEntry))
712                return false;
713            MapEntry e = (MapEntry) o;
714            return (key[index] == e.getKey())
715                    && (value[index] == e.getValue());
716        }
717        public int hashCode() {
718            return HashCommon.mix(key[index])
719                    ^ HashCommon.mix(NumberTools.doubleToMixedIntBits(value[index]));
720        }
721        @Override
722        public String toString() {
723            return key[index] + "=>" + value[index];
724        }
725    }
726
727    /**
728     * Modifies the ordering so that the given entry is removed. This method will complete in logarithmic time.
729     *
730     * @param i the index of an entry.
731     * @return the iteration-order index of the removed entry
732     */
733    protected int fixOrder(final int i) {
734        if (size == 0) {
735            order.clear();
736            return -1;
737        }
738        return order.removeValue(i);
739    }
740
741    /**
742     * Modifies the ordering for a shift from s to d.
743     * <br>
744     * This method will complete in logarithmic time or better.
745     *
746     * @param s the source position.
747     * @param d the destination position.
748     */
749    protected void fixOrder(int s, int d) {
750        if(size == 0)
751            return;
752        if (size == 1 || order.items[0] == s) {
753            order.set(0, d);
754        }
755        else if (order.items[order.size-1] == s) {
756            order.set(order.size - 1, d);
757        }
758        else
759        {
760            order.set(order.indexOf(s), d);
761        }
762    }
763
764    /**
765     * Returns the first key of this map in iteration order.
766     *
767     * @return the first key in iteration order.
768     */
769    public int firstKey() {
770        if (size == 0)
771            throw new NoSuchElementException();
772        return key[order.items[0]];
773    }
774    /**
775     * Returns the last key of this map in iteration order.
776     *
777     * @return the last key in iteration order.
778     */
779    public int lastKey() {
780        if (size == 0)
781            throw new NoSuchElementException();
782        return key[order.items[order.size-1]];
783    }
784    /**
785     * A list iterator over a OrderedMap.
786     *
787     * <P>
788     * This class provides a list iterator over a OrderedMap. The
789     * constructor runs in constant time.
790     */
791    private class MapIterator {
792        /**
793         * The entry that will be returned by the next call to
794         * {@link ListIterator#previous()} (or <code>null</code> if no
795         * previous entry exists).
796         */
797        int prev = -1;
798        /**
799         * The entry that will be returned by the next call to
800         * {@link ListIterator#next()} (or <code>null</code> if no
801         * next entry exists).
802         */
803        int next;
804        /**
805         * The last entry that was returned (or -1 if we did not iterate or used
806         * {@link Iterator#remove()}).
807         */
808        int curr = -1;
809        /**
810         * The current index (in the sense of a {@link ListIterator}).
811         * Note that this value is not meaningful when this iterator has been
812         * created using the nonempty constructor.
813         */
814        int index;
815        private MapIterator() {
816            next = size == 0 ? -1 : order.items[0];
817            index = 0;
818        }
819        /*
820        private MapIterator(final K from) {
821            if (((from) == null)) {
822                if (containsNullKey) {
823                    next = (int) link[n];
824                    prev = n;
825                    return;
826                } else
827                    throw new NoSuchElementException("The key null"
828                            + " does not belong to this map.");
829            }
830            if (((key[last]) != null && (key[last]).equals(from))) {
831                prev = last;
832                index = size;
833                return;
834            }
835            // The starting point.
836            int pos = (((from).hashCode()))
837                    & mask;
838            // There's always an unused entry.
839            while (!((key[pos]) == null)) {
840                if (((key[pos]).equals(from))) {
841                    // Note: no valid index known.
842                    next = (int) link[pos];
843                    prev = pos;
844                    return;
845                }
846                pos = (pos + 1) & mask;
847            }
848            throw new NoSuchElementException("The key " + from
849                    + " does not belong to this map.");
850        }*/
851        public boolean hasNext() {
852            return next != -1;
853        }
854        public boolean hasPrevious() {
855            return prev != -1;
856        }
857        private void ensureIndexKnown() {
858            if (index >= 0)
859                return;
860            if (prev == -1) {
861                index = 0;
862                return;
863            }
864            if (next == -1) {
865                index = size;
866                return;
867            }
868            index = 0;
869            /*while (pos != prev) {
870                pos = (int) link[pos];
871                index++;
872            }*/
873        }
874        public int nextIndex() {
875            ensureIndexKnown();
876            return index + 1;
877        }
878        public int previousIndex() {
879            ensureIndexKnown();
880            return index - 1;
881        }
882        public int nextEntry() {
883            if (!hasNext())
884                throw new NoSuchElementException();
885            curr = next;
886            if(++index >= order.size)
887                next = -1;
888            else
889                next = order.get(index);//(int) link[curr];
890            prev = curr;
891            return curr;
892        }
893        public int previousEntry() {
894            if (!hasPrevious())
895                throw new NoSuchElementException();
896            curr = prev;
897            if(--index < 1)
898                prev = -1;
899            else
900                prev = order.get(index - 1);
901            //prev = (int) (link[curr] >>> 32);
902            next = curr;
903            return curr;
904        }
905        public void remove() {
906            ensureIndexKnown();
907            if (curr == -1)
908                throw new IllegalStateException();
909            if (curr == prev) {
910                /*
911                 * If the last operation was a next(), we are removing an entry
912                 * that precedes the current index, and thus we must decrement
913                 * it.
914                 */
915                if(--index >= 1)
916                    prev = order.get(index - 1); //(int) (link[curr] >>> 32);
917                else
918                    prev = -1;
919            } else {
920                if(index < order.size - 1)
921                    next = order.get(index + 1);
922                else
923                    next = -1;
924            }
925            order.removeIndex(index);
926            size--;
927            int last, slot, pos = curr;
928            curr = -1;
929            if (pos == n) {
930                containsNullKey = false;
931            } else {
932                int curr;
933                final int[] key = IntDoubleOrderedMap.this.key;
934                // We have to horribly duplicate the shiftKeys() code because we
935                // need to update next/prev.
936                for (;;) {
937                    pos = ((last = pos) + 1) & mask;
938                    for (;;) {
939                        if ((curr = key[pos]) == 0) {
940                            key[last] = 0;
941                            return;
942                        }
943                        slot = (HashCommon.mix(curr)) & mask;
944                        if (last <= pos
945                                ? last >= slot || slot > pos
946                                : last >= slot && slot > pos)
947                            break;
948                        pos = (pos + 1) & mask;
949                    }
950                    key[last] = curr;
951                    value[last] = value[pos];
952                    if (next == pos)
953                        next = last;
954                    if (prev == pos)
955                        prev = last;
956                    fixOrder(pos, last);
957                }
958            }
959        }
960        public int skip(final int n) {
961            int i = n;
962            while (i-- != 0 && hasNext())
963                nextEntry();
964            return n - i - 1;
965        }
966        public int back(final int n) {
967            int i = n;
968            while (i-- != 0 && hasPrevious())
969                previousEntry();
970            return n - i - 1;
971        }
972    }
973    private class EntryIterator extends MapIterator
974            implements
975            Iterator<MapEntry>, Serializable {
976        private static final long serialVersionUID = 0L;
977
978        private MapEntry entry;
979        public EntryIterator() {
980        }
981        public MapEntry next() {
982            return entry = new MapEntry(nextEntry());
983        }
984        public MapEntry previous() {
985            return entry = new MapEntry(previousEntry());
986        }
987        @Override
988        public void remove() {
989            super.remove();
990            entry.index = -1; // You cannot use a deleted entry.
991        }
992    }
993
994    public class FastEntryIterator extends MapIterator implements ListIterator<MapEntry>, Serializable {
995        private static final long serialVersionUID = 0L;
996
997        final MapEntry entry = new MapEntry();
998
999        public FastEntryIterator() {
1000        }
1001        public MapEntry next() {
1002            entry.index = nextEntry();
1003            return entry;
1004        }
1005        public MapEntry previous() {
1006            entry.index = previousEntry();
1007            return entry;
1008        }
1009        public void set(MapEntry ok) {
1010            throw new UnsupportedOperationException();
1011        }
1012        public void add(MapEntry ok) {
1013            throw new UnsupportedOperationException();
1014        }
1015    }
1016    public final class MapEntrySet
1017            implements Cloneable, SortedSet<MapEntry>, Set<MapEntry>, Serializable {
1018        private static final long serialVersionUID = 0L;
1019        public EntryIterator iterator() {
1020            return new EntryIterator();
1021        }
1022        public Comparator<? super MapEntry> comparator() {
1023            return null;
1024        }
1025        public SortedSet<MapEntry> subSet(
1026                MapEntry fromElement,
1027                MapEntry toElement) {
1028            throw new UnsupportedOperationException();
1029        }
1030        public SortedSet<MapEntry> headSet(
1031                MapEntry toElement) {
1032            throw new UnsupportedOperationException();
1033        }
1034        public SortedSet<MapEntry> tailSet(
1035                MapEntry fromElement) {
1036            throw new UnsupportedOperationException();
1037        }
1038        public MapEntry first() {
1039            if (size == 0)
1040                throw new NoSuchElementException();
1041            return new MapEntry(order.items[0]);
1042        }
1043        public MapEntry last() {
1044            if (size == 0)
1045                throw new NoSuchElementException();
1046            return new MapEntry(order.items[order.size-1]);
1047        }
1048        public boolean contains(final Object o) {
1049            if (!(o instanceof MapEntry))
1050                return false;
1051            final MapEntry e = (MapEntry) o;
1052            final int k = e.getKey();
1053            final double v = e.getValue();
1054            if (k == 0)
1055                return containsNullKey && (value[n] == v);
1056            int curr;
1057            final int[] key = IntDoubleOrderedMap.this.key;
1058            int pos;
1059            // The starting point.
1060            if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0)
1061                return false;
1062            if (k == curr)
1063                return value[pos] == v;
1064            // There's always an unused entry.
1065            while (true) {
1066                if ((curr = key[pos = (pos + 1) & mask]) == 0)
1067                    return false;
1068                if (k == curr)
1069                    return value[pos] == v;
1070            }
1071        }
1072        public boolean remove(final Object o) {
1073            if (!(o instanceof MapEntry))
1074                return false;
1075            final MapEntry e = (MapEntry) o;
1076            final int k = e.getKey();
1077            final double v = e.getValue();
1078            if (k == 0) {
1079                if (containsNullKey && value[n] == v) {
1080                    removeNullEntry();
1081                    return true;
1082                }
1083                return false;
1084            }
1085            int curr;
1086            final int[] key = IntDoubleOrderedMap.this.key;
1087            int pos;
1088            // The starting point.
1089            if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0)
1090                return false;
1091            if (curr == k) {
1092                if (value[pos] == v) {
1093                    removeEntry(pos);
1094                    return true;
1095                }
1096                return false;
1097            }
1098            while (true) {
1099                if ((curr = key[pos = (pos + 1) & mask]) == 0)
1100                    return false;
1101                if (curr == k) {
1102                    if (value[pos] == v) {
1103                        removeEntry(pos);
1104                        return true;
1105                    }
1106                }
1107            }
1108        }
1109        public int size() {
1110            return size;
1111        }
1112        public void clear() {
1113            IntDoubleOrderedMap.this.clear();
1114        }
1115
1116        public FastEntryIterator fastIterator() {
1117            return new FastEntryIterator();
1118        }
1119
1120        @Override
1121        public boolean equals(final Object o) {
1122            if (o == this)
1123                return true;
1124            if (!(o instanceof Set))
1125                return false;
1126            Set<?> s = (Set<?>) o;
1127            return s.size() == size() && containsAll(s);
1128        }
1129
1130        public Object[] toArray() {
1131            final Object[] a = new Object[size()];
1132            objectUnwrap(iterator(), a);
1133            return a;
1134        }
1135
1136        @SuppressWarnings("unchecked")
1137        public <T> T[] toArray(T[] a) {
1138            if (a == null || a.length < size()) a = (T[]) new Object[size()];
1139            objectUnwrap(iterator(), a);
1140            return a;
1141        }
1142
1143        /**
1144         * Unsupported.
1145         *
1146         * @param c ignored
1147         * @return nothing, throws UnsupportedOperationException
1148         * @throws UnsupportedOperationException always
1149         */
1150        public boolean addAll(Collection<? extends MapEntry> c) {
1151            throw new UnsupportedOperationException("addAll not supported");
1152        }
1153
1154        /**
1155         * Unsupported.
1156         *
1157         * @param k ignored
1158         * @return nothing, throws UnsupportedOperationException
1159         * @throws UnsupportedOperationException always
1160         */
1161        public boolean add(MapEntry k) {
1162            throw new UnsupportedOperationException("add not supported");
1163        }
1164
1165        /**
1166         * Checks whether this collection contains all elements from the given
1167         * collection.
1168         *
1169         * @param c a collection.
1170         * @return <code>true</code> if this collection contains all elements of the
1171         * argument.
1172         */
1173        public boolean containsAll(Collection<?> c) {
1174            int n = c.size();
1175            final Iterator<?> i = c.iterator();
1176            while (n-- != 0)
1177                if (!contains(i.next()))
1178                    return false;
1179            return true;
1180        }
1181
1182        /**
1183         * Retains in this collection only elements from the given collection.
1184         *
1185         * @param c a collection.
1186         * @return <code>true</code> if this collection changed as a result of the
1187         * call.
1188         */
1189        public boolean retainAll(Collection<?> c) {
1190            boolean retVal = false;
1191            int n = size();
1192            final Iterator<?> i = iterator();
1193            while (n-- != 0) {
1194                if (!c.contains(i.next())) {
1195                    i.remove();
1196                    retVal = true;
1197                }
1198            }
1199            return retVal;
1200        }
1201
1202        /**
1203         * Remove from this collection all elements in the given collection. If the
1204         * collection is an instance of this class, it uses faster iterators.
1205         *
1206         * @param c a collection.
1207         * @return <code>true</code> if this collection changed as a result of the
1208         * call.
1209         */
1210        public boolean removeAll(Collection<?> c) {
1211            boolean retVal = false;
1212            int n = c.size();
1213            final Iterator<?> i = c.iterator();
1214            while (n-- != 0)
1215                if (remove(i.next()))
1216                    retVal = true;
1217            return retVal;
1218        }
1219
1220        public boolean isEmpty() {
1221            return size() == 0;
1222        }
1223
1224        @Override
1225        public String toString() {
1226            final StringBuilder s = new StringBuilder();
1227            final EntryIterator i = iterator();
1228            int n = size();
1229            MapEntry k;
1230            boolean first = true;
1231            s.append("{");
1232            while (n-- != 0) {
1233                if (first)
1234                    first = false;
1235                else
1236                    s.append(", ");
1237                k = i.next();                 
1238                s.append(key[k.index]).append("=>").append(value[k.index]);
1239            }
1240            s.append("}");
1241            return s.toString();
1242        }
1243
1244    }
1245
1246    public SortedSet<MapEntry> entrySet() {
1247        if (entries == null) entries = new MapEntrySet();
1248        return entries;
1249    }
1250
1251    /**
1252     * An iterator on keys.
1253     * <p>
1254     * <P>We simply override the {@link ListIterator#next()}/{@link ListIterator#previous()} methods (and possibly their type-specific counterparts) so that they return keys
1255     * instead of entries.
1256     */
1257    public final class KeyIterator extends MapIterator implements Iterator<Integer>, Serializable {
1258        private static final long serialVersionUID = 0L;
1259        public Integer previous() {
1260            return key[previousEntry()];
1261        }        
1262        public int previousInt() {
1263            return key[previousEntry()];
1264        }
1265        public void set(Integer k) {
1266            throw new UnsupportedOperationException();
1267        }
1268        public void add(Integer k) {
1269            throw new UnsupportedOperationException();
1270        }
1271        public KeyIterator() {}
1272        public Integer next() {
1273            return key[nextEntry()];
1274        }
1275        public int nextInt() {
1276            return key[nextEntry()];
1277        }
1278        public void remove() { super.remove(); }
1279    }
1280
1281    public final class KeySet implements SortedSet<Integer>, Serializable {
1282        private static final long serialVersionUID = 0L;
1283
1284        public KeyIterator iterator() {
1285            return new KeyIterator();
1286        }
1287
1288        public int size() {
1289            return size;
1290        }
1291
1292        public void clear() {
1293            IntDoubleOrderedMap.this.clear();
1294        }
1295
1296        public Integer first() {
1297            if (size == 0) throw new NoSuchElementException();
1298            return key[order.items[0]];
1299        }
1300
1301        public Integer last() {
1302            if (size == 0) throw new NoSuchElementException();
1303            return key[order.items[order.size-1]];
1304        }
1305
1306        public Comparator<Integer> comparator() {
1307            return null;
1308        }
1309
1310        public final SortedSet<Integer> tailSet(Integer from) {
1311            throw new UnsupportedOperationException();
1312        }
1313
1314        public final SortedSet<Integer> headSet(Integer to) {
1315            throw new UnsupportedOperationException();
1316        }
1317
1318        public final SortedSet<Integer> subSet(Integer from, Integer to) {
1319            throw new UnsupportedOperationException();
1320        }
1321
1322        @SuppressWarnings("unchecked")
1323        @Override
1324        public <T> T[] toArray(T[] a) {
1325            if (a == null || a.length < size()) a = (T[]) new Object[size()];
1326            unwrap(iterator(), a);
1327            return a;
1328        }
1329
1330        /**
1331         * Always throws an UnsupportedOperationException
1332         */
1333        public boolean remove(Object ok) {
1334            throw new UnsupportedOperationException("Cannot remove from the key set directly");
1335        }
1336
1337        /**
1338         * Always throws an UnsupportedOperationException
1339         */
1340        public boolean add(final Integer o) {
1341            throw new UnsupportedOperationException("Cannot add to the key set directly");
1342        }
1343
1344        /**
1345         * Delegates to the corresponding type-specific method.
1346         */
1347        public boolean contains(final Object o) {
1348            return o instanceof Integer && containsKey((Integer) o);
1349        }
1350
1351        /**
1352         * Checks whether this collection contains all elements from the given type-specific collection.
1353         *
1354         * @param c a type-specific collection.
1355         * @return <code>true</code> if this collection contains all elements of the argument.
1356         */
1357        public boolean containsAll(Collection<?> c) {
1358            final Iterator<?> i = c.iterator();
1359            int n = c.size();
1360            while (n-- != 0)
1361                if (!contains(i.next())) return false;
1362            return true;
1363        }
1364
1365        /**
1366         * Retains in this collection only elements from the given type-specific collection.
1367         *
1368         * @param c a type-specific collection.
1369         * @return <code>true</code> if this collection changed as a result of the call.
1370         */
1371        public boolean retainAll(Collection<?> c) {
1372            boolean retVal = false;
1373            int n = size();
1374            final Iterator<?> i = iterator();
1375            while (n-- != 0) {
1376                if (!c.contains(i.next())) {
1377                    i.remove();
1378                    retVal = true;
1379                }
1380            }
1381            return retVal;
1382        }
1383
1384        /**
1385         * Remove from this collection all elements in the given type-specific collection.
1386         *
1387         * @param c a type-specific collection.
1388         * @return <code>true</code> if this collection changed as a result of the call.
1389         */
1390        public boolean removeAll(Collection<?> c) {
1391            boolean retVal = false;
1392            int n = c.size();
1393            final Iterator<?> i = c.iterator();
1394            while (n-- != 0)
1395                if (remove(i.next())) retVal = true;
1396            return false;
1397        }
1398
1399        public Object[] toArray() {
1400            final Object[] a = new Object[size()];
1401            objectUnwrap(iterator(), a);
1402            return a;
1403        }
1404
1405        /**
1406         * Adds all elements of the given collection to this collection.
1407         *
1408         * @param c a collection.
1409         * @return <code>true</code> if this collection changed as a result of the call.
1410         */
1411        public boolean addAll(Collection<? extends Integer> c) {
1412            boolean retVal = false;
1413            final Iterator<? extends Integer> i = c.iterator();
1414            int n = c.size();
1415            while (n-- != 0)
1416                if (add(i.next())) retVal = true;
1417            return false;
1418        }
1419
1420        @Override
1421        public boolean equals(final Object o) {
1422            if (o == this)
1423                return true;
1424            if (!(o instanceof Set))
1425                return false;
1426            Set<?> s = (Set<?>) o;
1427            if (s.size() != size())
1428                return false;
1429            return containsAll(s);
1430        }
1431        /**
1432         * Unwraps an iterator into an array starting at a given offset for a given number of elements.
1433         * <p>
1434         * <P>This method iterates over the given type-specific iterator and stores the elements returned, up to a maximum of <code>length</code>, in the given array starting at <code>offset</code>. The
1435         * number of actually unwrapped elements is returned (it may be less than <code>max</code> if the iterator emits less than <code>max</code> elements).
1436         *
1437         * @param i      a type-specific iterator.
1438         * @param array  an array to contain the output of the iterator.
1439         * @param offset the first element of the array to be returned.
1440         * @param max    the maximum number of elements to unwrap.
1441         * @return the number of elements unwrapped.
1442         */
1443        public int unwrap(final KeyIterator i, final int[] array, int offset, final int max) {
1444            if (max < 0) throw new IllegalArgumentException("The maximum number of elements (" + max + ") is negative");
1445            if (offset < 0 || offset + max > array.length) throw new IllegalArgumentException();
1446            int j = max;
1447            while (j-- != 0 && i.hasNext())
1448                array[offset++] = i.nextInt();
1449            return max - j - 1;
1450        }
1451        /**
1452         * Unwraps an iterator into an array.
1453         * <p>
1454         * <P>This method iterates over the given type-specific iterator and stores the elements returned in the given array. The iteration will stop when the iterator has no more elements or when the end
1455         * of the array has been reached.
1456         *
1457         * @param i     a type-specific iterator.
1458         * @param array an array to contain the output of the iterator.
1459         * @return the number of elements unwrapped.
1460         */
1461        public int unwrap(final KeyIterator i, final int[] array) {
1462            return unwrap(i, array, 0, array.length);
1463        }
1464        public int[] toIntArray() {
1465            int[] a = new int[size()];
1466            unwrap(iterator(), a);
1467            return a;
1468        }
1469
1470        public int[] toIntArray(int[] a) {
1471            if (a == null || a.length < size()) a = new int[size()];
1472            unwrap(iterator(), a);
1473            return a;
1474        }
1475
1476        /**
1477         * Unwraps an iterator into an array starting at a given offset for a given number of elements.
1478         * <p>
1479         * <P>This method iterates over the given type-specific iterator and stores the elements returned, up to a maximum of <code>length</code>, in the given array starting at <code>offset</code>. The
1480         * number of actually unwrapped elements is returned (it may be less than <code>max</code> if the iterator emits less than <code>max</code> elements).
1481         *
1482         * @param i      a type-specific iterator.
1483         * @param array  an array to contain the output of the iterator.
1484         * @param offset the first element of the array to be returned.
1485         * @param max    the maximum number of elements to unwrap.
1486         * @return the number of elements unwrapped.
1487         */
1488        public int unwrap(final KeyIterator i, final Object[] array, int offset, final int max) {
1489            if (max < 0) throw new IllegalArgumentException("The maximum number of elements (" + max + ") is negative");
1490            if (offset < 0 || offset + max > array.length) throw new IllegalArgumentException();
1491            int j = max;
1492            while (j-- != 0 && i.hasNext())
1493                array[offset++] = i.next();
1494            return max - j - 1;
1495        }
1496
1497        /**
1498         * Unwraps an iterator into an array.
1499         * <p>
1500         * <P>This method iterates over the given type-specific iterator and stores the elements returned in the given array. The iteration will stop when the iterator has no more elements or when the end
1501         * of the array has been reached.
1502         *
1503         * @param i     a type-specific iterator.
1504         * @param array an array to contain the output of the iterator.
1505         * @return the number of elements unwrapped.
1506         */
1507        public int unwrap(final KeyIterator i, final Object[] array) {
1508            return unwrap(i, array, 0, array.length);
1509        }
1510
1511        public boolean isEmpty() {
1512            return size() == 0;
1513        }
1514
1515        @Override
1516        public String toString() {
1517            final StringBuilder s = new StringBuilder();
1518            final KeyIterator i = iterator();
1519            int n = size();
1520            boolean first = true;
1521            s.append("{");
1522            while (n-- != 0) {
1523                if (first) first = false;
1524                else s.append(", ");
1525                s.append(i.next());
1526            }
1527            s.append("}");
1528            return s.toString();
1529        }
1530    }
1531
1532    public KeySet keySet() {
1533        if (keys == null) keys = new KeySet();
1534        return keys;
1535    }
1536
1537    public OrderedSet<Integer> keysAsOrderedSet()
1538    {
1539        OrderedSet<Integer> os = new OrderedSet<>(size, f);
1540        for (int i = 0; i < size; i++) {
1541            os.add(keyAt(i));
1542        }
1543        return os;
1544    }
1545    public int[] keysAsArray() {
1546        return keySet().toIntArray();
1547    }
1548
1549    /**
1550     * An iterator on values.
1551     * <p>
1552     * <P>We simply override the {@link ListIterator#next()}/{@link ListIterator#previous()} methods (and possibly their type-specific counterparts) so that they return values
1553     * instead of entries.
1554     */
1555    public final class ValueIterator extends MapIterator implements ListIterator<Double>, Serializable {
1556        private static final long serialVersionUID = 0L;
1557
1558        public Double previous() {
1559            return value[previousEntry()];
1560        }
1561        public void set(Double v) {
1562            throw new UnsupportedOperationException();
1563        }
1564        public void add(Double v) {
1565            throw new UnsupportedOperationException();
1566        }
1567        public ValueIterator() {}
1568        public Double next() {
1569            return value[nextEntry()];
1570        }
1571        public void remove() { super.remove(); }
1572    }
1573    public final class ValueCollection extends AbstractCollection<Double> implements Serializable
1574    {
1575        private static final long serialVersionUID = 0L;
1576        public ValueIterator iterator() {
1577            return new ValueIterator();
1578        }
1579        public int size() {
1580            return size;
1581        }
1582        public boolean contains(Object v) {
1583            return v instanceof Double && containsValue((Double)v);
1584        }
1585        public void clear() {
1586            IntDoubleOrderedMap.this.clear();
1587        }
1588    }
1589    public Collection<Double> values() {
1590        if (values == null) values = new ValueCollection();
1591        return values;
1592    }
1593
1594    public double[] valuesAsArray()
1595    {
1596        double[] ls = new double[size];
1597        for (int i = 0; i < size; i++) {
1598            ls[i] = getAt(i);
1599        }
1600        return ls;
1601    }
1602
1603    /**
1604     * Rehashes the map, making the table as small as possible.
1605     * <p>
1606     * <P>This method rehashes the table to the smallest size satisfying the load factor. It can be used when the set will not be changed anymore, so to optimize access speed and size.
1607     * <p>
1608     * <P>If the table size is already the minimum possible, this method does nothing.
1609     *
1610     * @return true if there was enough memory to trim the map.
1611     * @see #trim(int)
1612     */
1613    public boolean trim() {
1614        final int l = arraySize(size, f);
1615        if (l >= n || size > maxFill(l, f)) return true;
1616        try {
1617            rehash(l);
1618        } catch (Exception cantDoIt) {
1619            return false;
1620        }
1621        return true;
1622    }
1623
1624    /**
1625     * Rehashes this map if the table is too large.
1626     * <p>
1627     * <P>Let <var>N</var> be the smallest table size that can hold <code>max(n,{@link #size()})</code> entries, still satisfying the load factor. If the current table size is smaller than or equal to
1628     * <var>N</var>, this method does nothing. Otherwise, it rehashes this map in a table of size <var>N</var>.
1629     * <p>
1630     * <P>This method is useful when reusing maps. {@linkplain #clear() Clearing a map} leaves the table size untouched. If you are reusing a map many times, you can call this method with a typical
1631     * size to avoid keeping around a very large table just because of a few large transient maps.
1632     *
1633     * @param n the threshold for the trimming.
1634     * @return true if there was enough memory to trim the map.
1635     * @see #trim()
1636     */
1637    public boolean trim(final int n) {
1638        final int l = HashCommon.nextPowerOfTwo((int) Math.ceil(n / f));
1639        if (l >= n || size > maxFill(l, f)) return true;
1640        try {
1641            rehash(l);
1642        } catch (Exception cantDoIt) {
1643            return false;
1644        }
1645        return true;
1646    }
1647
1648    /**
1649     * Rehashes the map.
1650     *
1651     * <P>
1652     * This method implements the basic rehashing strategy, and may be overriden
1653     * by subclasses implementing different rehashing strategies (e.g.,
1654     * disk-based rehashing). However, you should not override this method
1655     * unless you understand the internal workings of this class.
1656     *
1657     * @param newN
1658     *            the new size
1659     */
1660
1661    protected void rehash(final int newN) {
1662        final int[] key = this.key;
1663        final double[] value = this.value;
1664        final int mask = newN - 1; // Note that this is used by the hashing macro
1665        final int[] newKey = new int[newN + 1];
1666        final double[] newValue = new double[newN + 1];
1667        final int sz = order.size;
1668        int k;
1669        int i, pos;
1670        final int[] oi = order.items;
1671        for (int q = 0; q < sz; q++) {
1672            i = oi[q];
1673            if ((k = key[i]) == 0)
1674                pos = newN;
1675            else {
1676                pos = (HashCommon.mix(k)) & mask;
1677                while (newKey[pos] != 0)
1678                    pos = (pos + 1) & mask;
1679            }
1680            newKey[pos] = k;
1681            newValue[pos] = value[i];
1682            oi[q] = pos;
1683        }
1684        n = newN;
1685        this.mask = mask;
1686        maxFill = maxFill(n, f);
1687        this.key = newKey;
1688        this.value = newValue;
1689    }
1690    /**
1691     * Returns a deep copy of this map.
1692     *
1693     * <P>
1694     * This method performs a deep copy of this OrderedMap; the data stored in the
1695     * map, however, is not cloned. Note that this makes a difference only for
1696     * object keys.
1697     *
1698     * @return a deep copy of this map.
1699     */
1700    @GwtIncompatible
1701    public IntDoubleOrderedMap clone() {
1702        IntDoubleOrderedMap c;
1703        try {
1704            c = (IntDoubleOrderedMap) super.clone();
1705            c.key = new int[n + 1];
1706            System.arraycopy(key, 0, c.key, 0, n + 1);
1707            c.value = new double[n + 1];
1708            System.arraycopy(value, 0, c.value, 0, n + 1);
1709            c.order = order.copy();
1710            return c;
1711        } catch (Exception cantHappen) {
1712            throw new UnsupportedOperationException(cantHappen + (cantHappen.getMessage() != null ?
1713                    "; " + cantHappen.getMessage() : ""));
1714        }
1715    }
1716    /**
1717     * Returns a hash code for this map.
1718     *
1719     * @return a hash code for this map.
1720     */
1721    public int hashCode() {
1722        int h = 0;
1723        for (int j = realSize(), i = 0, t; j-- != 0;) {
1724            while (key[i] == 0)
1725                i++;             
1726            t = HashCommon.mix(key[i]) ^ HashCommon.mix(
1727                    NumberTools.doubleToMixedIntBits(value[i]) ^ HashCommon.INV_INT_PHI);
1728            h += t;
1729            i++;
1730        }
1731        // Zero / null keys have hash zero.
1732        if (containsNullKey)
1733            h += HashCommon.mix(NumberTools.doubleToMixedIntBits(value[n]) ^ HashCommon.INV_INT_PHI);
1734        return h;
1735    }
1736
1737    public long hash64()
1738    {
1739        return 31L * (31L * CrossHash.hash64(key) + CrossHash.hash64(value)) + size;
1740    }
1741    /**
1742     * Returns the maximum number of entries that can be filled before rehashing.
1743     *
1744     * @param n the size of the backing array.
1745     * @param f the load factor.
1746     * @return the maximum number of entries before rehashing.
1747     */
1748    public static int maxFill(final int n, final float f) {
1749        /* We must guarantee that there is always at least
1750         * one free entry (even with pathological load factors). */
1751        return Math.min((int)(n * f + 0.99999994f), n - 1);
1752    }
1753
1754    /**
1755     * Returns the least power of two smaller than or equal to 2<sup>30</sup> and larger than or equal to <code>Math.ceil( expected / f )</code>.
1756     *
1757     * @param expected the expected number of elements in a hash table.
1758     * @param f        the load factor.
1759     * @return the minimum possible size for a backing array.
1760     * @throws IllegalArgumentException if the necessary size is larger than 2<sup>30</sup>.
1761     */
1762    public static int arraySize(final int expected, final float f) {
1763        final long s = Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(expected / f)));
1764        if (s > (1 << 30))
1765            throw new IllegalArgumentException("Too large (" + expected + " expected elements with load factor " + f + ")");
1766        return (int) s;
1767    }
1768
1769    /**
1770     * Unwraps an iterator into an array starting at a given offset for a given number of elements.
1771     * <p>
1772     * <P>This method iterates over the given type-specific iterator and stores the elements returned, up to a maximum of <code>length</code>, in the given array starting at <code>offset</code>. The
1773     * number of actually unwrapped elements is returned (it may be less than <code>max</code> if the iterator emits less than <code>max</code> elements).
1774     *
1775     * @param i      a type-specific iterator.
1776     * @param array  an array to contain the output of the iterator.
1777     * @param offset the first element of the array to be returned.
1778     * @param max    the maximum number of elements to unwrap.
1779     * @return the number of elements unwrapped.
1780     */
1781    private int unwrap(final ValueIterator i, final Object[] array, int offset, final int max) {
1782        if (max < 0) throw new IllegalArgumentException("The maximum number of elements (" + max + ") is negative");
1783        if (offset < 0 || offset + max > array.length) throw new IllegalArgumentException();
1784        int j = max;
1785        while (j-- != 0 && i.hasNext())
1786            array[offset++] = i.next();
1787        return max - j - 1;
1788    }
1789
1790    /**
1791     * Unwraps an iterator into an array.
1792     * <p>
1793     * <P>This method iterates over the given type-specific iterator and stores the elements returned in the given array. The iteration will stop when the iterator has no more elements or when the end
1794     * of the array has been reached.
1795     *
1796     * @param i     a type-specific iterator.
1797     * @param array an array to contain the output of the iterator.
1798     * @return the number of elements unwrapped.
1799     */
1800    private int unwrap(final ValueIterator i, final Object[] array) {
1801        return unwrap(i, array, 0, array.length);
1802    }
1803
1804
1805    /** Unwraps an iterator into an array starting at a given offset for a given number of elements.
1806     *
1807     * <P>This method iterates over the given type-specific iterator and stores the elements returned, up to a maximum of <code>length</code>, in the given array starting at <code>offset</code>. The
1808     * number of actually unwrapped elements is returned (it may be less than <code>max</code> if the iterator emits less than <code>max</code> elements).
1809     *
1810     * @param i a type-specific iterator.
1811     * @param array an array to contain the output of the iterator.
1812     * @param offset the first element of the array to be returned.
1813     * @param max the maximum number of elements to unwrap.
1814     * @return the number of elements unwrapped. */
1815    private static <K> int objectUnwrap(final Iterator<? extends K> i, final K[] array, int offset, final int max ) {
1816        if ( max < 0 ) throw new IllegalArgumentException( "The maximum number of elements (" + max + ") is negative" );
1817        if ( offset < 0 || offset + max > array.length ) throw new IllegalArgumentException();
1818        int j = max;
1819        while ( j-- != 0 && i.hasNext() )
1820            array[ offset++ ] = i.next();
1821        return max - j - 1;
1822    }
1823
1824    /** Unwraps an iterator into an array.
1825     *
1826     * <P>This method iterates over the given type-specific iterator and stores the elements returned in the given array. The iteration will stop when the iterator has no more elements or when the end
1827     * of the array has been reached.
1828     *
1829     * @param i a type-specific iterator.
1830     * @param array an array to contain the output of the iterator.
1831     * @return the number of elements unwrapped. */
1832    private static <K> int objectUnwrap(final Iterator<? extends K> i, final K[] array) {
1833        return objectUnwrap(i, array, 0, array.length );
1834    }
1835
1836    @Override
1837    public String toString() {
1838        final StringBuilder s = new StringBuilder();
1839        int n = size(), i = 0;
1840        boolean first = true;
1841        s.append("IntDoubleOrderedMap{");
1842        while (i < n) {
1843            if (first) first = false;
1844            else s.append(", ");
1845            s.append(entryAt(i++));
1846        }
1847        s.append("}");
1848        return s.toString();
1849    }
1850    @Override
1851    public boolean equals(Object o) {
1852        if (o == this)
1853            return true;
1854        if (!(o instanceof IntDoubleOrderedMap))
1855            return false;
1856        IntDoubleOrderedMap m = (IntDoubleOrderedMap) o;
1857        if (m.size() != size())
1858            return false;
1859        return entrySet().containsAll(m.entrySet());
1860    }
1861
1862    @GwtIncompatible
1863    private void writeObject(java.io.ObjectOutputStream s)
1864            throws java.io.IOException {
1865        final int[] key = this.key;
1866        final double[] value = this.value;
1867        final MapIterator i = new MapIterator();
1868        s.defaultWriteObject();
1869        for (int j = size, e; j-- != 0;) {
1870            e = i.nextEntry();
1871            s.writeInt(key[e]);
1872            s.writeDouble(value[e]);
1873        }
1874    }
1875    @GwtIncompatible
1876    private void readObject(java.io.ObjectInputStream s)
1877            throws java.io.IOException, ClassNotFoundException {
1878        s.defaultReadObject();
1879        n = arraySize(size, f);
1880        maxFill = maxFill(n, f);
1881        mask = n - 1;
1882        final int[] key = this.key = new int[n + 1];
1883        final double[] value = this.value = new double[n + 1];
1884        final IntVLA order = this.order = new IntVLA(n + 1);
1885        int k;
1886        double v;
1887        for (int i = size, pos; i-- != 0;) {
1888            k = s.readInt();
1889            v = s.readDouble();
1890            if (k == 0) {
1891                pos = n;
1892                containsNullKey = true;
1893            } else {
1894                pos = (HashCommon.mix(k))
1895                        & mask;
1896                while (!(key[pos] == 0))
1897                    pos = (pos + 1) & mask;
1898            }
1899
1900            key[pos] = k;
1901            value[pos] = v;
1902            order.add(pos);
1903        }
1904    }
1905
1906    /**
1907     * Gets the value at the given index in the iteration order in constant time (random-access).
1908     * @param idx the index in the iteration order of the value to fetch
1909     * @return the value at the index, if the index is valid, otherwise the default return value
1910     */
1911    public double getAt(final int idx) {
1912        int pos;
1913        if (idx < 0 || idx >= order.size)
1914            return defRetValue;
1915        // The starting point.
1916        if (key[pos = order.get(idx)] == 0)
1917            return containsNullKey ? value[n] : defRetValue;
1918        return value[pos];
1919    }
1920    /**
1921     * Gets the key at the given index in the iteration order in constant time (random-access).
1922     * @param idx the index in the iteration order of the key to fetch
1923     * @return the key at the index, if the index is valid, otherwise 0
1924     */
1925    public int keyAt(final int idx) {
1926        if (idx < 0 || idx >= order.size)
1927            return 0;
1928        // The starting point.
1929        return key[order.get(idx)];
1930    }
1931
1932    /**
1933     * Gets the key-value Map.Entry at the given index in the iteration order in constant time (random-access).
1934     * @param idx the index in the iteration order of the entry to fetch
1935     * @return the key-value entry at the index, if the index is valid, otherwise null
1936     */
1937    public MapEntry entryAt(final int idx)
1938    {
1939        if (idx < 0 || idx >= order.size)
1940            return null;
1941        return new MapEntry(order.get(idx));
1942    }
1943
1944    /**
1945     * Removes the key and value at the given index in the iteration order in not-exactly constant time (though it still
1946     * should be efficient).
1947     * @param idx the index in the iteration order of the key and value to remove
1948     * @return the value removed, if there was anything removed, or the default return value otherwise (often null)
1949     */
1950    public double removeAt(final int idx) {
1951
1952        if (idx < 0 || idx >= order.size)
1953            return defRetValue;
1954        int pos = order.get(idx);
1955        if (key[pos] == 0) {
1956            if (containsNullKey)
1957                return removeNullEntry();
1958            return defRetValue;
1959        }
1960        return removeEntry(pos);
1961    }
1962    /**
1963     * Gets a random value from this OrderedMap in constant time, using the given IRNG to generate a random number.
1964     * @param rng used to generate a random index for a value
1965     * @return a random value from this OrderedMap
1966     */
1967    public double randomValue(IRNG rng)
1968    {
1969        return getAt(rng.nextInt(order.size));
1970    }
1971
1972    /**
1973     * Gets a random key from this OrderedMap in constant time, using the given IRNG to generate a random number.
1974     * @param rng used to generate a random index for a key
1975     * @return a random key from this OrderedMap
1976     */
1977    public int randomKey(IRNG rng)
1978    {
1979        return keyAt(rng.nextInt(order.size));
1980    }
1981
1982    /**
1983     * Gets a random entry from this OrderedMap in constant time, using the given IRNG to generate a random number.
1984     * @param rng used to generate a random index for a entry
1985     * @return a random key-value entry from this OrderedMap
1986     */
1987    public MapEntry randomEntry(IRNG rng)
1988    {
1989        return new MapEntry(order.getRandomElement(rng));
1990    }
1991
1992    /**
1993     * Randomly alters the iteration order for this OrderedMap using the given IRNG to shuffle.
1994     * @param rng used to generate a random ordering
1995     * @return this for chaining
1996     */
1997    public IntDoubleOrderedMap shuffle(IRNG rng)
1998    {
1999        if(size < 2)
2000            return this;
2001        order.shuffle(rng);
2002        return this;
2003    }
2004
2005    /**
2006     * Given an array or varargs of replacement indices for this OrderedMap's iteration order, reorders this so the
2007     * first item in the returned version is the same as {@code getAt(ordering[0])} (with some care taken for negative
2008     * or too-large indices), the second item in the returned version is the same as {@code getAt(ordering[1])}, etc.
2009     * <br>
2010     * Negative indices are considered reversed distances from the end of ordering, so -1 refers to the same index as
2011     * {@code ordering[ordering.length - 1]}. If ordering is smaller than {@code size()}, only the indices up to the
2012     * length of ordering will be modified. If ordering is larger than {@code size()}, only as many indices will be
2013     * affected as {@code size()}, and reversed distances are measured from the end of this Map's entries instead of
2014     * the end of ordering. Duplicate values in ordering will produce duplicate values in the returned Map.
2015     * <br>
2016     * This method modifies this OrderedMap in-place and also returns it for chaining.
2017     * @param ordering an array or varargs of int indices, where the nth item in ordering changes the nth item in this
2018     *                 Map to have the value currently in this Map at the index specified by the value in ordering
2019     * @return this for chaining, after modifying it in-place
2020     */
2021    public IntDoubleOrderedMap reorder(int... ordering)
2022    {
2023        order.reorder(ordering);
2024        return this;
2025    }
2026    private int alterEntry(final int pos) {
2027        int idx = fixOrder(pos);
2028        size--;
2029        shiftKeys(pos);
2030        return idx;
2031    }
2032    private int alterNullEntry() {
2033        int idx = fixOrder(n);
2034        containsNullKey = false;
2035        size--;
2036        return idx;
2037    }
2038    /**
2039     * Swaps a key, original, for another key, replacement, while keeping replacement at the same point in the iteration
2040     * order as original and keeping it associated with the same value (which also keeps its iteration index). Unlike
2041     * the similar method {@link #alter(int, int)}, this will not change this OrderedMap if replacement is already
2042     * present. To contrast, alter() can reduce the size of the OrderedMap if both original and replacement are already
2043     * in the Map. If replacement is found, this returns the default return value, otherwise it switches out original
2044     * for replacement and returns whatever was associated with original.
2045     * @param original the key to find and swap out
2046     * @param replacement the key to replace original with
2047     * @return the value associated with original before, and replacement now
2048     */
2049    public double alterCarefully(final int original, final int replacement) {
2050        if(!containsKey(replacement))
2051            return alter(original, replacement);
2052        else
2053            return defRetValue;
2054    }
2055    /**
2056     * Swaps a key, original, for another key, replacement, while keeping replacement at the same point in the iteration
2057     * order as original and keeping it associated with the same value (which also keeps its iteration index).
2058     * Be aware that if both original and replacement are present in the OrderedMap, this will still replace original
2059     * with replacement but will also remove the other occurrence of replacement to avoid duplicate keys. This can throw
2060     * off the expected order because the duplicate could be at any point in the ordering when it is removed. You may
2061     * want to prefer {@link #alterCarefully(int, int)} if you don't feel like checking by hand for whether
2062     * replacement is already present, but using this method is perfectly reasonable if you know overlaps won't happen.
2063     * @param original the key to find and swap out
2064     * @param replacement the key to replace original with
2065     * @return the value associated with original before, and replacement now
2066     */
2067    public double alter(final int original, final int replacement) {
2068        double v;
2069        int idx;
2070        if (original == 0) {
2071            if (containsNullKey) {
2072                v = value[n];
2073                idx = alterNullEntry();
2074                putAt(replacement, v, idx);
2075                return v;
2076            }
2077            else
2078                v = defRetValue;
2079            return v;
2080        }
2081        int curr;
2082        final int[] key = this.key;
2083        int pos;
2084        // The starting point.
2085        if ((curr = key[pos = (HashCommon.mix(original)) & mask]) == 0)
2086            return defRetValue;
2087        if (original == curr)
2088        {
2089            v = value[pos];
2090            idx = alterEntry(pos);
2091            putAt(replacement, v, idx);
2092            return v;
2093        }
2094        while (true) {
2095            if ((curr = key[pos = (pos + 1) & mask]) == 0)
2096                return defRetValue;
2097            if (original == curr)
2098            {
2099                v = value[pos];
2100                idx = alterEntry(pos);
2101                putAt(replacement, v, idx);
2102                return v;
2103            }
2104        }
2105    }
2106
2107    public double[] getMany(int... keys)
2108    {
2109        if(keys == null || keys.length == 0)
2110            return new double[0];
2111        final int len = keys.length;
2112        double[] vals = new double[len];
2113        for (int i = 0; i < len; i++) {
2114            vals[i] = get(keys[i]);
2115        }
2116        return vals;
2117    }
2118    /**
2119     * Changes the int at the given index to replacement while keeping replacement at the same point in the ordering.
2120     * Be aware that if replacement is present in the OrderedMap, this will still replace the given index
2121     * with replacement but will also remove the other occurrence of replacement to avoid duplicate keys. This can throw
2122     * off the expected order because the duplicate could be at any point in the ordering when it is removed. You may
2123     * want to prefer {@link #alterAtCarefully(int, int)} if you don't feel like checking by hand for whether
2124     * replacement is already present, but using this method is perfectly reasonable if you know overlaps won't happen.
2125     * @param index       an index to replace the int key at
2126     * @param replacement another int key that will replace the original at the remembered index
2127     * @return the value associated with the possibly-altered key
2128     */
2129    public double alterAt(int index, int replacement)
2130    {
2131        return alter(keyAt(index), replacement);
2132    }
2133    /**
2134     * Changes the int at the given index to replacement while keeping replacement at the same point in the ordering.
2135     * Unlike the similar method {@link #alterAt(int, int)}, this will not change this OrderedMap if replacement is
2136     * already present. To contrast, alterAt() can reduce the size of the OrderedMap if replacement is already
2137     * in the Map. If replacement is found, this returns the default return value, otherwise it switches out the index
2138     * for replacement and returns whatever value was at the index before.
2139     * @param index       an index to replace the int key at
2140     * @param replacement another int key that will replace the original at the remembered index
2141     * @return the value associated with the key at the altered index before, and replacement now
2142     */
2143    public double alterAtCarefully(int index, int replacement)
2144    {
2145        return alterCarefully(keyAt(index), replacement);
2146    }
2147
2148    /**
2149     * If the specified key is not already associated with a value, associates it with the given value
2150     * and returns that value, else returns the current value without changing anything.
2151     *
2152     * @param key   key with which the specified value is to be associated
2153     * @param value value to be associated with the specified key
2154     * @return the previous value associated with the specified key, or
2155     * {@code value} if there was no mapping for the key.
2156     */
2157    public double putIfAbsent(int key, double value) {
2158        if(containsKey(key))
2159            return get(key);         
2160        put(key, value);
2161        return value;
2162    }
2163
2164    /**
2165     * Removes the entry for the specified key only if it is currently
2166     * mapped to the specified value.
2167     *
2168     * @param key   key with which the specified value is associated
2169     * @param value value expected to be associated with the specified key
2170     * @return {@code true} if the value was removed
2171     */
2172    public boolean remove(int key, double value) {
2173        if (containsKey(key) && get(key) == value) {
2174            remove(key);
2175            return true;
2176        } else
2177            return false;
2178    }
2179
2180    /**
2181     * Replaces the entry for the specified key only if currently
2182     * mapped to the specified value. The position in the iteration
2183     * order is retained.
2184     *
2185     * @param key      key with which the specified value is associated
2186     * @param oldValue value expected to be associated with the specified key
2187     * @param newValue value to be associated with the specified key
2188     * @return {@code true} if the value was replaced
2189     */
2190    public boolean replace(int key, double oldValue, double newValue) {
2191        if (containsKey(key) && get(key) == oldValue) {
2192            put(key, newValue);
2193            return true;
2194        } else
2195            return false;
2196    }
2197
2198    /**
2199     * Replaces the entry for the specified key only if it is
2200     * currently mapped to some value. Preserves the existing key's
2201     * position in the iteration order.
2202     *
2203     * @param key   key with which the specified value is associated
2204     * @param value value to be associated with the specified key
2205     * @return the previous value associated with the specified key, or
2206     * {@code null} if there was no mapping for the key.
2207     * (A {@code null} return can also indicate that the map
2208     * previously associated {@code null} with the key.)
2209     */
2210    public double replace(int key, double value) {
2211        if (containsKey(key)) {
2212            return put(key, value);
2213        } else
2214            return defRetValue;
2215    }
2216    
2217    /**
2218     * Reverses the iteration order in linear time.
2219     */
2220    public void reverse()
2221    {
2222        order.reverse();
2223    }
2224}