"use strict";
/*
*  compare build to N-insert
*  
*  generate one data array
*  use that same array for build and N-insert
*  time each, compare
*  
*/
myMain();

var heapNinsertTime ;
var heapBuildTime;

function myMain() {
  var nums;
  var st, et, sortedNums;
  
  var N=32000000, MAX=900000000;  // for bubblesort use small... 100000

  /*==============================================================
  || 
  ||   1) select random data vs. ordered (bad, worst case) data
  */
  //==============================================================
  
  
  alert("gen ordered data: "+N+ " elts"); nums=genOrderedElts(N); 
  //alert("gen random data: "+N+" elts"); nums=genRandomElts(N,MAX); 
 
  // do heap construction demos, then end
  alert(N+" elts, Heap Build demo... ");
  //alert(nums);
  sortedNums = heapBuild(nums); 
  alert(N+" elts, Heap N-inserts demo... ");
  //alert(nums);
  sortedNums = heapNinsert(nums); 

  // report compare results
  alert("build: "+heapBuildTime+", N-inserts: "+heapNinsertTime);
}

function heapBuild(vals) {
  //alert("doing magic build");
  var hh = makeNewHeap();
  var st = (new Date()).getTime();
  hh.build(vals);
  var et = (new Date()).getTime();
  heapBuildTime = et-st;
  return;
}

function heapNinsert(vals) {
  //alert("doing N inserts");
  var hh = makeNewHeap();  
  var st = (new Date()).getTime();
  for (var i=0; i<vals.length; i++) { hh.insert(vals[i]); }
  var et = (new Date()).getTime();
  heapNinsertTime = et-st;
  return;
}

function makeNewHeap() {
  // constructor for a min heap
  var heap = {
    elts: [-Infinity],  // load bignum into elt 0, slot 0 not used
    root:1,             // slot 1 is always root
    last:0,             // slot last always holds last val used in array elts
    
    size:   function ( ) { return this.last; }, // num vals stored
    
    getMin: function ( ) { 
      if (this.size()===0) return NaN;
      return this.elts[this.root]; 
    },
    
    build: function(arr) {
      for (var i=0; i<arr.length; i++) {
        // load heap array from input data
        // this maintains heap structure property   
        this.elts[i+1] = arr[i]; 
      }
      this.last = i;  
      
      // now start with parent of last element
      // bubble it down to where you find heap order
      // go back one node towards root and repeat until root
      var sn = this.PN(this.last); // parent of last element
      for (var k=sn; k>0; k--) {
        // bubble down, like in delete
        var temp, done=false;
        var n=k, c=0;
        while(!done) { 
          if (this.isLeaf(n)) { done=true; }
          else {
            if (this.hasOnlyLC(n)) { c = this.LC(n); } 
            else { c = (this.LCV(n) < this.RCV(n)) ? this.LC(n) : this.RC(n) ; }
            if (this.elts[n]>this.elts[c]) {
              temp=this.elts[n]; this.elts[n]=this.elts[c]; this.elts[c]=temp;
              n = c;
            } 
            else { done=true; }
    } } } }, 
       
    insert: function (val) {
      this.last++;
      this.elts[this.last] = val;
      var n=this.last;
      var p=this.PN(n);
      var temp;
      while ( (p!==0) && (val<this.elts[p]) ) {
        // swap elt in n with elt in p
        temp=this.elts[n];  this.elts[n]=this.elts[p];  this.elts[p]=temp;
        n = p;
        p = this.PN(n);
      }
    },
   
    delMin: function () { 
      if (this.size()===0) return;
      if (this.size()===1) {
        this.elts[this.root]=null; this.last--; this.elts.length--;
        return;
      }
      this.elts[this.root] = this.elts[this.last];
      this.elts[this.last]=null; 
      this.last--;
      this.elts.length--;
      // bubble down from root
      var temp, done=false;
      var n=this.root, c=0;
      while(!done) { 
        if (this.isLeaf(n)) { done=true; }
        else {
          if (this.hasOnlyLC(n)) { c = this.LC(n); } 
          else { c = (this.LCV(n) < this.RCV(n)) ? this.LC(n) : this.RC(n) ; }
          if (this.elts[n]>this.elts[c]) {
            temp=this.elts[c]; this.elts[c]=this.elts[n]; this.elts[n]=temp;
            n = c;
          } 
          else { done=true; }
    } } },
    
    LC:     function (n) { return 2*n;             }, // slot num
    RC:     function (n) { return (2*n)+1;         }, // slot num
    PN:     function (n) { return Math.floor(n/2); }, // slot num
    LCV:    function (n) { return this.elts[this.LC(n)]; },  // element val
    RCV:    function (n) { return this.elts[this.RC(n)]; },  // element val
    PNV:    function (n) { return this.elts[this.PN(n)]; },  // element val   
    isLeaf:    function (n) { return ( this.LC(n)>this.last && this.RC(n)>this.last ); },
    hasOnlyLC: function (n) { return ( this.RC(n)>this.last && this.LC(n)<=this.last ); },  
    print:  function ( ) { alert("heap elts: "+ this.elts.slice(1)); },
  }
  return heap;    
}

//==================================================================================
//
// bubble sort
//
//==================================================================================

function bubbleUp ( vals ) {
  var temp;
  for (var i=0; i<vals.length-1; i++) {
    if (vals[i]>vals[i+1]) { temp=vals[i]; vals[i]=vals[i+1]; vals[i+1]=temp; }
  }
  return vals;
}

function bubbleSort ( vals ) {
  for (var i=0; i<vals.length-1; i++) { vals = bubbleUp(vals); }
  return vals;
}

//-----------------------------------------------------------------------
// random 
//-----------------------------------------------------------------------

function genOrderedElts(N) {
  var arr=[];
  for (var i=0; i<N; i++) {
    arr[i] = N-(i+1); // gens big down to small
  }
  return arr;
}


function genRandomElts(N,MAX) {
  var arr=[];
  for (var i=0; i<N; i++) { arr[i] = genNumber(MAX); }
  return arr;
}

function genNumber(MAX) { return Math.floor(Math.random()*MAX); }

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

  function ranAlpha() {
    var chars = "abcdefghijklmnopqurstuvwxyzABCDEFGHIJKLMNOPQURSTUVWXYZ";
    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);
  }
}