"use strict";

//var tab = window.open();   

shortestPathDijkstra( );

function shortestPathDijkstra( ) {
  var G = mazeB();
  //G.print(); return;  
  
  var sNode;  // source node number

  while (sNode<0 || sNode>G.nnum | sNode%1!==0) {
    sNode = Number(prompt("source node? (int 0 to "+G.nnum+")?"));
  }
  
  var edge, n, ob;               // temps
  var pq = makePriorityQueue();  // priority queue for best performance 
  var pLen = 0;
  G.nodes[sNode].dist = pLen;       // shortest path source to source is 0
  pq.insert(pLen,sNode);            // put source node num on queue to get ball rolling
  
  while (pq.size() > 0) {   
    // process the min node on the heap
    ob = pq.getMin(); pq.delMin();
    n = ob.val;
    if (G.nodes[n].handled) { continue; } // might be in pq from earlier pathlength
    
    G.nodes[n].handled = true; 
    edge = G.nodes[n].adj;  // deal with out edge nodes if any
    while (edge!==null) { 
      if (!G.nodes[edge.tn].handled) { // dont process if we have already done it
        pLen = G.nodes[n].dist + edge.weight;
        if (pLen < G.nodes[edge.tn].dist) {
          // update distance for dest node
          G.nodes[edge.tn].dist = pLen;
          G.nodes[edge.tn].path = n;
          pq.insert(pLen,edge.tn); 
        }
      }
      edge = edge.next;  // on to next edge
    }
  }
  //alert("end: ");
  
  
  // now report the results

  var str = "shortest path lengths from node " + sNode + " (" + G.nodes[sNode].name + ") to:\n";
  for (var n=0; n<G.nnum; n++) {
    str += "  node "+n+ " (" + G.nodes[n].name + "): "
            + G.nodes[n].dist + ", from: " + G.nodes[n].path + "\n";
  }
  G.print(str);
   
 
  //===================================================================== 
  // end of body of myMain 
  //=====================================================================
  // pre-defined graphs to work on
  //=====================================================================

  function graph_fig_9_20() {
    var G = makeGraph();
    G.addNode("v0");
    G.addNode("v1"); G.addNode("v2"); G.addNode("v3"); G.addNode("v4"); 
    G.addNode("v5"); G.addNode("v6"); G.addNode("v7");
    G.addEdge(0,1,1);
    G.addEdge(1,2,2); G.addEdge(1,4,1); 
    G.addEdge(2,4,3); G.addEdge(2,5,10);
    G.addEdge(3,6,5); G.addEdge(3,1,4);
    G.addEdge(4,3,2); G.addEdge(4,6,8); G.addEdge(4,7,4); G.addEdge(4,5,2);
    G.addEdge(5,7,6);
    G.addEdge(7,6,1);
    // added for trials
    //G.addEdge(7,2);
    return G;
  }

  function graph_ex2 () {
    var G = makeGraph();
    G.addNode("v0"); 
    G.addNode("v1"); G.addNode("v2"); G.addNode("v3"); 
    G.addNode("v4"); G.addNode("v5"); G.addNode("v6");
    G.addEdge(0,1,2); G.addEdge(0,2,4);
    G.addEdge(1,5,3); G.addEdge(1,6,8);
    G.addEdge(2,1,1); G.addEdge(2,3,2); G.addEdge(2,4,5);
    G.addEdge(3,5,5);
    G.addEdge(4,3,2); G.addEdge(4,5,4); G.addEdge(4,1,3);
    G.addEdge(5,6,4);
    return G;
  }

  function graph_cycle () {
    var G = makeGraph();
    G.addNode("v0"); G.addNode("v1"); G.addNode("v2");
    G.addEdge(0,1,2); G.addEdge(1,2,4); G.addEdge(2,0,8);
    return G;
  }
  
  function mazeA () {
    var G = makeGraph();
    G.addNode("0-a1");  G.addNode("1-a2");  G.addNode("2-a3");  G.addNode("3-a4");
    G.addNode("4-b1");  G.addNode("5-b2");  G.addNode("6-b3");  G.addNode("7-b4");
    G.addNode("8-c1");  G.addNode("9-c2");  G.addNode("10-c3"); G.addNode("11-c4");
    G.addNode("12-d1"); G.addNode("13-d2"); G.addNode("14-d3"); G.addNode("15-d4");
    G.addNode("16-e1"); G.addNode("17-e2"); G.addNode("18-e3"); G.addNode("19-e4");
    
    G.addEdge(0,1);  G.addEdge(1,2); G.addEdge(2,3); 
    G.addEdge(0,16); G.addEdge(16,17);
    G.addEdge(1,13); G.addEdge(13,14); G.addEdge(14,15);
    G.addEdge(2,10); G.addEdge(14,18); G.addEdge(15,7);  G.addEdge(15,19);
    return G;
  }
    function mazeB () {
    var G = makeGraph();
    G.addNode("0-a1");  G.addNode("1-a2");  G.addNode("2-a3");  G.addNode("3-a4");
    G.addNode("4-b1");  G.addNode("5-b2");  G.addNode("6-b3");  G.addNode("7-b4");
    G.addNode("8-c1");  G.addNode("9-c2");  G.addNode("10-c3"); G.addNode("11-c4");
    G.addNode("12-d1"); G.addNode("13-d2"); G.addNode("14-d3"); G.addNode("15-d4");
    G.addNode("16-e1"); G.addNode("17-e2"); G.addNode("18-e3"); G.addNode("19-e4");
    
    G.addEdge(0,1);  G.addEdge(1,2); G.addEdge(2,3); 
    G.addEdge(0,16); G.addEdge(16,17);
    G.addEdge(1,13);    
    //G.addEdge(1,13,8); 
    G.addEdge(13,14); G.addEdge(14,15);
    G.addEdge(2,10); G.addEdge(14,18); G.addEdge(15,7);  G.addEdge(15,19);
    G.addEdge(17,13);
    return G;
  }
  
} // end myMain


