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

/*
 * Implementation of HashSet<String>
 * Separate chaining hashing
 */

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

struct HashSet
{
    struct HashNode ** lists;
    int currentSize;
    int tableSize;
};

typedef struct HashSet HASH_SET;

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

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

    return result % tableSize;
}

void hs_init( HASH_SET * hs, int tableSize )
{
    int i;

    hs->currentSize = 0;
    hs->tableSize = tableSize;
    
    hs->lists = (struct HashNode **) malloc( tableSize * sizeof( struct HashNode * ) );
    
    for( i = 0; i < hs->tableSize; i++ )
        hs->lists[ i ] = NULL;
}

void hs_dispose0( struct HashNode **lists, int tableSize )
{
    int i;
    struct HashNode *ptr, *tmp;
    
    for( i = 0; i < tableSize; i++ )
    {
        for( ptr = lists[ i ]; ptr != NULL; ptr = tmp )
        {
            tmp = ptr->next;
            free( ptr->key );
            free( ptr );
        }
    }

    free( lists );
}

void hs_dispose( HASH_SET * hs )
{
    hs_dispose0( hs->lists, hs->tableSize );
}

HASH_SET * newHashSet( int tableSize )
{
    HASH_SET *hs = (HASH_SET *) malloc( sizeof( HASH_SET ) );
    hs_init( hs, tableSize );
    return hs;
}

void deleteHashSet( HASH_SET * hs )
{
    hs_dispose( hs );
    free( hs );
}

int isPrime( int N )
{
    int i;
    
    for( i = 3; i * i <= N; i += 2 )
        if( N % i == 0 )
            return 0;
    
    return 1;
}

int nextPrime( int N )
{
    if( N % 2 == 0 )
        N++;
    
    while( !isPrime( N ) )
        N += 2;
    
    return N;
}

void hs_rehash( HASH_SET * hs )
{
    int i;
    int oldTableSize = hs->tableSize;
    struct HashNode **oldLists = hs->lists;
    struct HashNode *ptr;
    
    hs_init( hs, nextPrime( oldTableSize * 2 + 1 ) );
    
    for( i = 0; i < oldTableSize; i++ )
        for( ptr = oldLists[ i ]; ptr != NULL; ptr = ptr->next )
        {
            hs_add0( hs, ptr->key, 0 );
            ptr->key = NULL;
        }
    
    hs_dispose0( oldLists, oldTableSize );
}


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

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

    return ptr != NULL;
}


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

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

    if( hs->currentSize == hs->tableSize )
        hs_rehash( hs );
    
    listNum = hash( key, hs->tableSize );

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

    if( makeDup )
        newNode->key = strdup( key );
    else
        newNode->key = (char *) key;
    
    newNode->next = hs->lists[ listNum ];
    hs->lists[ listNum ] = newNode;
    hs->currentSize++;

    return 1;
}


int hs_add( HASH_SET * hs, const char *key  )
{
    return hs_add0( hs, key, 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, hs->tableSize );
    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 < hs->tableSize; i++ )
        for( ptr = hs->lists[ i ]; ptr != NULL; ptr = ptr->next )
            printf( "%s\n", ptr->key );
}

int main( )
{
    int N = 1000000;
    HASH_SET *hs = newHashSet( 17 );
    int i = 0;
    char buffer[ 10 ];

    for( i = 0; i < N; 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 < N; 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" ) );

    deleteHashSet( hs );
    
    return 0;
}