// Cloned by Leonard Alphonso on 11 Oct 2023 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 visualize 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) {
  for (var i = 0; i < arguments.length; i++) {
    this.edges.push(arguments[i]);
    // Connect both ways
    arguments[i].edges.push(this);
  }
}

// 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);
    // 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);
        actors[name] = actorNode;
      }

      // Connect movie and actor
      movieNode.connect(actorNode);
    }
  }

  // Create dropdown
  actorlist = createSelect();
  actorlist.parent('actorlist');
  var allactors = Object.keys(actors);
  // Add all the actors
  for ( 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 and path
  var queue = [];
  var path = [];

  // Create a set to keep track of nodes in the queue
  var queuedNodes = new Set();

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

  while (queue.length > 0) {
    var node = queue.shift();

    console.log("======");
    console.log("start of search of " + node.label);

    // Are we done?
    if (node == graph.end) {
      console.log("found the 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 neighbors of " + node.label);
      // Check all neighbors
       next = node.edges;
      for (var i = 0; i < next.length; i++) {
        var neighbor = next[i];
        // Check if the neighbor is in the set
        if (!queuedNodes.has(neighbor)) {
          console.log("adding unsearched neighbor " + neighbor.label + " to the queue");
          queue.push(neighbor);
          queuedNodes.add(neighbor);
          // Update the parent
          neighbor.parent = node;
        }
      }
      // Mark node as searched
      node.searched = true;
      console.log("end of search of " + node.label);
    }
  }

  // Now output the path
  console.log('finished search for path');

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