var INIT_SIZE = 11; // initial size of the hashtable
var KEY = 0; // enum for a hashtable "key"
var VAL = 1; // enum for a hashtable "value"

/*
 * Hashtable:
 *      very basic implementation of a hashtable.  Supports adding, replacing
 *      and searching for a given key.  The hashtable will resize itself when
 *      it fills up (again, a very simplistic mechanism for resizing).  The
 *      implementation does support deletions, but at a performance penalty.
 * Params:
 *      none
 * Returns:
 *      false
 */
function Hashtable()
{
    this.mTable = [];
    this.mTable.length = INIT_SIZE;
    this.mCount = 0;

    return false;
}

/*
 * add:
 *      allows the caller to add a key/value pair to the hashtable.  If an
 *      entry with the specified key already exists in the hashtable, the
 *      key's data is overwritten with the new value
 * Params:
 *      key - the numeric or string key of the item to add.  This value can
 *          not be null
 *      val - the data to associate with the key.  This value can be null
 * Returns:
 *      true if the item was added; otherwise false
 */
Hashtable.prototype.add = function(key, val) {
    var result = false;
    
    if ( key ) {
        // check the number of items against the size of our table.  The
        // hashtable is considered full when there is no more than a single
        // null entry
        if ( this.mCount == (this.mTable.length-1) ) {
            this.rehash();
        }

        // generate a hash key for this item
        var start = this.genHashIdx(key);
        var idx = start;
        
        // we're now going to probe the hashtable and insert the key/value
        // pair in the first null entry.  Alternatively, if the key already
        // exists in the hashtable, we'll just overwrite the existing value.
        // In the first case, the item count for the table is incremented
        // and in the second case it is not
        do {
            if ( !this.mTable[idx] ) {
                this.mTable[idx] = [key, val];
                result = true;
                this.mCount++;
                break;
            }
            else if (this.mTable[idx][KEY] == key) {
                this.mTable[idx][VAL] = val;
                result = true;
                break;
            }
            else {
                idx = (0 == idx) ? this.mTable.length - 1: idx-1;
            }
        } while (idx != start);
    }
    
    return result;
}

/*
 * contains:
 *      checks the hashtable for the existence of the specified key
 * Params:
 *      key - the key to search for.  This value must not be null
 * Returns:
 *      true if the hashtable contains the specified key; otherwise false
 */
Hashtable.prototype.contains = function(key) {
    var result = false;
    
    // only search if key is valid and if we have items stored in
    // our list
    if ( (key) && (0 < this.mCount) ) {
        var start = genHashIdx(key);
        var idx = start;
        
        // probe the table until either we hit an empty entry or
        // we find a match
        do {
            if ( !this.mTable[idx] ) {
                break;
            }
            else if ( this.mTable[idx][KEY] == key ) {
                result = true;
            }
            else {
                idx = (0 == idx) ? this.mTable.length - 1: idx-1;
            }
        } while ((idx != start) && (false == result));
    }
    
    return result;
}

/*
 * containsValue:
 *      searches the hashtable for the first occurence of "val"
 * Params:
 *      val - the value item to search for.  This item can not be null
 * Returns:
 *      true if a key/value pair is found where the value portion of
 *      the key matches "val"; otherwise false
 */
Hashtable.prototype.containsValue = function(val) {
    var result = false;
    
    if ( (val) && (0 < this.mCount) ) {
        // values are not indexed ... we'll have to do this the hard
        // way by iterating through all the table's entries
        for (var cnt=0; cnt<this.mTable.length; cnt++) {
            if ( (this.mTable[cnt]) && (this.mTable[cnt][VAL] == val) ) {
                result = true;
                break;
            }
        }
    }
    
    return result;
}

/*
 * find:
 *      gets the value associated with the specified key
 * Params:
 *      key - the key to retrieve the value for.  This value can not be null
 * Returns:
 *      the value associated with the given key or null if the key
 *      does not exist in the hashtable
 */
Hashtable.prototype.find = function(key) {
    var result = null;
    
    // only search if key is not null and if we have items in our hashtable
    if ( (key) && (0 < this.mCount) ) {
        var start = this.genHashIdx(key);
        var idx = start;
        
        do {
            // if we hit an empty entry then the key doesn't exist in the table
            if ( !this.mTable[idx] ) {
                break;
            }
            else if ( this.mTable[idx][KEY] == key ) {
                result = this.mTable[idx][VAL];
            }
            else {
                idx = (0 == idx) ? this.mTable.length - 1: idx-1;
            }
        } while ( (idx != start) && (null == result) );
    }
    
    return result;
}

/*
 * genHashIdx:
 *      generates an inital index into the hashtable.  Probes, inserts, and deletes
 *      start from this index
 * Params:
 *      key - an integer or string value that is the key of the entry
 * Returns:
 *      the initial index into the hashtable for this key
 */
Hashtable.prototype.genHashIdx = function(key) {
    var result = 0;
    
    // the table length should never be 0, but check in case I've screwed up
    if ( 0 == this.mTable.length ) this.mTable.length = INIT_SIZE;
    
    // if "key" is an integer value, then just use it as a seed value
    if ( false == isNaN(key) ) {
        result = key % this.mTable.length;
    }
    else {
        // string value ... we'll compute an integer by multiplying each character
        // in the string by its ordinal value in the string against the character's
        // ASCII value
        var num = 0;
        
        for (var cnt=0; cnt<key.length; cnt++) {
            num += (cnt * key.charCodeAt(cnt));
        }
        
        result = num % this.mTable.length;
    }
    
    return result;
}

/*
 * rehash:
 *      resizes the hashtable and re-hashes all existing entries in the hashtable
 * Params:
 *      none
 * Returns:
 *      true
 */
Hashtable.prototype.rehash = function() {
    var orig = this.mTable;
    this.mTable = [];
    // I admit this could be a better algorithm, but I can't think of one off the top
    // of my head at the moment
    this.mTable.length = orig.length * 2 + 1;
    
    // now, re-hash every single entry in the old table
    for (var cnt=0; cnt<orig.length; cnt++) {
        if ( orig[cnt] ) this.add(orig[cnt][KEY], orig[cnt][VAL]);
    }
    
    return true;
}

/*
 * remove:
 *      removes an item from the hashtable.  Note that this operation is expensive since
 *      every successful removal requires a re-hash of the table
 * Params:
 *      key - the key of the item to remove
 * Returns:
 *      true if the item was removed, otherwise false
 */
Hashtable.prototype.remove = function(key) {
    var result = false;
    
    // only search if key is valid and if we have items stored in
    // our list
    if ( (key) && (0 < this.mCount) ) {
        var start = genHashIdx(key);
        var idx = start;
        
        // probe the table until either we hit an empty entry or
        // we find a match
        do {
            if ( !this.mTable[idx] ) {
                break;
            }
            else if ( this.mTable[idx][KEY] == key ) {
                result = true;
                // the entry is being removed - set its value to null
                this.mTable[idx] = null;
            }
            else {
                idx = (0 == idx) ? this.mTable.length - 1: idx-1;
            }
        } while ((idx != start) && (false == result));
    }
    
    // if we've found the item and deleted it, then we have to reorganize
    // the hashtable since the current probe index values are now invalid
    if ( true == result ) {
        this.rehash();
    }
    
    return result;
}