kodkod.util.collections

Class FixedMap<K,V>

java.lang.Object

java.util.AbstractMap<K,V>

kodkod.util.collections.FixedMap<K,V>

All Implemented Interfaces:

Map<K,V>, Indexer<K>

public final class FixedMap<K,V>
extends AbstractMap<K,V>
implements Indexer<K>

A map with a fixed set of keys that acts as an indexer, assigning a unique integer in the range [0..#keys) to each key. This class implements the Map interface with an array, using reference-equality in place of object-equality when comparing keys (and values). In other words, in a FixedMap, two keys k1 and k2 are considered equal if and only if (k1==k2). (In normal Map implementations (like HashMap) two keys k1 and k2 are considered equal if and only if (k1==null ? k2==null : k1.equals(k2)).)

This class is not a general-purpose Map implementation! While this class implements the Map interface, it intentionally violates Map's general contract, which mandates the use of the equals method when comparing objects.

This class provides put(Object, Object) operation for the keys within its fixed key set and permits null values and the null key. The remove(Object) operation is not supported. This class guarantees that the order of the map will remain constant over time.

This class provides log-time performance for the basic operations (get and put), assuming the system identity hash function (System.identityHashCode(Object)) disperses elements properly among the buckets.

This implementation is not synchronized, and its iterators are not fail-fast.

Author:

Emina Torlak

Specfields:

keys: set K

map: keys -> one V

indices: keys lone->one [0..#keys)

Nested Class Summary

Nested classes/interfaces inherited from class java.util.AbstractMap

AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>

Constructor Summary

Constructors

Constructor and Description
FixedMap(K[] keys) Constructs a new fixed map, backed by the given array of keys.
FixedMap(Map<K,V> map) Constructs a new fixed map from the given map.
FixedMap(Set<K> keys) Constructs a new fixed map for the given set of keys.

Method Summary

Modifier and Type	Method and Description
boolean	containsKey(Object key) Tests whether the specified object reference is a key in this fixed map.
boolean	containsValue(Object value) Tests whether the specified object reference is a value in this fixed map.
Set<Map.Entry<K,V>>	entrySet() Returns a set view of the mappings contained in this map.
boolean	equals(Object o) Compares the specified object with this map for equality.
V	get(int index) Returns the value to which the key at the specified index is mapped in this fixed map.
V	get(Object key) Returns the value to which the specified key is mapped in this fixed map, or null if the map contains no mapping for this key.
int	hashCode() Returns the hash code value for this map.
int	indexOf(K key) Returns the index of the given key, if it is in this.keys.
boolean	isEmpty()
K	keyAt(int index) Returns the key at the given index.
V	put(K key, V value) Associates the specified value with the specified key in this fixed map.
V	remove(Object key) Throws an UnsupportedOperationException exception.
int	size() Returns the number of keys in this.indexer.

Methods inherited from class java.util.AbstractMap

clear, keySet, putAll, toString, values

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map

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

Constructor Detail

FixedMap

public FixedMap(K[] keys)

Constructs a new fixed map, backed by the given array of keys. The provided array must not contain duplicates, its entries must be sorted in the increasing order of identity hashcodes, and it must not be modified while in use by this map. The map will not behave correctly if these requirements are violated.

Requires:

no disj i, j: [0..keys.length) | keys[i] == keys[j]

all i, j: [0..keys.length) | i < j => System.identityHashCode(keys[i]) <= System.identityHashCode(keys[j])

Ensures:

this.keys' = keys && no this.map'

FixedMap

public FixedMap(Map<K,V> map)

Constructs a new fixed map from the given map.

Ensures:

this.keys' = keys && this.map = map.map

FixedMap

public FixedMap(Set<K> keys)

Constructs a new fixed map for the given set of keys.

Ensures:

this.keys' = keys && no this.map'

Method Detail

containsKey

public final boolean containsKey(Object key)

Tests whether the specified object reference is a key in this fixed map.

Specified by:

containsKey in interface Map<K,V>

Overrides:

containsKey in class AbstractMap<K,V>

Returns:

key in this.keys

containsValue

public final boolean containsValue(Object value)

Tests whether the specified object reference is a value in this fixed map.

Specified by:

containsValue in interface Map<K,V>

Overrides:

containsValue in class AbstractMap<K,V>

Returns:

value in this.map[this.keys]

entrySet

public final Set<Map.Entry<K,V>> entrySet()

Returns a set view of the mappings contained in this map. Each element in the returned set is a reference-equality-based Map.Entry. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress, the results of the iteration are undefined. The set does support neither removal nor addition.

Like the backing map, the Map.Entry objects in the set returned by this method define key and value equality as reference-equality rather than object-equality. This affects the behavior of the equals and hashCode methods of these Map.Entry objects. A reference-equality based Map.Entry e is equal to an object o if and only if o is a Map.Entry and e.getKey()==o.getKey() && e.getValue()==o.getValue(). To accommodate these equals semantics, the hashCode method returns System.identityHashCode(e.getKey()) ^ System.identityHashCode(e.getValue()).

Owing to the reference-equality-based semantics of the Map.Entry instances in the set returned by this method, it is possible that the symmetry and transitivity requirements of the Object.equals(Object) contract may be violated if any of the entries in the set is compared to a normal map entry, or if the set returned by this method is compared to a set of normal map entries (such as would be returned by a call to this method on a normal map). However, the Object.equals contract is guaranteed to hold among identity-based map entries, and among sets of such entries.

Specified by:

entrySet in interface Map<K,V>

Specified by:

entrySet in class AbstractMap<K,V>

Returns:

a set view of the identity-mappings contained in this map.

equals

public boolean equals(Object o)

Compares the specified object with this map for equality. Returns true if the given object is also a map and the two maps represent identical object-reference mappings. More formally, this map is equal to another map m if and only if map this.entrySet().equals(m.entrySet()).

Owing to the reference-equality-based semantics of this map it is possible that the symmetry and transitivity requirements of the Object.equals contract may be violated if this map is compared to a normal map. However, the Object.equals contract is guaranteed to hold among FixedMap instances.

Specified by:

equals in interface Map<K,V>

Overrides:

equals in class AbstractMap<K,V>

Parameters:

o - object to be compared for equality with this map.

Returns:

true if the specified object is equal to this map.

See Also:

Object.equals(Object)

get

public final V get(int index)

Returns the value to which the key at the specified index is mapped in this fixed map.

Requires:

index in this.indices[this.keys]

Returns:

this.map[this.indices.index]

Throws:

IndexOutOfBoundsException - index !in this.indices[this.keys]

get

public final V get(Object key)

Returns the value to which the specified key is mapped in this fixed map, or null if the map contains no mapping for this key. A return value of null does not necessarily indicate that the map contains no mapping for the key; it is also possible that the map explicitly maps the key to null. The containsKey method may be used to distinguish these two cases.

Specified by:

get in interface Map<K,V>

Overrides:

get in class AbstractMap<K,V>

Returns:

this.map[key]

hashCode

public int hashCode()

Returns the hash code value for this map. The hash code of a map is defined to be the sum of the hashcode of each entry in the map's entrySet view. This ensures that t1.equals(t2) implies that t1.hashCode()==t2.hashCode() for any two FixedMap instances t1 and t2, as required by the general contract of Object.hashCode().

Owing to the reference-equality-based semantics of the Map.Entry instances in the set returned by this map's entrySet method, it is possible that the contractual requirement of Object.hashCode mentioned in the previous paragraph will be violated if one of the two objects being compared is an FixedMap instance and the other is a normal map.

Specified by:

hashCode in interface Map<K,V>

Overrides:

hashCode in class AbstractMap<K,V>

Returns:

the hash code value for this map.

See Also:

Object.hashCode(), Object.equals(Object), equals(Object)

indexOf

public final int indexOf(K key)

Returns the index of the given key, if it is in this.keys. Otherwise returns a negative number.

Specified by:

indexOf in interface Indexer<K>

Returns:

key in this.keys => this.indices[key], {i: int | i < 0 }

isEmpty

public final boolean isEmpty()

Specified by:

isEmpty in interface Map<K,V>

Overrides:

isEmpty in class AbstractMap<K,V>

See Also:

Map.isEmpty()

keyAt

public final K keyAt(int index)

Returns the key at the given index.

Specified by:

keyAt in interface Indexer<K>

Returns:

this.indices.index

Throws:

IndexOutOfBoundsException - index !in this.indices[this.keys]

put

public final V put(K key,
                   V value)

Associates the specified value with the specified key in this fixed map. If the map previously contained a mapping for this key, the old value is replaced. This method assumes that the given key is in the fixed keyset of this map.

Specified by:

put in interface Map<K,V>

Overrides:

put in class AbstractMap<K,V>

Requires:

key in this.keys

Ensures:

this.map' = this.map ++ key->value

Returns:

this.map[key]

Throws:

IllegalArgumentException - key !in this.keys

remove

public final V remove(Object key)

Throws an UnsupportedOperationException exception.

Specified by:

remove in interface Map<K,V>

Overrides:

remove in class AbstractMap<K,V>

See Also:

Map.remove(java.lang.Object)

size

public final int size()

Description copied from interface: Indexer

Returns the number of keys in this.indexer.

Specified by:

size in interface Map<K,V>

Specified by:

size in interface Indexer<K>

Overrides:

size in class AbstractMap<K,V>

Returns:

#this.keys

See Also:

Map.size()