public class IntDoubleOrderedMap
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.
keyAt(int)
and getAt(int)
operations,
among many others, and a refactor of the class has made it much closer to IntIntOrderedMap
and to some extent
OrderedMap
, making order control a priority. Some method names have changed; if you used code like
putAndMoveToFirst(k, v)
, that should be replaced with putAt(k, v, 0)
. The API for the data structures
returned by keySet()
and values()
has changed in some places; you should use
keysAsArray()
and valuesAsArray()
instead of creating a key set or values collection and calling
toArray() on that, as you had to before. The usage of this class should now be similar to the rest of the library.
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, double, 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 |
IntDoubleOrderedMap.FastEntryIterator |
class |
IntDoubleOrderedMap.KeyIterator
An iterator on keys.
|
class |
IntDoubleOrderedMap.KeySet |
class |
IntDoubleOrderedMap.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 |
IntDoubleOrderedMap.MapEntrySet |
class |
IntDoubleOrderedMap.ValueCollection |
class |
IntDoubleOrderedMap.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 double |
defRetValue
Default return value.
|
protected IntDoubleOrderedMap.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 IntDoubleOrderedMap.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 double[] |
value
The array of values.
|
protected IntDoubleOrderedMap.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 |
---|
IntDoubleOrderedMap()
Creates a new OrderedMap with initial expected 16 entries and 0.75f as load factor.
|
IntDoubleOrderedMap(int expected)
Creates a new OrderedMap with 0.75f as load factor.
|
IntDoubleOrderedMap(int[] keyArray,
double[] valueArray)
Creates a new OrderedMap with 0.75f as load factor using the elements of two parallel arrays.
|
IntDoubleOrderedMap(int[] keyArray,
double[] valueArray,
float f)
Creates a new OrderedMap using the elements of two parallel arrays.
|
IntDoubleOrderedMap(IntDoubleOrderedMap m)
Creates a new OrderedMap with 0.75f as load factor copying a given one.
|
IntDoubleOrderedMap(IntDoubleOrderedMap m,
float f)
Creates a new OrderedMap copying a given one.
|
IntDoubleOrderedMap(int expected,
float f)
Creates a new OrderedMap.
|
Modifier and Type | Method and Description |
---|---|
double |
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).
|
double |
alterAt(int index,
int replacement)
Changes the int at the given index to replacement while keeping replacement at the same point in the ordering.
|
double |
alterAtCarefully(int index,
int replacement)
Changes the int at the given index to replacement while keeping replacement at the same point in the ordering.
|
double |
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() |
IntDoubleOrderedMap |
clone()
Returns a deep copy of this map.
|
boolean |
containsKey(int k) |
boolean |
containsValue(double v) |
double |
defaultReturnValue() |
void |
defaultReturnValue(double rv) |
IntDoubleOrderedMap.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<IntDoubleOrderedMap.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.
|
double |
get(int k) |
double |
getAndIncrement(int k,
double 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. |
double |
getAt(int idx)
Gets the value at the given index in the iteration order in constant time (random-access).
|
double[] |
getMany(int... keys) |
double |
getOrDefault(int k,
double 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() |
IntDoubleOrderedMap.KeySet |
keySet() |
int |
lastKey()
Returns the last key of this map in iteration 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) |
double |
put(int k,
double v) |
void |
putAll(int[] keyArray,
double[] valueArray)
Puts the first key in keyArray with the first value in valueArray, then the second in each and so on.
|
void |
putAll(IntDoubleOrderedMap m)
Puts all key-value pairs in the Map m into this OrderedMap.
|
double |
putAt(int k,
double v,
int idx) |
double |
putIfAbsent(int key,
double 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.
|
IntDoubleOrderedMap.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.
|
double |
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.
|
double |
remove(int k) |
boolean |
remove(int key,
double value)
Removes the entry for the specified key only if it is currently
mapped to the specified value.
|
double |
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).
|
double |
removeFirst()
Removes the mapping associated with the first key in iteration order.
|
double |
removeLast()
Removes the mapping associated with the last key in iteration order.
|
IntDoubleOrderedMap |
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. |
double |
replace(int key,
double value)
Replaces the entry for the specified key only if it is
currently mapped to some value.
|
boolean |
replace(int key,
double oldValue,
double 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.
|
IntDoubleOrderedMap |
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.Double> |
values() |
double[] |
valuesAsArray() |
protected int[] key
protected double[] 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 IntDoubleOrderedMap.MapEntrySet entries
protected volatile IntDoubleOrderedMap.KeySet keys
protected volatile IntDoubleOrderedMap.ValueCollection values
protected double 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 IntDoubleOrderedMap(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 IntDoubleOrderedMap(int expected)
expected
- the expected number of elements in the OrderedMap.public IntDoubleOrderedMap()
public IntDoubleOrderedMap(IntDoubleOrderedMap m, float f)
m
- a Map
to be copied into the new OrderedMap.f
- the load factor.public IntDoubleOrderedMap(IntDoubleOrderedMap m)
m
- a Map
to be copied into the new OrderedMap.public IntDoubleOrderedMap(int[] keyArray, double[] 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 IntDoubleOrderedMap(int[] keyArray, double[] 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(double rv)
public double defaultReturnValue()
public void putAll(int[] keyArray, double[] 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(IntDoubleOrderedMap m)
m
- an IntIntOrderedMap to add into thispublic double put(int k, double v)
public double putAt(int k, double v, int idx)
protected final void shiftKeys(int pos)
pos
- a starting position.public double remove(int k)
public double removeFirst()
java.util.NoSuchElementException
- is this map is empty.public double removeLast()
java.util.NoSuchElementException
- is this map is empty.public double get(int k)
public double getOrDefault(int k, double 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(double v)
public void clear()
public int size()
public boolean isEmpty()
public double getAndIncrement(int k, double 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
- a double 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<IntDoubleOrderedMap.MapEntry> entrySet()
public IntDoubleOrderedMap.KeySet keySet()
public OrderedSet<java.lang.Integer> keysAsOrderedSet()
public int[] keysAsArray()
public java.util.Collection<java.lang.Double> values()
public double[] valuesAsArray()
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 IntDoubleOrderedMap 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 double 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 IntDoubleOrderedMap.MapEntry entryAt(int idx)
idx
- the index in the iteration order of the entry to fetchpublic double removeAt(int idx)
idx
- the index in the iteration order of the key and value to removepublic double 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 IntDoubleOrderedMap.MapEntry randomEntry(IRNG rng)
rng
- used to generate a random index for a entrypublic IntDoubleOrderedMap shuffle(IRNG rng)
rng
- used to generate a random orderingpublic IntDoubleOrderedMap 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 double 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 double 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 double[] getMany(int... keys)
public double 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 double 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 double putIfAbsent(int key, double 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, double 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, double oldValue, double 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 double replace(int key, double 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 void reverse()
Copyright © Eben Howard 2012–2022. All rights reserved.