Hashtable and Vector like data structure for
* Objects. Each object is associated with a key, with the
* usual Hashtable put/get methods, but some Vector-like
* accessors have been included (eg: size(), indexOf(), elementAt()). Ideally,
* this class will have all the best characteristics of Hashtables
* and Vectors.
*
* @author Michael Coury
* @version 1.03, 05/16/2001
*/
public class ObjectMap implements java.io.Serializable {
private static final long serialVersionUID = -7885802476177462599L;
private MapItem[] hashArray;
private final MapItem nonItem;
private int arraySize, itemCount;
private float loadFactor;
////////////////////////
///// CONSTRUCTORS /////
////////////////////////
/**
* Constructs a new, empty map with a default capacity and load
* factor, which is 0.65.
*/
public ObjectMap() { this(11, 0.65f); }
/**
* Constructs a new, empty map with the specified initial capacity
* and default load factor, which is 0.65.
* @param size the initial capacity of the HashMap.
* @throws IllegalArgumentException if the initial capacity is less
* than zero.
*/
public ObjectMap(int size) { this(size, 0.65f); }
/**
* Constructs a new, empty map with the specified initial
* capacity and the specified load factor.
* @param size the initial capacity of the HashMap.
* @param loadFactor the load factor of the HashMap
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive.
*/
public ObjectMap(int size, float loadFactor) {
if (size < 0)
throw new IllegalArgumentException("Illegal Initial Capacity: "+ size);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load factor: "+ loadFactor);
if (size==0)
size = 1;
arraySize = size;
itemCount = 0;
this.loadFactor = loadFactor;
hashArray = new MapItem[arraySize];
nonItem = new MapItem(new Object(), new Object());
nonItem.itemHash = -1;
}
/**
* Constructs a new map from a Hashtable
* @param aTable the hashtable to use to create the map from
*/
public ObjectMap(Hashtable aTable) {
this((int)(aTable.size()/0.65f), 0.65f);
Iterator i = aTable.entrySet().iterator();
while (i.hasNext()) {
Map.Entry e = (Map.Entry) i.next();
put(e.getKey(), e.getValue());
}
}
/**
* Constructs a new map from a Vector
* @param aVector the vector to use to create the map from
*/
public ObjectMap(Vector aVector) {
this((int)(aVector.size()/0.65f), 0.65f);
int vs = aVector.size();
for(int i = 0; i < vs; i++)
this.addElement(aVector.elementAt(i));
}
/////////////////////////////
///// HASHTABLE METHODS /////
/////////////////////////////
/**
* Associates the specified Object with the specified key
* in this map. If the map previously contained a mapping for this key,
* the old value is replaced.
*
* @param aKey key with which the specified value is to be associated.
* @param aValue the object to be associated with the specified key.
* @return success
*/
public void put(Object aKey, Object aValue) {
_put(new MapItem(aKey, aValue));
itemCount++;
}
/**
* Removes the mapping for this key if present.
* @param aKey key whose object is to be removed.
* @return success
*/
public Object remove(Object aKey) {
int hashVal = _hashFunc(aKey.hashCode());
int keyHash = aKey.hashCode();
while(hashArray[hashVal] != null) {
if(hashArray[hashVal].itemHash == keyHash) {
MapItem temp = hashArray[hashVal];
hashArray[hashVal] = nonItem;
itemCount--;
if(arraySize > itemCount*3)
_condense();
return temp.val;
}
hashVal++;
hashVal %= arraySize;
}
return null;
}
/**
* Returns the value to which this map maps the specified key. Returns
* 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's also possible that the map
* explicitly maps the key to null. The containsKey
* operation may be used to distinguish these two cases.
* @param aKey key whose associated value is to be returned.
* @return the value to which this map maps the specified key.
*/
public Object get(Object aKey) {
int hashVal = _hashFunc(aKey.hashCode());
int keyHash = aKey.hashCode();
while(hashArray[hashVal] != null) {
if(hashArray[hashVal].itemHash == keyHash)
return hashArray[hashVal].val;
hashVal++;
hashVal %= arraySize;
}
return null;
}
/**
* Returns true if this map contains a mapping for the specified
* key.
* @return true if this map contains a mapping for the specified key.
* @param aKey key whose presence in this Map is to be tested.
*/
public boolean containsKey(Object aKey) {
int hashVal = _hashFunc(aKey.hashCode());
int keyHash = aKey.hashCode();
while(hashArray[hashVal] != null) {
if(hashArray[hashVal].itemHash == keyHash)
return true;
hashVal++;
hashVal %= arraySize;
}
return false;
}
/**
* Searches for the occurrence of the requested key
* @param aKey object to search for.
* @return the index of the argument in this map.
*/
public int indexOf(Object aKey) {
int hashVal = _hashFunc(aKey.hashCode());
int keyHash = aKey.hashCode();
while(hashArray[hashVal] != null) {
if(hashArray[hashVal].itemHash == keyHash)
return hashVal;
hashVal++;
hashVal %= arraySize;
}
return -1;
}
/**
* Searches for the occurrence of the requested key
* @param aKey object to search for.
* @return the index of the argument in this map.
*/
public int indexOfKey(Object aKey) { return indexOf(aKey); }
//////////////////////////
///// VECTOR METHODS /////
//////////////////////////
/**
* Adds the specified Object to the map with its toString() as the key.
* The capacity is increased if its size becomes greater than its capacity
* and load factor.
* @param aValue the component to be added.
*/
public void addElement(Object aValue) {
_put(new MapItem(aValue.toString(), aValue));
itemCount++;
}
/**
* Removes the first (lowest-indexed) occurrence of the argument
* from this map.
* @param aValue the component to be removed.
* @exception NullPointerException if the value is null.
*/
public void removeElement(Object aValue) {
if(aValue == null)
throw new NullPointerException();
for(int i = 0; i < arraySize; i++) {
if(hashArray[i] != null)
if(hashArray[i].val.equals(aValue))
hashArray[i] = nonItem;
}
}
/**
* Tests if some key maps into the specified value in this map.
* This operation is more expensive than the containsKey
* method.
* @param aValue a value to search for.
* @return true if and only if some key maps to the
* aValue argument in this hashtable as
* determined by the equals method;
* false otherwise.
* @exception NullPointerException if the value is null.
*/
public boolean contains(Object aValue) {
if(aValue == null)
throw new NullPointerException();
for(int i = 0; i < arraySize; i++) {
if(hashArray[i] != null)
if(hashArray[i].val.equals(aValue))
return true;
}
return false;
}
/**
* Returns true if this ObjectMap maps one or more keys to this value.
*
* Note that this method is identical in functionality to contains
*
* @param aValue value whose presence in this Hashtable is to be tested.
* @return true if this map maps one or more keys to the
* specified value.
*/
public boolean containsValue(Object aValue) { return contains(aValue); }
/**
* Searches for the first occurence of the given argument, testing
* for equality using the equals method.
* @param aValue object to search for.
* @return the index of the first occurrence of the argument in this
* map.
* @exception NullPointerException if the value is null.
*/
public int indexOfValue(Object aValue) {
if(aValue == null)
throw new NullPointerException();
for(int i = 0; i < arraySize; i++) {
if(hashArray[i] != null)
if(hashArray[i].val.equals(aValue))
return i;
}
return -1;
}
/**
* Deletes the component at the specified index.
* The index must be a value greater than or equal to 0
* and less than the current size of the map.
* @param index the index of the object to remove.
* @exception ArrayIndexOutOfBoundsException if the index was invalid.
*/
public boolean removeElementAt(int index) {
if(index >= arraySize)
throw new ArrayIndexOutOfBoundsException(index + " >= " + arraySize);
if(index < 0)
throw new ArrayIndexOutOfBoundsException(index + " < 0");
try {
hashArray[index] = nonItem;
return true;
}
catch(NullPointerException npe) {
return false;
}
}
/**
* Returns the component at the specified index.
* @param index an index into this vector.
* @return the component at the specified index.
* @exception ArrayIndexOutOfBoundsException if the index
* is negative or not less than the current size
*/
public Object elementAt(int index) throws ArrayIndexOutOfBoundsException {
try {
return hashArray[index].val;
}
catch(NullPointerException npe) {
return null;
}
}
/////////////////////////
///// OTHER METHODS /////
/////////////////////////
/**
* Sets the load factor
* @param newLoad the load factor of the ObjectMap
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive.
*/
public void setLoadFactor(float newLoad) {
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load factor: "+ loadFactor);
loadFactor = newLoad;
if((double)itemCount/arraySize >= loadFactor)
_rehash();
}
/**
* Returns the current load factor of the ObjectMap
* @return the load factor
*/
public float getLoadFactor() { return loadFactor; }
/**
* Tests if this ObjectMap maps no keys to values.
* @return true if this hashtable maps no keys to values;
* false otherwise.
*/
public boolean isEmpty() { return itemCount == 0; }
/**
* Returns all the keys as a string array
* @return all the keys as a string array
*/
public Object[] getKeys() {
Object[] keys = new Object[itemCount];
for(int i = 0; i < arraySize; i++)
if(hashArray[i] != null && hashArray[i] != nonItem)
keys[i] = hashArray[i].key;
return keys;
}
/**
* Removes all objects and keys from this map
*/
public void removeAll() { hashArray = new MapItem[arraySize]; }
/**
* Returns the number of components in this map.
* @return the number of components in this map.
*/
public int size() { return itemCount; }
/**
* Returns the current capacity of this map (not the number of items).
* @return the current capacity (the length of its internal
* data array) of this map
*/
public int capacity() { return arraySize; }
/**
* Returns a string representation of this map, containing
* the String representation of each item.
*/
public String toString() {
String s = "";
for(int i = 0; i < arraySize; i++)
if(hashArray[i] != null && hashArray[i] != nonItem)
s = s + hashArray[i].toString()+", ";
else if(hashArray[i] != null && hashArray[i] == nonItem)
s = s + "(empty), ";
else
s = s + "(null), ";
return s;
}
/**
* Get all items as a vector
* @return a vector containing all non-null items in the map
*/
public Vector getAsVector() {
Vector v = new Vector(itemCount);
for(int i = 0; i < arraySize; i++)
if(hashArray[i] != null && hashArray[i] != nonItem)
v.addElement(hashArray[i].val);
return v;
}
/**
* Get all items in the map as a Hashtable with a load factor of
* 0.65F
* @return a hashtable containing all non-null items in the map
*/
public Hashtable getAsHashtable() { return getAsHashtable(0.65f); }
/**
* Get all items in the map as a Hashtable with the load factor
* specified.
* @return a hashtable containing all non-null items in the map
*/
public Hashtable getAsHashtable(float loadFactor) {
Hashtable h = new Hashtable((int)(itemCount/loadFactor), loadFactor);
for(int i = 0; i < arraySize; i++)
if(hashArray[i] != null && hashArray[i] != nonItem)
h.put(hashArray[i].key, hashArray[i].val);
return h;
}
/**
*
*/
private int _hashFunc(int key) { return key % arraySize; }
/**
* Rehashes the contents of this map with a larger capacity. This method is
* called automatically when the number of keys in this map exceeds
* its capacity and load factor.
*/
private void _rehash() {
MapItem[] oldArray = hashArray;
hashArray = new MapItem[arraySize*2+1];
arraySize = hashArray.length;
for(int i = 0; i < oldArray.length; i++)
if(oldArray[i] != null && oldArray[i] != nonItem)
_put(oldArray[i]);
}
/**
* Rehashes the contents of this map with a smaller capacity. This method is
* called automatically when the array size is more than 3 times the item
* count.
*/
private void _condense() {
arraySize = itemCount*3;
MapItem[] oldArray = hashArray;
hashArray = new MapItem[arraySize];
for(int i = 0; i < oldArray.length; i++)
if(oldArray[i] != null && oldArray[i] != nonItem)
_put(oldArray[i]);
}
/**
*
*/
private void _put(MapItem item) {
if((double)itemCount/arraySize >= loadFactor)
_rehash();
int key = item.itemHash;
int hashVal = _hashFunc(key);
while(hashArray[hashVal] != null && hashArray[hashVal].itemHash != -1) {
hashVal++;
hashVal %= arraySize;
}
hashArray[hashVal] = item;
}
/**
*
*/
class MapItem implements java.io.Serializable {
public int itemHash;
public Object key, val;
public MapItem(Object aKey, Object aVal) {
key = aKey;
val = aVal;
itemHash = key.hashCode();
}
public String toString() { return "("+key+","+val+")"; }
}
}