"use strict";

var tab = window.open();

myMain();
//
// hashing with probing demo
// allows table resizing to prime sizes
//
function myMain() {

  var TABMAX = 29;; 
  var ht = makeHashTab(TABMAX);
  
  var inp, val, num;
  
  while(true) {
    inp = prompt("comm (n,i,r,f,s,l,m,x,w,p,q) ?");
    switch(inp) {
      case "q": return; break; 
      case "n": ht = makeHashTab( Number(prompt("table size?")) ); 
                break;
      case "i": val = prompt("val?"); alert(ht.insert(val));  break;
      case "r": alert("no remove implemented"); break;
      case "f": val = prompt("val?"); alert(ht.find(val)); break;
      case "s": alert(ht.size()); break;
      case "m": alert(ht.tabMax()); break;
      case "l": alert(ht.lambda()); break;
      case "p": ht.print(); break;
      case "w": num = Number(prompt("add how many keys?"));
                for (var i=0; i<num; i++) {
                  ht.insert(genString(7));
                }
                break;
      case "x": alert(ht.extend());
                break;
      default:  alert("not a command"); break;
    } 
  }
  
  tab.close();
  return;
}

function makeHashTab( numSlots ) { // constructor for a 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 = 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: numSlots,
    nelts: 0,
    
    primes: [29,61,131,269,599,1213,2447,5051,10111,20507,41177,83773],    
    //primes: [29,61],
    resizes:0,
    
    size: function() { return this.nelts; },
    tabMax: function() { return this.max; },
    lambda: function() { return this.nelts/this.max; },

    hash: hashes.prettyGoodString, // install a function from hashes  
    
    insert: function( v ) {
      var hv = this.hash(v,this.max);
      if (this.table[hv] === null) { // no collision, 
        this.table[hv] = v;  // not a list
        this.nelts++;
        return true;
      }
      else { // collision... need to probe for a free spot
        var tries=1;
        var pv = hv;
        while (this.table[pv] !== null) {
          if (this.table[pv]===v) { return false; } // v is already in
          pv = hv + this.probe(tries++);
          if (pv >= this.max) { pv = pv % this.max; }
          if (tries > this.max) { return false; }  // table is full
        }
        this.table[pv] = v;
        this.nelts++;
        return true;
      }
    },
           
    probe: function ( i ) {
      //return i;  // skip by ones
      return i*i;  // skip by square
    },
    
    remove: function( v ) {
      // not really working... has no markers in table
      var hv = this.hash(v,this.max);
      var pv = hv;
      var tries = 1;
      while (this.table[pv] !== v) {
        if (this.table[pv]===null) { return false; }
        pv = hv + this.probe(tries++);
        if (pv >= this.max) { pv =  pv % this.max; }
        if (tries > this.max) { return false; } // its not there 
      }
      this.table[pv] = null;
      this.nelts--;
      return true;     
    },
  
    find: function( v ) {
      var hv = this.hash(v,this.max);
      var pv = hv;
      var tries = 1;
      if (this.table[pv]===null) { return false; }
      if (this.table[pv]===v) { return true; }
      while (this.table[pv] !== v) {
        pv = hv + this.probe(tries++);
        if (pv >= this.max) { pv =  pv % this.max; }
        if (tries > this.max) { return false; } // its not there 
      }
      return true;   
    },
    
    extend: function() {
      // initial: double table size
      // better is to find a prime beyond double
      if (this.resizes===(this.primes.length-1)) return false;
      var oldMax = this.max;
      var oldTab = this.table;
      this.resizes++;
      this.max = this.primes[this.resizes]; 
      // make and null out new table
      this.table = [];
      this.nelts = 0;
      for (var i=0; i<this.max; i++) { this.table[i] = null; }
      // go through old table and rehash all keys there into new table
      for (var k=0; k<oldMax; k++) {
        if (oldTab[k]!==null) {
          alert("rehash "+oldTab[k]);
          this.insert(oldTab[k],this.max);
        }
      }
      return true;
    },
    
    print: function() {
      var str="";
      for (var i=0; i<htobj.max; i++) {
        str += i+": "+this.table[i];
        if (this.table[i]!==null) str += "("+this.hash(this.table[i],this.max)+")";
        str += "\n";
      }
      alert(str);
    },
    
  }
  
  for (var i=0; i<htobj.max; i++) { htobj.table[i] = null; }

  return htobj;   
}

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

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 = "0123456789abcdefghijklmnopqurstuvwxyzABCDEFGHIJKLMNOPQURSTUVWXYZ";
    return chars.substr( Math.floor(Math.random() * chars.length), 1);
  }
}