// A tree search algorithm that uses a user-defined open list to determine the 
// order in which nodes are visited.
class TreeSearch {

    // Node class representing a node in the tree. Each node has a value, 
    // a parent pointer, and a list of children. Can be used as a base class 
    // for a custom node class that extends it for additional functionality like
    // conversion to and from a string.
    static Node = class {

        // Constructor for the Node class. Initializes the value, parent, and 
        // children of the node.
        constructor(value = '', parent = null, children = []) {
            this.value = value;
            this.parent = parent;
            this.children = children;
        }

        // A member function that returns an array of values representing the path
        // from the root node to the current node. The path is constructed by
        // traversing up the parent pointers until reaching the root node, and
        // collecting the values along the way. The resulting vector is ordered
        // from the root to the current node.
        getPath() {
            let r = [];
            r.unshift(this.value); // Push front
            let node = this.parent;
            while (node) {
                r.unshift(node.value); // Push front
                node = node.parent;
            }
            return r;
        }
    }

    // Constructor for the TreeSearch class. The open list is a data structure that 
    // stores nodes that have been discovered but not yet visited. The order in 
    // which nodes are visited is determined by the order in which they are removed
    // from the open list. The open list can be implemented as a stack, queue, or 
    // priority queue, depending on the desired search strategy (e.g., depth-first, 
    // breadth-first, or best-first search).
    constructor(openlist) {
        this.openlist = openlist;
    }

    // The search algorithm that takes a root node and a value to search for. 
    // It returns the node containing the value if found, or null otherwise.
    run(root, lookingfor) {
        this.openlist.clear();
        this.openlist.push(root);
        while (!this.openlist.empty()) {
            let current = this.openlist.pop();
            if (current.value == lookingfor)
                return current;
            for (let child of current.children)
                this.openlist.push(child);
        }
        return null;
    }
}