// Cloned by Andrew Merrigan on 19 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
// Graph object
class Graph {
    constructor() {
        // 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
    setStart(node) {
        this.start = node;
    }
    // Set the end
    setEnd(node) {
        this.end = node;
    }
    // Add a node
    addNode(label, type) {
        var n = new Node(label, type);
        // 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
    clear() {
        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
class Node {
    constructor(label, type) {
        this.label = label;
        this.type = type;
        this.edges = [];
        this.parent = null;
        this.searched = false;
    }

    // Connect one or more neighbor nodes
    connect(...nodes) {
        if (nodes) {
            nodes.forEach(node => {
                this.edges.push(node); // increase the size of the array 
                node.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;
    if (movies) {
        movies.forEach(movie => {
            var movieNode = graph.addNode(movie.title, "MOVIE");
            if (movie.cast) {
                movie.cast.forEach(name => {
                    var actorNode;

                    // Does the actor exist already?
                    if (actors[name]) {
                        actorNode = actors[name];

                    } else {
                        actorNode = graph.addNode(name, "ACTOR");        // Node person 
                        actors[name] = actorNode;
                    }

                    // Connect movie and actor
                    // movie connects to person 
                    movieNode.connect(actorNode);
                });
            }
        });
    }
    // 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);

    // inside the loop we keep adding things to queue
    while (queue.length > 0) {
        var node = queue.shift();               // remove first item
        console.log("======");
        console.log("start of search of " + node.label);
        var edges;
        
        // Are we done?
        if (node == graph.end) {
            console.log("found goal node");
            // Figure out the path
            path.push(node);
            edges = node.parent;
            while (edges) {
                path.push(edges);
                edges = edges.parent;
            }
            break;

        } else {
            console.log("checking neighbours of " + node.label);
            // Check all neighbors
            edges = node.edges;
            // console.log ("checking " + next.length + " neighbours");
            for (var i = 0; i < edges.length; i++) {
                var neighbor = edges[i];
                // Any neighbor not already searched add to queue
                if (!neighbor.searched && !queue.includes(neighbor)) {
                    console.log("adding unsearched neighbour " + neighbor.label + " to queue");
                    queue.push(neighbor);
                    node.searched = true;
                    neighbor.parent = node;
                }
            }

            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 nodeIndex = path.length-1; nodeIndex >= 0; nodeIndex--) {
        var node = path[nodeIndex];
        if(node.type === 'MOVIE'){
            s = s + '<b>' + node.label + '</b><br>';
        }else{
            s = s + node.label + '</b><br>';
        }
    }


    AB.newDiv("theoutput");

    $("#theoutput").css({
        "margin": "30",
        "padding": "30",
        "display": "inline-block",
        "border": "1px solid black"
    });

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

}