fr.univNantes.intcolls
Class DualArrayIntMap<V>

java.lang.Object
  extended by java.util.AbstractMap<java.lang.Integer,V>
      extended by fr.univNantes.intcolls.DualArrayIntMap<V>
All Implemented Interfaces:
java.util.Map<java.lang.Integer,V>, java.util.NavigableMap<java.lang.Integer,V>, java.util.SortedMap<java.lang.Integer,V>

public class DualArrayIntMap<V>
extends java.util.AbstractMap<java.lang.Integer,V>
implements java.util.NavigableMap<java.lang.Integer,V>

This class is a specialized map with integer keys. Keys are always integers (int).

It can contain null values but not null keys.

Beware when multithreading environment : it is not synchronized. This implementation never throws ConcurrentModificationException.

This implementation uses two arrays, one for integer keys, another for object values.

The keys are found by dichotomy, so that the cost of retrieving a value with a key is log2(size()). Last key access is cached.

You have two additional methods :

Author:
Pierre-Olivier Terrisse

Nested Class Summary
private static class DualArrayIntMap.DAIMValueCollection<V>
          Describes a Set view overs values
 
Nested classes/interfaces inherited from class java.util.AbstractMap
java.util.AbstractMap.SimpleEntry<K,V>, java.util.AbstractMap.SimpleImmutableEntry<K,V>
 
Nested classes/interfaces inherited from interface java.util.Map
java.util.Map.Entry<K,V>
 
Field Summary
private static int DEFAULT_CAPACITY
          Default capacity
private  boolean hasLastKey
           
private  int increment
          Increment of the capacity of the backing arrays
private  int[] keys
          Table of keys
private  int lastIndex
           
private  int lastKey
           
private  int size
          Actuel size of the map
private  java.lang.Object[] values
          Table of values
 
Constructor Summary
DualArrayIntMap()
          Parameterless constructor
DualArrayIntMap(int capacity)
          Constructor
DualArrayIntMap(java.util.Map<java.lang.Integer,? extends V> coll)
          Constructor with another collection of Integers
 
Method Summary
 java.util.Map.Entry<java.lang.Integer,V> ceilingEntry(java.lang.Integer key)
          Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.
 java.lang.Integer ceilingKey(java.lang.Integer key)
          Returns the least key greater than or equal to the given key, or null if there is no such key.
 java.util.Comparator<? super java.lang.Integer> comparator()
           
 boolean containsKey(java.lang.Object key)
          Returns true if this map contains a specified key
 boolean containsValue(java.lang.Object value)
          Returns true if the map contains a specified value
 int countHigher(int key)
          Counts higher keys
 int countLower(int key)
          Counts lower keys
 java.util.NavigableSet<java.lang.Integer> descendingKeySet()
           
 java.util.NavigableMap<java.lang.Integer,V> descendingMap()
          Return a descending view of this map
 java.lang.String dump()
          Dumps arrays for debugging purpose
 java.util.Set<java.util.Map.Entry<java.lang.Integer,V>> entrySet()
          Returns a Set view of the mappings contained in this map.
 boolean equals(java.lang.Object obj)
          Returns true if this map is equal to another
 java.util.Map.Entry<java.lang.Integer,V> firstEntry()
          Returns the first (lower) entry (key - value pair) currenty in this map
 java.lang.Integer firstKey()
          Returns the first (lowest) key currently in this map.
 java.util.Map.Entry<java.lang.Integer,V> floorEntry(java.lang.Integer key)
          Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.
 java.lang.Integer floorKey(java.lang.Integer key)
          Returns the greatest key less than or equal to the given key, or null if there is no such key.
 V get(java.lang.Object key)
          Returns the value associated to a key
