// Unit tests for Flood Fill algorithm

// Domain specific implementation of recursive Flood Fill algorithm that operates 
// on a 2D map represented as a 1D array. The map is defined by its size and the 
// values in the array, where 0 represents an empty cell and any other value 
// represents a filled or blocked cell.
class Map_Flood_Fill_Recursive extends Flood_Fill_Recursive {

    // Constructor that initializes members.
    constructor(map = [], size = 0) {
        super();
        this.domain = new Map_Flood_Fill_Recursive.Domain(map, size);
    }

    // Domain-specific class that implements methods from the base class.
    static Domain = class extends Flood_Fill_Recursive.Domain {

        // Constructor that initializes members.
        constructor(map = [], size = 0) {
            super();
            this.map = map;
            this.size = size;
        }

        // Updates the value at a specific key (coordinates) in the map.
        markFilled(node) {
            let j = node[0];
            let i = node[1];
            this.map[j * this.size + i] = 2;
        }

        // Returns adjacent nodes that are within the bounds of the map and have 
        // a value of 0. The method checks the four adjacent positions
        // (up, down, left, right) and adds valid adjacent nodes to the list that 
        // is returned.
        getAdjacents(node) {
            let j = node[0];
            let i = node[1];
            let array = [];
            if (j >= 0 && j < this.size && i >= 0 && i < this.size) {
                if (i > 0 && this.map[j * this.size + i - 1] == 0)
                    array.push([j, i - 1]);
                if (i < this.size - 1 && this.map[j * this.size + i + 1] == 0)
                    array.push([j, i + 1]);
                if (j > 0 && this.map[(j - 1) * this.size + i] == 0)
                    array.push([j - 1, i]);
                if (j < this.size - 1 && this.map[(j + 1) * this.size + i] == 0)
                    array.push([j + 1, i]);
            }
            return array;
        }
    }
}

// Domain specific implementation of iterative Flood Fill algorithm that operates
// on a 2D map represented as a 1D array.
class Map_Flood_Fill_Iterative extends Flood_Fill_Iterative {

    // Constructor that initializes members.
    constructor(map = [], size = 0, openlist = new Queue()) {
        super(openlist);
        this.domain = new Map_Flood_Fill_Iterative.Domain(map, size);
    }

    // Domain-specific class that implements methods from the base class.
    static Domain = class extends Flood_Fill_Iterative.Domain {

        // Constructor that initializes members.
        constructor(map = [], size = 0) {
            super();
            this.map = map;
            this.size = size;
        }

        // Updates the value at a specific key (coordinates) in the map.
        markFilled(node) {
            let j = node[0];
            let i = node[1];
            this.map[j * this.size + i] = 2;
        }

        // Returns adjacent nodes that are within the bounds of the map and have 
        // a value of 0. The method checks the four adjacent positions
        // (up, down, left, right) and adds valid adjacent nodes to the list that 
        // is returned.
        getAdjacents(node) {
            let j = node[0];
            let i = node[1];
            let array = [];
            if (j >= 0 && j < this.size && i >= 0 && i < this.size) {
                if (i > 0 && this.map[j * this.size + i - 1] == 0)
                    array.push([j, i - 1]);
                if (i < this.size - 1 && this.map[j * this.size + i + 1] == 0)
                    array.push([j, i + 1]);
                if (j > 0 && this.map[(j - 1) * this.size + i] == 0)
                    array.push([j - 1, i]);
                if (j < this.size - 1 && this.map[(j + 1) * this.size + i] == 0)
                    array.push([j + 1, i]);
            }
            return array;
        }
    }
}

// Domain specific implementation based on recursive Flood Fill algorithm that 
// shuffle the order of adjacent nodes.
class Map_Flood_Fill_Recursive_Stochastic extends Map_Flood_Fill_Recursive {

    // Constructor that initializes members.
    constructor(map = [], size = 0) {
        super();
        this.domain = new Map_Flood_Fill_Recursive_Stochastic.Domain(map, size);
    }

