public class IntIntOrderedMap
extends java.lang.Object
implements java.io.Serializable, java.lang.Cloneable
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.
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.
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.
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).
Modifier and Type | Class and 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.
|
Modifier and Type | Field and 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 and 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.
|
Modifier and Type | Method and 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).
|
java.util.SortedSet<IntIntOrderedMap.MapEntry> |
entrySet() |
boolean |
equals(java.lang.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<java.lang.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.
|
java.lang.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.
|
java.util.Collection<java.lang.Integer> |
values() |
IntVLA |
valuesAsList() |
protected int[] key
protected int[] value
protected int mask
protected boolean containsNullKey
protected IntVLA order
reorder(int...)
and other methods.protected int n
protected int maxFill
f
.protected int size
public final float f
protected volatile IntIntOrderedMap.MapEntrySet entries
protected volatile IntIntOrderedMap.KeySet keys
protected volatile IntIntOrderedMap.ValueCollection values
protected int defRetValue
public static final int DEFAULT_INITIAL_SIZE
public static final float DEFAULT_LOAD_FACTOR
public static final float FAST_LOAD_FACTOR
public static final float VERY_FAST_LOAD_FACTOR
public IntIntOrderedMap(int expected, float f)
The actual table size will be the least power of two greater than expected
/f
.
expected
- the expected number of elements in the hash set.f
- the load factor.public IntIntOrderedMap(int expected)
expected
- the expected number of elements in the OrderedMap.public IntIntOrderedMap()
public IntIntOrderedMap(IntIntOrderedMap m, float f)
m
- a Map
to be copied into the new OrderedMap.f
- the load factor.public IntIntOrderedMap(IntIntOrderedMap m)
m
- a Map
to be copied into the new OrderedMap.public IntIntOrderedMap(int[] keyArray, int[] valueArray, float f)
keyArray
- the array of keys of the new OrderedMap.valueArray
- the array of corresponding values in the new OrderedMap.f
- the load factor.java.lang.IllegalArgumentException
- if k
and v
have different lengths.public IntIntOrderedMap(IntVLA keyColl, IntVLA valueColl)
keyColl
- the collection of keys of the new OrderedMap.valueColl
- the collection of corresponding values in the new OrderedMap.java.lang.IllegalArgumentException
- if k
and v
have different lengths.public IntIntOrderedMap(IntVLA keyColl, IntVLA valueColl, float f)
keyColl
- the collection of keys of the new OrderedMap.valueColl
- the collection of corresponding values in the new OrderedMap.f
- the load factor.java.lang.IllegalArgumentException
- if k
and v
have different lengths.public IntIntOrderedMap(int[] keyArray, int[] valueArray)
keyArray
- the array of keys of the new OrderedMap.valueArray
- the array of corresponding values in the new OrderedMap.java.lang.IllegalArgumentException
- if k
and v
have different lengths.public void defaultReturnValue(int rv)
public int defaultReturnValue()
public void putAll(int[] keyArray, int[] valueArray)
keyArray
- an array of int keys that should usually have the same length as valueArrayvalueArray
- an array of int values that should usually have the same length as keyArraypublic void putAll(IntIntOrderedMap m)
m
- an IntIntOrderedMap to add into thispublic int put(int k, int v)
public int putAt(int k, int v, int idx)
protected final void shiftKeys(int pos)
pos
- a starting position.public int remove(int k)
public int removeFirst()
java.util.NoSuchElementException
- is this map is empty.public int removeLast()
java.util.NoSuchElementException
- is this map is empty.public int get(int k)
public int getOrDefault(int k, int defaultValue)
protected int positionOf(int k)
public int indexOf(int k)
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.k
- a key or possible key that this should find the index ofpublic boolean swap(int left, int right)
left
- an item that should be present in this OrderedMapright
- an item that should be present in this OrderedMappublic boolean swapIndices(int left, int right)
public boolean containsKey(int k)
public boolean containsValue(int v)
public void clear()
public int size()
public boolean isEmpty()
public int getAndIncrement(int k, int increment)
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.k
- a key to look upincrement
- an int to add to the value associated with k
defaultReturnValue()
if k wasn't foundprotected int fixOrder(int i)
i
- the index of an entry.protected void fixOrder(int s, int d)
s
- the source position.d
- the destination position.public int firstKey()
public int lastKey()
public java.util.SortedSet<IntIntOrderedMap.MapEntry> entrySet()
public IntIntOrderedMap.KeySet keySet()
public OrderedSet<java.lang.Integer> keysAsOrderedSet()
public int[] keysAsArray()
public java.util.Collection<java.lang.Integer> values()
public IntVLA valuesAsList()
public boolean trim()
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.
trim(int)
public boolean trim(int n)
Let N be the smallest table size that can hold max(n,
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.
size()
)
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.
n
- the threshold for the trimming.trim()
protected void rehash(int newN)
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.
newN
- the new sizepublic IntIntOrderedMap clone()
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.
clone
in class java.lang.Object
public int hashCode()
hashCode
in class java.lang.Object
public long hash64()
public static int maxFill(int n, float f)
n
- the size of the backing array.f
- the load factor.public static int arraySize(int expected, float f)
Math.ceil( expected / f )
.expected
- the expected number of elements in a hash table.f
- the load factor.java.lang.IllegalArgumentException
- if the necessary size is larger than 230.public java.lang.String toString()
toString
in class java.lang.Object
public boolean equals(java.lang.Object o)
equals
in class java.lang.Object
public int getAt(int idx)
idx
- the index in the iteration order of the value to fetchpublic int keyAt(int idx)
idx
- the index in the iteration order of the key to fetchpublic IntIntOrderedMap.MapEntry entryAt(int idx)
idx
- the index in the iteration order of the entry to fetchpublic int removeAt(int idx)
idx
- the index in the iteration order of the key and value to removepublic int randomValue(IRNG rng)
rng
- used to generate a random index for a valuepublic int randomKey(IRNG rng)
rng
- used to generate a random index for a keypublic IntIntOrderedMap.MapEntry randomEntry(IRNG rng)
rng
- used to generate a random index for a entrypublic IntIntOrderedMap shuffle(IRNG rng)
rng
- used to generate a random orderingpublic IntIntOrderedMap reorder(int... ordering)
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.
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.
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 orderingpublic int alterCarefully(int original, int replacement)
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.original
- the key to find and swap outreplacement
- the key to replace original withpublic int alter(int original, int replacement)
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.original
- the key to find and swap outreplacement
- the key to replace original withpublic IntVLA getMany(int... keys)
public int alterAt(int index, int replacement)
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.index
- an index to replace the int key atreplacement
- another int key that will replace the original at the remembered indexpublic int alterAtCarefully(int index, int replacement)
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.index
- an index to replace the int key atreplacement
- another int key that will replace the original at the remembered indexpublic int putIfAbsent(int key, int value)
key
- key with which the specified value is to be associatedvalue
- value to be associated with the specified keyvalue
if there was no mapping for the key.public boolean remove(int key, int value)
key
- key with which the specified value is associatedvalue
- value expected to be associated with the specified keytrue
if the value was removedpublic boolean replace(int key, int oldValue, int newValue)
key
- key with which the specified value is associatedoldValue
- value expected to be associated with the specified keynewValue
- value to be associated with the specified keytrue
if the value was replacedpublic int replace(int key, int value)
key
- key with which the specified value is associatedvalue
- value to be associated with the specified keynull
if there was no mapping for the key.
(A null
return can also indicate that the map
previously associated null
with the key.)public IntIntOrderedMap putPairs(int k0, int v0, int... rest)
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.k0
- the first key to addv0
- the first value to addrest
- an array or vararg of keys and values in pairs; should contain alternating only int elementspublic static IntIntOrderedMap makeMap(int k0, int v0, int... rest)
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 elementspublic static IntIntOrderedMap makeMap()
public void reverse()
Copyright © Eben Howard 2012–2022. All rights reserved.