org.eclipse.emf.compare.util
Class EMFCompareMap<K,V>

java.lang.Object
  extended by org.eclipse.emf.compare.util.EMFCompareMap<K,V>
Type Parameters:
K - Specifies the keys' class for this Map.
V - Specifies the values' class for this Map.
All Implemented Interfaces:
java.io.Serializable, java.lang.Cloneable, java.util.Map<K,V>

public class EMFCompareMap<K,V>
extends java.lang.Object
implements java.util.Map<K,V>, java.io.Serializable, java.lang.Cloneable

Implementation of a map that stores its content using an hash table.

Initial capacity and load factor greatly affect the map's performances. Capacity is the number of elements the map can contain and the load factor represents how much the hash table can be filled before it is automatically rehashed.

This implementation ensures the capacity of this Map is a prime number at all time.

See Also:
Serialized Form

Field Summary
protected static int DEFAULT_INITIAL_CAPACITY
          Default value used as the initial capacity for a Map.
protected static float DEFAULT_LOAD_FACTOR
          The load factor used when none specified in constructor
protected  int freeSlots
          Current number of free buckets this Map holds.
protected  K[] keys
          Keys of this Map's entries.
protected  float loadFactor
          Load factor of this Map.
protected static float MINIMUM_LOAD_FACTOR
          Minimal allowed load factor for the map.
protected  int nextPrimeIndex
          Index of the next prime in the primes list.
protected static java.lang.Object NULL_KEY
          Object used as key for the null key.
protected static java.lang.Object REMOVED_ENTRY
          Object used as key for the "removed" entries of this Map.
protected  int threshold
          Threshold for resizing.
protected  int usedSlots
          Current number of non-empty slots.
protected  V[] values
          Values contained within this Map.
 
Constructor Summary
EMFCompareMap()
          Constructs an empty EMFCompareMap with the default initial capacity (31) and the default load factor (0.75).
EMFCompareMap(int initialCapacity)
          Constructs an empty EMFCompareMap with the specified initial capacity and the default load factor (0.75).
EMFCompareMap(int initialCapacity, float theLoadFactor)
          Constructs an empty EMFCompareMap with the specified initial capacity and load factor.This class will automatically use as the Map's initial capacity if initialCapacity is lower.
EMFCompareMap(java.util.Map<K,V> map)
          Construcs a EMFCompareMap populated by the entries of map.
 
Method Summary
protected  int capacity()
          Returns the current capacity of the Map.
protected  void changeCapacity(int newCapacity)
          Modifies the capacity of this Map.
protected  void checkCapacity(int desiredSlots)
          Ensures the map has sufficient empty slots to hold desiredSlots additional elements and resizes it if needed.
 void clear()
          Removes all mappings from this Map.
 java.lang.Object clone()
          Returns a copy of this Map containing all its elements.
 boolean containsKey(java.lang.Object key)
          Returns True if the Map contains a mapping for the specified key.
 boolean containsValue(java.lang.Object value)
          Checks for a mapping to the specified value in the Map.
 java.util.Set<java.util.Map.Entry<K,V>> entrySet()
          
protected  boolean equal(java.lang.Object obj1, java.lang.Object obj2)
          Returns True if the two object are equal.
 boolean equals(java.lang.Object another)
          
 V get(java.lang.Object key)
          Retrieves the value to which the specified key is mapped.
protected  int getNearestPrime(int number)
          Finds the nearest pseudo-prime greater than number.
 int hashCode()
          
protected  int indexOf(java.lang.Object key)
          Determines the index of the specified key in the keys array.
protected  int insertionIndexFor(K key)
          Returns the index at which key can be inserted.
 boolean isEmpty()
          
 java.util.Set<K> keySet()
          
protected  void postInsert(boolean usedFreeSlot)
          Called after an insert to update the used and free slots information and rehash the map if needed.
 V put(K key, V value)
          Associates the specified key with the specified value in the Map.
 void putAll(java.util.Map<? extends K,? extends V> map)
          
 V remove(java.lang.Object key)
          Removes the mapping for this key from this Map if present.
