// Base class for Flood Fill algorithms. It defines the interface and common 
// functionality for derived classes. The derived classes must implement the 
// run() method to perform the flood fill operation. The domain property is 
// used to define the specific behavior of the flood fill algorithm.
class Flood_Fill {

    // Defines and initializes all required members.
    constructor() {
        this.domain = undefined; // Member with domain-specific implementation.
                                 // Must reference an object of a class derived
                                 // from Flood_Fill.Domain.
    }

    // A domain-specific base class that enforces method overriding in subclasses. 
    static Domain = class {

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

        // Enforced interface method to mark a node as filled.
        markFilled(node) {
            throw new Error("Method 'markFilled()' must be implemented.");
        }

        // Enforced interface method for finding the adjacent nodes of the specified
        // node. Returns all adjacent nodes that have not yet been filled.
        getAdjacents(node) {
            throw new Error("Method 'getAdjacents()' must be implemented.");
        }
    }

    // Enforced interface method for running the flood fill algorithm starting 
    // from the specified seed node. This method must be implemented in derived classes. 
    run(seed) {
        throw new Error("Method 'run()' must be implemented.");
    }
}

// Implementation of the Flood Fill algorithm that gets all adjacent nodes,
// mark them as filled, and repeat the process recursively for each adjacent node.
// This implementation can lead to stack overflow for large domains due to 
// deep recursion.
class Flood_Fill_Recursive extends Flood_Fill {

    // Constructor calls the base class constructor.
    constructor() {
        super();
    }

    // Recursive method that runs the flood fill algorithm starting 
    // from the specified seed node.
    run(seed) {
        let adjacentNodes = this.domain.getAdjacents(seed);
        for (let adjacentNode of adjacentNodes) {
            this.domain.markFilled(adjacentNode);
            this.run(adjacentNode);
        }
    }
}

// Utility function to introduce a delay in asynchronous operations to allow
// the UI to remain responsive during long-running tasks. 
function delay() { return new Promise(resolve => setTimeout(resolve, 0)); }

// Iterative Flood Fill implementation that processes adjacent nodes by
// marking and adding them to the open list. Using an explicit data structure 
// instead of recursion eliminates the risk of stack overflow.
class Flood_Fill_Iterative extends Flood_Fill {

    // Constructor that defined the open list type and calls the base class 
    // constructor.
    constructor(openlist = new Queue()) {
        super();
        this.openlist = openlist;
    }
    
    // Reset the openlist to start a new search from the beginning.
    reset(seed) {
        if (!seed)
            throw new Error("Parameter must be provided to seed the search.");
        this.openlist.clear();
        this.openlist.push(seed);
    }

    // This method keep calling next() until all nodes are visited.
    async run(seed, yieldInterval = 100) {
        this.reset(seed);
        let lastYieldAt = performance.now();
        while (this.next())
            // Yield control based on time interval to prevent freezing the UI
            if (performance.now() - lastYieldAt >= yieldInterval) {
                await delay();
                lastYieldAt = performance.now();
            }
    }

    // One step of the Flood Fill algorithm. It processes the next node from the
    // open list. This method can be used outside run() for visualizing the 
    // algorithm's progress step by step. In such case call reset(node) before
    // calling next() to start a new search.
    next() {
        if (this.openlist.empty())
            return false;
        let currentNode = this.openlist.pop();
        let adjacentNodes = this.domain.getAdjacents(currentNode);
        for (let adjacentNode of adjacentNodes) {
            this.domain.markFilled(adjacentNode);
            this.openlist.push(adjacentNode);
        }
        return true;
    }
}