private  int getIndex(int key)
          Returns index given a key, using cache
 V getInt(int key)
          Returns the value associated to a key
 int hashCode()
          Returns a hash code value for the object
 boolean hasHigherKey(int key)
          Returns true if the map has a higher key that a given one
 java.util.SortedMap<java.lang.Integer,V> headMap(java.lang.Integer toKey)
           
 java.util.NavigableMap<java.lang.Integer,V> headMap(java.lang.Integer toKey, boolean inclusive)
           
 java.util.Map.Entry<java.lang.Integer,V> higherEntry(java.lang.Integer key)
          Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.
 int higherIntKey(java.lang.Integer key)
          Returns the least key strictly greater than the given key, or null if there is no such key.
 java.lang.Integer higherKey(java.lang.Integer key)
          Returns the least key strictly greater than the given key, or null if there is no such key.
 boolean isEmpty()
          Returns true if this map contains no key-value mappings.
 java.util.Set<java.lang.Integer> keySet()
          Returns a Set view of the keys contained in this map.
 java.util.Map.Entry<java.lang.Integer,V> lastEntry()
          Returns the last (higher) entry (key - value pair) currenty in this map
 java.lang.Integer lastKey()
          Returns the last (highest) key currently in this map.
 java.util.Map.Entry<java.lang.Integer,V> lowerEntry(java.lang.Integer key)
          Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.
 int lowerIntKey(int key)
          Returns the greatest key strictly less than the given key, or null if there is no such key.
 java.lang.Integer lowerKey(java.lang.Integer key)
          Returns the greatest key strictly less than the given key, or null if there is no such key.
 java.util.NavigableSet<java.lang.Integer> navigableKeySet()
           
 java.util.Map.Entry<java.lang.Integer,V> pollFirstEntry()
          Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty.
 java.util.Map.Entry<java.lang.Integer,V> pollLastEntry()
          Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
 V put(java.lang.Integer k, V v)
          Puts a value into the map
 V putInt(int k, V v)
          Puts a value into the map
 V remove(java.lang.Object key)
          Removes the mapping for a key from this map if it is present
 V removeInt(int key)
          Removes the mapping for a key from this map if it is present
private  void resetIndexCache()
           
 int size()
          Returns the size of the map
 java.util.NavigableMap<java.lang.Integer,V> subMap(java.lang.Integer fromKey, boolean fromInclusive, java.lang.Integer toKey, boolean toInclusive)
           
 java.util.SortedMap<java.lang.Integer,V> subMap(java.lang.Integer fromKey, java.lang.Integer toKey)
           
 java.util.SortedMap<java.lang.Integer,V> tailMap(java.lang.Integer fromKey)
           
 java.util.NavigableMap<java.lang.Integer,V> tailMap(java.lang.Integer fromKey, boolean inclusive)
           
 java.util.Collection<V> values()
          Returns a Collection view of the values contained in this map.
protected  void verifyCapacity(int incSize)
          Increase the size of the backing arrays if necessary.
 
Methods inherited from class java.util.AbstractMap
clear, clone, putAll, toString
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.Map
clear, putAll
 

Field Detail

DEFAULT_CAPACITY

private static final int DEFAULT_CAPACITY
Default capacity

See Also:
Constant Field Values

keys

private int[] keys
Table of keys


values

private java.lang.Object[] values
Table of values


increment

private int increment
Increment of the capacity of the backing arrays


size

private int size
Actuel size of the map


lastKey

private int lastKey

hasLastKey

private boolean hasLastKey

lastIndex

private int lastIndex
Constructor Detail

DualArrayIntMap

public DualArrayIntMap(int capacity)
Constructor

Parameters:
capacity - initial capacity of the map

DualArrayIntMap

public DualArrayIntMap(java.util.Map<java.lang.Integer,? extends V> coll)
Constructor with another collection of Integers

Parameters:
coll - another collection

DualArrayIntMap

public DualArrayIntMap()
Parameterless constructor

Method Detail

equals

public boolean equals(java.lang.Object obj)
Returns true if this map is equal to another

Specified by:
equals in interface java.util.Map<java.lang.Integer,V>
Overrides:
equals in class java.util.AbstractMap<java.lang.Integer,V>
Parameters:
obj - the reference object with which to compare.
Returns:
true if this object is the same as the obj argument; false otherwise

hashCode

public int hashCode()
Returns a hash code value for the object

