"use strict";

var tab = window.open();   

//-------------------------------------------------------------------
//
// basic graph representation
//
//   directed graph, edges (from, to)
//
//     uses an array for holding nodes
//     each node has a link to adjacencies 
//     for now an adjaceny is just a node number
//
//-------------------------------------------------------------------

( function myMain() { testLoop( makeGraph() ); } ) ( );

tab.window.close;

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
      //
      // could efficiently reject dupe names with a hash map of nodes by name
      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) {
        // hash map is more efficient
        // this works OK for sparse graph, not a lot of edges
        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() {
      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;
        }
      }
      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;
}


//------------------------------------------------------------------
//
//  interactive test driver
//
//------------------------------------------------------------------

function testLoop ( graph ) {
  var comm, str;
  var fn, tn;
  while(true) {
    comm = prompt("comm (q,n,an,ae,dn,de,s,hpg,pg) ?");
    switch(comm) {
      case "q": return; break;
      case "n": graph = makeGraph(); break;
      case "an": alert( graph.addNode(prompt("name?")) ); break;
      case "ae": alert(  graph.addEdge( 
                          Number(prompt("from node?")), 
                          Number(prompt("to node?")) 
                      ) ); 
                break; 
      case "de": alert(graph.delEdge(
                          Number(prompt("from node?")), 
                          Number(prompt("to node?")) 
                      ) ); 
                 break;
      case "dn": alert("not implemented"); break;
      case "s": alert(graph.numNodes()+" nodes, "+ graph.numEdges()+" edges"); 
                break;
      case "pg": graph.print(); break;
      case "hpg": graph.hprint(); break;
      default:  alert("bad"); break;
    } 
  }
}