// Node class based on TreeSearch.Node that extends it for additional 
// functionality to read from and write to a string.
class Node extends TreeSearch.Node {

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

    // Deserialization function that turns a string into a tree object.
    // The string is in the format of "value { child1 child2 ... }".
    // The value is a string without spaces. The children are separated by
    // spaces and enclosed in curly braces. The function returns the remaining
    // string after parsing the current node and its children.
    // You can safely assume the input string is well-formed and
    // does not contain syntax errors.
    setFromString(string) {
        if (string.length) {
            let n = string.indexOf(' ');
            if (n >= 0) {
                this.value = string.slice(0, n);
                string = string.slice(n).trimStart();

                if (string[0] == '{') {
                    string = string.slice(1).trimStart();   // Skip {
                    while (string[0] != '}') {
                        let child = new Node('', this);
                        string = child.setFromString(string);
                        this.children.push(child);
                    }

                    string = string.slice(1).trimStart();   // Skip }
                }
            }
            else {
                this.value = string;
                string = '';
            }
        }
        return string;
    }

    // Serialization function that turns a node object into a string.
    // A node is serialized in the format of "value { child1 child2 ... }"
    toString() {
        let string = this.value;

        if (this.children.length > 0) {
            string += ' { ';
            let sep = '';
            for (let child of this.children) {
                string += sep + child.toString();
                sep = ' ';
            }
            string += ' }';
        }

        return string;
    }
}


// Implementation of the Breadth-First Search algorithm in a tree.
// The algorithm uses a queue to explore the nodes level by level,
// starting from the root node and moving down to the children.
class BFS extends TreeSearch {
    constructor() {
        super(new Queue());
    }
}

// Implementation of the Depth-First Search algorithm in a tree.
// The algorithm uses a stack to explore the nodes depth-wise, starting
// from the root node and moving down to the children before
// exploring siblings.
class DFS extends TreeSearch {
    constructor() {
        super(new Stack());
    }
}


// The following code contains unit test function that test the functionality 
// of the classes and functions for Depth-First Search (DFS) and Breadth-First 
// Search (BFS).

// Tests 1–6: Verify round-trip serialization — a string is parsed into a tree
//            via setFromString(), then serialized back with getAsString(),
//            and compared to the original.

function test1() {
    let string = '';

    let root = new Node();
    root.setFromString(string);
    let actual = root.toString();
    let expected = string;

    compareStringsAndReport('Test 1', actual, expected);
}

function test2() {
    let string = 'a';

    let root = new Node();
    root.setFromString(string);
    let actual = root.toString();
    let expected = string;

    compareStringsAndReport('Test 2', actual, expected);
}

function test3() {
    let string = 'a { aa }';

    let root = new Node();
    root.setFromString(string);
    let actual = root.toString();
    let expected = string;

    compareStringsAndReport('Test 3', actual, expected);
}

function test4() {
    let string = 'a { aa { aaa } }';

    let root = new Node();
    root.setFromString(string);
    let actual = root.toString();
    let expected = string;

    compareStringsAndReport('Test 4', actual, expected);
}

function test5() {
    let string = 'a { aa bb cc }';

    let root = new Node();
    root.setFromString(string);
    let actual = root.toString();
    let expected = string;

    compareStringsAndReport('Test 5', actual, expected);
}

function test6() {
    let string = 'a { aa { aaa aab ooo } ooo { aba abb abc } ac { aca ooo acc } }';

    let root = new Node();
    root.setFromString(string);
    let actual = root.toString();
    let expected = string;

    compareStringsAndReport('Test 6', actual, expected);
}

// Tests 7–8: Validate BFS on a multi-level tree — test 7 checks that searching
//            for a missing value returns null; test 8 checks that 'ooo' is
//            found at path a,ooo (first match at level 1).

function test7() {
    let string =
`a {
  aa {
     aaa aab ooo }
  ooo {
     aba abb abc }
  ac {
     aca ooo acc } }
`;

    let lookingfor = 'N';
    let root = new Node();
    root.setFromString(string);
    let actual = new BFS().run(root, lookingfor);
    let expected = null;

    compareStringsAndReport('Test 7', actual, expected);
}

function test8() {
    let string =
`a {
  aa {
     aaa aab ooo }
  ooo {
     aba abb abc }
  ac {
     aca ooo acc } }
`;

    let lookingfor = 'ooo';
    let root = new Node();
    root.setFromString(string);
    let search_result = new BFS().run(root, lookingfor);
    let actual = search_result !== null ? search_result.getPath().join(',')
        : null;
    let expected = 'a,ooo';

    compareStringsAndReport('Test 8', actual, expected);
}

// Tests 9–10: Validate DFS on the same tree — test 9 checks the missing-value
//            case; test 10 checks that 'ooo' is found at path a,ac,ooo
//            (deeper match due to DFS's stack-based traversal order).

function test9() {
    let string =
`a {
  aa {
     aaa aab ooo }
  ooo {
     aba abb abc }
  ac {
     aca ooo acc } }
`;

    let lookingfor = 'N';
    let root = new Node();
    root.setFromString(string);
    let actual = new DFS().run(root, lookingfor);
    let expected = null;

    compareStringsAndReport('Test 9', actual, expected);
}

function test10() {
    let string =
`a {
  aa {
     aaa aab ooo }
  ooo {
     aba abb abc }
  ac {
     aca ooo acc } }
`;

    let lookingfor = 'ooo';
    let root = new Node();
    root.setFromString(string);
    let search_result = new DFS().run(root, lookingfor);
    let actual = search_result != null ? search_result.getPath().join(',')
        : null;
    let expected = 'a,ac,ooo';

    compareStringsAndReport('Test 10', actual, expected);
}