// Cloned by Jorge Blanco on 18 Oct 2019 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


var data;
var graph;
var actorlist;
var actors = {};

const CW = 900;
const CH = 900;
   
const ELLIPSE_SIZE = CW / 25;

const ROOT_X = CW / 2;
const ROOT_Y = CH / 10;

function preload() 
{
  data = loadJSON('/uploads/9jblanco/bacon2.json');
}

function setup() 
{
   createCanvas(CW,CH);
   background('white');
   
    $.getScript ( "/uploads/9jblanco/breadth-first-graph.js", function() {
    
        $.getScript ( "/uploads/9jblanco/breadth-first-node.js", function() {
            
            graph = new Graph();

            var movies = data.movies;
            for (var i = 0; i < movies.length; i++) 
            {
                var movie = movies[i];
                var cast = movie.cast;
                
                var movieNode = graph.addNode(movie.title);
                    movieNode.setMovieNode();
                
                // Go through all the cast list
                for (var j = 0; j < cast.length; j++) {
                  var name = cast[j];
                  var actorNode = (actors[name])? actors[name]: graph.addNode(name);
                  
                  if (!actors[name]) {
                      actorNode.setActorNode();
                      actors[name] = actorNode;
                  }
                  
                  // Connect movie and actor
                  movieNode.connect(actorNode); 
                }
              }
            
              // Create dropdown
              actorlist = createSelect();           // https://p5js.org/reference/#/p5/createSelect 
              actorlist.parent('actorlist');
              var allactors = Object.keys(actors);
                  allactors.sort();
              
              actorlist.option("Select Actor:");
              for (var index = 0; index < allactors.length; index++) {
                  actorlist.option(allactors[index]);
              }
        
              // Set up an event
              actorlist.changed(findbacon);
            
        });
    });
}


function findbacon() 
{
  graph.clear(); 
  clear(); //canvas

  var path = [];
  var start = actors[actorlist.value()];
  var end = actors['Kevin Bacon'];
  
  if (start && end) {
    graph.setStart(start);
    graph.setEnd(end);

    path = getPath(graph.start);
  }

  printPathKevinBacon(path);
  print2DPathKevinBacon(path);
}

function connectTwoActors (next, last) {
  stroke ("grey");
  line( next.x, next.y, last.x, last.y );   
}

function drawActorNode(actorName, detailsXY) 
{
  // Draw a circle
  stroke ("black");
  fill("black");
  ellipse(detailsXY.x, detailsXY.y, ELLIPSE_SIZE, ELLIPSE_SIZE);
  
  // Display the value
  fill("white");
  textAlign(CENTER);
  textSize(14);
  text (actorName, detailsXY.x,  detailsXY.y + (ELLIPSE_SIZE/6));
}

// note: this requires more work - very hacky
function getNextXY(detailsXY, indexPath) {
    var left = floor(random(0, 2));

    var nextLeft = {
        x: detailsXY.x - (CW / pow(2, indexPath)),
        y: detailsXY.y + (CH / 20)
    };
    
    var nextRight = {
        x: detailsXY.x + (CW / pow(2, indexPath)),
        y: detailsXY.y + (CH / 20)
    };
    
    if (left >= 1 && nextLeft.x < 0) {
        return nextRight;
    }
    
    return nextLeft;
}
      
function printPathKevinBacon(path) 
{
  var s = '<h1> Path length ' + path.length + '</h1>';
  
  for (var indexPath = path.length-1; indexPath >= 0; indexPath--) {
      var nodePath = path[indexPath];
      var actorName = nodePath.label;
     
      s += nodePath.isMovieNode()? "<span style='background: blue; color: white;'>" + actorName + "</span>" : actorName;
      s += "<br>";
  }
  
  AB.msg(s, 2);
}

function print2DPathKevinBacon(path) 
{
  var last = null, next = { x:ROOT_X, y:ROOT_Y }, index = 0;
  for (var indexPath = path.length-1; indexPath >= 0; indexPath--) {
      var nodePath = path[indexPath];
      
      if (!nodePath.isMovieNode()) {
          var actorName = nodePath.label;
          
          if (last) {
              connectTwoActors(next, last);
          }
    
          drawActorNode(actorInitials(actorName), next);
          
          var newValues = getNextXY(next, indexPath);
          last = next;
          next = newValues;
          index ++;
      }
  }
}

function actorInitials(actorName) {
   return actorName.split(" ").map((n)=>n[0]).join("");
}

function populatePath(path, endNode) {
    path.push(endNode);
    
    var next = endNode.parent;
    while (next) {
        path.push(next);
        next = next.parent;
    }
      
    return path;
}

function getPath(node) {
  var queueMap = new Map();
  var path = [];

  do
  {
      var next = node.edges;

      node.setNodeSearched();
      for (var i = 0; i < next.length; i++) {
        var neighbor = next[i];
        var label = neighbor.label;
        if (!neighbor.searched) {
           if (graph.equlEndNode(neighbor)) {
              queueMap.clear();
              
              neighbor.parent = node;
              path = populatePath(path, neighbor);
              
              break;
          }
          else if(!queueMap.has(label)) {
             queueMap.set(label, neighbor);
             
             neighbor.parent = node;
          }
        }
      }

    // get next node
    var nodeLabel = queueMap.keys().next().value;
    node = queueMap.get(nodeLabel);
    if (node) {
        if (queueMap.has(node.label)) {
            queueMap.delete(node.label);
        }
     }
   
  } while (node !== undefined);
  
  return path;
}