#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * Implementation of HashSet<String>
 * Separate chaining hashing
 * Assume fixed table size 10007
 */

#define TABLE_SIZE 10007

struct HashNode
{
    char *key;
    struct HashNode *next;
};

struct HashSet
{
    struct HashNode * lists[ TABLE_SIZE ];
    int currentSize;
};

typedef struct HashSet HASH_SET;

unsigned int hash( const char *str )
{
    int i;
    unsigned int result = 0;

    for( i = 0; str[ i ] != '\0'; i++ )
        result = result * 31 + str[ i ];

    return result % TABLE_SIZE;
}

void hs_init( HASH_SET * hs )
{
    int i;

    hs->currentSize = 0;
    for( i = 0; i < TABLE_SIZE; i++ )
        hs->lists[ i ] = NULL;
}

int hs_contains( const HASH_SET * hs, const char *key )
{
    int listNum = hash( key );
    struct HashNode *ptr = hs->lists[ listNum ];

    while( ptr != NULL && strcmp( ptr->key, key ) != 0 )
        ptr = ptr->next;

    return ptr != NULL;
}

int hs_add( HASH_SET * hs, const char *key )
{
    struct HashNode *newNode;
    int listNum;

    if( hs_contains( hs, key ) )
        return 0;

    listNum = hash( key );


    newNode = (struct HashNode *) malloc( sizeof ( struct HashNode ) );
    if( newNode == NULL )
    {
        fprintf( stderr, "Error allocating node" );
        return 0;
    }

    newNode->key = strdup( key );
    newNode->next = hs->lists[ listNum ];
    hs->lists[ listNum ] = newNode;
    hs->currentSize++;

    return 1;
}

int hs_remove( HASH_SET * hs, const char *key )
{
    struct HashNode *curr;
    struct HashNode *prev = NULL;
    int listNum;

    if( !hs_contains( hs, key ) )
        return 0;

    listNum = hash( key );
    curr = hs->lists[ listNum ];
    while( strcmp( curr->key, key ) != 0 )
    {
        prev = curr;
        curr = curr->next;
    }

    if( prev == NULL ) // first item
        hs->lists[ listNum ] = curr->next;
    else      // middle of list
        prev->next = curr->next;

    // cleanup node curr
    free( curr->key );
    free( curr );

    hs->currentSize--;
    return 1;
}

int hs_size( const HASH_SET * hs )
{
    return hs->currentSize;
}

void hs_print( const HASH_SET * hs )
{
    int i;
    struct HashNode *ptr;

    for( i = 0; i < TABLE_SIZE; i++ )
        for( ptr = hs->lists[ i ]; ptr != NULL; ptr = ptr->next )
            printf( "%s\n", ptr->key );
}

int main( )
{
    HASH_SET hs;
    int i = 0;
    char buffer[ 10 ];

    hs_init( &hs );

    for( i = 0; i < 10000; i++ )
    {
        sprintf( buffer, "abc%d", i );
        hs_add( &hs, buffer );
    }

    printf( "Size is %d\n", hs_size( &hs ) );

    
    hs_add( &hs, "hello" );
    hs_add( &hs, "world" );

    for( i = 0; i < 10000; i++ )
    {
        sprintf( buffer, "abc%d", i );
        hs_remove( &hs, buffer );
    }

    printf( "Size is %d\n", hs_size( &hs ) );


    hs_print( &hs );

    printf( "Contains hello?: %d\n", hs_contains( &hs, "hello" ) );
    printf( "Contains world?: %d\n", hs_contains( &hs, "world" ) );
    printf( "Contains abc0?: %d\n", hs_contains( &hs, "abc0" ) );

    return 0;
}