fr.univNantes.intcolls
Class DualArrayLongMap<V>

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

public class DualArrayLongMap<V>
extends java.util.AbstractMap<java.lang.Long,V>
implements java.util.NavigableMap<java.lang.Long,V>

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

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 DualArrayLongMap.DALMValueCollection<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  long[] keys
          Table of keys
private  int lastIndex
           
private  long lastKey
           
private  int size
          Actuel size of the map
private  java.lang.Object[] values
          Table of values
 
Constructor Summary
DualArrayLongMap()
          Parameterless constructor
DualArrayLongMap(int capacity)
          Constructor
DualArrayLongMap(java.util.Map<java.lang.Long,? extends V> coll)
          Constructor with another collection of Longs
 
Method Summary
 java.util.Map.Entry<java.lang.Long,V> ceilingEntry(java.lang.Long 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.Long ceilingKey(java.lang.Long 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.Long> 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(long key)
          Counts higher keys
 int countLower(long key)
          Counts lower keys
 java.util.NavigableSet<java.lang.Long> descendingKeySet()
           
 java.util.NavigableMap<java.lang.Long,V> descendingMap()
           
 java.util.Set<java.util.Map.Entry<java.lang.Long,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.Long,V> firstEntry()
           
 java.lang.Long firstKey()
          Returns the first (lowest) key currently in this map.
 java.util.Map.Entry<java.lang.Long,V> floorEntry(java.lang.Long 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.Long floorKey(java.lang.Long 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(long key)
          Returns index given a key, using cache
 V getLong(long key)
          Returns the value associated to a key
 int hashCode()
          Returns a hash code value for the object
 java.util.SortedMap<java.lang.Long,V> headMap(java.lang.Long toKey)
           
 java.util.NavigableMap<java.lang.Long,V> headMap(java.lang.Long toKey, boolean inclusive)
           
 java.util.Map.Entry<java.lang.Long,V> higherEntry(java.lang.Long 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.
 java.lang.Long higherKey(java.lang.Long key)
          Returns the least key strictly greater than the given key, or null if there is no such key.
 long higherLongKey(long 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.Long> keySet()
          Returns a Set view of the keys contained in this map.
 java.util.Map.Entry<java.lang.Long,V> lastEntry()
           
 java.lang.Long lastKey()
          Returns the last (highest) key currently in this map.
 java.util.Map.Entry<java.lang.Long,V> lowerEntry(java.lang.Long 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.
 java.lang.Long lowerKey(java.lang.Long key)
          Returns the greatest key strictly less than the given key, or null if there is no such key.
 long lowerLongKey(long key)
          Returns the greatest key strictly less than the given key, or null if there is no such key.
 java.util.NavigableSet<java.lang.Long> navigableKeySet()
           
 java.util.Map.Entry<java.lang.Long,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.Long,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.Long k, V v)
          Puts a value into the map
 V putLong(long 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 removeLong(long 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.Long,V> subMap(java.lang.Long fromKey, boolean fromInclusive, java.lang.Long toKey, boolean toInclusive)
           
 java.util.SortedMap<java.lang.Long,V> subMap(java.lang.Long fromKey, java.lang.Long toKey)
           
 java.util.SortedMap<java.lang.Long,V> tailMap(java.lang.Long fromKey)
           
 java.util.NavigableMap<java.lang.Long,V> tailMap(java.lang.Long 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 long[] 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 long lastKey

hasLastKey

private boolean hasLastKey

lastIndex

private int lastIndex
Constructor Detail

DualArrayLongMap

public DualArrayLongMap(int capacity)
Constructor

Parameters:
capacity - initial capacity of the map

DualArrayLongMap

public DualArrayLongMap(java.util.Map<java.lang.Long,? extends V> coll)
Constructor with another collection of Longs

Parameters:
coll - another collection

DualArrayLongMap

public DualArrayLongMap()
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.Long,V>
Overrides:
equals in class java.util.AbstractMap<java.lang.Long,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.Long,V>
Overrides:
hashCode in class java.util.AbstractMap<java.lang.Long,V>
Returns:
a hash code value for this object.

getIndex

private int getIndex(long 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()

getLong

public V getLong(long 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.Long,V>
Overrides:
get in class java.util.AbstractMap<java.lang.Long,V>
Parameters:
key - a key
Returns:
the corresponding value in this map or null if this map does not contains the key

putLong

public V putLong(long 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.Long k,
             V v)
Puts a value into the map

Specified by:
put in interface java.util.Map<java.lang.Long,V>
Overrides:
put in class java.util.AbstractMap<java.lang.Long,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

removeLong

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

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.

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.Long,V>
Overrides:
remove in class java.util.AbstractMap<java.lang.Long,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.Long,V>
Overrides:
size in class java.util.AbstractMap<java.lang.Long,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.Long,V>
Overrides:
isEmpty in class java.util.AbstractMap<java.lang.Long,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.Long,V>
Overrides:
containsKey in class java.util.AbstractMap<java.lang.Long,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.Long,V>
Overrides:
containsValue in class java.util.AbstractMap<java.lang.Long,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.Long,V>> entrySet()
Returns a Set view of the mappings contained in this map.

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

keySet

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

Specified by:
keySet in interface java.util.Map<java.lang.Long,V>
Specified by:
keySet in interface java.util.SortedMap<java.lang.Long,V>
Overrides:
keySet in class java.util.AbstractMap<java.lang.Long,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.Long,V>
Specified by:
values in interface java.util.SortedMap<java.lang.Long,V>
Overrides:
values in class java.util.AbstractMap<java.lang.Long,V>
Returns:
a collection view of the values contained in this map

lowerEntry

public java.util.Map.Entry<java.lang.Long,V> lowerEntry(java.lang.Long 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.Long,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.Long lowerKey(java.lang.Long 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.Long,V>
Parameters:
key -
Returns:
the greatest key less than key, or null if there is no such key

lowerLongKey

public long lowerLongKey(long 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.Long,V> floorEntry(java.lang.Long 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.Long,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.Long floorKey(java.lang.Long 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.Long,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.Long,V> ceilingEntry(java.lang.Long 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.Long,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.Long ceilingKey(java.lang.Long 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.Long,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.Long,V> higherEntry(java.lang.Long 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.Long,V>
Parameters:
key - the key
Returns:
an entry with the least key greater than key, or null if there is no such key

higherKey

public java.lang.Long higherKey(java.lang.Long 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.Long,V>
Parameters:
key - the key
Returns:
the least key greater than key, or null if there is no such key

higherLongKey

public long higherLongKey(long 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 Long.MIN_VALUE if there is no such key

firstKey

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

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

firstEntry

public java.util.Map.Entry<java.lang.Long,V> firstEntry()
Specified by:
firstEntry in interface java.util.NavigableMap<java.lang.Long,V>

lastKey

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

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

lastEntry

public java.util.Map.Entry<java.lang.Long,V> lastEntry()
Specified by:
lastEntry in interface java.util.NavigableMap<java.lang.Long,V>

pollFirstEntry

public java.util.Map.Entry<java.lang.Long,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.Long,V>
Returns:
the removed first entry of this map, or null if this map is empty

pollLastEntry

public java.util.Map.Entry<java.lang.Long,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.Long,V>
Returns:
the removed last entry of this map, or null if this map is empty

descendingMap

public java.util.NavigableMap<java.lang.Long,V> descendingMap()
Specified by:
descendingMap in interface java.util.NavigableMap<java.lang.Long,V>

navigableKeySet

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

descendingKeySet

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

subMap

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

headMap

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

tailMap

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

subMap

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

headMap

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

tailMap

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

comparator

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

countLower

public int countLower(long 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(long key)
Counts higher keys

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