#ifndef _HASHTABLE_H
#define _HASHTABLE_H

/* File: hashtable.h
 * ------------------
 * Defines the interface for the HashTable ADT.
 * The HashTable allows the client to store any number of elements of any
 * type in a hash table for fast storage and retrieval.  The client specifies
 * the size (in bytes) of the elements that will be stored in the table when
 * it is created. Thereafter the client and the HashTable refer to elements
 * via (void*) ptrs. The HashTable imposes no upper bound on the number of
 * elements and deals with all its own memory management.
 *
 * The client-supplied information (in the form of the number of buckets
 * to use and the hashing function to be applied to each element) is employed
 * to divide elements in buckets with hopefully only few collisions, resulting
 * in Enter & Lookup performance in constant-time.  The HashTable also supports
 * iterating over all elements by use of mapping function.
 */

#ifdef __cplusplus
extern "C" {
#endif

/* Type: HashTable
 * ----------------
 * Defines the HashTable type itself. The client can declare variables of type
 * HashTable, but these variables must be initialized with the result of
 * TableNew.  The HashTable is implemented with pointers, so all client
 * copies in variables or parameters will be "shallow" -- they will all
 * actually point to the same HashTable structure.  Only calls to TableNew
 * create new tables. The struct declaration below is "incomplete"- the
 * implementation details are literally not visible in the client .h file.
 */
typedef struct HashImplementation *HashTable;


/* TableHashFn
 * -----------
 * TableHashFn is a pointer to a client-supplied function which the
 * HashTable uses to hash elements. The hash function takes a (const void*)
 * pointer to an element and the number of buckets and returns an int,
 * which represents the hash code for this element.  The returned hash code
 * should be within the range 0 to numBuckets-1 and should be stable (i.e.
 * an element's hash code should not change over time).
 * For best performance, the hash function should be designed to
 * uniformly distribute elements over the available number of buckets.
 */
typedef int (*TableHashFn)(const void *elem, int numBuckets);


/* TableCompareFn
 * --------------
 * TableCompareFn is a pointer to a client-supplied function which the
 * HashTable uses to compare elements. The comparator takes two
 * (const void*) pointers (these will point to elements) and returns an int.
 * The comparator should indicate the ordering of the two elements
 * using the same convention as the strcmp library function:
 * If elem1 is "less than" elem2, return a negative number.
 * If elem1 is "greater than" elem2, return a positive number.
 * If the two elements are "equal", return 0.
 */
typedef int (*TableCompareFn)(const void *elem1, const void *elem2);
 /* TableMapFn
 * ----------
 * TableMapFn defines the space of functions that can be used to map over
 * the elements in a HashTable.  A map function is called with a pointer to
 * the element and a client data pointer passed in from the original caller.
 */
typedef void (*TableMapFn)(void *elem, void *clientData);


/* TableElementFreeFn
 * ------------------
 * TableElementFreeFn defines the space of functions that can be used as the
 * clean-up function for each element as it is deleted from the array
 * or when the entire array of elements is freed.  The cleanup function is
 * called with a pointer to an element about to be deleted.
 */
typedef void (*TableElementFreeFn)(void *elem);


/* TableNew
 * --------
 * Creates a new HashTable with no entries and returns it. The elemSize
 * parameter specifies the number of bytes that a single element of the
 * table should take up. For example, if you want to store elements of type
 * Binky, you would pass sizeof(Binky) as this parameter. An assert is
 * raised if this size is not greater than 0.
 *
 * The nBuckets parameter specifies the number of buckets that the elements
 * will be partitioned into.  Once a HashTable is created, this number does
 * not change.  The nBuckets parameter must be in synch with the behavior of
 * the hashFn, which must return a hash code between 0 and nBuckets-1.
 * The hashFn parameter specifies the function that is called to retrieve the
 * hash code for a given element.  See the type declaration of TableHashFn
 * above for more information.  An assert is raised if nBuckets is not
 * greater than 0.
 *
 * The compFn is used for testing equality between elements.  See the
 * type declaration for TableCompareFn above for more information.
 *
 * The elemFreeFn is the function that will be called on an element that is
 * about to be overwritten (by a new entry in TableEnter) or on each element
 * in the table when the entire table is being freed (using TableFree).  This
 * function is your chance to do any deallocation/cleanup required,
 * (such as freeing any pointers contained in the element). The client can pass
 * NULL for the cleanupFn if the elements don't require any handling on free.
 * An assert is raised if either the hash or compare functions are NULL.
 */

HashTable TableNew(int elemSize, int nBuckets,
                   TableHashFn hashFn, TableCompareFn compFn,
                   TableElementFreeFn freeFn);


/* TableFree
 * ----------
 * Frees up all the memory for the table and its elements. It DOES NOT
 * automatically free memory owned by pointers embedded in the elements. This
 * would require knowledge of the structure of the elements which the HashTable
 * does not have.  However, it will iterate over the elements calling
 * the elementFreeFn earlier supplied to TableNew and therefore, the client,
 * who knows what the elements are,can do the appropriate deallocation of any
 * embedded pointers through that function.
 * After calling this, the value of what table points to is undefined.
 */
void TableFree(HashTable table);


/* TableCount
 * ----------
 * Returns the number of elements currently in the table.
 */
int TableCount(HashTable table);


/* TableEnter
 * ----------
 * Enters a new element into the table. Uses the hash function to determine
 * which bucket to place the new element. Its contents are copied from the
 * memory pointed to by newElem. If there is already an element in the table
 * which is determined to be equal (using the comparison function) this will
 * use the contents of the new element to replace the previous element,
 * calling the free function on the replaced element.
 */
void TableEnter(HashTable table, const void *newElem);


/* TableLookup
 * ----------
 * Returns a pointer to the table element which matches the elemKey parameter
 * (equality is determined by the comparison function).  If there is no
 * matching element, returns NULL. Calling this function does not
 * re-arrange or change contents of the table or modify elemKey in any way.
 */
void *TableLookup(HashTable table, const void *elemKey);


/* TableMap
 * -----------
 * Iterates through each element in the table (in any order) and calls the 
 * function fn for that element. The function is called with the address of 
 * the table element and the clientData pointer. The clientData value allows
 * the client to pass extra state information to the client-supplied function,
 * if necessary.  If no client data is required, this argument should be NULL.
 * An assert is raised if the map function is NULL.
 */
void TableMap(HashTable table, TableMapFn fn, void *clientData);

#ifdef __cplusplus
}
#endif

#endif /* _HASHTABLE_H */
