squidpony.squidmath.Arrangement<K>

All Implemented Interfaces:: Serializable, Cloneable, Iterable<K>, Map<K,Integer>, SortedMap<K,Integer>

public class Arrangement<K>
extends Object
implements SortedMap<K,Integer>, Iterable<K>, Serializable, Cloneable

A bi-directional mapping of objects to positions in an ordering (which this generates), and vice versa. Useful for various indirection techniques where you want to be able to retrieve a value in several ways, such as with multiple Arrangements all sharing the same ordering but with different types for keys.
Originally, this started as a generic linked hash map with with a fast implementation, originally from fastutil as Object2IntLinkedOpenHashMap but modified to support indexed access. The code is extremely close to OrderedMap, and like OrderedMap you can look up keys by index, but this is specialized to int values which it can automatically assign.

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.

This class implements the interface of a sorted map, so to allow easy access of the iteration order: for instance, you can get the first key in iteration order with firstKey() without having to create an iterator; however, this class partially violates the SortedMap contract because all submap methods throw an exception and comparator() returns always null.

Additional methods, such as getAndMoveToFirst(), make it easy to use instances of this class as a cache (e.g., with LRU policy).

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`	`Arrangement.FastEntryIterator`
`class`	`Arrangement.KeyIterator`	An iterator on keys.
`class`	`Arrangement.KeySet`
`class`	`Arrangement.ValueCollection`
`class`	`Arrangement.ValueIterator`	An iterator on values.

Nested classes/interfaces inherited from interface java.util.Map

Map.Entry<K extends Object,V extends Object>

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 squidpony.squidmath.Arrangement.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 CrossHash.IHasher`	`hasher`
`protected K[]`	`key`	The array of keys.
`protected Arrangement.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`	The ordering of entries, with the nth entry in order being the index into `key` and `value` to find that entry's key and value.
`protected int`	`size`	Number of entries in the set (including the key zero, if present).
`protected int[]`	`value`	The array of values.
`protected Collection<Integer>`	`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
`Arrangement()`	Creates a new Arrangement with initial expected 16 entries and 0.5f as load factor.
`Arrangement(int expected)`	Creates a new Arrangement with 0.5f as load factor.
`Arrangement(int expected, float f)`	Creates a new Arrangement.
`Arrangement(int expected, float f, CrossHash.IHasher hasher)`	Creates a new Arrangement.
`Arrangement(int expected, CrossHash.IHasher hasher)`	Creates a new Arrangement with 0.5f as load factor.
`Arrangement(Collection<K> keyColl)`	Creates a new Arrangement using the elements of an array.
`Arrangement(Collection<K> keyColl, float f)`	Creates a new Arrangement using the given collection of keys.
`Arrangement(Map<? extends K,? extends Integer> m)`	Creates a new Arrangement with 0.5f as load factor copying a given one.
`Arrangement(Map<? extends K,? extends Integer> m, float f)`	Creates a new Arrangement copying a given one.
`Arrangement(Map<? extends K,? extends Integer> m, float f, CrossHash.IHasher hasher)`	Creates a new Arrangement copying a given one.
`Arrangement(Map<? extends K,? extends Integer> m, CrossHash.IHasher hasher)`	Creates a new Arrangement with 0.5f as load factor copying a given one.
`Arrangement(K[] keyArray)`	Creates a new Arrangement with 0.5f as load factor using the elements of an array.
`Arrangement(K[] keyArray, float f)`	Creates a new Arrangement using the elements of an array.
`Arrangement(K[] keyArray, float f, CrossHash.IHasher hasher)`	Creates a new Arrangement using the elements of two parallel arrays.
`Arrangement(K[] keyArray, CrossHash.IHasher hasher)`	Creates a new Arrangement with 0.5f as load factor using the elements of two parallel arrays.
`Arrangement(Arrangement<? extends K> a)`
`Arrangement(CrossHash.IHasher hasher)`	Creates a new Arrangement with initial expected 16 entries and 0.5f as load factor.

Method Summary

Modifier and Type	Method	Description
`int`	`add(K k)`
`int`	`addAt(int idx, K k)`	Equivalent to `add(Object)`, except that it can place k at any point in the ordering (shifting up later entries and changing their values to match their new positions in the ordering).
`int`	`addIfAbsent(K k)`
`int`	`addOrIndex(K k)`	If the given key `k` is present, this returns its index without modifying the Arrangement; otherwise, it adds k to the end of the collection and returns the index for it there.
`int`	`alter(K original, K 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, K replacement)`	Changes the K at the given index to replacement while keeping replacement at the same point in the ordering.
`static int`	`arraySize(int expected, float f)`	Returns the least power of two smaller than or equal to 2³⁰ and larger than or equal to `Math.ceil( expected / f )`.
`void`	`clear()`
`Arrangement<K>`	`clone()`	Returns a deep copy of this map.
`Comparator<? super K>`	`comparator()`
`boolean`	`containsKey(Object k)`
`boolean`	`containsValue(int v)`
`boolean`	`containsValue(Object ov)`
`Map.Entry<K,Integer>`	`entryAt(int idx)`	Gets the key-value Map.Entry at the given index in the iteration order in constant time (random-access).
`SortedSet<Map.Entry<K,Integer>>`	`entrySet()`
`boolean`	`equals(Object o)`
`K`	`firstKey()`	Returns the first key of this map in iteration order.
`protected void`	`fixOrder(int i)`	Modifies the link vector so that the given entry is removed.
`protected void`	`fixOrder(int s, int d)`	Modifies the link vector for a shift from s to d.
`protected void`	`fixValues(int start)`
`Integer`	`get(Object k)`
`int`	`getAndMoveToFirst(K k)`	Returns the value to which the given key is mapped; if the key is present, it is moved to the first position of the iteration order.
`int`	`getAndMoveToLast(K k)`	Returns the value to which the given key is mapped; if the key is present, it is moved to the last position of the iteration order.
`int[]`	`getArray(Collection<? extends K> keys)`
`int[]`	`getArray(K[] keys)`
`int`	`getAt(int idx)`	Gets the value at the given index in the iteration order in constant time (random-access).
`int`	`getInt(Object k)`
`IntVLA`	`getMany(Iterable<? extends K> keys)`
`long`	`hash64()`
`int`	`hashCode()`	Returns a hash code for this map.
`SortedMap<K,Integer>`	`headMap(K to)`
`boolean`	`isEmpty()`
`Iterator<K>`	`iterator()`	Returns an iterator over elements of type `T`.
`K`	`keyAt(int idx)`	Gets the key at the given index in the iteration order in constant time (random-access).
`OrderedSet<K>`	`keysAsOrderedSet()`
`OrderedSet<K>`	`keysAt(int... positions)`
`OrderedSet<K>`	`keysAt(IntVLA positions)`
`Arrangement.KeySet`	`keySet()`
`K`	`lastKey()`	Returns the last key of this map in iteration order.
`squidpony.squidmath.Arrangement.MapEntrySet`	`mapEntrySet()`
`static int`	`maxFill(int n, float f)`	Returns the maximum number of entries that can be filled before rehashing.
`static long`	`maxFill(long n, float f)`	Returns the maximum number of entries that can be filled before rehashing.
`protected int`	`positionOf(Object k)`
`int`	`put(K k, int v)`
`Integer`	`put(K k, Integer v)`	Deprecated.
`void`	`putAll(Collection<? extends K> keyColl)`
`void`	`putAll(Map<? extends K,? extends Integer> m)`
`void`	`putAll(K[] keyArray)`
`int`	`putAndMoveToFirst(K k, int v)`	Adds a pair to the map; if the key is already present, it is moved to the first position of the iteration order.
`int`	`putAndMoveToLast(K k, int v)`	Adds a pair to the map; if the key is already present, it is moved to the last position of the iteration order.
`Map.Entry<K,Integer>`	`randomEntry(IRNG rng)`	Gets a random entry from this Arrangement in constant time, using the given IRNG to generate a random number.
`K`	`randomKey(IRNG rng)`	Gets a random key from this Arrangement in constant time, using the given IRNG to generate a random number.
`int`	`randomValue(IRNG rng)`	Gets a random value from this Arrangement in constant time, using the given IRNG to generate a random number.
`protected void`	`rehash(int newN)`	Rehashes the map.
`protected Integer`	`rem(Object k)`
`Integer`	`remove(Object o)`
`K`	`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).
`K`	`removeFirst()`	Removes the mapping associated with the first key in iteration order.
`int`	`removeInt(Object k)`
`K`	`removeLast()`	Removes the mapping associated with the last key in iteration order.
`Arrangement<K>`	`reorder(int... ordering)`	Given an array or varargs of replacement indices for this Arrangement'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.
`boolean`	`retainAll(Collection<?> c)`	Retains in this collection only elements from the given collection.
`protected void`	`shiftKeys(int pos)`	Shifts left entries with the specified hash code, starting at the specified position, and empties the resulting free entry.
`protected void`	`shiftKeysValues(int pos)`	Shifts left entries with the specified hash code, starting at the specified position, and empties the resulting free entry.
`Arrangement<K>`	`shuffle(IRNG rng)`	Randomly alters the iteration order for this Arrangement using the given IRNG to shuffle.
`int`	`size()`
`void`	`sort(Comparator<? super K> comparator)`	Sorts this whole Arrangement using the supplied Comparator.
`void`	`sort(Comparator<? super K> comparator, int start, int end)`	Sorts a sub-range of this Arrangement from what is currently the index `start` up to (but not including) the index `end`, using the supplied Comparator.
`SortedMap<K,Integer>`	`subMap(K from, K to)`
`boolean`	`swap(K left, K 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 ints between 0 and size.
`SortedMap<K,Integer>`	`tailMap(K from)`
`Arrangement<K>`	`take(int amount)`	Produces a copy of this Arrangement, but only using up to the given amount of items to take.
`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()`
`int[]`	`valuesAsArray()`
`IntVLA`	`valuesAsIntVLA()`
`ArrayList<Integer>`	`valuesAsList()`

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface java.util.Map

compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll

Field Details
- key
  
  protected K[] key
  
  The array of keys.
- value
  
  protected int[] value
  
  The array of values.
- mask
  
  protected int mask
  
  The mask for wrapping a position counter.
- containsNullKey
  
  protected boolean containsNullKey
  
  Whether this set contains the key zero.
- order
  
  protected IntVLA order
  
  The ordering of entries, with the nth entry in order being the index into key and value to find that entry's key and value. The ints in order are always less than or equal to n, and greater than or equal to 0.
- n
  
  protected int n
  
  The current table size.
- maxFill
  
  protected int maxFill
  
  Threshold after which we rehash. It must be the table size times f.
- size
  
  protected int size
  
  Number of entries in the set (including the key zero, if present).
- f
  
  public final float f
  
  The acceptable load factor.
- entries
  
  protected volatile squidpony.squidmath.Arrangement.MapEntrySet entries
  
  Cached set of entries.
- keys
  
  protected volatile Arrangement.KeySet keys
  
  Cached set of keys.
- values
  
  protected volatile Collection<Integer> values
  
  Cached collection of values.
- defRetValue
  
  protected final int defRetValue
  
  Default return value.
  
  See Also:
  
  Constant Field Values
- DEFAULT_INITIAL_SIZE
  
  public static final int DEFAULT_INITIAL_SIZE
  
  The initial default size of a hash table.
  
  See Also:
  
  Constant Field Values
- DEFAULT_LOAD_FACTOR
  
  public static final float DEFAULT_LOAD_FACTOR
  
  The default load factor of a hash table.
  
  See Also:
  
  Constant Field Values
- FAST_LOAD_FACTOR
  
  public static final float FAST_LOAD_FACTOR
  
  The load factor for a (usually small) table that is meant to be particularly fast.
  
  See Also:
  
  Constant Field Values
- VERY_FAST_LOAD_FACTOR
  
  public static final float VERY_FAST_LOAD_FACTOR
  
  The load factor for a (usually very small) table that is meant to be extremely fast.
  
  See Also:
  
  Constant Field Values
- hasher
  
  protected final CrossHash.IHasher hasher
Constructor Details
- Arrangement
  
  public Arrangement(int expected, float f)
  
  Creates a new Arrangement.
  
  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.
- Arrangement
  
  public Arrangement(int expected)
  
  Creates a new Arrangement with 0.5f as load factor.
  
  Parameters:
  
  expected - the expected number of elements in the Arrangement.
- Arrangement
  
  public Arrangement()
  
  Creates a new Arrangement with initial expected 16 entries and 0.5f as load factor.
- Arrangement
  
  public Arrangement(Map<? extends K,? extends Integer> m, float f)
  
  Creates a new Arrangement copying a given one.
  
  Parameters:
  
  m - a Map to be copied into the new Arrangement.
  
  f - the load factor.
- Arrangement
  
  public Arrangement(Map<? extends K,? extends Integer> m)
  
  Creates a new Arrangement with 0.5f as load factor copying a given one.
  
  Parameters:
  
  m - a Map to be copied into the new Arrangement.
- Arrangement
  
  public Arrangement(Arrangement<? extends K> a)
- Arrangement
  
  public Arrangement(K[] keyArray, float f)
  
  Creates a new Arrangement using the elements of an array.
  
  Parameters:
  
  keyArray - the array of keys of the new Arrangement.
  
  f - the load factor.
  
  Throws:
  
  IllegalArgumentException - if k and v have different lengths.
- Arrangement
  
  public Arrangement(Collection<K> keyColl)
  
  Creates a new Arrangement using the elements of an array.
  
  Parameters:
  
  keyColl - the collection of keys of the new Arrangement.
  
  Throws:
  
  IllegalArgumentException - if k and v have different lengths.
- Arrangement
  
  public Arrangement(Collection<K> keyColl, float f)
  
  Creates a new Arrangement using the given collection of keys.
  
  Parameters:
  
  keyColl - the collection of keys of the new Arrangement.
  
  f - the load factor.
  
  Throws:
  
  IllegalArgumentException - if k and v have different lengths.
- Arrangement
  
  public Arrangement(K[] keyArray)
  
  Creates a new Arrangement with 0.5f as load factor using the elements of an array.
  
  Parameters:
  
  keyArray - the array of keys of the new Arrangement.
  
  Throws:
  
  IllegalArgumentException - if k and v have different lengths.
- Arrangement
  
  public Arrangement(int expected, float f, CrossHash.IHasher hasher)
  
  Creates a new Arrangement.
  
  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.
  
  hasher - used to hash items; typically only needed when K is an array, where CrossHash has implementations
- Arrangement
  
  public Arrangement(int expected, CrossHash.IHasher hasher)
  
  Creates a new Arrangement with 0.5f as load factor.
  
  Parameters:
  
  expected - the expected number of elements in the Arrangement.
  
  hasher - used to hash items; typically only needed when K is an array, where CrossHash has implementations
- Arrangement
  
  public Arrangement(CrossHash.IHasher hasher)
  
  Creates a new Arrangement with initial expected 16 entries and 0.5f as load factor.
- Arrangement
  
  public Arrangement(Map<? extends K,? extends Integer> m, float f, CrossHash.IHasher hasher)
  
  Creates a new Arrangement copying a given one.
  
  Parameters:
  
  m - a Map to be copied into the new Arrangement.
  
  f - the load factor.
  
  hasher - used to hash items; typically only needed when K is an array, where CrossHash has implementations
- Arrangement
  
  public Arrangement(Map<? extends K,? extends Integer> m, CrossHash.IHasher hasher)
  
  Creates a new Arrangement with 0.5f as load factor copying a given one.
  
  Parameters:
  
  m - a Map to be copied into the new Arrangement.
  
  hasher - used to hash items; typically only needed when K is an array, where CrossHash has implementations
- Arrangement
  
  public Arrangement(K[] keyArray, float f, CrossHash.IHasher hasher)
  
  Creates a new Arrangement using the elements of two parallel arrays.
  
  Parameters:
  
  keyArray - the array of keys of the new Arrangement.
  
  f - the load factor.
  
  hasher - used to hash items; typically only needed when K is an array, where CrossHash has implementations
  
  Throws:
  
  IllegalArgumentException - if k and v have different lengths.
- Arrangement
  
  public Arrangement(K[] keyArray, CrossHash.IHasher hasher)
  
  Creates a new Arrangement with 0.5f as load factor using the elements of two parallel arrays.
  
  Parameters:
  
  keyArray - the array of keys of the new Arrangement.
  
  hasher - used to hash items; typically only needed when K is an array, where CrossHash has implementations
  
  Throws:
  
  IllegalArgumentException - if k and v have different lengths.
Method Details
- putAll
  
  public void putAll(Map<? extends K,? extends Integer> m)
  
  Specified by:
  
  putAll in interface Map<K,Integer>
- putAll
  
  public void putAll(K[] keyArray)
- putAll
  
  public void putAll(Collection<? extends K> keyColl)
- put
  
  @Deprecated public Integer put(K k, Integer v)
  
  Deprecated.
  
  Puts the key k into this Arrangement with a value equal to the current number of keys; v is disregarded.
  
  Specified by:
  
  put in interface Map<K,Integer>
  
  Parameters:
  
  k - any K type, including null
  
  v - any Integer, doesn't matter what it is and will be disregarded. Only here for compatibility
  
  Returns:
  
  the Integer that was previously associated with k, or -1 if there was none
- put
  
  public int put(K k, int v)
- add
  
  public int add(K k)
- addIfAbsent
  
  public int addIfAbsent(K k)
- addOrIndex
  
  public int addOrIndex(K k)
  
  If the given key k is present, this returns its index without modifying the Arrangement; otherwise, it adds k to the end of the collection and returns the index for it there.
  
  Parameters:
  
  k - a key to get the index of, adding it if not present
  
  Returns:
  
  the index of k in this Arrangement
- fixValues
  
  protected void fixValues(int start)
- 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.
- shiftKeysValues
  
  protected final void shiftKeysValues(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.
- rem
  
  protected Integer rem(Object k)
- remove
  
  public Integer remove(Object o)
  
  Specified by:
  
  remove in interface Map<K,Integer>
- removeInt
  
  public int removeInt(Object k)
- removeFirst
  
  public K 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 K 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.
- getAndMoveToFirst
  
  public int getAndMoveToFirst(K k)
  
  Returns the value to which the given key is mapped; if the key is present, it is moved to the first position of the iteration order.
  
  Parameters:
  
  k - the key.
  
  Returns:
  
  the corresponding value, or -1 if no value was present for the given key.
- getAndMoveToLast
  
  public int getAndMoveToLast(K k)
  
  Returns the value to which the given key is mapped; if the key is present, it is moved to the last position of the iteration order.
  
  Parameters:
  
  k - the key.
  
  Returns:
  
  the corresponding value, or -1 if no value was present for the given key.
- putAndMoveToFirst
  
  public int putAndMoveToFirst(K k, int v)
  
  Adds a pair to the map; if the key is already present, it is moved to the first position of the iteration order.
  
  Parameters:
  
  k - the key.
  
  v - the value.
  
  Returns:
  
  the old value, or -1 if no value was present for the given key.
- putAndMoveToLast
  
  public int putAndMoveToLast(K k, int v)
  
  Adds a pair to the map; if the key is already present, it is moved to the last position of the iteration order.
  
  Parameters:
  
  k - the key.
  
  v - the value.
  
  Returns:
  
  the old value, or -1 if no value was present for the given key.
- get
  
  public Integer get(Object k)
  
  Specified by:
  
  get in interface Map<K,Integer>
- getInt
  
  public int getInt(Object k)
- containsKey
  
  public boolean containsKey(Object k)
  
  Specified by:
  
  containsKey in interface Map<K,Integer>
- containsValue
  
  public boolean containsValue(int v)
- containsValue
  
  public boolean containsValue(Object ov)
  
  Specified by:
  
  containsValue in interface Map<K,Integer>
- clear
  
  public void clear()
  
  Specified by:
  
  clear in interface Map<K,Integer>
- size
  
  public int size()
  
  Specified by:
  
  size in interface Map<K,Integer>
- isEmpty
  
  public boolean isEmpty()
  
  Specified by:
  
  isEmpty in interface Map<K,Integer>
- iterator
  
  public Iterator<K> iterator()
  
  Returns an iterator over elements of type T.
  
  Specified by:
  
  iterator in interface Iterable<K>
  
  Returns:
  
  an Iterator.
- fixOrder
  
  protected void fixOrder(int i)
  
  Modifies the link vector so that the given entry is removed. This method will complete in linear time.
  
  Parameters:
  
  i - the index of an entry.
- fixOrder
  
  protected void fixOrder(int s, int d)
  
  Modifies the link vector 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 K firstKey()
  
  Returns the first key of this map in iteration order.
  
  Specified by:
  
  firstKey in interface SortedMap<K,Integer>
  
  Returns:
  
  the first key in iteration order.
- lastKey
  
  public K lastKey()
  
  Returns the last key of this map in iteration order.
  
  Specified by:
  
  lastKey in interface SortedMap<K,Integer>
  
  Returns:
  
  the last key in iteration order.
- retainAll
  
  public boolean retainAll(Collection<?> c)
  
  Retains in this collection only elements from the given collection.
  
  Parameters:
  
  c - a collection.
  
  Returns:
  
  true if this collection changed as a result of the call.
- comparator
  
  public Comparator<? super K> comparator()
  
  Specified by:
  
  comparator in interface SortedMap<K,Integer>
- tailMap
  
  public SortedMap<K,Integer> tailMap(K from)
  
  Specified by:
  
  tailMap in interface SortedMap<K,Integer>
- headMap
  
  public SortedMap<K,Integer> headMap(K to)
  
  Specified by:
  
  headMap in interface SortedMap<K,Integer>
- subMap
  
  public SortedMap<K,Integer> subMap(K from, K to)
  
  Specified by:
  
  subMap in interface SortedMap<K,Integer>
- entrySet
  
  public SortedSet<Map.Entry<K,Integer>> entrySet()
  
  Specified by:
  
  entrySet in interface Map<K,Integer>
  
  Specified by:
  
  entrySet in interface SortedMap<K,Integer>
- mapEntrySet
  
  public squidpony.squidmath.Arrangement.MapEntrySet mapEntrySet()
- keySet
  
  public Arrangement.KeySet keySet()
  
  Specified by:
  
  keySet in interface Map<K,Integer>
  
  Specified by:
  
  keySet in interface SortedMap<K,Integer>
- keysAsOrderedSet
  
  public OrderedSet<K> keysAsOrderedSet()
- values
  
  public Collection<Integer> values()
  
  Specified by:
  
  values in interface Map<K,Integer>
  
  Specified by:
  
  values in interface SortedMap<K,Integer>
- valuesAsList
  
  public ArrayList<Integer> valuesAsList()
- valuesAsIntVLA
  
  public IntVLA valuesAsIntVLA()
- valuesAsArray
  
  public int[] valuesAsArray()
- 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 Arrangement<K> clone()
  
  Returns a deep copy of this map.
  This method performs a deep copy of this Arrangement; 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. This method overrides the generic method provided by the superclass. Since equals() is not overriden, it is important that the value returned by this method is the same value as the one returned by the overriden method.
  
  Specified by:
  
  hashCode in interface Map<K,Integer>
  
  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.
- maxFill
  
  public static long maxFill(long 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 2³⁰ 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 2³⁰.
- toString
  
  public String toString()
  
  Overrides:
  
  toString in class Object
- equals
  
  public boolean equals(Object o)
  
  Specified by:
  
  equals in interface Map<K,Integer>
  
  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 K 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 null
- entryAt
  
  public Map.Entry<K,Integer> 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 K 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 key removed, if there was anything removed, or null otherwise
- addAt
  
  public int addAt(int idx, K k)
  
  Equivalent to add(Object), except that it can place k at any point in the ordering (shifting up later entries and changing their values to match their new positions in the ordering).
  
  Parameters:
  
  idx - the position in the ordering to place k at; will not be used if negative or greater than the current size (it can be equal to the current size)
  
  k - the key to add into this Arrangement; its value will be idx
  
  Returns:
  
  the previous position in the ordering that k had if already present, the previous size of the Arrangement if k was just added now, or -1 if idx is invalid
- randomValue
  
  public int randomValue(IRNG rng)
  
  Gets a random value from this Arrangement 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 Arrangement, or -1 if this is empty
- randomKey
  
  public K randomKey(IRNG rng)
  
  Gets a random key from this Arrangement 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 Arrangement, or null if this is empty
- randomEntry
  
  public Map.Entry<K,Integer> randomEntry(IRNG rng)
  
  Gets a random entry from this Arrangement 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 Arrangement
- shuffle
  
  public Arrangement<K> shuffle(IRNG rng)
  
  Randomly alters the iteration order for this Arrangement using the given IRNG to shuffle.
  
  Parameters:
  
  rng - used to generate a random ordering
  
  Returns:
  
  this for chaining
- reorder
  
  public Arrangement<K> reorder(int... ordering)
  
  Given an array or varargs of replacement indices for this Arrangement'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 Arrangement 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
- alter
  
  public int alter(K original, K 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).
  
  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
- getArray
  
  public int[] getArray(K[] keys)
- getArray
  
  public int[] getArray(Collection<? extends K> keys)
- getMany
  
  public IntVLA getMany(Iterable<? extends K> keys)
- keysAt
  
  public OrderedSet<K> keysAt(int... positions)
- keysAt
  
  public OrderedSet<K> keysAt(IntVLA positions)
- take
  
  public Arrangement<K> take(int amount)
  
  Produces a copy of this Arrangement, but only using up to the given amount of items to take. Does a shallow copy of individual keys, so the references will be shared.
  
  Parameters:
  
  amount - the number of items to copy from this Arrangement; will copy all items if greater than size
  
  Returns:
  
  a new Arrangement with up to amount items copied from this into it.
- positionOf
  
  protected int positionOf(Object k)
- swap
  
  public boolean swap(K left, K 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 OrderedSet
  
  right - an item that should be present in this OrderedSet
  
  Returns:
  
  true if this OrderedSet 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 ints between 0 and size. 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 OrderedSet, at least 0 and less than size()
  
  right - an index of an item in this OrderedSet, at least 0 and less than size()
  
  Returns:
  
  true if this OrderedSet changed in ordering as a result of this call, or false otherwise
- alterAt
  
  public int alterAt(int index, K replacement)
  
  Changes the K at the given index to replacement while keeping replacement at the same point in the ordering.
  
  Parameters:
  
  index - an index to replace the K key at
  
  replacement - another K key that will replace the original at the remembered index
  
  Returns:
  
  the int associated with the possibly-altered key; should be equal to index
- sort
  
  public void sort(Comparator<? super K> comparator)
  
  Sorts this whole Arrangement using the supplied Comparator.
  
  Parameters:
  
  comparator - a Comparator that can be used on the same type this uses for its keys (may need wildcards)
- sort
  
  public void sort(Comparator<? super K> comparator, int start, int end)
  
  Sorts a sub-range of this Arrangement from what is currently the index start up to (but not including) the index end, using the supplied Comparator.
  
  Parameters:
  
  comparator - a Comparator that can be used on the same type this uses for its keys (may need wildcards)
  
  start - the first index of a key to sort (the index can change after this)
  
  end - the exclusive bound on the indices to sort; often this is just size()

Class Arrangement<K>