/**
 * HashCount, by David Greenspan. Reads words from the text file $1
 * and prints out the top 25 most frequent words using a hashing
 * algorithm.
 */

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

#define MAX_WORD_LENGTH 31
#define INPUT_BUFFER_SIZE 1024
#define LETTER_DATA_SIZE (1024*1024)
#define NUM_HASH_BINS 0x00010000
#define HASH_MASK 0x0000FFFF
#define HASH_X 179424673 // the 10-millionth prime number

#define NUM_TOP_WORDS 25

char _letters[LETTER_DATA_SIZE];
int _numLetters = 0;

char *_hashBins[NUM_HASH_BINS];
int _hashBinCounts[NUM_HASH_BINS];

int _topWords[NUM_TOP_WORDS];
int _curTopWords = 0;
int _lowestTopWordCount = 0;

void printTopWords() {
  int i;
  for(i=0;i<_curTopWords;i++) {
    int w = _topWords[i];
    printf("%d %s\n", _hashBinCounts[w], _hashBins[w]);
  }
}

void registerTopWord(int w) {
  int newCount = _hashBinCounts[w];
  int insertionPos = _curTopWords;
  int pos;
  
  if (newCount <= _lowestTopWordCount) {
    return;
  }
  
  pos = _curTopWords-1;
  
  while (pos >= 0) {
    int tw = _topWords[pos];
    int count = _hashBinCounts[tw];
    if (count > newCount) {
      break;
    }
    else {
      insertionPos = pos;
    }
    pos--;
  }
  
  if (_curTopWords < NUM_TOP_WORDS) {
    _curTopWords++;
  }
  
  pos = _curTopWords-1;
  while (pos > 0) {
    if (pos == insertionPos) {
      break;
    }
    pos--;
    _topWords[pos+1] = _topWords[pos];
  }
  
  _topWords[insertionPos] = w;
  
  if (_curTopWords == NUM_TOP_WORDS) {
    _lowestTopWordCount = _hashBinCounts[_topWords[NUM_TOP_WORDS-1]];
  }

}  

void registerAll() {
  int i;
  for(i=0;i<NUM_HASH_BINS;i++) {
    if (_hashBins[i] != NULL) {
      registerTopWord(i);
    }
  }
}

char * allocateString(char *str) {
  char *src = str;
  char *dst = &_letters[_numLetters];
  char *result = dst;
  int newLetters = 0;
  do {
    *dst = *src;
    dst++;
    newLetters++;
  } while ((*(src++)) != 0);
  _numLetters += newLetters;
  return result;
}

int hash(char *str) {
  char *c = str;
  int value = 1;
  while ((*c) != 0) {
    value = value*HASH_X + *(c++);
  }
  return value & HASH_MASK;
}

int stringCompare(char *str1, char *str2) {
  char *a = str1;
  char *b = str2;
  do {
    if (*a != *b) return 1;
    a++;
    b++;
  } while (!(((*(a-1)) == 0) || ((*(b-1)) == 0)));
  return 0;
}

/*void dumpLetters() {
  int i;
  for(i=0;i<_numLetters;i++) {
    char c = _letters[i];
    if (c == '\0') printf("~");
    else printf("%c", c);
  }
  printf("\n");
  }*/

void newWord(char *word) {
  int bin = hash(word);
  while (_hashBins[bin] != NULL && stringCompare(word, _hashBins[bin]) != 0) {
    bin = (bin+1) & HASH_MASK;
  }
  if (_hashBins[bin] == NULL) {
    _hashBins[bin] = allocateString(word);
  }
  _hashBinCounts[bin]++;
}

int main(int argc, char *argv[]) {

  FILE *inFile;
  char inBuffer[INPUT_BUFFER_SIZE];
  int charsRead;
  char wordBuffer[MAX_WORD_LENGTH+1];
  int wordLength;
  
  bzero(_hashBins, sizeof(_hashBins));
  bzero(_hashBinCounts, sizeof(_hashBinCounts));

  if (argc < 2) {
    fprintf(stderr, "No input file specified.\n");
    return 1;
  }
  
  inFile = fopen(argv[1], "r");
  
  if (inFile == NULL) {
    fprintf(stderr, "Could not open file %s.", argv[1]);
    return 1;
  }
  
  wordLength = 0;
  while ((charsRead = fread(inBuffer, 1, INPUT_BUFFER_SIZE, inFile)) > 0) {
    int i;
    for(i=0;i<charsRead;i++) {
      char c = inBuffer[i];
      if (c >= 'a' && c <= 'z') {
        wordBuffer[wordLength++] = c;
      }
      else if (c >= 'A' && c <= 'Z') {
        wordBuffer[wordLength++] = c + 'a' - 'A';
      }
      else {
        if (wordLength > 0) {
          wordBuffer[wordLength] = '\0';
          newWord(wordBuffer);
          wordLength = 0;
        }
      }
    }
  }

  registerAll();
  printTopWords();

  return 0;
}