cz.cuni.jagrlib
Class IntMap<T>

java.lang.Object
  extended by java.util.AbstractCollection<T>
      extended by cz.cuni.jagrlib.IntMap<T>
All Implemented Interfaces:
java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<T>, java.util.Collection<T>
Direct Known Subclasses:
LRUCache

public class IntMap<T>
extends java.util.AbstractCollection<T>
implements java.lang.Cloneable, java.io.Serializable

This object maps integer keys to Object values. Each key can map to at most one Object instance, null values are allowed.

Efficient alternative to Map<K,V> container classes. Method signatures are as similar as possible (for convenience), the class now implements abstract Collection interface.

Since:
0.24
See Also:
IntMap.java, Serialized Form

Nested Class Summary
protected  class IntMap.CommonIterator
          Common iterator ancestor.
protected  class IntMap.TargetIterator
          Internal class handling target object iteration.
protected  class IntMap.TupleIterator
          Internal class handling tuple-iteration.
 
Field Summary
protected  float maxLoad
          Overload bound.
 int NULL_KEY
          Special value used in keyArray for empty (unused) slots.
protected  int REMOVED_KEY
          Special value used in keyArray for slots with removed keys.
 
Constructor Summary
IntMap()
          Dafault parameters (small initial capacity, default load factor = 0.6).
IntMap(int capacity)
          Explicit map capacity, default load factor (0.6).
IntMap(int capacity, float loadFactor)
          Explicit map capacity and load-factor.
IntMap(java.util.Map<? extends java.lang.Integer,? extends T> m)
          The same mappings as the specified Map.
 
Method Summary
 void clear()
          Removes all mappings from this map.
 java.lang.Object clone()
          Returns a shallow copy of this IntMap instance: the values themselves are not cloned.
 void compact()
          Rehashes the data structure to be more compact (and fast - if remove(int) operations were performed before).
 boolean containsKey(int key)
          "Contains" predicate for keys
 boolean containsValue(T value)
          "Contains" predicate for values.
protected  int find(int key)
          Finds slot with the given key value.
 T get(int key)
          Returns the value to which this map maps the specified key.
 boolean isEmpty()
          Is the map empty?
 java.util.Iterator<T> iterator()
          Iterates through all target values.
 java.util.Set<java.lang.Integer> keySet()
          Returns a set view of the keys contained in this map.
 T put(int key, T value)
          Associates the specified value with the specified key in this map If the map previously contained a mapping for this key, the old value is replaced by the specified value (a returned back).
 void putAll(java.util.Map<? extends java.lang.Integer,? extends T> m)
          Copies all of the mappings from the specified map to this map.
protected  void readObject(java.io.ObjectInputStream s)
          Reconstitute the IntMap instance from a stream (i.e. deserialize it).
protected  void rehash(int newSize)
          Rehashes the map arrays and prepares them for the specified capacity.
 T remove(int key)
          Removes the mapping for this key from this map if it is present Returns the value to which the map previously associated the key, or null if the map contained no mapping for this key.
 int size()
          Returns the number of key-value mappings in this map.
 java.util.Iterator<IntTuple<T>> tupleIterator()
          Iterates through all map tuples.
 java.util.Collection<T> values()
          Returns a collection view of the values contained in this map.
protected  void writeObject(java.io.ObjectOutputStream s)
          Save the state of the IntMap instance to a stream (i.e., serialize it).
 
Methods inherited from class java.util.AbstractCollection
add, addAll, contains, containsAll, remove, removeAll, retainAll, toArray, toArray, toString
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.Collection
equals, hashCode
 

Field Detail

NULL_KEY

public final int NULL_KEY
Special value used in keyArray for empty (unused) slots.

See Also:
Constant Field Values

REMOVED_KEY

protected final int REMOVED_KEY
Special value used in keyArray for slots with removed keys.

See Also:
Constant Field Values

maxLoad

protected float maxLoad
Overload bound.

Constructor Detail

IntMap

public IntMap()
Dafault parameters (small initial capacity, default load factor = 0.6).


IntMap

public IntMap(int capacity)
Explicit map capacity, default load factor (0.6).


IntMap

public IntMap(int capacity,
              float loadFactor)
Explicit map capacity and load-factor.


IntMap

public IntMap(java.util.Map<? extends java.lang.Integer,? extends T> m)
The same mappings as the specified Map. The IntMap is created with default load factor (0.6) and an initial capacity sufficient to hold the mappings in the specified Map.

Parameters:
m - the map whose mappings are to be placed in this map.
Method Detail

rehash

protected void rehash(int newSize)
Rehashes the map arrays and prepares them for the specified capacity.

Parameters:
newSize - New map capacity.

find

