// Class that implements domain-independent non-recursive functionality for
// the Backtracking algorithm with interfaces for domain-specific functionality.
class Backtracking {

    // A domain-specific base class that enforces method overriding in subclasses.
    // The base class defines the interface for the implementation. If a subclass
    // fails to overwrite a method, the base class throws a descriptive error.
    static Domain = class {

        // A domain-specific base class that enforces method overriding in subclasses.
        // The base class defines the interface for the implementation. If a subclass
        // fails to overwrite a method, the base class throws a descriptive error.
        static Location = class {

            // Constructor that initializes the location with a given map and indices.
            constructor() {
                // Prevent direct instantiation of the interface itself
                if (this.constructor === Backtracking.Domain.Location) {
                    throw new TypeError("Cannot instantiate an interface class directly.");
                }
            }

            // Enforced interface method to reset the value at the location to the 
            // empty value.
            resetValue() {
                throw new Error("Method 'resetValue()' must be implemented.");
            }

            // Enforced interface method to set the value at the location to the 
            // specified value.
            setValue(value) {
                throw new Error("Method 'setValue()' must be implemented.");
            }
        }

        constructor() {
            // Prevent direct instantiation of the interface itself
            if (this.constructor === Backtracking.Domain) {
                throw new TypeError("Cannot instantiate an interface class directly.");
            }
        }

        // Enforced interface method for running the search for the next location
        // which is not occupied yet to be processed by the Backtracking algorithm.
        getNextLocation() {
            throw new Error("Method 'getNextLocation()' must be implemented.");
        }

        // Enforced interface method for running the search for the next candidate
        // for a specified location.
        getNextCandidate(location) {
            throw new Error("Method 'getNextCandidate()' must be implemented.");
        }
    }

    // Constructor that initializes members.
    constructor() {
        // Stack to keep track of the locations being processed.
        this.stack = undefined; 

        // Domain specific code. Must be set in derived class by using a class 
        // derived from Backtracking.Domain class.
        this.domain = undefined;
    }

    // Reset the stack to start a new search from the beginning.
    reset() {
        this.stack = undefined;
    }

    // This method keep calling next() until a solution is found. Once a 
    // solution is found, the method can be called again to find the next 
    // solution.
    async run(yieldInterval = 100) {

        let lastYieldAt = performance.now();
        // The main loop of the algorithm continues until the next step is not
        // the last. 
        while (this.next())
        {
            // Yield control based on time interval to prevent freezing the UI
            if (performance.now() - lastYieldAt >= yieldInterval) {
                await new Promise(resolve => setTimeout(resolve, 0));
                lastYieldAt = performance.now();
            }
        }
    }

    // One step of the search.
    next() {
        // If the stack is undefined, it means that the search is just starting.
        // In this case, we create a new stack.
        if (this.stack == undefined)
            this.stack = new Stack();

        // If the stack is empty, it means that the search is just starting or
        // we have backtracked all the way to the beginning. In the first case,
        // we need to find the first location to start the search.
        if (this.stack.empty()) {
            let location = this.domain.getNextLocation();
            if (!location)
                return false; // No location found, search cannot proceed
            this.stack.push(location);
        }

        // Get the current location from the top of the stack and find the next
        // candidate for it.
        let location = this.stack.top();
        let candidate = this.domain.getNextCandidate(location);
        if (candidate) {
            // If there is a new candidate for the current location, set it
            // and find next location to check in the next call of this function.
            location.setValue(candidate);
            let nextLocation = this.domain.getNextLocation();
            if (!nextLocation) // No more locations, a solution is found.
                return false;
            this.stack.push(nextLocation);
        } else {
            // If a new candidate not found, backtrack by cleaning 
            // location and popping it from the stack.
            location.resetValue();
            this.stack.pop();
            if (this.stack.empty())
                return false; // All solutions have been found
        }
        // Solution not found yet, so return true to repeat the process.
        return true;
    }
}

// Special class of Backtracking that implements domain-specific 
// functionality on a two-dimensional map.
class Map_Backtracking extends Backtracking {

    // Class that defines a two-dimensional collection of elements. The class 
    // represents a searching space (map) for the Backtracking algorithm.
    static Map = class {

        // Constructor that initializes the map's data and sets the size.
        constructor(data, width, height = 1) {
            this.EMPTY = 0;       // A value representing an empty cell.
            this.data = data;     // The map's data.
            this.width = width;   // The map's width.
            this.height = height; // The map's height.
        }

        // Method to check the state is EMPTY at a location defined by the key.
        isEmpty(key) {
            return this.getState(key) == this.EMPTY;
        }

        // Method to get the state at a location defined by the key.
        getState(key) {
            return this.data[key.j][key.i];
        }

        // Method to get the row of state at a location defined by the row index.
        getStateRow(j) {
            return this.data[j];
        }

        // Method to set the state at a location defined by the key.
        setState(key, state) {
            this.data[key.j][key.i] = state;
        }

        // Serialization function that turns a map object into a string.
        toString() {
            let s = '';
            for (let j = 0; j < this.height; ++j)
                s += this.data[j].join(',') + (j < this.height - 1 ? '\n' : '');
            return s;
        }
    }

    // Constructor that initializes the map that is used during the search 
    // of the next location and candidate.
    constructor(map) {
        super();
        this.domain = new Map_Backtracking.Domain(map);
    }

    // Domain-specific implementations.
    static Domain = class extends Backtracking.Domain {

        // Class that represents a location on a map used by Backtracking algorithm.
        static Location = class extends Backtracking.Domain.Location {

            // Constructor that initializes the location with a given map and indices.
            constructor(map, i = 0, j = 0) {
                super();
                this.map = map; // Reference to the map
                this.i = i;     // Column index
                this.j = j;     // Row index (optional, for 2D maps)
            }

            // Reset the value at the location to the empty value defined in the map.
            resetValue() {
                this.map.data[this.j][this.i] = this.map.EMPTY;
            }

            // Set the value at the location to the specified value.
            setValue(value) {
                this.map.data[this.j][this.i] = value;
            }

            // Returns the indices of the location as an object {i, j}.
            getIndices() {
                return { i: this.i, j: this.j };
            }
        }

        // Constructor that initializes the map that is used during the search 
        // of the next location and candidate.
        constructor(map) {
            super();
            this.map = map;
        }
    }
}