"use strict";

//var tab = window.open();   

topoSort();

//tab.close();

function topoSort() {
  var topo = []; // when done this list will have the nodes in topo sort order
  
  var G = graph_fig_9_4();
  //var G = graph_ex2();
  //var G = graph_cycle();  // cycle in this one
 
  var origG = G.print(false);
  //G.print(); return;
  
  var queue = []; // contains nodes with in degree 0  
  for(var i=0; i<G.nnum; i++) {
    if (G.nodes[i].indeg===0) { queue.push(i); }
  }
 
  var tns = [];   // scratch pad for finding nodes at end of out arcs
  var node, fn, tn;
  var elst;
  
  while ( queue.length > 0 ) {
    fn = queue.shift(); 
    topo.push(fn);    
    elst = G.nodes[fn].adj;
    while (elst !== null) { // collect out arc to nodes
      tns.push(elst.tn);
      elst = elst.next;
    }
    while (tns.length>0) {
      tn = tns.pop();
      G.delEdge(fn,tn);
      if (G.nodes[tn].indeg===0) { queue.push(tn); }
    }
  }
  if (topo.length !== G.nnum) { 
    alert("cycle found"); 
    return false; 
  }
  
  // print the topo order
  var str = "";
  for (var k=0; k<topo.length; k++) { str += G.nodes[topo[k]].name + ", " ; }
  alert(str + "\n\n" + origG);
  
  return true;

  //===========================================================
  // end main body of topoSort
  //===========================================================

  function graph_fig_9_4() {
    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);
    G.addEdge(1,2); G.addEdge(1,3); G.addEdge(1,4); 
    G.addEdge(2,4); G.addEdge(2,5);
    G.addEdge(3,6);
    G.addEdge(4,3); G.addEdge(4,6); G.addEdge(4,7);
    G.addEdge(5,4); G.addEdge(5,7);
    G.addEdge(7,6);
    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); G.addEdge(0,2);
    G.addEdge(1,5); G.addEdge(1,6);
    G.addEdge(2,1); G.addEdge(2,3); G.addEdge(2,4);
    G.addEdge(3,5);
    G.addEdge(4,3); G.addEdge(4,5); G.addEdge(4,1);
    G.addEdge(5,6);
    return G;
  }

  function graph_cycle () {
    var G = makeGraph();
    G.addNode("v0"); G.addNode("v1"); G.addNode("v2");
    G.addEdge(0,1); G.addEdge(1,2); G.addEdge(2,0);
    return G;
  }
}

//============================================================================
// 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) {  // 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);
      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) {
      // NOT FULLY IMPLEMENTED
      // 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.tn + "<br/>");
          lst = lst.next;
        }
      }
    },
    print: function(flag) {
      var lst;
      var str = "";
      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.tn + "\n" ;
          lst = lst.next;
        }
      }
      if (flag!==undefined) { return str; }
      alert(str);
    }, 
  } 
  return gobj;   

  //===========================================================
  // factories
  //===========================================================

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