"use strict";

myMain();

function myMain() {
  var L = makeList();
  
  L.insort(21);
  L.insort(12);
  L.insort(31);
  L.insort(5); 
  L.insort(9); 
  L.insort(28);
  alert(L.size());
  L.print(); //return;
  
  
  var nitems = 64000;
  alert("start insorts: "+nitems); 
  var st = (new Date()).getTime();

  for (var i=0; i<=nitems; i++) {
  //for (var i=nitems; i>=0; i--) {
    L.insort(i);
  }
 
  var et = (new Date()).getTime();
  alert("time: "+(et-st)+" msec");
  alert("size: "+L.size());
  
  return;
}


function makeCell( v ) {
  var cell = {
    val: v,
    next: null
  }; 
  return cell; 
}

function makeList() {
  var lst = {
    nelts: 0,
    head: makeCell(null),
    tail: makeCell(null),
    
    size: function() { return this.nelts; },
    
    find: function(val) { 
      var cur=this.head;
      while (cur!==null) {
        if (cur.val===val) return true;
        cur = cur.next;
      }
      return false;
    },
    
    insort: function (key) { 
      var cur = this.head.next;
      var prev=this.head;
      var added=false;
      while (cur!==this.tail) {
        if (cur.val>key) {
          prev.next = makeCell(key);
          prev.next.next = cur;
          this.nelts++;
          added = true;
          break;
        }
        prev = cur;
        cur = cur.next;
      }
      if (!added) {
        var cel = makeCell(key);
        cel.next = prev.next;
        prev.next = cel;
        this.nelts++;
      }
      return true;
    },
   
    removeVal: function(val) { },

    genAll: function() {
      var elts = [];
      var cur = this.head.next;
      var i=0;
      while (cur !== this.tail) {
        elts[i++] = cur.val; alert(cur.val);
        cur = cur.next;
      }
      return elts;
    },
  
    insert: function (val,loc) { },
    removeLoc: function(loc) { },
    
    print: function() {
      var elts = [];
      var cel = this.head.next;
      for (var i=0; i<this.nelts; i++) {
        elts[i] = cel.val;
        cel = cel.next;
      }
      alert(elts);
    },
  };
  
  lst.head.next = lst.tail; // hook sentinels together
  
  return lst;
}


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

function genChar(pos) { 
  var chars = "abcdefghijklmnopqrstuvwxyz";
  return chars.substr( pos-1, 1);
}

function ranAlpha() {
  var chars = "abcdefghijklmnopqrstuvwxyz";
  return chars.substr( Math.floor(Math.random() * chars.length), 1);
}
  
function ranChar() {
  var chars = "0123456789abcdefghijklmnopqrstuvwxyz";
  return chars.substr( Math.floor(Math.random() * chars.length), 1);
}
*/