    // Domain-specific class that implements methods from the base class.
    static Domain = class extends Map_Flood_Fill_Recursive.Domain {

        constructor(map = [], size = 0) {
            super();
            this.map = map;
            this.size = size;
        }

        // Returns adjacent nodes that are within the bounds of the map and have 
        // a value of 0. The method checks the four adjacent positions
        // (up, down, left, right) and adds valid adjacent nodes to the list that 
        // is returned.
        getAdjacents(node) {
            return shuffleArray(super.getAdjacents(node));
        }
    }
}

// Domain specific implementation based on iterative Flood Fill algorithm that 
// shuffle the order of adjacent nodes.
class Map_Flood_Fill_Iterative_Stochastic extends Map_Flood_Fill_Iterative {

    // Constructor that initializes members.
    constructor(map = [], size = 0) {
        super();
        this.domain = new Map_Flood_Fill_Iterative_Stochastic.Domain(map, size);
    }

    // Domain-specific class that implements methods from the base class.
    static Domain = class extends Map_Flood_Fill_Iterative.Domain {

        // Constructor that initializes members.
        constructor(map = [], size = 0) {
            super();
            this.map = map;
            this.size = size;
        }

        // Returns adjacent nodes that are within the bounds of the map and have 
        // a value of 0. The method checks the four adjacent positions
        // (up, down, left, right) and adds valid adjacent nodes to the list that 
        // is returned.
        getAdjacents(node) {
            return shuffleArray(super.getAdjacents(node));
        }
    }
}

// The following code contains unit test function that test the functionality 
// of classes and functions for Flood Fill algorithms.