protected final int find(int key)
Finds slot with the given key value. Returns either used slot (with valid mapping) or unused slot (key/value pair is not present in the map).

Parameters:
key - Key to be looked for.
Returns:
Index into the array: where the given key resides or where it should be inserted. -1 for invalid key.

size

public final int size()
Returns the number of key-value mappings in this map. null values are counted in.

Specified by:
size in interface java.util.Collection<T>
Specified by:
size in class java.util.AbstractCollection<T>
Returns:
The number of key-value mappings in this map.

isEmpty

public final boolean isEmpty()
Is the map empty?

Specified by:
isEmpty in interface java.util.Collection<T>
Overrides:
isEmpty in class java.util.AbstractCollection<T>
Returns:
true if this map contains no key-value mappings.

containsKey

public final boolean containsKey(int key)
"Contains" predicate for keys

Parameters:
key - Key whose presence in this map is to be tested.
Returns:
true if this map contains a mapping (even null) for the specified key.

containsValue

public boolean containsValue(T value)
"Contains" predicate for values. More formally, returns true if and only if this map contains at least one mapping to a value v such that (value==null ? v==null : value.equals(v)).

Parameters:
value - Value whose presence in this map is to be tested.
Returns:
true if this map maps one or more keys to the specified value.

get

public T get(int key)
Returns the value to which this map maps the specified key. Cannot distinguish between empty mapping (i.e. no put( key, x ) was called) and mapping with null value (put( key, null ) was called). The containsKey predicate can be used to distinguish these two cases.

Parameters:
key - Key whose associated value is to be returned.
Returns:
The value to which this map maps the specified key, or null if the map contains no mapping for this key.
See Also:
containsKey(int)

put

public T put(int key,
             T value)
Associates the specified value with the specified key in this map If the map previously contained a mapping for this key, the old value is replaced by the specified value (a returned back).

Parameters:
key - Key with which the specified value is to be associated.
value - Value to be associated with the specified key.
Returns:
Previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key.

remove

public T remove(int key)
Removes the mapping for this key from this map if it is present

Returns the value to which the map previously associated the key, or null if the map contained no mapping for this key. (A null return can also indicate that the map previously associated null with the specified key). The map will not contain a mapping for the specified key once the call returns.

Parameters:
key - Key whose mapping is to be removed from the map.
Returns:
Previous value associated with specified key, or null if there was no mapping for key.

putAll

public void putAll(java.util.Map<? extends java.lang.Integer,? extends T> m)
Copies all of the mappings from the specified map to this map.

Parameters:
m - Mappings to be stored in this map.
Throws:
java.lang.ClassCastException - if the class of a key or value in the specified map prevents it from being stored in this map.

clear

public void clear()
Removes all mappings from this map.

Specified by:
clear in interface java.util.Collection<T>
Overrides:
clear in class java.util.AbstractCollection<T>

compact

public void compact()
Rehashes the data structure to be more compact (and fast - if remove(int) operations were performed before).


keySet

public java.util.Set<java.lang.Integer> keySet()
Returns a set view of the keys contained in this map. The set IS NOT backed by the map, it reflects exact IntMap state in the moment of method invocation.

Returns:
A set view of the keys contained in this map.

values

public java.util.Collection<T> values()
Returns a collection view of the values contained in this map. The collection IS NOT backed by the map, it reflects exact IntMap state in the moment of method invocation.

Returns:
A collection view of the values contained in this map.

tupleIterator

public final java.util.Iterator<IntTuple<T>> tupleIterator()
Iterates through all map tuples. Iterator handles only mappings existing in the moment this method is called. Consecutive adds/removes are not handled.

See Also:
IntTuple, iterator()

iterator

public final java.util.Iterator<T> iterator()
Iterates through all target values. Iterator handles only mappings existing in the moment this method is called. Consecutive adds/removes are not handled.

Specified by:
iterator in interface java.lang.Iterable<T>
Specified by:
iterator in interface java.util.Collection<T>
Specified by:
iterator in class java.util.AbstractCollection<T>
See Also:
tupleIterator()

clone

public java.lang.Object clone()
Returns a shallow copy of this IntMap instance: the values themselves are not cloned.

Overrides:
clone in class java.lang.Object
Returns:
A shallow copy of this map.

writeObject

protected void writeObject(java.io.ObjectOutputStream s)
                    throws java.io.IOException
Save the state of the IntMap instance to a stream (i.e., serialize it).

Throws:
java.io.IOException

readObject

protected void readObject(java.io.ObjectInputStream s)
                   throws java.io.IOException,
                          java.lang.ClassNotFoundException
Reconstitute the IntMap instance from a stream (i.e. deserialize it).

Throws:
java.io.IOException
java.lang.ClassNotFoundException