public class Arrangement<K>
extends java.lang.Object
implements java.util.SortedMap<K,java.lang.Integer>, java.lang.Iterable<K>, java.io.Serializable, java.lang.Cloneable
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).
Modifier and Type | Class and Description |
---|---|
class |
Arrangement.FastEntryIterator |
class |
Arrangement.KeyIterator
An iterator on keys.
|
class |
Arrangement.KeySet |
class |
Arrangement.ValueCollection |
class |
Arrangement.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 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
|
protected int |
size
Number of entries in the set (including the key zero, if present).
|
protected int[] |
value
The array of values.
|
protected java.util.Collection<java.lang.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 and Description |
---|
Arrangement()
Creates a new Arrangement with initial expected 16 entries and 0.5f as load factor.
|
Arrangement(Arrangement<? extends K> a) |
Arrangement(java.util.Collection<K> keyColl)
Creates a new Arrangement using the elements of an array.
|
Arrangement(java.util.Collection<K> keyColl,
float f)
Creates a new Arrangement using the given collection of keys.
|
Arrangement(CrossHash.IHasher hasher)
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,
CrossHash.IHasher hasher)
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(K[] keyArray)
Creates a new Arrangement with 0.5f as load factor using the elements of an array.
|
Arrangement(K[] keyArray,
CrossHash.IHasher hasher)
Creates a new Arrangement with 0.5f as load factor using the elements of two parallel arrays.
|
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(java.util.Map<? extends K,? extends java.lang.Integer> m)
Creates a new Arrangement with 0.5f as load factor copying a given one.
|
Arrangement(java.util.Map<? extends K,? extends java.lang.Integer> m,
CrossHash.IHasher hasher)
Creates a new Arrangement with 0.5f as load factor copying a given one.
|
Arrangement(java.util.Map<? extends K,? extends java.lang.Integer> m,
float f)
Creates a new Arrangement copying a given one.
|
Arrangement(java.util.Map<? extends K,? extends java.lang.Integer> m,
float f,
CrossHash.IHasher hasher)
Creates a new Arrangement copying a given one.
|
Modifier and Type | Method and 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 230 and larger than or equal to
Math.ceil( expected / f ) . |
void |
clear() |
Arrangement<K> |
clone()
Returns a deep copy of this map.
|
java.util.Comparator<? super K> |
comparator() |
boolean |
containsKey(java.lang.Object k) |
boolean |
containsValue(int v) |
boolean |
containsValue(java.lang.Object ov) |
java.util.Map.Entry<K,java.lang.Integer> |
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<java.util.Map.Entry<K,java.lang.Integer>> |
entrySet() |
boolean |
equals(java.lang.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) |
java.lang.Integer |
get(java.lang.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(java.util.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(java.lang.Object k) |
IntVLA |
getMany(java.lang.Iterable<? extends K> keys) |
long |
hash64() |
int |
hashCode()
Returns a hash code for this map.
|
java.util.SortedMap<K,java.lang.Integer> |
headMap(K to) |
boolean |
isEmpty() |
java.util.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(java.lang.Object k) |
int |
put(K k,
int v) |
java.lang.Integer |
put(K k,
java.lang.Integer v)
Deprecated.
|
void |
putAll(java.util.Collection<? extends K> keyColl) |
void |
putAll(K[] keyArray) |
void |
putAll(java.util.Map<? extends K,? extends java.lang.Integer> m) |
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.
|
java.util.Map.Entry<K,java.lang.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 java.lang.Integer |
rem(java.lang.Object k) |
java.lang.Integer |
remove(java.lang.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(java.lang.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(java.util.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(java.util.Comparator<? super K> comparator)
Sorts this whole Arrangement using the supplied Comparator.
|
void |
sort(java.util.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. |
java.util.SortedMap<K,java.lang.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.
|
java.util.SortedMap<K,java.lang.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.
|
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() |
int[] |
valuesAsArray() |
IntVLA |
valuesAsIntVLA() |
java.util.ArrayList<java.lang.Integer> |
valuesAsList() |
finalize, getClass, notify, notifyAll, wait, wait, wait
protected K[] key
protected int[] value
protected int mask
protected boolean containsNullKey
protected IntVLA order
protected int n
protected int maxFill
f
.protected int size
public final float f
protected volatile squidpony.squidmath.Arrangement.MapEntrySet entries
protected volatile Arrangement.KeySet keys
protected volatile java.util.Collection<java.lang.Integer> values
protected final 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
protected final CrossHash.IHasher hasher
public Arrangement(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 Arrangement(int expected)
expected
- the expected number of elements in the Arrangement.public Arrangement()
public Arrangement(java.util.Map<? extends K,? extends java.lang.Integer> m, float f)
m
- a Map
to be copied into the new Arrangement.f
- the load factor.public Arrangement(java.util.Map<? extends K,? extends java.lang.Integer> m)
m
- a Map
to be copied into the new Arrangement.public Arrangement(Arrangement<? extends K> a)
public Arrangement(K[] keyArray, float f)
keyArray
- the array of keys of the new Arrangement.f
- the load factor.java.lang.IllegalArgumentException
- if k
and v
have different lengths.public Arrangement(java.util.Collection<K> keyColl)
keyColl
- the collection of keys of the new Arrangement.java.lang.IllegalArgumentException
- if k
and v
have different lengths.public Arrangement(java.util.Collection<K> keyColl, float f)
keyColl
- the collection of keys of the new Arrangement.f
- the load factor.java.lang.IllegalArgumentException
- if k
and v
have different lengths.public Arrangement(K[] keyArray)
keyArray
- the array of keys of the new Arrangement.java.lang.IllegalArgumentException
- if k
and v
have different lengths.public Arrangement(int expected, float f, CrossHash.IHasher hasher)
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.hasher
- used to hash items; typically only needed when K is an array, where CrossHash has implementationspublic Arrangement(int expected, CrossHash.IHasher hasher)
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 implementationspublic Arrangement(CrossHash.IHasher hasher)
public Arrangement(java.util.Map<? extends K,? extends java.lang.Integer> m, float f, CrossHash.IHasher hasher)
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 implementationspublic Arrangement(java.util.Map<? extends K,? extends java.lang.Integer> m, CrossHash.IHasher hasher)
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 implementationspublic Arrangement(K[] keyArray, float f, CrossHash.IHasher hasher)
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 implementationsjava.lang.IllegalArgumentException
- if k
and v
have different lengths.public Arrangement(K[] keyArray, CrossHash.IHasher hasher)
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 implementationsjava.lang.IllegalArgumentException
- if k
and v
have different lengths.public void putAll(java.util.Map<? extends K,? extends java.lang.Integer> m)
putAll
in interface java.util.Map<K,java.lang.Integer>
public void putAll(K[] keyArray)
public void putAll(java.util.Collection<? extends K> keyColl)
@Deprecated public java.lang.Integer put(K k, java.lang.Integer v)
put
in interface java.util.Map<K,java.lang.Integer>
k
- any K type, including nullv
- any Integer, doesn't matter what it is and will be disregarded. Only here for compatibilitypublic int put(K k, int v)
public int add(K k)
public int addIfAbsent(K k)
public int addOrIndex(K k)
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.k
- a key to get the index of, adding it if not presentk
in this Arrangementprotected void fixValues(int start)
protected final void shiftKeys(int pos)
pos
- a starting position.protected final void shiftKeysValues(int pos)
pos
- a starting position.protected java.lang.Integer rem(java.lang.Object k)
public java.lang.Integer remove(java.lang.Object o)
remove
in interface java.util.Map<K,java.lang.Integer>
public int removeInt(java.lang.Object k)
public K removeFirst()
java.util.NoSuchElementException
- is this map is empty.public K removeLast()
java.util.NoSuchElementException
- is this map is empty.public int getAndMoveToFirst(K k)
k
- the key.public int getAndMoveToLast(K k)
k
- the key.public int putAndMoveToFirst(K k, int v)
k
- the key.v
- the value.public int putAndMoveToLast(K k, int v)
k
- the key.v
- the value.public java.lang.Integer get(java.lang.Object k)
get
in interface java.util.Map<K,java.lang.Integer>
public int getInt(java.lang.Object k)
public boolean containsKey(java.lang.Object k)
containsKey
in interface java.util.Map<K,java.lang.Integer>
public boolean containsValue(int v)
public boolean containsValue(java.lang.Object ov)
containsValue
in interface java.util.Map<K,java.lang.Integer>
public void clear()
clear
in interface java.util.Map<K,java.lang.Integer>
public int size()
size
in interface java.util.Map<K,java.lang.Integer>
public boolean isEmpty()
isEmpty
in interface java.util.Map<K,java.lang.Integer>
public java.util.Iterator<K> iterator()
T
.iterator
in interface java.lang.Iterable<K>
protected void 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 K firstKey()
firstKey
in interface java.util.SortedMap<K,java.lang.Integer>
public K lastKey()
lastKey
in interface java.util.SortedMap<K,java.lang.Integer>
public boolean retainAll(java.util.Collection<?> c)
c
- a collection.true
if this collection changed as a result of the
call.public java.util.Comparator<? super K> comparator()
comparator
in interface java.util.SortedMap<K,java.lang.Integer>
public java.util.SortedMap<K,java.lang.Integer> tailMap(K from)
tailMap
in interface java.util.SortedMap<K,java.lang.Integer>
public java.util.SortedMap<K,java.lang.Integer> headMap(K to)
headMap
in interface java.util.SortedMap<K,java.lang.Integer>
public java.util.SortedMap<K,java.lang.Integer> subMap(K from, K to)
subMap
in interface java.util.SortedMap<K,java.lang.Integer>
public java.util.SortedSet<java.util.Map.Entry<K,java.lang.Integer>> entrySet()
public squidpony.squidmath.Arrangement.MapEntrySet mapEntrySet()
public Arrangement.KeySet keySet()
public OrderedSet<K> keysAsOrderedSet()
public java.util.Collection<java.lang.Integer> values()
public java.util.ArrayList<java.lang.Integer> valuesAsList()
public IntVLA valuesAsIntVLA()
public int[] 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 Arrangement<K> clone()
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.
clone
in class java.lang.Object
public int hashCode()
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.hashCode
in interface java.util.Map<K,java.lang.Integer>
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 long maxFill(long 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 interface java.util.Map<K,java.lang.Integer>
equals
in class java.lang.Object
public int getAt(int idx)
idx
- the index in the iteration order of the value to fetchpublic K keyAt(int idx)
idx
- the index in the iteration order of the key to fetchpublic java.util.Map.Entry<K,java.lang.Integer> entryAt(int idx)
idx
- the index in the iteration order of the entry to fetchpublic K removeAt(int idx)
idx
- the index in the iteration order of the key and value to removepublic int addAt(int idx, K k)
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).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 idxpublic int randomValue(IRNG rng)
rng
- used to generate a random index for a valuepublic K randomKey(IRNG rng)
rng
- used to generate a random index for a keypublic java.util.Map.Entry<K,java.lang.Integer> randomEntry(IRNG rng)
rng
- used to generate a random index for a entrypublic Arrangement<K> shuffle(IRNG rng)
rng
- used to generate a random orderingpublic Arrangement<K> 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 alter(K original, K replacement)
original
- the key to find and swap outreplacement
- the key to replace original withpublic int[] getArray(K[] keys)
public int[] getArray(java.util.Collection<? extends K> keys)
public OrderedSet<K> keysAt(int... positions)
public OrderedSet<K> keysAt(IntVLA positions)
public Arrangement<K> take(int amount)
amount
- the number of items to copy from this Arrangement; will copy all items if greater than sizeprotected int positionOf(java.lang.Object k)
public boolean swap(K left, K right)
left
- an item that should be present in this OrderedSetright
- an item that should be present in this OrderedSetpublic boolean swapIndices(int left, int right)
public int alterAt(int index, K replacement)
index
- an index to replace the K key atreplacement
- another K key that will replace the original at the remembered indexpublic void sort(java.util.Comparator<? super K> comparator)
comparator
- a Comparator that can be used on the same type this uses for its keys (may need wildcards)public void sort(java.util.Comparator<? super K> comparator, int start, int end)
start
up to (but not including)
the index end
, using the supplied Comparator.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()
Copyright © Eben Howard 2012–2022. All rights reserved.