// Test 1 checks that GetMapAdjacents.run() returns no adjacents when given 
// an out-of-bounds key on an empty map.
function test1() {
    let domain = new Map_Flood_Fill_Recursive().domain;
    let actual = domain.getAdjacents([10, 10]).map(node => node.toString()).join('|');
    let expected = "";

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

// Test 2 verifies the exact neighbors returned for three different cells 
// on a 5×5 map with walls.
function test2() {
    let map = [
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 1,
        0, 0, 0, 1, 0,
        0, 0, 1, 0, 0
    ];
    let domain = new Map_Flood_Fill_Recursive(map, 5).domain;
    let adjacents1 = domain.getAdjacents([0, 0]);
    let adjacents2 = domain.getAdjacents([1, 1]);
    let adjacents3 = domain.getAdjacents([3, 4]);

    let actual = adjacents1.map(node => node.toString()).join('|') + '||' +
        adjacents2.map(node => node.toString()).join('|') + '||' +
        adjacents3.map(node => node.toString()).join('|');

    let expected = '0,1|1,0||1,0|1,2|0,1|2,1||4,4';

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

// Test 3 does the same but with stochastic adjacents, confirming the result 
// is a valid shuffled permutation.
function test3() {
    let map = [
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 1,
        0, 0, 0, 1, 0,
        0, 0, 1, 0, 0
    ];
    let domain = new Map_Flood_Fill_Recursive_Stochastic(map, 5).domain;
    let adjacents = domain.getAdjacents([1, 1]);

    let a0 = adjacents[0].toString();
    let a1 = adjacents[1].toString();
    let a2 = adjacents[2].toString();
    let a3 = adjacents[3].toString();
    let actual0 = (a0 == '0,1' || a0 == '1,0' || a0 == '1,2' || a0 == '2,1');
    let actual1 = (a1 != a0) &&
        (a1 == '0,1' || a1 == '1,0' || a1 == '1,2' || a1 == '2,1');
    let actual2 = (a2 != a0) && (a2 != a1) &&
        (a2 == '0,1' || a2 == '1,0' || a2 == '1,2' || a2 == '2,1');
    let actual3 = (a3 != a0) && (a3 != a1) && (a3 != a2) &&
        (a3 == '0,1' || a3 == '1,0' || a3 == '1,2' || a3 == '2,1');

    let actual = '' + actual0 + ' ' + actual1 + ' ' + actual2 + ' ' + actual3;
    let expected = 'true true true true';
    
    compareStringsAndReport('Test 3', actual, expected);
}

// Test 4 runs Flood_Fill_Recursive from [0,0] and checks that all reachable 
// cells are filled while walled-off cells are not.
function test4() {
    let actual = [
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 1,
        0, 0, 0, 1, 0,
        0, 0, 1, 0, 0
    ];
    new Map_Flood_Fill_Recursive(actual, 5).run([0, 0], 2);
    let expected = [
        2, 2, 2, 2, 2,
        2, 2, 2, 2, 2,
        2, 2, 2, 2, 1,
        2, 2, 2, 1, 0,
        2, 2, 1, 0, 0
    ];

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

// Test 5 repeats that with Flood_Fill_Iterative using a Queue (BFS). 
function test5() {
    let actual = [
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 1,
        0, 0, 0, 1, 0,
        0, 0, 1, 0, 0
    ];
    new Map_Flood_Fill_Iterative(actual, 5, new Queue()).run([0, 0]);
    let expected = [
        2, 2, 2, 2, 2,
        2, 2, 2, 2, 2,
        2, 2, 2, 2, 1,
        2, 2, 2, 1, 0,
        2, 2, 1, 0, 0
    ];

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

// Test 6 repeats it using a Stack (DFS). 
function test6() {
    let actual = [
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 1,
        0, 0, 0, 1, 0,
        0, 0, 1, 0, 0
    ];
    new Map_Flood_Fill_Iterative(actual, 5, new Stack()).run([0, 0]);
    let expected = [
        2, 2, 2, 2, 2,
        2, 2, 2, 2, 2,
        2, 2, 2, 2, 1,
        2, 2, 2, 1, 0,
        2, 2, 1, 0, 0
    ];

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

// Test 7 starts the fill from [4,4], which is in a small isolated pocket, 
// and verifies only that pocket fills. 
function test7() {
    let actual = [
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 1,
        0, 0, 0, 1, 0,
        0, 0, 1, 0, 0
    ];
    new Map_Flood_Fill_Iterative(actual, 5, new Stack()).run([4, 4]);
    let expected = [
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 1,
        0, 0, 0, 1, 2,
        0, 0, 1, 2, 2
    ];

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

// Test 8 runs the fill from [0,0] with stochastic adjacents and confirms 
// the full region still fills. 
function test8() {
    let actual = [
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 1,
        0, 0, 0, 1, 0,
        0, 0, 1, 0, 0
    ];
    new Map_Flood_Fill_Iterative(actual, 5, new Stack()).run([0, 0]);
    let expected = [
        2, 2, 2, 2, 2,
        2, 2, 2, 2, 2,
        2, 2, 2, 2, 1,
        2, 2, 2, 1, 0,
        2, 2, 1, 0, 0
    ];

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

// Test 9 repeats Test 7 with stochastic adjacents. 
function test9() {
    let actual = [
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 1,
        0, 0, 0, 1, 0,
        0, 0, 1, 0, 0
    ];
    new Map_Flood_Fill_Iterative_Stochastic(actual, 5, new Stack()).run([4, 4]);
    let expected = [
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 1,
        0, 0, 0, 1, 2,
        0, 0, 1, 2, 2
    ];

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

// Test 10 starts from [3,3], which connects to the main region and the 
// isolated pocket, and verifies the entire reachable area fills.
function test10() {
    let actual = [
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 1,
        0, 0, 0, 1, 0,
        0, 0, 1, 0, 0
    ];
    new Map_Flood_Fill_Iterative_Stochastic(actual, 5, new Stack()).run([3, 3]);
    let expected = [
        2, 2, 2, 2, 2,
        2, 2, 2, 2, 2,
        2, 2, 2, 2, 1,
        2, 2, 2, 1, 2,
        2, 2, 1, 2, 2
    ];

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