Specified by:
hashCode in interface java.util.Map<java.lang.Integer,V>
Overrides:
hashCode in class java.util.AbstractMap<java.lang.Integer,V>
Returns:
a hash code value for this object.

getIndex

private int getIndex(int key)
Returns index given a key, using cache

Parameters:
key - key to find
Returns:
index index, can be negative if key is not in the map

resetIndexCache

private void resetIndexCache()

getInt

public V getInt(int key)
Returns the value associated to a key

Parameters:
key - an integer key
Returns:
the corresponding value in this map or null if this map does not contains the key

get

public V get(java.lang.Object key)
Returns the value associated to a key

Specified by:
get in interface java.util.Map<java.lang.Integer,V>
Overrides:
get in class java.util.AbstractMap<java.lang.Integer,V>
Parameters:
key - a key
Returns:
the corresponding value in this map or null if this map does not contains the key

putInt

public V putInt(int k,
                V v)
Puts a value into the map

Parameters:
k - key to put
v - associated value
Returns:
the previous value associated with key, or null if there was no mapping for key

put

public V put(java.lang.Integer k,
             V v)
Puts a value into the map

Specified by:
put in interface java.util.Map<java.lang.Integer,V>
Overrides:
put in class java.util.AbstractMap<java.lang.Integer,V>
Parameters:
k - key to put
v - associated value
Returns:
the previous value associated with key, or null if there was no mapping for key

removeInt

public V removeInt(int key)
Removes the mapping for a key from this map if it is present

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

remove

public V remove(java.lang.Object key)
Removes the mapping for a key from this map if it is present

Specified by:
remove in interface java.util.Map<java.lang.Integer,V>
Overrides:
remove in class java.util.AbstractMap<java.lang.Integer,V>
Parameters:
key - key whose mapping is to be removed from the map
Returns:
the previous value associated with key, or null if there was no mapping for key.

size

public int size()
Returns the size of the map

Specified by:
size in interface java.util.Map<java.lang.Integer,V>
Overrides:
size in class java.util.AbstractMap<java.lang.Integer,V>
Returns:
the number of elements contained in this map

isEmpty

public boolean isEmpty()
Returns true if this map contains no key-value mappings.

Specified by:
isEmpty in interface java.util.Map<java.lang.Integer,V>
Overrides:
isEmpty in class java.util.AbstractMap<java.lang.Integer,V>
Returns:
trus if this map is empty

containsKey

public boolean containsKey(java.lang.Object key)
Returns true if this map contains a specified key

Specified by:
containsKey in interface java.util.Map<java.lang.Integer,V>
Overrides:
containsKey in class java.util.AbstractMap<java.lang.Integer,V>
Parameters:
key - key
Returns:
true if the key is in the map

containsValue

public boolean containsValue(java.lang.Object value)
Returns true if the map contains a specified value

Specified by:
containsValue in interface java.util.Map<java.lang.Integer,V>
Overrides:
containsValue in class java.util.AbstractMap<java.lang.Integer,V>
Parameters:
value - whose presence in this map is to be tested
Returns:
true if the map contains the value

verifyCapacity

protected void verifyCapacity(int incSize)
Increase the size of the backing arrays if necessary.

Parameters:
incSize - incremental size

entrySet

public java.util.Set<java.util.Map.Entry<java.lang.Integer,V>> entrySet()
Returns a Set view of the mappings contained in this map.

Specified by:
entrySet in interface java.util.Map<java.lang.Integer,V>
Specified by:
entrySet in interface java.util.SortedMap<java.lang.Integer,V>
Specified by:
entrySet in class java.util.AbstractMap<java.lang.Integer,V>
Returns:
a set view of the mappings contained in this map

keySet

public java.util.Set<java.lang.Integer> keySet()
Returns a Set view of the keys contained in this map.

Specified by:
keySet in interface java.util.Map<java.lang.Integer,V>
Specified by:
keySet in interface java.util.SortedMap<java.lang.Integer,V>
Overrides:
keySet in class java.util.AbstractMap<java.lang.Integer,V>
Returns:
a set view of the keys contained in this map

