// Cloned by Himanshu Warekar on 14 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 

AB.headerRHS(); 
AB.newDiv("selectdiv");

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

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

class Node {
    constructor(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(neighbor) {
        // This is a fancy way of having a function
        // that can accept a variable number of arguments
        for (let arg of arguments) {
            this.edges.push(arg);              // increase the size of the array 
            // Connect both ways
            arg.edges.push(this);
        }
    }
}

// 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;
    }
    
    setStart(node) {
        this.start = node;
    }
    
    setEnd(node) {
        this.end = node;
    }
    
    addNode(label) {
        let node = new Node(label);
        // Add to both the graph object and the nodes array
        this.graph[label] = node;
        this.nodes.push(node);
        return node;
    }
    
    clear() {
        for (let node of this.nodes) {
            node.searched = false;
            node.parent = null;
        }
    }

}

class Bacon{
    constructor(data) {
        this.data = data;
        this.graph = new Graph();
        this.actors = {};
        this.actorList = null;
        window.bacon = this;
    }
    
    init() {
        this.createTree();
        this.createSelect();
        this.renderDropdown();
    }
    
    createTree() {
        let me = this;
        
        return new Promise((resolve) => {
            for (let movie of me.data.movies) {
                // Add the movie to the graph
                let movieNode = me.graph.addNode(movie.title);       // Node movie 
                // Go through all the cast list
                for (let cast of movie.cast) {
                    let name = cast;
                    let actorNode;
                  
                  // Does the actor exist already?
                    if (me.actors[cast]) {
                        actorNode = me.actors[name];
                    } else {
                        me.actors[cast] = actorNode = me.graph.addNode(cast);
                    }
                  
                    movieNode.connect(actorNode);
                }
                resolve();
            } 
        });
    }
    
    renderDropdown() {
        let me = this;
        me.actorList = document.createElement("select");
        document.getElementById("actorlist").append(me.actorList)
        

        let allActors = Object.keys(me.actors);
        
        // Add all the actors
        for (let actor of allActors) {
            let option = document.createElement("option");
            option.value = actor;
            option.text = actor;
            me.actorList.appendChild(option);
        }
        
        // Set up an event
        $(me.actorList).on('change', function() {
            me.findBacon(this.value)
        });
    }
    
    findBacon(actor) {
        this.graph.clear();
        
        // Start and end
        let start = this.actors[actor];
        let end = this.actors['Kevin Bacon'];
        
        this.graph.setStart(start);
        this.graph.setEnd(end);
        // Run the search!
        this.bfs();   
    }
    
    bfs() {
         // Create a queue ad path
        let queue = [this.graph.start];
        let path = [];
        
        while (queue.length > 0){      // inside the loop we keep adding things to queue{
            let node = queue.shift();               // remove first item
            console.log ("======" );
            console.log ("start of search of " + node.label);
            
            // Are we done?
            if (node == this.graph.end) {
                console.log ("found goal node");
                // Figure out the path
                path.push(node);
                let next = node.parent;
                
                while (next) {
                    path.push(next);
                    next = next.parent;
                }
                
                break;
            } else {
                console.log ("checking neighbours of " + node.label);
                // Check all neighbors
                let next = node.edges;
                // console.log ("checking " + next.length + " neighbours");
                for (let neighbor of next) {
                    // 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);
            }
        }         // end of while loop
        
        
        // now output path 
        
        console.log('finished search for path');
        
        // path = bacon + movie + x + movie + x ... + movie + x
        
        let s = '<h1> Path length ' + path.length + '</h1>';
        
        for (let p of path) {
            s += p.label + "<br>";
        }
        
        AB.newDiv("theoutput");
        
        $("#theoutput").css({
            "margin": "30",
            "padding": "30",
            "display": "inline-block",
            "border": "1px solid black"
        });
        
        $("#theoutput").html(s);
    }
    
    createSelect() {
        
    }
}

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

function setup() {
    noCanvas();
    let bacon = new Bacon(data);
    bacon.init();
}