// Cloned by Adam Gray on 11 Oct 2022 from World "Breadth-first search (Kevin Bacon)" by "Coding Train" project 
// Please leave this clone trail here.
 

// Breadth-first search

// Port from:
// https://github.com/nature-of-code/NOC-S17-2-Intelligence-Learning/tree/master/week1-graphs/P2_six_degrees_kevin_bacon
// https://www.youtube.com/watch?v=piBq7VD0ZSo

// Hard to visualise graph 


  AB.headerRHS(); 

  AB.newDiv("selectdiv");
  
  $("#selectdiv").css({
      "margin": "30",
      });

  $("#selectdiv").html(" Pick an actor: <span id='actorlist'></span> ");




// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning

// Graph object

function Graph() 
{
  // store nodes by key and also in an array
  this.graph = {};
  this.nodes = [];
  // Start and end
  this.start = null;
  this.end = null;
}

// Set the start
Graph.prototype.setStart = function(node) 
{
  this.start = node;
}

// Set the end
Graph.prototype.setEnd = function(node) 
{
  this.end = node;
}

// Add a node
Graph.prototype.addNode = function(label) 
{
  var n = new Node(label);
  // Add to both the graph object and the nodes array
  this.graph[label] = n;
  this.nodes.push(n);
  return n;
}

// Clear all searched and parent values
Graph.prototype.clear = function() 
{
  for (var i = 0; i < this.nodes.length; i++) 
  {
    this.nodes[i].searched = false;
    this.nodes[i].parent = null;
  }
}







// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning

// Node object
function Node(label) 
{
  // Has a label
  this.label = label;
  // zero or more edges
  this.edges = [];
  // No parent and not searched by default
  this.parent = null;
  this.searched = false;
}

// Connect one or more neighbors
Node.prototype.connect = function(neighbor)         // one Node (movie) has a connection to another Node (person)
{
  // This is a fancy way of having a function
  // that can accept a variable number of arguments
  for (var i = 0; i < arguments.length; i++) 
  {
    this.edges.push(arguments[i]);              // increase the size of the array 
    // Connect both ways
    arguments[i].edges.push(this);
  }
}






// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning

// The data
var data;

// The graph
var graph;
// A lookup table for actors
// (redundant, the graph could handle this)
var actors;
// Dropdown menu for actors
var actorlist;

function preload() 
{
  data = loadJSON('/uploads/codingtrain/bacon.json');
}

function setup() 
{

 noCanvas();


  // Create the graph
  graph = new Graph();
  // A separate lookup table for actors
  actors = {};
  // For all movies
  var movies = data.movies;
  
  for (var i = 0; i < movies.length; i++) 
  {
    // Title and castlist
    var movie = movies[i].title;
    var cast = movies[i].cast;
    // Add the movie to the graph
    var movieNode = graph.addNode(movie);       // Node movie 
    // Go through all the cast list
    for (var j = 0; j < cast.length; j++) 
    {
      var name = cast[j];
      var actorNode;
      
      // Does the actor exist already?
      if (actors[name]) actorNode = actors[name];
      // If not add a new node
      else 
      {
        actorNode = graph.addNode(name);        // Node person 
        actors[name] = actorNode;
      }
      
      // Connect movie and actor
      movieNode.connect(actorNode);             // movie connects to person 
    }
  }

  // Create dropdown
  actorlist = createSelect();           // https://p5js.org/reference/#/p5/createSelect 
  actorlist.parent('actorlist');
  var allactors = Object.keys(actors);
  // Add all the actors
  for (var i = 0; i < allactors.length; i++) 
    actorlist.option(allactors[i]);
  
  // Set up an event
  actorlist.changed(findbacon);
}


function findbacon() 
{
  // Clear everyone from having been searched
  graph.clear();
  // Start and end
  var start = actors[actorlist.value()];
  var end = actors['Kevin Bacon'];
  graph.setStart(start);
  graph.setEnd(end);
  // Run the search!
  bfs();
}


function bfs() 
{
  // Create a queue ad path
  var queue = [];
  var path = [];

  // Get started
  queue.push(graph.start);

  while (queue.length > 0)      // inside the loop we keep adding things to queue
  {
    var node = queue.shift();               // remove first item
    console.log ("======" );
    console.log ("start of search of " + node.label);
    
    // Are we done?
    if (node == graph.end) 
    {
      console.log ("found goal node");
      // Figure out the path
      path.push(node);
      var next = node.parent;
      while (next) 
      {
        path.push(next);
        next = next.parent;
      }
      break;
    } 
    else 
    {
     console.log ("checking neighbours of " + node.label);
     // Check all neighbors
      var next = node.edges;
      // console.log ("checking " + next.length + " neighbours");
      for (var i = 0; i < next.length; i++) 
      {
        var neighbor = next[i];
        // Any neighbor not already searched add to queue
        if (!neighbor.searched) 
        {
          console.log ("adding unsearched neighbour " + neighbor.label + " to queue");
          queue.push(neighbor);
          // Update the parent
          neighbor.parent = node;
        }
      }
      // Mark node as searched
      node.searched = true;
     console.log ("end of search of " + node.label);
    // console.log ("======" );
   }
  }         // end of while loop
  

// now output path 

  console.log('finished search for path');
  
  // path = bacon + movie + x + movie + x ... + movie + x

  var s = '<h1> Path length ' + path.length + '</h1>';
  
  for (var i = path.length-1; i >= 0; i--) 
  {
    s = s + path[i].label + "<br>";
  }
  
  AB.newDiv("theoutput");
  
  $("#theoutput").css({
      "margin": "30",
      "padding": "30",
      "display": "inline-block",
      "border": "1px solid black"
      });

  $("#theoutput").html(s);


}