//=========================================================================
// graph data structure constructor
//=========================================================================

function makeGraph( ) { // constructor 
  var gobj = {
    nodeFac: makeNodeFactory(),  
    edgeFac: makeEdgeFactory(),
    nodes: [],  // array list of nodes
    nnum: 0,
    enum: 0,
    
    addNode: function(name) {
      // doesnt reject duplicate names
      // factory creates unique id nums
      var n = this.nodeFac.gen(name);
      this.nodes[n.idn] = n;
      this.nnum++;
      return true;
    },
    
    addEdge: function(fn, tn, wt) {  // args are int, subscripts
      if (this.nodes[fn]===undefined || this.nodes[tn]===undefined) { return false; }
      var elst = this.nodes[fn].adj;
      if (isIn(tn,elst)) return false;
      this.nodes[fn].adj = this.edgeFac.gen(tn,wt);
      this.nodes[fn].adj.next = elst;
      this.enum++;
      this.nodes[fn].outdeg++;
      this.nodes[tn].indeg++;  // the to node has a new inarc
      return true;
      
      function isIn(n,lst) {
        while (lst !== null) {
          if (lst.tn===n) return true;
          lst = lst.next;
        }
        return false;
      }
    },
    
    delEdge: function(fn,tn) {  // some algs work by removing parts
      if (this.nodes[fn]===undefined) { return false; }
      if (this.nodes[tn]===undefined) { return false; }
      var elst = this.nodes[fn].adj;
      var plst = null;
      while (elst!==null) {
        if (tn===elst.tn) {
          if (plst===null) { this.nodes[fn].adj = elst.next;  }
          else { plst.next = elst.next;  }
          this.enum--;
          this.nodes[fn].outdeg--;
          this.nodes[tn].indeg--;
          return true;
        }
        plst = elst;
        elst = elst.next;
      }
      return false;  
    },  

    delNode: function(n) {
      // doesnt work yet
      // this removes the node object and it's out edges in the adj list      
      this.nodes[n] = undefined; 
      // must now do delEdge for in arcs coming to n
      // its linear #E + #N
    },
    
    numNodes: function() { return this.nnum; },
    numEdges: function() { return this.enum; },
    
    hprint: function() {
      var lst;
      for (var i=0; i<this.nnum; i++) {
        tab.document.write(this.nodes[i].idn + ' "' + this.nodes[i].name+ '" <br/>');
        lst = this.nodes[i].adj;
        while (lst!==null) {
          tab.document.write("&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp--'" 
                             + lst.weight + "'---> "+lst.tn + "<br/>");
          lst = lst.next;
        }
      }
    },
    print: function(exStr) {
      var lst;
      var str = (exStr || "") + "\n";
      for (var i=0; i<this.nnum; i++) {
        str += this.nodes[i].idn + ' "' + this.nodes[i].name + '"\n';
        lst = this.nodes[i].adj;
        while (lst!==null) {
          str += "       --'" + lst.weight + "'---> " + lst.tn + "\n" ;
          lst = lst.next;
        }
      }
      alert(str);
    },
    
  } 
  return gobj;   
  
  //==================================================================
  // end of main graph constructor code body
  //==================================================================
  // node and edge factory constructors
  //==================================================================

  function makeNodeFactory() {
    var factory = {  
      idNum:0,
      gen: function (s) {
        var node = {
          idn:this.idNum++,
          name:(s || "..."),
          next:null, // list of nodes
          adj:null,  // list of edges  
          indeg:0,
          outdeg:0,
          dist:Infinity,  // use for shortest path info, etc
          path:-1,
          handled:false,
        }
        return node;
      },  
    }
    return factory;
  }

  function makeEdgeFactory() {
    var factory = {
      idNum:0,
      gen: function (n,wt) {
        var node = {
          tn:n,
          weight:(wt || 1),
          next:null, // list of edges
          idn:this.idNum++,
        }
        return node;
      },  
    }
    return factory;
  }
  
} // end of graph constructor


//==================================================================
// binary heap constructor
//==================================================================

function makePriorityQueue() {
  // 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
    
    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 value
    RCV:    function (n) { return this.elts[this.RC(n)]; },  // element value
    PNV:    function (n) { return this.elts[this.PN(n)]; },  // element value 

    size:   function ( ) { return this.last;       }, // num vals stored
    
    getMin: function ( ) { return this.elts[this.root]; },
    
    insert: function (p,v) {
      var ob = {pri:p, val:v};
      this.last++;
      this.elts[this.last] = ob;
      var n=this.last;
      var p=this.PN(n);
      var temp;
      while ( (p!==0) && (ob.pri < this.elts[p].pri) ) {
        // 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[1]=Infinity; this.last--; return;}
      // havbe at least two elts
      // move last val to root
      this.elts[this.root]= this.elts[this.last];
      this.elts[this.last] = Infinity; this.last--;
      // 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).pri < this.RCV(n).pri) ? this.LC(n) : this.RC(n);
          }
          if (this.elts[n].pri > this.elts[c].pri) {
            temp=this.elts[c]; this.elts[c]=this.elts[n]; this.elts[n]=temp;
            n = c;
          }
          else { done=true; }
        }
      }
    },
     
    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 ( ) { 
      var str="heap elts: \n";
      for (var i=1; i<=this.size(); i++) {
        str += "p: "+this.elts[i].pri + ", v: "+ this.elts[i].val + "\n";
      }
      alert(str);
    },
    
  }
  return heap;    
}