/*
 * Created on Jul 27, 2004
 */
package hashing;


/** Interface for a hash table, that is, a collection which stores objects
 * based on their key.  Concrete implementations should have a constructor
 * with two arguments as follows:<br />
 * param tableSize: an int giving the size (>=1) (number of buckets)
 *  of the internal hash table
 * <br />
 * param hasher: an IHasher object that can compute hash functions.
 * <br />
 * The intention is that the hasher should be called whenever the hash
 * value of an object is needed.
 * @author dickey
 */
public interface IHashTable {
	
	/** Add the value to the table, using its key to store it.  Unless
	 * deleted or modified, the value can then be retrieved by the get(key) operation.
	 * @param key the non-null key of the value; this should have a type which the
	 * IHasher of the table is able to process.  Within the hashtable, keys
	 * must be unique (as determined by the .equals() method).
	 * @param value the value to be added.
	 * @return true if the value was successfully added to the table; false
	 * otherwise.
	 * @throws IllegalArgumentException if the key null.
	 */
	boolean add(Object key, Object value);
	
	/** Locate and return the object whose key is given.  If an object obj
	 * had previously been stored by a call to add(key, obj), and had not been
	 * deleted, then obj is returned.  Otherwise, null is returned.
	 * @param key the key of the object being sought.
	 * @return the object whose key is supplied, or null if there is no object
	 * with that key.
	 * @throws IllegalArgumentException if the key null.
	 */
	Object get(Object key);
	
	/** (Optional operation) Locate and delete the object whose key is given.  If an object obj
	 * had previously been stored by a call to add(key, obj), and had not been
	 * deleted, then the remove should word.
	 * @param key the key of the object being sought (non-null).
	 * @return true iff the object with that key was removed, false if there is no object
	 * with that key.
	 * @throws IllegalArgumentException if the key is null.
	 * @throws UnsupportedOperationException if the concrete class does not support
	 * this operation.
	 */
	boolean remove(Object key);
	
	/** (Optional operation) Locate the object whose key is given and
	 * replace its value.  If an object obj
	 * had previously been stored by a call to add(key, obj), and had not been
	 * deleted, then the replace should word.
	 * @param key the key of the object being sought (non-null).
	 * @param newvalue the value that will replace the current value for this key.
	 * @return true iff the object with that key was replaced, false if there is no object
	 * with that key.
	 * @throws IllegalArgumentException if the key is null.
	 * @throws UnsupportedOperationException if the concrete class does not support
	 * this operation.
	 */
	boolean replace(Object key, Object newvalue);
	
	/** Tell how many values are currently stored in the table.  
	 * 
	 * @return the number of elements currently stored in the table.
	 */
	int size();
	
	/** Tell how many entries (buckets) there are in the internal table.  Note
	 * carefully that this number is independent of the value returned by size(). 
	 * 
	 * @return the number of entries (buckets) in the internal table.
	 */
	int tableSize();
	
	/** Summarize the distribution of keys in the table.
	 * 
	 * @param max the size of the returned array, minus 1; should be >= -1.  
	 * There is no point
	 * in making max greater than tableSize(), but there is no prohibition
	 * against it, either.
	 * @return an array of size max+2; except for the last entry (max+1), 
	 * entry n tells how many buckets
	 * of the table contain exactly n values.  For example, entry 0 tells
	 * how many buckets are empty; entry 1 tells how many buckets have
	 * exactly one value; etc.  Entery max+1 has a special meaning: it tells
	 * how many buckets contain max+1 or more entries.  The total of all the
	 * numbers in the returned array should exactly equal size().
	 * <br /> DOCUMENTATION ERROR!  The line above should read <br />
	 * "... should exactly equal tablesize()." (i.e., number of buckets,
	 * not the number of records currently stored).
	 */
	int[] keyDistribution(int max);

}