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

#define MinTableSize (10)

typedef int ElementType;
typedef unsigned int Index;

struct ListNode;
typedef struct ListNode *Position;
struct HashTbl;
typedef struct HashTbl *HashTable;

struct ListNode
{
  ElementType Element;
  Position    Next;
};

typedef Position List;

/* List *TheList will be an array of lists, allocated later */
/* The lists use headers (for simplicity), */
/* though this wastes space */

struct HashTbl
{
  int TableSize;
  List *TheLists;
};

//---------------------------------
/* Hash function for ints */

Index
Hash( ElementType Key, int TableSize )
{
  return Key % TableSize;
}

//---------------------------------
HashTable
InitializeTable( int TableSize )
{
  HashTable T;
  int i;

  /* 1*/      if( TableSize < MinTableSize )
    {
  /* 2*/          printf( "Table size too small.\n" );
  /* 3*/          return NULL;
    }

  /* Allocate table */
  /* 4*/      T = malloc( sizeof( struct HashTbl ) );
  /* 5*/      if( T == NULL )
  /* 6*/          printf( "Out of space!!!\n" );

  /* 7*/      T->TableSize = TableSize ;

  /* Allocate array of lists */
  /* 8*/      T->TheLists = malloc( sizeof( List ) * T->TableSize );
  /* 9*/      if( T->TheLists == NULL )
  /*10*/          printf( "Out of space!!!\n" );

  /* Allocate list headers */
  /*11*/      for( i = 0; i < T->TableSize; i++ )
    {
  /*12*/          T->TheLists[ i ] = malloc( sizeof( struct ListNode ) );
  /*13*/          if( T->TheLists[ i ] == NULL )
  /*14*/              printf( "Out of space!!!\n" );
      else
  /*15*/              T->TheLists[ i ]->Next = NULL;
    }
  /*16*/      return T;
}
//---------------------------------------------------
Position
Chained_Hash_Search(HashTable T, ElementType Key)
{
  Position P;
  List L;

  /* 1*/      L = T->TheLists[ Hash( Key, T->TableSize ) ];
  /* 2*/      P = L->Next;
  /* 3*/      while( P != NULL && P->Element != Key )
  /* Probably need strcmp!! */
  /* 4*/          P = P->Next;
  /* 5*/      return P;
}
//---------------------------------------------------

void
Chained_Hash_Insert(HashTable T, ElementType Key)
{
  Position Pos, NewCell;
  List L;
      
  /* 1*/      Pos = Chained_Hash_Search( T, Key );
  /* 2*/      if( Pos == NULL )   /* Key is not found */
    {
  /* 3*/          NewCell = malloc( sizeof( struct ListNode ) );
  /* 4*/          if( NewCell == NULL )
  /* 5*/              printf( "Out of space!!!\n" );
	    else
	      {
  /* 6*/              L = T->TheLists[ Hash( Key, T->TableSize ) ];
  /* 7*/              NewCell->Next = L->Next;
  /* 8*/              NewCell->Element = Key;  /* Probably need strcpy! */
  /* 9*/              L->Next = NewCell;
	}
    }
}
//-----------------------------------------------------

ElementType
Retrieve( Position P )
{
  return P->Element;
}

//-----------------------------------------------------
void
Chained_Hash_Delete( HashTable T, ElementType Key )
{
  List L;
  Position P, PreP;

  L = T->TheLists[ Hash( Key, T->TableSize ) ];
  PreP=L; P = L->Next;
  while( P != NULL && P->Element != Key )
    {
      PreP=P;
      P = P->Next;
    }
  if ( P != NULL)
    {
      PreP->Next =P->Next; 
      free(P);
    }
}

//----------------------------------------------------
// Inspect the hash table.

void
DumpTable (HashTable T)
{ Position P;
  List L;
  int i;

  for( i = 0 ; i < T->TableSize; i++ )
    { L = T->TheLists[i ];
      P = L->Next;
      printf("%4d:", i);
      while( P != NULL )
	{ printf(" %4d  ", Retrieve(P));
	  P = P->Next;
	}
      printf("\n");
    }
}

//----------------------------------------------------
#define NumItems 100

main( )
{
  HashTable T;
  Position P;
  List L;
  int i;
  int CurrentSize;
  ElementType delkey;

  T = InitializeTable( CurrentSize = 13 );
  srand(time(0));
  for( i = 0; i < NumItems; i++ )
    Chained_Hash_Insert( T, rand() %100 );
  
  printf("Dump the hash table after insertions.\n");
  DumpTable (T); 
  printf("Type in the key to be deleted:\n");
  scanf("%d", &delkey);
  while ( delkey > 0)
    { Chained_Hash_Delete(T, delkey);
      DumpTable(T);
      printf("Type in the key to be deleted:\n");
      scanf("%d", &delkey);
    }
  printf( "End of program.\n" );
  return 0;
}