"use strict";

// skip list
// basic structure : insert, find

myMain();

function myMain() {
  var nLevels = 16;
  var nTrials = 20000;
  
  var SL = makeSkipList(nLevels);
  var levHits = [];
  for (var i=0; i<nLevels; i++) { levHits[i]=0; }
  for (var i=0; i<nTrials; i++) { levHits[SL.dice(nLevels)]++; }
  alert(levHits);
  //return;
  /*
  alert(SL.size());
  alert("3 in? "+SL.find(3));
  SL.insert(15);
  SL.insert(3);
  SL.insert(8);
  alert(SL.size());
  alert(SL.allOrder());
  return;
  */
  
  for (var k=120; k>0; k-=5) { SL.insert(k); }
  alert(SL.allOrder());
  alert("21 in list? "+SL.find(21));
  alert("55 in list? "+SL.find(55)); 
  alert("SL maxLev: "+ SL.maxlev);
  alert("SL numLev: "+ SL.numlev);

  return; 
}


function makeSkipList( maxLevels ) {  
  var genLevFuncs = { 
    // object containing various coin flipping functions
    // install one of these in the SL object below
    // they all generate integers from 0 up
    decisionTree: function(max) {
      var rLev;
      var rn = Math.floor(15*Math.random());
      if (rn>13) { rLev = 3; }
      else if (rn>11) { rLev = 2; }
      else if (rn>7)  { rLev = 1; }
      else { rLev=0; }
      return rLev;
    }, 
    bitString: function(max) {
      // gen random num
      // start at left, count 1 bits until you hit a 0 bit
    },   
    flipRepeater: function(max) {
      // returns integer 0 to max-1
      while (true) {
        var rLev=0;
        while (Math.random()>0.5) { rLev++; }
        if (rLev<max) return rLev;
      }
    },
  };
  
  var SL = {
    maxlev: maxLevels,  
    numlev: 0,         // 1 or more for non-empty list
    nelts: 0,    
    head: makeSLCell(maxLevels,null), // start sentinel
    tail: makeSLCell(maxLevels,null), // end sentinel
   
    dice: genLevFuncs.flipRepeater,  // install one of the random funcs here
    
    size: function() { return this.nelts; },
    
    find: function(key) { // return true if its found, false if its not found
      var curcel=this.head;
      for (var i=this.numlev-1; i>=0; i--) {
        for ( /* */; curcel.next[i]!=null; curcel=curcel.next[i]) {
          if (curcel.next[i].val > key) break;
          if (curcel.next[i].val===key) return true;
        }
      }
      return false;      
    },
  
    insert: function(key) { 
      // always inserts, allows duplicates
      var newlev=this.dice(this.maxlev-1); 
      //alert("new lev: "+newlev);
      if (newlev>this.numlev) { 
        this.numlev=newlev;
        //this.numlev++;
        newlev=this.numlev; 
        alert("new newlev: "+newlev);
      }
      
      
      var curcel=this.head;      
      var node = makeSLCell(newlev+1, key);

      for (var i=this.numlev; i>=0; i--) {
         for ( /* */; curcel.next[i]!=null; curcel=curcel.next[i]) {
            if (curcel.next[i].val > key) break;
         }
         if (i<=newlev) { 
           node.next[i]=curcel.next[i]; 
           curcel.next[i] = node; 
         }
      } 
      this.nelts++;
    },
    
    allOrder: function() {
      // scoot along the 0 level
      var elts = [];
      var node = this.head.next[0];
      for (var i=0; i<this.nelts; i++) {
        elts[i] = node.val;  
        //alert("AO: "+elts[i]+"("+node.levs+")");
        node = node.next[0];    
      }
      return elts;
    },
    
  };
  
  // set up front and back sentinels and link them down the pile
  for (var i=0; i<SL.maxlevs; i++) { SL.head.next[i] = SL.tail; }
  
  return SL;
}


function makeSLCell ( nlevs, value ) {
  // cell is made with nlevs levels and given val of value
  // nlevs is integer 1 or larger
  var cel = {
    val: value,
    levs: nlevs,
    next: [],
  };
  for (var i=0; i<nlevs; i++) { cel.next[i] = null; }  // fill array of ptr

  return cel;
}