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

#define numOfChars ('z' - 'a' + 1) //Capitol letters are not used.

unsigned int hashFunction(char* key, int keyLength, int numOfHashcodes) {
  /* This simple hash function uses the bytes in the key as a number in base 256.*/
  unsigned int hash = 0;

  for (int i=0; i<keyLength; i++) {
    hash = (hash << 5 ^ key[i]) ^ hash; // % is used to avoid loosing early bytes.
  }

  return hash % numOfHashcodes;
}

/*
  Test the hash function by generating keys that contain all possible strings of the
  specified length.
  command line argument one is the number of characters in the keys.
  command line argument two is the number of different hashcodes allowed.
*/

main(int argn, char** args) {
  int keyLength = atoi(args[1]);
  int numOfHashcodes = atoi(args[2]);

  int hashcodes[numOfHashcodes];
  memset(hashcodes, 0, sizeof(int)*numOfHashcodes);

  char* key = (char *)malloc( sizeof(char) * keyLength );
  memset(key, 'a', keyLength);
  
  // These loops generate all the different keys.
  int currentIteration = 0;
  long numOfKeys = (long)pow(numOfChars, keyLength);
  for (long i=0; i<numOfKeys; i++) {
    currentIteration++;
    for(int j=0; j<keyLength; j++) {
      key[j] = 'a' + (int)(currentIteration / pow(numOfChars, j)) % numOfChars;
      //printf("%c ", key[j]);
    }
    //printf("\n");
    // Count how many times each hashcode is genereated.
    hashcodes[hashFunction(key, keyLength, numOfHashcodes)]++;
  }

  //Calculate and print some statistics about the hashcodes.
  int numOfCollisions = 0;
  int numOfNonUsedHashcodes = 0;
  int mostUsedHashcode = 0;
  int leastUsedHashcode = 0;
  for (int i=0; i<numOfHashcodes; i++) {
    if (hashcodes[i] > hashcodes[mostUsedHashcode]) {
      mostUsedHashcode = i;
    }
    if (hashcodes[i] < hashcodes[leastUsedHashcode]) {
      leastUsedHashcode = i;
    }
    numOfCollisions += hashcodes[i] == 0 ? 0 : hashcodes[i] - 1;
    if (hashcodes[i] == 0) {
      numOfNonUsedHashcodes++;
    }
  }

  printf("There were %i hashCodes\n", numOfHashcodes);
  printf("There were %i different keys\n", numOfKeys);
  printf("There were %i unused hashcodes\n", numOfNonUsedHashcodes);
  printf("There were %i collisions, number of keys - number of hash codes = %i\n", 
	 numOfCollisions, numOfKeys - numOfHashcodes);
  printf("Max %i keys got the same hashCode, number of keys / number of hashcodes = %i\n", 
	 hashcodes[mostUsedHashcode], (int)(numOfKeys / numOfHashcodes));
  printf("Min %i keys got the same hashCode, number of keys / number of hashcodes = %i\n", 
	 hashcodes[leastUsedHashcode], (int)(numOfKeys / numOfHashcodes));

}