// Cloned by Ankit on 26 Oct 2021 from World "Breadth-first search (Kevin Bacon) (clone by Ankit)" by Ankit 
// Please leave this clone trail here.
 


// Cloned by Ankit on 26 Oct 2021 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 


//grandmaster-gogo (Ankit Malik) 



//Define a Node

function Node(value) {
    this.value = value;
    this.edges = [];
    this.searched = false;
    this.parent = null;
}

Node.prototype.addEdge = function(neighbour) {
    this.edges.push(neighbour);
    neighbour.edges.push(this);
}

//Defining a graph

function Graph() {
    this.nodes = []; // creats an array of nodes defined above
    this.graph = {}; // create an object containing all the nodes
    this.start = null;
    this.end = null;
}

Graph.prototype.addNode = function(n) {
    //node into an array
    this.nodes.push(n);
    var title = n.value;
    //node into a "hash"
    this.graph[title] = n;
}

Graph.prototype.getNode = function(actor) {
    var n = this.graph[actor];
    return n;
}

Graph.prototype.setStart = function(actor) {
    this.start = this.graph[actor];
    return this.start;
}

Graph.prototype.setEnd = function(actor) {
    this.end = this.graph[actor];
    return this.end;
}

// initialize the data

var data;
var graph;

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

// load/view the data

function setup() {
    
    var dropdown = createSelect();
        
    graph = new Graph();
    noCanvas();
    //console.log(data);

    var movies = data.movies;
    
    for(var i = 0; i < movies.length; i++) {
        var movie = movies[i].title;
        var cast = movies[i].cast;
        var movieNode = new Node(movie);
        graph.addNode(movieNode);
    
        for(var j = 0; j<cast.length; j++) {
            var actor = cast[j];   
            var actorNode = graph.getNode(actor);
            if (actorNode === undefined) {
                actorNode = new Node(actor);
                dropdown.option(actor);
            }
            
            graph.addNode(actorNode);
            //console.log(actor);
            
            movieNode.addEdge(actorNode);
        }
    }
    
    var start = graph.setStart("Mickey Rourke");
    var end = graph.setEnd("Kevin Bacon");
    
    console.log(graph);
    
    var queue = [];
    
    start.searched = true;
    queue.push(start);
    
    while(queue.length > 0) {
        var current = queue.shift();
        console.log(current.value);
        if (current == end) {
            console.log("Found "+ current.value);
            break;
        }
        var edges = current.edges;
        for (var i=0; i < edges.length; i++) {
            var neighbour = edges[i];
            if (!neighbour.searched) {
                neighbour.searched = true;
                neighbour.parent = current;
                queue.push(neighbour);
            }
        }
    }
    
    var path = [];
    
    path.push(graph.end);
    
    var next = end.parent;
    while (next !== null){
        path.push(next);
        next = next.parent;
    }
    
    var txt = '';
    for (var i = path.length-1; i >= 0; i--) {
        var n = path[i];
        
        txt += n.value; + '-->';
        if (i!==0) {
            txt += '-->';
        }
        
    }
    
    createP(txt);
    
}