Package squidpony.squidmath

Class IntIntOrderedMap

java.lang.Object
squidpony.squidmath.IntIntOrderedMap
All Implemented Interfaces:
Serializable, Cloneable
public class IntIntOrderedMap
extends Object
implements Serializable, Cloneable
An int-key and int-value insertion-ordered hash map with with a fast implementation, originally from fastutil as Object2ObjectLinkedOpenHashMap but modified (in OrderedMap) to support constant-time indexed access of keys, values, and entries, and reordering. Deletion is slower with this algorithm (O(n) because the array used to keep track of ordering and indexing only allows linear-time deletion, instead of a linked-list approach allowing constant-time deletion but not helping at all with indexed access), and insertion sometimes takes longer than an ordered map using a linked-list for order because rehashing is more expensive. The benefits from constant-time access by index are numerous, especially for games, since fetching a random element becomes O(1) instead of O(n), and the index can be used to store extra info for no cost.
Instances of this class use a hash table to represent a map. The table is filled up to a specified load factor, and then doubled in size to accommodate new entries. If the table is emptied below one fourth 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 process.
Note that clear() does not modify the hash table size. Rather, a family of trimming methods lets you control the size of the table; this is particularly useful if you reuse instances of this class.
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 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, IntVLA, and is modifiable with this class' reorder(int...) and shuffle(IRNG) methods, among other tools. It may be preferable to avoid instantiating an Iterator object and instead use a normal int-based for loop with getAt(int) called in each iteration. Though this doesn't allow easy deletion of items during iteration, it may be the fastest way to iterate through an OrderedMap.
This class allows approximately constant-time lookup of keys or values by their index in the ordering, which can allow some novel usage of the data structure. OrderedSet can be used like a list of unique elements, keeping order like a list does but also allowing rapid checks for whether an item exists in the OrderedSet, and OrderedMap can be used like that but with values associated as well (where OrderedSet uses contains(), OrderedMap uses containsKey()). You can also set the key and value at a position with putAt(int, int, int), or alter the key while keeping its value and index the same with alter(int, int). Reordering works here too, both with completely random orders from shuffle(IRNG) or with a previously-generated ordering from reorder(int...) (you can produce such an ordering for a given size and reuse it across multiple Ordered data structures with IRNG.randomOrdering(int)). Note that putAt() and removeAt(int) do not run in constant time, and depending on the point of insertion/removal, they are likely to run in linear time (but also note that most insertion-ordered Maps and Sets don't allow insertion or removal at anywhere but the beginning or end of the order).
This doesn't allow custom IHashers because IHasher expects an Object to hash, and that would box the keys every time.
Thank you, Sebastiano Vigna, for making FastUtil available to the public with such high quality.
See https://github.com/vigna/fastutil for the original library.
Author:
Sebastiano Vigna (responsible for all the hard parts), Tommy Ettinger (mostly responsible for squashing several layers of parent classes into one monster class)
See Also:
Serialized Form

  • Nested Class Summary

    Nested Classes 
    Modifier and Type Class Description
    class  IntIntOrderedMap.FastEntryIterator  
    class  IntIntOrderedMap.KeyIterator
    An iterator on keys.
    class  IntIntOrderedMap.KeySet  
    class  IntIntOrderedMap.MapEntry
    The entry class for a OrderedMap does not record key and value, but rather the position in the hash table of the corresponding entry.
    class  IntIntOrderedMap.MapEntrySet  
    class  IntIntOrderedMap.ValueCollection  
    class  IntIntOrderedMap.ValueIterator
    An iterator on values.

  • Field Summary

    Fields 
    Modifier and Type Field Description
    protected boolean containsNullKey
    Whether this set contains the key zero.
    static int DEFAULT_INITIAL_SIZE
    The initial default size of a hash table.
    static float DEFAULT_LOAD_FACTOR
    The default load factor of a hash table.
    protected int defRetValue
    Default return value.
    protected IntIntOrderedMap.MapEntrySet entries
    Cached set of entries.
    float f
    The acceptable load factor.
    static float FAST_LOAD_FACTOR
    The load factor for a (usually small) table that is meant to be particularly fast.
    protected int[] key
    The array of keys.
    protected IntIntOrderedMap.KeySet keys
    Cached set of keys.
    protected int mask
    The mask for wrapping a position counter.
    protected int maxFill
    Threshold after which we rehash.
    protected int n
    The current table size.
    protected IntVLA order
    An IntVLA (variable-length int sequence) that stores the positions in the key array of specific keys, with the positions in insertion order.
    protected int size
    Number of entries in the set (including the key zero, if present).
    protected int[] value
    The array of values.
    protected IntIntOrderedMap.ValueCollection values
    Cached collection of values.
    static float VERY_FAST_LOAD_FACTOR
    The load factor for a (usually very small) table that is meant to be extremely fast.

  • Constructor Summary

    Constructors 
    Constructor Description
    IntIntOrderedMap()
    Creates a new OrderedMap with initial expected 16 entries and 0.75f as load factor.
    IntIntOrderedMap​(int expected)
    Creates a new OrderedMap with 0.75f as load factor.
    IntIntOrderedMap​(int[] keyArray, int[] valueArray)
    Creates a new OrderedMap with 0.75f as load factor using the elements of two parallel arrays.
    IntIntOrderedMap​(int[] keyArray, int[] valueArray, float f)
    Creates a new OrderedMap using the elements of two parallel arrays.
    IntIntOrderedMap​(int expected, float f)
    Creates a new OrderedMap.
    IntIntOrderedMap​(IntIntOrderedMap m)
    Creates a new OrderedMap with 0.75f as load factor copying a given one.
    IntIntOrderedMap​(IntIntOrderedMap m, float f)
    Creates a new OrderedMap copying a given one.
    IntIntOrderedMap​(IntVLA keyColl, IntVLA valueColl)
    Creates a new OrderedMap using the elements of two parallel arrays.
    IntIntOrderedMap​(IntVLA keyColl, IntVLA valueColl, float f)
    Creates a new OrderedMap using the elements of two parallel arrays.

  • Method Summary

    Modifier and Type Method Description
    int alter​(int original, int replacement)
    Swaps a key, original, for another key, replacement, while keeping replacement at the same point in the iteration order as original and keeping it associated with the same value (which also keeps its iteration index).
    int alterAt​(int index, int replacement)
    Changes the int at the given index to replacement while keeping replacement at the same point in the ordering.
    int alterAtCarefully​(int index, int replacement)
    Changes the int at the given index to replacement while keeping replacement at the same point in the ordering.
    int alterCarefully​(int original, int replacement)
    Swaps a key, original, for another key, replacement, while keeping replacement at the same point in the iteration order as original and keeping it associated with the same value (which also keeps its iteration index).
    static int arraySize​(int expected, float f)
    Returns the least power of two smaller than or equal to 230 and larger than or equal to Math.ceil( expected / f ).
    void clear()  
    IntIntOrderedMap clone()
    Returns a deep copy of this map.
    boolean containsKey​(int k)  
    boolean containsValue​(int v)  
    int defaultReturnValue()  
    void defaultReturnValue​(int rv)  
    IntIntOrderedMap.MapEntry entryAt​(int idx)
    Gets the key-value Map.Entry at the given index in the iteration order in constant time (random-access).
    SortedSet<IntIntOrderedMap.MapEntry> entrySet()  
    boolean equals​(Object o)  
    int firstKey()
    Returns the first key of this map in iteration order.
    protected int fixOrder​(int i)
    Modifies the ordering so that the given entry is removed.
    protected void fixOrder​(int s, int d)
    Modifies the ordering for a shift from s to d.
    int get​(int k)  
    int getAndIncrement​(int k, int increment)
    Looks up the key k in this map, remembers the associated value (which will be defaultReturnValue() if k wasn't found), adds increment to the actual associated value in the map, and returns the remembered value.
    int getAt​(int idx)
    Gets the value at the given index in the iteration order in constant time (random-access).
    IntVLA getMany​(int... keys)  
    int getOrDefault​(int k, int defaultValue)  
    long hash64()  
    int hashCode()
    Returns a hash code for this map.
    int indexOf​(int k)
    Gets the position in the ordering of the given key, though not as efficiently as some data structures can do it (e.g.
    boolean isEmpty()  
    int keyAt​(int idx)
    Gets the key at the given index in the iteration order in constant time (random-access).
    int[] keysAsArray()  
    OrderedSet<Integer> keysAsOrderedSet()  
    IntIntOrderedMap.KeySet keySet()  
    int lastKey()
    Returns the last key of this map in iteration order.
    static IntIntOrderedMap makeMap()
    Makes an empty IntIntOrderedMap.This method is provided for completeness relative to makeMap() with 2 or more parameters.
    static IntIntOrderedMap makeMap​(int k0, int v0, int... rest)
    Makes an IntIntOrderedMap using the given int keys and values in alternating key-value-key-value order.
    static int maxFill​(int n, float f)
    Returns the maximum number of entries that can be filled before rehashing.
    protected int positionOf​(int k)  
    int put​(int k, int v)  
    void putAll​(int[] keyArray, int[] valueArray)
    Puts the first key in keyArray with the first value in valueArray, then the second in each and so on.
    void putAll​(IntIntOrderedMap m)
    Puts all key-value pairs in the Map m into this OrderedMap.
    int putAt​(int k, int v, int idx)  
    int putIfAbsent​(int key, int value)
    If the specified key is not already associated with a value, associates it with the given value and returns that value, else returns the current value without changing anything.
    IntIntOrderedMap putPairs​(int k0, int v0, int... rest)
    Given alternating key and value arguments in pairs, puts each key-value pair into this OrderedMap as if by calling put(int, int) repeatedly for each pair.
    IntIntOrderedMap.MapEntry randomEntry​(IRNG rng)
    Gets a random entry from this OrderedMap in constant time, using the given IRNG to generate a random number.
    int randomKey​(IRNG rng)
    Gets a random key from this OrderedMap in constant time, using the given IRNG to generate a random number.
    int randomValue​(IRNG rng)
    Gets a random value from this OrderedMap in constant time, using the given IRNG to generate a random number.
    protected void rehash​(int newN)
    Rehashes the map.
    int remove​(int k)  
    boolean remove​(int key, int value)
    Removes the entry for the specified key only if it is currently mapped to the specified value.
    int removeAt​(int idx)
    Removes the key and value at the given index in the iteration order in not-exactly constant time (though it still should be efficient).
    int removeFirst()
    Removes the mapping associated with the first key in iteration order.
    int removeLast()
    Removes the mapping associated with the last key in iteration order.
    IntIntOrderedMap reorder​(int... ordering)
    Given an array or varargs of replacement indices for this OrderedMap's iteration order, reorders this so the first item in the returned version is the same as getAt(ordering[0]) (with some care taken for negative or too-large indices), the second item in the returned version is the same as getAt(ordering[1]), etc.
    int replace​(int key, int value)
    Replaces the entry for the specified key only if it is currently mapped to some value.
    boolean replace​(int key, int oldValue, int newValue)
    Replaces the entry for the specified key only if currently mapped to the specified value.
    void reverse()
    Reverses the iteration order in linear time.
    protected void shiftKeys​(int pos)
    Shifts left entries with the specified hash code, starting at the specified position, and empties the resulting free entry.
    IntIntOrderedMap shuffle​(IRNG rng)
    Randomly alters the iteration order for this OrderedMap using the given IRNG to shuffle.
    int size()  
    boolean swap​(int left, int right)
    Swaps the positions in the ordering for the given items, if they are both present.
    boolean swapIndices​(int left, int right)
    Swaps the given indices in the ordering, if they are both valid int indices.
    String toString()  
    boolean trim()
    Rehashes the map, making the table as small as possible.
    boolean trim​(int n)
    Rehashes this map if the table is too large.
    Collection<Integer> values()  
    IntVLA valuesAsList()  

    Methods inherited from class java.lang.Object

    finalize, getClass, notify, notifyAll, wait, wait, wait

  • Field Details

  • Constructor Details

    • IntIntOrderedMap

      public IntIntOrderedMap​(int expected, float f)
      Creates a new OrderedMap.

      The actual table size will be the least power of two greater than expected/f.

      Parameters:
      expected - the expected number of elements in the hash set.
      f - the load factor.

    • IntIntOrderedMap

      public IntIntOrderedMap​(int expected)
      Creates a new OrderedMap with 0.75f as load factor.
      Parameters:
      expected - the expected number of elements in the OrderedMap.

    • IntIntOrderedMap

      public IntIntOrderedMap()
      Creates a new OrderedMap with initial expected 16 entries and 0.75f as load factor.

    • IntIntOrderedMap

      public IntIntOrderedMap​(IntIntOrderedMap m, float f)
      Creates a new OrderedMap copying a given one.
      Parameters:
      m - a Map to be copied into the new OrderedMap.
      f - the load factor.

    • IntIntOrderedMap

      public IntIntOrderedMap​(IntIntOrderedMap m)
      Creates a new OrderedMap with 0.75f as load factor copying a given one.
      Parameters:
      m - a Map to be copied into the new OrderedMap.

    • IntIntOrderedMap

      public IntIntOrderedMap​(int[] keyArray, int[] valueArray, float f)
      Creates a new OrderedMap using the elements of two parallel arrays.
      Parameters:
      keyArray - the array of keys of the new OrderedMap.
      valueArray - the array of corresponding values in the new OrderedMap.
      f - the load factor.
      Throws:
      IllegalArgumentException - if k and v have different lengths.

    • IntIntOrderedMap

      public IntIntOrderedMap​(IntVLA keyColl, IntVLA valueColl)
      Creates a new OrderedMap using the elements of two parallel arrays.
      Parameters:
      keyColl - the collection of keys of the new OrderedMap.
      valueColl - the collection of corresponding values in the new OrderedMap.
      Throws:
      IllegalArgumentException - if k and v have different lengths.

    • IntIntOrderedMap

      public IntIntOrderedMap​(IntVLA keyColl, IntVLA valueColl, float f)
      Creates a new OrderedMap using the elements of two parallel arrays.
      Parameters:
      keyColl - the collection of keys of the new OrderedMap.
      valueColl - the collection of corresponding values in the new OrderedMap.
      f - the load factor.
      Throws:
      IllegalArgumentException - if k and v have different lengths.

    • IntIntOrderedMap

      public IntIntOrderedMap​(int[] keyArray, int[] valueArray)
      Creates a new OrderedMap with 0.75f as load factor using the elements of two parallel arrays.
      Parameters:
      keyArray - the array of keys of the new OrderedMap.
      valueArray - the array of corresponding values in the new OrderedMap.
      Throws:
      IllegalArgumentException - if k and v have different lengths.

  • Method Details

    • defaultReturnValue

      public void defaultReturnValue​(int rv)

    • defaultReturnValue

      public int defaultReturnValue()

    • putAll

      public void putAll​(int[] keyArray, int[] valueArray)
      Puts the first key in keyArray with the first value in valueArray, then the second in each and so on. The entries are all appended to the end of the iteration order, unless a key was already present. Then, its value is changed at the existing position in the iteration order. If the lengths of the two arrays are not equal, this puts a number of entries equal to the lesser length. If either array is null, this returns without performing any changes.
      Parameters:
      keyArray - an array of int keys that should usually have the same length as valueArray
      valueArray - an array of int values that should usually have the same length as keyArray

    • putAll

      public void putAll​(IntIntOrderedMap m)
      Puts all key-value pairs in the Map m into this OrderedMap. The entries are all appended to the end of the iteration order, unless a key was already present. Then, its value is changed at the existing position in the iteration order. This can take any kind of Map, including unordered HashMap objects; if the Map does not have stable ordering, the order in which entries will be appended is not stable either. For this reason, OrderedMap, LinkedHashMap, and TreeMap (or other SortedMap implementations) will work best when order matters.
      Parameters:
      m - an IntIntOrderedMap to add into this

    • put

      public int put​(int k, int v)

    • putAt

      public int putAt​(int k, int v, int idx)

    • shiftKeys

      protected final void shiftKeys​(int pos)
      Shifts left entries with the specified hash code, starting at the specified position, and empties the resulting free entry.
      Parameters:
      pos - a starting position.

    • remove

      public int remove​(int k)

    • removeFirst

      public int removeFirst()
      Removes the mapping associated with the first key in iteration order.
      Returns:
      the value previously associated with the first key in iteration order.
      Throws:
      NoSuchElementException - is this map is empty.

    • removeLast

      public int removeLast()
      Removes the mapping associated with the last key in iteration order.
      Returns:
      the value previously associated with the last key in iteration order.
      Throws:
      NoSuchElementException - is this map is empty.

    • get

      public int get​(int k)

    • getOrDefault

      public int getOrDefault​(int k, int defaultValue)

    • positionOf

      protected int positionOf​(int k)

    • indexOf

      public int indexOf​(int k)
      Gets the position in the ordering of the given key, though not as efficiently as some data structures can do it (e.g. Arrangement can access ordering position very quickly but doesn't store other values on its own). Returns a value that is at least 0 if it found k, or -1 if k was not present.
      Parameters:
      k - a key or possible key that this should find the index of
      Returns:
      the index of k, if present, or -1 if it is not present in this OrderedMap

    • swap

      public boolean swap​(int left, int right)
      Swaps the positions in the ordering for the given items, if they are both present. Returns true if the ordering changed as a result of this call, or false if it stayed the same (which can be because left or right was not present, or because left and right are the same reference (so swapping would do nothing)).
      Parameters:
      left - an item that should be present in this OrderedMap
      right - an item that should be present in this OrderedMap
      Returns:
      true if this OrderedMap changed in ordering as a result of this call, or false otherwise

    • swapIndices

      public boolean swapIndices​(int left, int right)
      Swaps the given indices in the ordering, if they are both valid int indices. Returns true if the ordering changed as a result of this call, or false if it stayed the same (which can be because left or right referred to an out-of-bounds index, or because left and right are equal (so swapping would do nothing)).
      Parameters:
      left - an index of an item in this OrderedMap, at least 0 and less than size()
      right - an index of an item in this OrderedMap, at least 0 and less than size()
      Returns:
      true if this OrderedMap changed in ordering as a result of this call, or false otherwise

    • containsKey

      public boolean containsKey​(int k)

    • containsValue

      public boolean containsValue​(int v)

    • clear

      public void clear()

    • size

      public int size()

    • isEmpty

      public boolean isEmpty()

    • getAndIncrement

      public int getAndIncrement​(int k, int increment)
      Looks up the key k in this map, remembers the associated value (which will be defaultReturnValue() if k wasn't found), adds increment to the actual associated value in the map, and returns the remembered value.
      Parameters:
      k - a key to look up
      increment - an int to add to the value associated with k
      Returns:
      the previous value associated with k, or defaultReturnValue() if k wasn't found

    • fixOrder

      protected int fixOrder​(int i)
      Modifies the ordering so that the given entry is removed. This method will complete in logarithmic time.
      Parameters:
      i - the index of an entry.
      Returns:
      the iteration-order index of the removed entry

    • fixOrder

      protected void fixOrder​(int s, int d)
      Modifies the ordering for a shift from s to d.
      This method will complete in logarithmic time or better.
      Parameters:
      s - the source position.
      d - the destination position.

    • firstKey

      public int firstKey()
      Returns the first key of this map in iteration order.
      Returns:
      the first key in iteration order.

    • lastKey

      public int lastKey()
      Returns the last key of this map in iteration order.
      Returns:
      the last key in iteration order.

    • entrySet

      public SortedSet<IntIntOrderedMap.MapEntry> entrySet()

    • keySet

      public IntIntOrderedMap.KeySet keySet()

    • keysAsOrderedSet

      public OrderedSet<Integer> keysAsOrderedSet()

    • keysAsArray

      public int[] keysAsArray()

    • values

      public Collection<Integer> values()

    • valuesAsList

      public IntVLA valuesAsList()

    • trim

      public boolean trim()
      Rehashes the map, making the table as small as possible.

      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.

      If the table size is already the minimum possible, this method does nothing.

      Returns:
      true if there was enough memory to trim the map.
      See Also:
      trim(int)

    • trim

      public boolean trim​(int n)
      Rehashes this map if the table is too large.

      Let N be the smallest table size that can hold max(n,size()) entries, still satisfying the load factor. If the current table size is smaller than or equal to N, this method does nothing. Otherwise, it rehashes this map in a table of size N.

      This method is useful when reusing maps. Clearing a map leaves the table size untouched. If you are reusing a map many times, you can call this method with a typical size to avoid keeping around a very large table just because of a few large transient maps.

      Parameters:
      n - the threshold for the trimming.
      Returns:
      true if there was enough memory to trim the map.
      See Also:
      trim()

    • rehash

      protected void rehash​(int newN)
      Rehashes the map.

      This method implements the basic rehashing strategy, and may be overriden by subclasses implementing different rehashing strategies (e.g., disk-based rehashing). However, you should not override this method unless you understand the internal workings of this class.

      Parameters:
      newN - the new size

    • clone

      public IntIntOrderedMap clone()
      Returns a deep copy of this map.

      This method performs a deep copy of this OrderedMap; the data stored in the map, however, is not cloned. Note that this makes a difference only for object keys.

      Overrides:
      clone in class Object
      Returns:
      a deep copy of this map.

    • hashCode

      public int hashCode()
      Returns a hash code for this map.
      Overrides:
      hashCode in class Object
      Returns:
      a hash code for this map.

    • hash64

      public long hash64()

    • maxFill

      public static int maxFill​(int n, float f)
      Returns the maximum number of entries that can be filled before rehashing.
      Parameters:
      n - the size of the backing array.
      f - the load factor.
      Returns:
      the maximum number of entries before rehashing.

    • arraySize

      public static int arraySize​(int expected, float f)
      Returns the least power of two smaller than or equal to 230 and larger than or equal to Math.ceil( expected / f ).
      Parameters:
      expected - the expected number of elements in a hash table.
      f - the load factor.
      Returns:
      the minimum possible size for a backing array.
      Throws:
      IllegalArgumentException - if the necessary size is larger than 230.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • equals

      public boolean equals​(Object o)
      Overrides:
      equals in class Object

    • getAt

      public int getAt​(int idx)
      Gets the value at the given index in the iteration order in constant time (random-access).
      Parameters:
      idx - the index in the iteration order of the value to fetch
      Returns:
      the value at the index, if the index is valid, otherwise the default return value

    • keyAt

      public int keyAt​(int idx)
      Gets the key at the given index in the iteration order in constant time (random-access).
      Parameters:
      idx - the index in the iteration order of the key to fetch
      Returns:
      the key at the index, if the index is valid, otherwise 0

    • entryAt

      public IntIntOrderedMap.MapEntry entryAt​(int idx)
      Gets the key-value Map.Entry at the given index in the iteration order in constant time (random-access).
      Parameters:
      idx - the index in the iteration order of the entry to fetch
      Returns:
      the key-value entry at the index, if the index is valid, otherwise null

    • removeAt

      public int removeAt​(int idx)
      Removes the key and value at the given index in the iteration order in not-exactly constant time (though it still should be efficient).
      Parameters:
      idx - the index in the iteration order of the key and value to remove
      Returns:
      the value removed, if there was anything removed, or the default return value otherwise (often null)

    • randomValue

      public int randomValue​(IRNG rng)
      Gets a random value from this OrderedMap in constant time, using the given IRNG to generate a random number.
      Parameters:
      rng - used to generate a random index for a value
      Returns:
      a random value from this OrderedMap

    • randomKey

      public int randomKey​(IRNG rng)
      Gets a random key from this OrderedMap in constant time, using the given IRNG to generate a random number.
      Parameters:
      rng - used to generate a random index for a key
      Returns:
      a random key from this OrderedMap

    • randomEntry

      public IntIntOrderedMap.MapEntry randomEntry​(IRNG rng)
      Gets a random entry from this OrderedMap in constant time, using the given IRNG to generate a random number.
      Parameters:
      rng - used to generate a random index for a entry
      Returns:
      a random key-value entry from this OrderedMap

    • shuffle

      public IntIntOrderedMap shuffle​(IRNG rng)
      Randomly alters the iteration order for this OrderedMap using the given IRNG to shuffle.
      Parameters:
      rng - used to generate a random ordering
      Returns:
      this for chaining

    • reorder

      public IntIntOrderedMap reorder​(int... ordering)
      Given an array or varargs of replacement indices for this OrderedMap's iteration order, reorders this so the first item in the returned version is the same as getAt(ordering[0]) (with some care taken for negative or too-large indices), the second item in the returned version is the same as getAt(ordering[1]), etc.
      Negative indices are considered reversed distances from the end of ordering, so -1 refers to the same index as ordering[ordering.length - 1]. If ordering is smaller than size(), only the indices up to the length of ordering will be modified. If ordering is larger than size(), only as many indices will be affected as size(), and reversed distances are measured from the end of this Map's entries instead of the end of ordering. Duplicate values in ordering will produce duplicate values in the returned Map.
      This method modifies this OrderedMap in-place and also returns it for chaining.
      Parameters:
      ordering - an array or varargs of int indices, where the nth item in ordering changes the nth item in this Map to have the value currently in this Map at the index specified by the value in ordering
      Returns:
      this for chaining, after modifying it in-place

    • alterCarefully

      public int alterCarefully​(int original, int replacement)
      Swaps a key, original, for another key, replacement, while keeping replacement at the same point in the iteration order as original and keeping it associated with the same value (which also keeps its iteration index). Unlike the similar method alter(int, int), this will not change this OrderedMap if replacement is already present. To contrast, alter() can reduce the size of the OrderedMap if both original and replacement are already in the Map. If replacement is found, this returns the default return value, otherwise it switches out original for replacement and returns whatever was associated with original.
      Parameters:
      original - the key to find and swap out
      replacement - the key to replace original with
      Returns:
      the value associated with original before, and replacement now

    • alter

      public int alter​(int original, int replacement)
      Swaps a key, original, for another key, replacement, while keeping replacement at the same point in the iteration order as original and keeping it associated with the same value (which also keeps its iteration index). Be aware that if both original and replacement are present in the OrderedMap, this will still replace original with replacement but will also remove the other occurrence of replacement to avoid duplicate keys. This can throw off the expected order because the duplicate could be at any point in the ordering when it is removed. You may want to prefer alterCarefully(int, int) if you don't feel like checking by hand for whether replacement is already present, but using this method is perfectly reasonable if you know overlaps won't happen.
      Parameters:
      original - the key to find and swap out
      replacement - the key to replace original with
      Returns:
      the value associated with original before, and replacement now

    • getMany

      public IntVLA getMany​(int... keys)

    • alterAt

      public int alterAt​(int index, int replacement)
      Changes the int at the given index to replacement while keeping replacement at the same point in the ordering. Be aware that if replacement is present in the OrderedMap, this will still replace the given index with replacement but will also remove the other occurrence of replacement to avoid duplicate keys. This can throw off the expected order because the duplicate could be at any point in the ordering when it is removed. You may want to prefer alterAtCarefully(int, int) if you don't feel like checking by hand for whether replacement is already present, but using this method is perfectly reasonable if you know overlaps won't happen.
      Parameters:
      index - an index to replace the int key at
      replacement - another int key that will replace the original at the remembered index
      Returns:
      the value associated with the possibly-altered key

    • alterAtCarefully

      public int alterAtCarefully​(int index, int replacement)
      Changes the int at the given index to replacement while keeping replacement at the same point in the ordering. Unlike the similar method alterAt(int, int), this will not change this OrderedMap if replacement is already present. To contrast, alterAt() can reduce the size of the OrderedMap if replacement is already in the Map. If replacement is found, this returns the default return value, otherwise it switches out the index for replacement and returns whatever value was at the index before.
      Parameters:
      index - an index to replace the int key at
      replacement - another int key that will replace the original at the remembered index
      Returns:
      the value associated with the key at the altered index before, and replacement now

    • putIfAbsent

      public int putIfAbsent​(int key, int value)
      If the specified key is not already associated with a value, associates it with the given value and returns that value, else returns the current value without changing anything.
      Parameters:
      key - key with which the specified value is to be associated
      value - value to be associated with the specified key
      Returns:
      the previous value associated with the specified key, or value if there was no mapping for the key.

    • remove

      public boolean remove​(int key, int value)
      Removes the entry for the specified key only if it is currently mapped to the specified value.
      Parameters:
      key - key with which the specified value is associated
      value - value expected to be associated with the specified key
      Returns:
      true if the value was removed

    • replace

      public boolean replace​(int key, int oldValue, int newValue)
      Replaces the entry for the specified key only if currently mapped to the specified value. The position in the iteration order is retained.
      Parameters:
      key - key with which the specified value is associated
      oldValue - value expected to be associated with the specified key
      newValue - value to be associated with the specified key
      Returns:
      true if the value was replaced

    • replace

      public int replace​(int key, int value)
      Replaces the entry for the specified key only if it is currently mapped to some value. Preserves the existing key's position in the iteration order.
      Parameters:
      key - key with which the specified value is associated
      value - value to be associated with the specified key
      Returns:
      the previous value associated with the specified key, or null if there was no mapping for the key. (A null return can also indicate that the map previously associated null with the key.)

    • putPairs

      public IntIntOrderedMap putPairs​(int k0, int v0, int... rest)
      Given alternating key and value arguments in pairs, puts each key-value pair into this OrderedMap as if by calling put(int, int) repeatedly for each pair. This mimics the parameter syntax used for makeMap(int, int, int...), and can be used to retain that style of insertion after an IntIntOrderedMap has been instantiated.
      Parameters:
      k0 - the first key to add
      v0 - the first value to add
      rest - an array or vararg of keys and values in pairs; should contain alternating only int elements
      Returns:
      this, after adding all viable key-value pairs given

    • makeMap

      public static IntIntOrderedMap makeMap​(int k0, int v0, int... rest)
      Makes an IntIntOrderedMap using the given int keys and values in alternating key-value-key-value order. If rest has an odd-number length, then it discards the last item. If any item in rest is not an int, this will not compile. This is similar to the makeOM method in the Maker class, but produces an IntIntOrderedMap.
      This is named makeMap to indicate that it expects key and value parameters, unlike a Set or List. This convention may be extended to other data structures that also have static methods for instantiation.
      Parameters:
      k0 - the first key; used to infer the types of other keys if generic parameters aren't specified.
      v0 - the first value; used to infer the types of other values if generic parameters aren't specified.
      rest - an array or vararg of keys and values in pairs; should contain only int elements
      Returns:
      a freshly-made IntIntOrderedMap, using k0, v0, and the contents of rest to fill it

    • makeMap

      public static IntIntOrderedMap makeMap()
      Makes an empty IntIntOrderedMap.This method is provided for completeness relative to makeMap() with 2 or more parameters.
      Returns:
      an empty IntIntOrderedMap

    • reverse

      public void reverse()
      Reverses the iteration order in linear time.