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

myMain();
//
// hashing with chaining demo
// chains (lists) are implemented with arrays
//
function myMain() {
  var TABMAX = 40; 
  var ht = makeHashTab(TABMAX);
  
  var inp, val, num;
  while(true) {
    inp = prompt("comm (n,i,r,f,s,l,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": val = prompt("val?"); alert(ht.remove(val)); break;
      case "f": val = prompt("val?"); alert(ht.find(val)); break;
      case "s": alert(ht.size()); break;
      case "x": alert(ht.tabMax()); break;
      case "l": alert(ht.lambda()); break;
      case "p": ht.print(); break;
      case "w": ht = ranLoad(ht,Number(prompt("how many?")),7); break;
      default:  alert("not a command"); break;
    } 
  }
  tab.document.close();
  return;
  
  function ranLoad(htab,nwords,wsize) {
    for (var i=0; i<nwords; i++) {
      htab.insert(genString(wsize));
    }
    return htab;
  }
}

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 = 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; },
    tabMax: function() { return this.max; },
    lambda: function() { return this.nelts/this.max; },

    hash: hashes.alphaFirst, // install a function from hashes
 
    insert: function( v ) { 
      var hv = this.hash(v,this.max); // hash the key
      var lst = this.table[hv]; // grab the chain
      if (lst===null) { // no list, so no collision
        this.table[hv] = [v]; // make new list
        this.nelts++;
        return true;
      }
      else { // list is there, so collision... 
        //check to see if key is in list
        for (var i=0; i<lst.length; i++) {
          if (lst[i]===v) { // key in list, dupe so dont add
            return false; 
          }
        }
        // key not in list, so add it at the end
        lst[i]=v;
        this.nelts++;
        return true;    
      }
    },
    
    remove: function( v ) { 
      var hv = this.hash(v,this.max);
      var lst = this.table[hv];
      if (lst!==null) {
        if (lst.length===1) { // single item
          if (lst[0]!==v) return false;
          // v is the single item, null out the list
          this.table[hv] = null;
          this.nelts--;
          return true;
        }
        else { // 2 or more items in list
          for (var i=0; i<lst.length; i++) {
            if (lst[i]===v) { // found it
              for (var k=i+1; k<lst.length; k++) { lst[k-1] = lst[k]; }
              this.nelts--; lst.length--;
              return true;
            }
          } // for  
        } // else
      }
      return false;
    },
    
    find: function( v ) {
      var lst = this.table[this.hash(v,this.max)];
      if (lst!==null) {
        for (var i=0; i<lst.length; i++) {
          if (lst[i]===v) return true;
        }
      }
      return false;
    },
    
    print: function () {
      var lst = null;
      var str = "";
      for (var k=0; k<this.max; k++) {
        str +=  k + ": ";
        lst = this.table[k];
        if (lst!==null) {
          str += "("+lst.length+") ";
          for (var i=0; i<lst.length; i++) {str += lst[i]+", ";}
        }
        str += "<>\n";
      }
      alert(str);
    },
    
  };
  
  // init table to all nulls
  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 = "0123456789abcdefghijklmnopqurstuvwxyz";
    return chars.substr( Math.floor(Math.random() * chars.length), 1);
  }
}