#include <string>
#include <iostream>
#include <fstream>
#include <strings.h>
#include <cmath>

using namespace std;

double factorial(int n)
{ double f = 1;
  for (int i = 1; i <= n; i += 1)
    f *= i;
  return f; }

class hashtable
{ struct entry
  { string word;
    int count;
    entry * next;
    entry(string s, int c, entry * n); };

  int size, uniques;
  entry * * table;

  public:
    hashtable(int sz);
    unsigned int hash(string s);
    void add(string s);
    void inspect();
};

hashtable::hashtable(int sz)
{ size = sz;
  uniques = 0;
  table = new entry * [size];
  for (int i = 0; i < size; i += 1)
    table[i] = NULL; }

unsigned int hashtable::hash(string s)
{ unsigned int h = 371691;
  for (int i = 0; i < s.length(); i += 1)
    h = h * 69 + s[i];
  return h % size; }

void hashtable::add(string s)
{ int h = hash(s);
  entry * e = table[h];
  while (e != NULL)
  { if (e->word == s)
    { e->count += 1;
      return; }
    e = e->next; }
  table[h] = new entry(s, 1, table[h]);
  uniques += 1; }

void hashtable::inspect()
{ cout << "uniques = " << uniques << "\n";
  double lambda = (double)uniques / size;
  cout << "fullness = " << (double)uniques / size << "\n";
  int length;
  int counts[15];
  bzero(counts, sizeof(counts));
  for (int i = 0; i < size; i += 1)
  { length = 0;
    entry * e = table[i];
    while (e != NULL)
    { length += 1;
      e = e->next; } 
    if (length >= 14)
      counts[14] += 1;
    else
      counts[length] += 1; }
  for (int i = 0; i< 15; i += 1)
  { double ideal = exp(-lambda) * pow(lambda, i) / factorial(i) * size;
    cout << "length = " << i << " appears " << counts[i] << " times, " <<
            " ideal = " << ideal << "\n"; } }

hashtable::entry::entry(string s, int c, hashtable::entry * n)
{ word = s;
  count = c;
  next = n; }

int main(int argc, char * argv[])
{ 
  if (argc != 2)
  { cout << "Tell me the table size\n";
    exit(1); }
  int tabsize = atoi(argv[1]);

  ifstream in("/home/www/text/barrie/peterpan");
  if (in.fail())
  { cout << "Can't open it\n";
    exit(1); }

  hashtable HT(tabsize);

  while (true)
  { string word;
    in >> word;
    if (in.fail())
      break;
    HT.add(word); }

  HT.inspect();
  in.close();
}