"use strict";
/*
*  compare heap sort with build to heap sort with sequence of inserts
*  the different is slight with random input values  ( genRandomElts )
*  the difference is larger with bad data... unfortunate, worst case 
*  input sequences ( genOrderedElts )
*
*  bubble sort included for comparison
*/
myMain();

function myMain() {
  //var nums= [12,3,51,13,-8.5,25,101,4.3,44,-10,25.3, -17,0,0.01,551,308,17,2];
  //var nums= [21,32,-19,4,71,-3,17,0,8,11,54];
  //var N=3770000, MAX=900000000;
  var N=20000000, MAX=900000000;     // for bubblesort
  //var nums = genRandomElts(N,MAX);
  var nums = genOrderedElts(N);
  
  
  var st, et, sortedNums;
  
  alert(N+" elts, Sorting demo... ");
  st = (new Date()).getTime();
  //sortedNums = heapishSortBuild(nums); 
  sortedNums = heapishSortInsert(nums); 
  //sortedNums = bubbleSort(nums); // dont do this on more than 
                                   // 100,000 items or you will be sorry
  et = (new Date()).getTime();
  alert(et-st + " msec");
}

function heapishSortBuild(vals) {
  var hh = makeNewHeap();
  hh.build(vals);
  //hh.print(); 
  var sVals = [];
  var s = hh.size();
  for (var k=0; k<s; k++) { sVals[k] = hh.getMin(); hh.delMin(); }
  return sVals;
}

function heapishSortInsert(vals) {
  var hh = makeNewHeap();   
  for (var i=0; i<vals.length; i++) { hh.insert(vals[i]); }
  //hh.print();
  var sVals = [];
  var s = hh.size();
  for (var k=0; k<s; k++) { sVals[k] = hh.getMin(); hh.delMin(); }
  return sVals;
}

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);
  }
  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);
  }
}