protected  java.util.Map.Entry<K,V> removeEntry(java.lang.Object e)
          Removes the specified entry from this Map.
protected  void removeEntryForIndex(int index)
          Removes the mapping at index from this Map.
protected  void resize(int newCapacity)
          Rehashes the content of this Map into a new Array with a larger capacity.
 int size()
          
 java.lang.String toString()
          Returns a String representation of this Map.
 java.util.Collection<V> values()
          
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

DEFAULT_INITIAL_CAPACITY

protected static final int DEFAULT_INITIAL_CAPACITY
Default value used as the initial capacity for a Map.

See Also:
Constant Field Values

DEFAULT_LOAD_FACTOR

protected static final float DEFAULT_LOAD_FACTOR
The load factor used when none specified in constructor. *

See Also:
Constant Field Values

MINIMUM_LOAD_FACTOR

protected static final float MINIMUM_LOAD_FACTOR
Minimal allowed load factor for the map.

See Also:
Constant Field Values

NULL_KEY

protected static final java.lang.Object NULL_KEY
Object used as key for the null key.


REMOVED_ENTRY

protected static final java.lang.Object REMOVED_ENTRY
Object used as key for the "removed" entries of this Map.


freeSlots

protected int freeSlots
Current number of free buckets this Map holds.


keys

protected transient K[] keys
Keys of this Map's entries.


loadFactor

protected float loadFactor
Load factor of this Map.


nextPrimeIndex

protected int nextPrimeIndex
Index of the next prime in the primes list.


threshold

protected int threshold
Threshold for resizing.


usedSlots

protected transient int usedSlots
Current number of non-empty slots.


values

protected transient V[] values
Values contained within this Map.

Constructor Detail

EMFCompareMap

public EMFCompareMap()
Constructs an empty EMFCompareMap with the default initial capacity (31) and the default load factor (0.75).


EMFCompareMap

public EMFCompareMap(int initialCapacity)
Constructs an empty EMFCompareMap with the specified initial capacity and the default load factor (0.75). This class will automatically use as the Map's initial capacity if initialCapacity is lower.

Parameters:
initialCapacity - Initial capacity of the Map.

EMFCompareMap

public EMFCompareMap(int initialCapacity,
                     float theLoadFactor)
Constructs an empty EMFCompareMap with the specified initial capacity and load factor.This class will automatically use as the Map's initial capacity if initialCapacity is lower.

Parameters:
initialCapacity - Initial capacity of the Map.
theLoadFactor - Load factor to apply to this Map.

EMFCompareMap

public EMFCompareMap(java.util.Map<K,V> map)
Construcs a EMFCompareMap populated by the entries of map.

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

clear

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

Specified by:
clear in interface java.util.Map<K,V>

clone

public java.lang.Object clone()
Returns a copy of this Map containing all its elements.

Overrides:
clone in class java.lang.Object
Returns:
A clone of this instance.

containsKey

public boolean containsKey(java.lang.Object key)
Returns True if the Map contains a mapping for the specified key.

Specified by:
containsKey in interface java.util.Map<K,V>
Parameters:
key - The key whose presence in this Map is to be tested.
Returns:
True if the Map contains a mapping for key, False otherwise.

containsValue

public boolean containsValue(java.lang.Object value)
Checks for a mapping to the specified value in the Map.

Specified by:
containsValue in interface java.util.Map<K,V>
Parameters:
value - Value whose presence is to be tested.
Returns:
True if the Map contains a mapping to value, False otherwise.

entrySet

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

Specified by:
entrySet in interface java.util.Map<K,V>
See Also:
Map.entrySet()

equals

public boolean equals(java.lang.Object another)

Specified by:
equals in interface java.util.Map<K,V>
Overrides:
equals in class java.lang.Object
See Also:
Object.equals(java.lang.Object)

get

public V get(java.lang.Object key)
Retrieves the value to which the specified key is mapped.

Specified by:
get in interface java.util.Map<K,V>
Parameters:
key - The key whose associated value is to be returned.
Returns:
Value mapped to key, null if none.

hashCode

public int hashCode()