values

public java.util.Collection<V> values()
Returns a Collection view of the values contained in this map.

Specified by:
values in interface java.util.Map<java.lang.Integer,V>
Specified by:
values in interface java.util.SortedMap<java.lang.Integer,V>
Overrides:
values in class java.util.AbstractMap<java.lang.Integer,V>
Returns:
a collection view of the values contained in this map

lowerEntry

public java.util.Map.Entry<java.lang.Integer,V> lowerEntry(java.lang.Integer key)
Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.

Specified by:
lowerEntry in interface java.util.NavigableMap<java.lang.Integer,V>
Parameters:
key - the key
Returns:
an entry with the greatest key less than key, or null if there is no such key

lowerKey

public java.lang.Integer lowerKey(java.lang.Integer key)
Returns the greatest key strictly less than the given key, or null if there is no such key.

Specified by:
lowerKey in interface java.util.NavigableMap<java.lang.Integer,V>
Parameters:
key -
Returns:
the greatest key less than key, or null if there is no such key

lowerIntKey

public int lowerIntKey(int key)
Returns the greatest key strictly less than the given key, or null if there is no such key.

Parameters:
key -
Returns:
the greatest key less than key, or null if there is no such key

floorEntry

public java.util.Map.Entry<java.lang.Integer,V> floorEntry(java.lang.Integer key)
Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.

Specified by:
floorEntry in interface java.util.NavigableMap<java.lang.Integer,V>
Parameters:
key - the key
Returns:
an entry with the greatest key less than or equal to key, or null if there is no such key

floorKey

public java.lang.Integer floorKey(java.lang.Integer key)
Returns the greatest key less than or equal to the given key, or null if there is no such key.

Specified by:
floorKey in interface java.util.NavigableMap<java.lang.Integer,V>
Parameters:
key - the key
Returns:
the greatest key less than or equal to key, or null if there is no such key

ceilingEntry

public java.util.Map.Entry<java.lang.Integer,V> ceilingEntry(java.lang.Integer key)
Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.

Specified by:
ceilingEntry in interface java.util.NavigableMap<java.lang.Integer,V>
Parameters:
key - the key
Returns:
an entry with the least key greater than or equal to key, or null if there is no such key

ceilingKey

public java.lang.Integer ceilingKey(java.lang.Integer key)
Returns the least key greater than or equal to the given key, or null if there is no such key.

Specified by:
ceilingKey in interface java.util.NavigableMap<java.lang.Integer,V>
Parameters:
key - the key
Returns:
the least key greater than or equal to key, or null if there is no such key

higherEntry

public java.util.Map.Entry<java.lang.Integer,V> higherEntry(java.lang.Integer key)
Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.

Specified by:
higherEntry in interface java.util.NavigableMap<java.lang.Integer,V>
Parameters:
key - the key
Returns:
an entry with the least key greater than key, or null if there is no such key

hasHigherKey

public boolean hasHigherKey(int key)
Returns true if the map has a higher key that a given one

Parameters:
key - a key
Returns:
true if the map has a key strictly greater than key

higherKey

public java.lang.Integer higherKey(java.lang.Integer key)
Returns the least key strictly greater than the given key, or null if there is no such key.

Specified by:
higherKey in interface java.util.NavigableMap<java.lang.Integer,V>
Parameters:
key - the key
Returns:
the least key greater than key, or null if there is no such key

higherIntKey

public int higherIntKey(java.lang.Integer key)
Returns the least key strictly greater than the given key, or null if there is no such key.

Parameters:
key - the key
Returns:
the least key greater than key, or null if there is no such key

firstKey

public java.lang.Integer firstKey()
Returns the first (lowest) key currently in this map.

Specified by:
firstKey in interface java.util.SortedMap<java.lang.Integer,V>
Returns:
the first key

firstEntry

public java.util.Map.Entry<java.lang.Integer,V> firstEntry()
Returns the first (lower) entry (key - value pair) currenty in this map

