"use strict";
var tab = window.open();  

myMain();
//
// hash function demo
// collects hash hits and graphs collision deistributions
//
// does not implement other hash table operations
//
function myMain() {
  var TABMAX = 191; // some primes 79 97 113 199 397 977 1987 4999 10007
  var ht = makeHashTab(TABMAX);
  
  var nElts = 700;
  var dist = collectHashes(nElts,ht);
  graphDist(dist);
  
  tab.document.close();
}

function makeHashTab( N ) { // constructor for hash table
  var hashes = { 
    // object containing various hash functions to test
    // install one of these in the hash table object below
    alphaFirst: function(key,max) {
      // hash for string keys
      // this returns 0 - 25 position in alphabet of first character
      //var factor = 299;
      var factor = 1;
      var hval=0;
      hval = factor * (key[0].charCodeAt() - "a".charCodeAt() )  ;
      hval %= max;
      if (hval<0) hval += max;
      return hval;
    },    
    alpha137: function(key,max) {
      // hash for string keys
      // this combines first, third, 7th characters
      // assuming the key is at least 7 characters long
      var factor = 1;
      var hval=0;
      hval = (key[0].charCodeAt() - "a".charCodeAt() )  ;
      hval += (key[2].charCodeAt() - "a".charCodeAt() )  ;
      hval += (key[7].charCodeAt() - "a".charCodeAt() )  ;
      hval *= factor;
      hval %= max;
      if (hval<0) hval += max;
      return hval;
    },
    alpha137Scaled: function(key,max) {
      // hash for string keys
      // this combines first, third, 7th characters
      // assuming the key is at least 7 characters long
      var factor = 47;
      var hval=0;
      hval = 43* (key[0].charCodeAt() - "a".charCodeAt() )  ;
      hval += 113 *(key[2].charCodeAt() - "a".charCodeAt() )  ;
      hval += 10007 * (key[7].charCodeAt() - "a".charCodeAt() )  ;
      hval *= factor;
      hval %= max;
      if (hval<0) hval += max;
      return hval;
    },
    prettyGoodString: function(key,max) {
      // hash for string keys
      // similar to the one used in Java
      var hval=0;
      for (var i=0; i<key.length; i++) {
        hval = 31*hval + key[i].charCodeAt();
      }
      hval %= max;
      if (hval<0) hval += max;
      return hval;
    },  
  };
  
  var htobj = {
    table: [],
    max: N,
    nelts: 0,

    size: function() { return this.nelts; },
    lambda: function() { return this.nelts/this.max; },
    
    hash: hashes.alpha137, // install a function from hashes object
 
    insert: function( v ) { return false; }, 
    remove: function( v ) { return false; },
    find: function( v ) { return false; },
  };
  
  // init table to all nulls
  for (var i=0; i<htobj.max; i++) { htobj.table[i] = null; }

  return htobj; 
}

//---- utility functions --------------------------------------------------

function collectHashes(nwords,htab) {
  var arr=[];
  for (var i=0; i<htab.max; i++) { arr[i]=0; }
  for (var i=0; i<nwords; i++) { arr[htab.hash(genString(10),htab.max)]++; }
  return arr;
}

function graphDist(vals) {
  tab.document.writeln("<pre><br/>");
  for (var k=0; k<vals.length; k++) {
    tab.document.write("[hash "+k+"]("+vals[k]+")");
    for (var i=0; i<vals[k]; i++) { tab.document.write("*"); }
    tab.document.writeln();
  }
  tab.document.writeln("</pre><br/>");
}

function genString(size){
  if (size===0) { return ranAlpha(); }
  else {  
    var str = "";
    for (var i=0; i<size; i++) { str += ranAlpha(); }
    return str;
  }

  function ranAlpha() {
    var chars = "abcdefghijklmnopqurstuvwxyz";
    return chars.substr( Math.floor(Math.random() * chars.length), 1);
  }
  
  function ranChar() {
    var chars = "0123456789abcdefghijklmnopqurstuvwxyz";
    return chars.substr( Math.floor(Math.random() * chars.length), 1);
  }
}