Specified by:
hashCode in interface java.util.Map<K,V>
Overrides:
hashCode in class java.lang.Object
See Also:
Object.hashCode()

isEmpty

public boolean isEmpty()

Specified by:
isEmpty in interface java.util.Map<K,V>
See Also:
Map.isEmpty()

keySet

public java.util.Set<K> keySet()

Specified by:
keySet in interface java.util.Map<K,V>
See Also:
Map.keySet()

put

public V put(K key,
             V value)
Associates the specified key with the specified value in the Map. If a value was already associated to this key, it is replaced and returned.

Specified by:
put in interface java.util.Map<K,V>
Parameters:
key - Key with which the value will be associated.
value - Value to associate with the key.
Returns:
The previous value associated with key. Null if there were none or null was associated.
See Also:
Map.put(java.lang.Object, java.lang.Object)

putAll

public void putAll(java.util.Map<? extends K,? extends V> map)

Specified by:
putAll in interface java.util.Map<K,V>
See Also:
Map.putAll(java.util.Map)

remove

public V remove(java.lang.Object key)
Removes the mapping for this key from this Map if present.

Specified by:
remove in interface java.util.Map<K,V>
Parameters:
key - Key whose mapping is to be removed.
Returns:
The old value mapped to key.

size

public int size()

Specified by:
size in interface java.util.Map<K,V>
See Also:
Map.size()

toString

public java.lang.String toString()
Returns a String representation of this Map.

Overrides:
toString in class java.lang.Object
Returns:
A String representation of this Map.

values

public java.util.Collection<V> values()

Specified by:
values in interface java.util.Map<K,V>
See Also:
Map.values()

capacity

protected int capacity()
Returns the current capacity of the Map.

Returns:
The current capacity of the Map.

changeCapacity

protected void changeCapacity(int newCapacity)
Modifies the capacity of this Map. This computes the new maximum size and number of free slots.

Parameters:
newCapacity - Capacity from which to compute the maximum capacity and the new number of free slots.

checkCapacity

protected void checkCapacity(int desiredSlots)
Ensures the map has sufficient empty slots to hold desiredSlots additional elements and resizes it if needed.

Parameters:
desiredSlots - Desired number of additional elements.

equal

protected boolean equal(java.lang.Object obj1,
                        java.lang.Object obj2)
Returns True if the two object are equal.

Parameters:
obj1 - First of the objects to compare.
obj2 - Second of the objects to compare.
Returns:
True if the two object are equal, False otherwise.

getNearestPrime

protected int getNearestPrime(int number)
Finds the nearest pseudo-prime greater than number. Based on Rabin-Miller primality test.

Parameters:
number - Number we will use as a starting point to find a greater prime.
Returns:
First pseudo-prime greater than number

indexOf

protected int indexOf(java.lang.Object key)
Determines the index of the specified key in the keys array.

Parameters:
key - Key whose index is to be fetched.
Returns:
The index of the specified key, -1 if inexistant.

insertionIndexFor

protected int insertionIndexFor(K key)
Returns the index at which key can be inserted. If such a key already exists, returns its negative value minus 1.

Parameters:
key - Key to be inserted.
Returns:
The index at which key can be inserted. If such a key already exists, returns its negative value minus 1.

postInsert

protected void postInsert(boolean usedFreeSlot)
Called after an insert to update the used and free slots information and rehash the map if needed.

Parameters:
usedFreeSlot - Indicates whether the insert used up a free slot.

removeEntry

protected java.util.Map.Entry<K,V> removeEntry(java.lang.Object e)
Removes the specified entry from this Map. This is only called from EntrySet.

Parameters:
e - Entry to be removed from the Map.
Returns:
The old entry.

removeEntryForIndex

protected void removeEntryForIndex(int index)
Removes the mapping at index from this Map.

Parameters:
index - Index of the mapping to be removed.

resize

protected void resize(int newCapacity)
Rehashes the content of this Map into a new Array with a larger capacity. Also used without modifying capacity to delete removed entries in order to free space.

Parameters:
newCapacity - New capacity of the Map.

Copyright 2006 IBM Corporation and others.
All Rights Reserved.