/*
 * class: hashClass - a dictionary implemented using an open hash table.
 *
 * public procedures:
 *      create( size )  create the hash table with the given size.  Note
 *                      that more elements than this can be stored in
 *                      the table; it is a space/time tradeoff; smaller
 *                      tables take somewhat less space, but run more
 *                      slowly; larger tables take more space, but
 *                      run more quickly.
 *      insert( name, val )     insert the given name into the dictionary
 *                      with the given val.  If name already exists in
 *                      the dictionary, its previous value is discarded
 *                      and the new val put in its place.  No return
 *                      value.
 *      lookup( name )  Looks up a name in the dictionary, and returns
 *                      the value found there, or nil if the name is not
 *                      present in the dictionary.
 */
using namespace oadl;

class hashClass {
    var
        hashSize,       /* Number of elements in the hash table */
        hashTab;        /* The hash table itself - initialized by create() */

    public proc
        create( size )
        {
            var
                i;

            hashSize = size;
            hashTab = new Array( size );
            for( i = 0; i < size; i += 1 ) {
                hashTab[i] = {};
            }
        }

    /* This procedure computes a "hash" index based on the characters
     * in the given string.  Copied from the Dragon Book; look there
     * for more info about hash functions.
     */
    proc
        hash( val )
        {
            var
                i, n, t, result;

            n = val.length();
            result = 0;
            for( i = 0; i < n; i += 1 ) {
                result = (result << 4) + val[i];
                t = result & 0xF0000000;
                if( t ) {
                    result ^= (t >> 24);        /* OADL >> is unsigned */
                    result ^= t;
                }
            }
            n = result % hashSize;
            if( n < 0 ) n = -n;
            return n;
        }

    public proc
        insert( name, val )
        {
            var
                a, i, x, n;

            x = hash( name );   /* Find the bucket in the hash table */
            a = hashTab[x];     /* Get the entries in this bucket */
            n = a.length();    /* Number of entries, times 2 */

            /* Search the bucket for the given name. */
            for( i = 0; i < n; i += 2 ) {
                if( a[i] == name ) {
                    /* Overwrite old value with new value */
                    a[i+1] = val;
                    return;
                }
            }

            /* Extend the bucket with the new name/value pair. */
            hashTab[x] = a ## {name, val};
        }

    public proc
        lookup( name )
        {
            var
                a, i, x, n;

            x = hash( name );   /* Find the bucket in the hash table */
            a = hashTab[x];     /* Get the entries in this bucket */
            n = a.length();    /* Number of entries, times 2 */

            /* Search the bucket for the given name */
            for( i = 0; i < n; i += 2 ) {
                if( a[i] == name ) {
                    /* Found it!  Return the value. */
                    return a[i+1];
                }
            }

            /* If we get here, we couldn't find it.  Return failure. */
            return nil;
        }
} /* class hashClass */

proc main()
{
    var
        i, hash;

    hash = new hashClass(256);
    hash.insert( "fred", 1 );
    hash.insert( "foo", 2 );
    hash.insert( "bar", 3 );
    say( "fred = ", hash.lookup( "fred" ), "\n" );
    say( "foo  = ", hash.lookup( "foo"  ), "\n" );
    say( "bar  = ", hash.lookup( "bar"  ), "\n" );
    say( "fr   = ", hash.lookup( "fr"   ), "\n" );
}