//
//sort the text by word using hash table
//
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define HASHSIZE 1000
#define LISTSIZE 10000

struct word
{
  char str[30];
  int count;
  struct word *next;
};

int wordsum=0;
struct word words[100000];
struct word *ptwords[100000];
struct word *hashtable[HASHSIZE];


main()
{
 FILE *f;
 int i=0;
 int j=0;
 int tmpvalue;
 char *str;
 char key;
 char tmpword[100];
 struct word *tmp;

 if ((f = fopen("bbe.txt","r"))==NULL)
    {
      puts("unable to open file");
      return 0;
    } 
 while(!feof(f))
   {
     key=fgetc(f);
     if (((key>=65)&&(key<=90))||((key>=97)&&(key<=122)))
       {
	 tmpword[i]=tolower(key);
	 i++;
       }
     else
       {
	 tmpword[i]='\0';
	 i=0;
	 if(!hashtable[hash(tmpword)])
	   {
	     strcpy(words[wordsum].str,tmpword);
	     words[wordsum].count=1;
	     words[wordsum].next=0;
	     ptwords[wordsum]=&words[wordsum];
	     hashtable[hash(tmpword)]=&words[wordsum];
	     wordsum++;
	   }
	 else
	   {
	     addtohashtable(tmpword,hashtable[hash(tmpword)]);
	     
	   }
       }
     }

 for (i=0;i<wordsum;i++)
     for(j=i;j<wordsum;j++)
     {
       if(ptwords[i]->count>ptwords[j]->count)
	 {
	   tmp=ptwords[i];
	   ptwords[i]=ptwords[j];
	   ptwords[j]=tmp;
	 }
     }
 fclose(f); 

 printword(ptwords);

 for (i=0;i<HASHSIZE;i++)
   {
     if(hashtable[i])
       {
	 printf("hashtable[%d]",i);
	 printchain(hashtable[i]);
       }
   }   

}

int printchain(struct word *p)
{
  printf("->%s:%d",p->str,p->count);
  if (p->next)
    printchain(p->next);
  else
    printf("\n");
  return 0;
}

int printword(struct word *x[])
{
  int i;
  for(i=0;i<wordsum;i++)
      printf("%s,%d\n",x[i]->str,x[i]->count);
  return 0;
}

int addtohashtable(char *wrd, struct word *p)
  {  
    //printf("I'm in addto; ");
     if (!strcmp(wrd,p->str))
     {
       p->count++;
       // printf("count(%s)=%d\n",p->str,p->count);
       return 0;
     }
     if (!p->next)
      {
	strcpy(words[wordsum].str, wrd);
	words[wordsum].count = 1;
	words[wordsum].next=0;
        ptwords[wordsum]=&words[wordsum];
	p->next = &words[wordsum];
	wordsum++;
	return 0;
      }
     addtohashtable(wrd, p->next);
  }



int hash(unsigned char *str)
{
  int hash=0;
  int c;
  while (c=*str++)
    hash+=c;
  return hash%HASHSIZE;
}