Specified by:
firstEntry in interface java.util.NavigableMap<java.lang.Integer,V>
Returns:
the first entry

lastKey

public java.lang.Integer lastKey()
Returns the last (highest) key currently in this map.

Specified by:
lastKey in interface java.util.SortedMap<java.lang.Integer,V>
Returns:
the last (highest) key currently in this map

lastEntry

public java.util.Map.Entry<java.lang.Integer,V> lastEntry()
Returns the last (higher) entry (key - value pair) currenty in this map

Specified by:
lastEntry in interface java.util.NavigableMap<java.lang.Integer,V>
Returns:
the last entry

pollFirstEntry

public java.util.Map.Entry<java.lang.Integer,V> pollFirstEntry()
Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty.

Specified by:
pollFirstEntry in interface java.util.NavigableMap<java.lang.Integer,V>
Returns:
the removed first entry of this map, or null if this map is empty

pollLastEntry

public java.util.Map.Entry<java.lang.Integer,V> pollLastEntry()
Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.

Specified by:
pollLastEntry in interface java.util.NavigableMap<java.lang.Integer,V>
Returns:
the removed last entry of this map, or null if this map is empty

descendingMap

public java.util.NavigableMap<java.lang.Integer,V> descendingMap()
Return a descending view of this map

Specified by:
descendingMap in interface java.util.NavigableMap<java.lang.Integer,V>
Returns:
a navigable map sorted in reverse order

navigableKeySet

public java.util.NavigableSet<java.lang.Integer> navigableKeySet()
Specified by:
navigableKeySet in interface java.util.NavigableMap<java.lang.Integer,V>

descendingKeySet

public java.util.NavigableSet<java.lang.Integer> descendingKeySet()
Specified by:
descendingKeySet in interface java.util.NavigableMap<java.lang.Integer,V>

subMap

public java.util.NavigableMap<java.lang.Integer,V> subMap(java.lang.Integer fromKey,
                                                          boolean fromInclusive,
                                                          java.lang.Integer toKey,
                                                          boolean toInclusive)
Specified by:
subMap in interface java.util.NavigableMap<java.lang.Integer,V>

headMap

public java.util.NavigableMap<java.lang.Integer,V> headMap(java.lang.Integer toKey,
                                                           boolean inclusive)
Specified by:
headMap in interface java.util.NavigableMap<java.lang.Integer,V>

tailMap

public java.util.NavigableMap<java.lang.Integer,V> tailMap(java.lang.Integer fromKey,
                                                           boolean inclusive)
Specified by:
tailMap in interface java.util.NavigableMap<java.lang.Integer,V>

subMap

public java.util.SortedMap<java.lang.Integer,V> subMap(java.lang.Integer fromKey,
                                                       java.lang.Integer toKey)
Specified by:
subMap in interface java.util.NavigableMap<java.lang.Integer,V>
Specified by:
subMap in interface java.util.SortedMap<java.lang.Integer,V>

headMap

public java.util.SortedMap<java.lang.Integer,V> headMap(java.lang.Integer toKey)
Specified by:
headMap in interface java.util.NavigableMap<java.lang.Integer,V>
Specified by:
headMap in interface java.util.SortedMap<java.lang.Integer,V>

tailMap

public java.util.SortedMap<java.lang.Integer,V> tailMap(java.lang.Integer fromKey)
Specified by:
tailMap in interface java.util.NavigableMap<java.lang.Integer,V>
Specified by:
tailMap in interface java.util.SortedMap<java.lang.Integer,V>

comparator

public java.util.Comparator<? super java.lang.Integer> comparator()
Specified by:
comparator in interface java.util.SortedMap<java.lang.Integer,V>

countLower

public int countLower(int key)
Counts lower keys

Parameters:
key - a key
Returns:
the number of entries that are strictly lower than a given one

countHigher

public int countHigher(int key)
Counts higher keys

Parameters:
key - a key
Returns:
the number of entries that are strictly higher than a given one

dump

public java.lang.String dump()
Dumps arrays for debugging purpose

Returns:
dumped arrays into a two-lined string