/*
File: swIsland.js
Date: 2026-03-18
Author: klp
Workspace: SWIslandRecurnSaga2026-03-16-Stg1
Purpose: SWIsland -- a single island in the ocean grid, built by recursive backtracking.
         Mirrors Island.java from the SWIsland Recursion Saga Java source, with one
         JavaScript-specific addition: SWIsland records every ADD and BACKTRACK decision
         into an internal step queue so the sketch can replay the algorithm as animation.

=== Connection to Island.java ===
  Island.java holds the core recursive algorithm taught in APCS A.  SWIsland mirrors
  every method and rule in Island.java:

    contains()          → same logic, uses Coordinates instances
    isValidExpansion()  → same Rule 1 / Rule 2 / Rule 3 (8-neighbor separation)
    grow()              → same recursive backtracking; also records ADD/BACKTRACK steps
    buildIsland()       → same static factory (seed search + grow loop)

  Two additions over Island.java (for the JS animation runtime):
    1. grow() writes every ADD and BACKTRACK into this._stepQueue.
    2. A BFS reachability pre-check inside buildIsland() fast-fails impossible
       configurations before starting recursion (prevents browser hangs).

=== Separation Rule ===
  Two different islands may NOT touch — not even diagonally.
  They must be separated by at least one water cell in all 8 directions.
  This is enforced by isValidExpansion() Rule 3.

=== Step Queue ===
  After buildIsland() returns a successful island, call getStepQueue() to retrieve
  an array of {type:'ADD'|'BACKTRACK', row, col} objects recorded by grow().
  The sketch splices these into its global step queue between ISLAND_START and
  ISLAND_SUCCESS markers for animation replay.

=== Direction Arrays ===
  Static constants mirror Island.java exactly:
    DR4 / DC4  — orthogonal only (candidate collection inside grow)
    DR8 / DC8  — all 8 directions (isValidExpansion Rule 3 + buildIsland seed check)
*/

/**
 * SWIsland
 * ========
 * Represents a single island grown by recursive backtracking.
 * Mirrors Island.java from the Java source, adapted for JavaScript animation.
 *
 * Cells are stored as Coordinates instances (see coordinates.js).
 */
class SWIsland {

    // ── Direction arrays (mirrors Island.java static finals) ─────────────────
    //
    // DR4 / DC4: orthogonal directions used to collect expansion candidates.
    //   i=0 : UP    (row-1, col  )
    //   i=1 : DOWN  (row+1, col  )
    //   i=2 : LEFT  (row,   col-1)
    //   i=3 : RIGHT (row,   col+1)
    static DR4 = [-1,  1,  0,  0];
    static DC4 = [ 0,  0, -1,  1];

    // DR8 / DC8: all 8 surrounding directions used in isValidExpansion and buildIsland.
    //   i=0 : UP-LEFT    i=1 : UP    i=2 : UP-RIGHT
    //   i=3 : LEFT                   i=4 : RIGHT
    //   i=5 : DOWN-LEFT  i=6 : DOWN  i=7 : DOWN-RIGHT
    static DR8 = [-1, -1, -1,  0,  0,  1,  1,  1];
    static DC8 = [-1,  0,  1, -1,  1, -1,  0,  1];

    // ─────────────────────────────────────────────────────────────────────────

    /**
     * Creates a new island seeded with a single land cell.
     * Mirrors Island(Coordinates startCell) in Java.
     *
     * @param {Coordinates} startCell  The seed cell (already planted in ocean by the caller).
     */
    constructor(startCell) {
        this._cells       = [startCell];  // Coordinates[]
        this._stepQueue   = [];           // { type:'ADD'|'BACKTRACK', row, col }[]
        this._buildAborted = false;
    }

    // ── Getters ───────────────────────────────────────────────────────────────

    /**
     * Returns the list of land cells that make up this island (Coordinates[]).
     * Mirrors Island.getCells() in Java.
     */
    getCells() { return this._cells; }

    /**
     * Returns the number of land cells in this island.
     * Mirrors Island.getSize() in Java.
     */
    getSize() { return this._cells.length; }

    /**
     * Returns the ADD / BACKTRACK step queue recorded during grow().
     * (JS addition — no equivalent in Java.)
     * @returns {{ type: string, row: number, col: number }[]}
     */
    getStepQueue() { return this._stepQueue; }

    /**
     * Returns true if grow() hit the maximum step limit and was aborted.
     * (JS addition — no equivalent in Java.)
     * @returns {boolean}
     */
    wasAborted() { return this._buildAborted; }

    // ── Helper: contains ─────────────────────────────────────────────────────

    /**
     * Returns true if this island already owns the cell at (row, col).
     * Mirrors Island.contains() in Java.
     *
     * Used by isValidExpansion() to distinguish this island's land from
     * land that belongs to a different island.
     *
     * @param {number} row
     * @param {number} col
     * @returns {boolean}
     */
    contains(row, col) {
        return this._cells.some(c => c.getRow() === row && c.getCol() === col);
    }//end contains

    // ── Helper: isValidExpansion ──────────────────────────────────────────────

    /**
     * Decides whether it is legal to expand this island to include (row, col).
     * Mirrors Island.isValidExpansion() in Java exactly (3 rules).
     *
     * Rule 1 – In bounds  : (row, col) must be inside the ocean grid.
     * Rule 2 – Water only : ocean[row][col] must be 0 (pits and land also fail).
     * Rule 3 – No conflict: none of the 8 surrounding neighbors of (row, col)
     *                       may be land (ocean value === 1) belonging to a
     *                       DIFFERENT island. Land from THIS island is fine.
     *
     * NOTE: This method does NOT verify adjacency to an existing island cell.
     *       The caller (grow) guarantees this by only passing orthogonal neighbors.
     *
     * @param {number}     row
     * @param {number}     col
     * @param {number[][]} ocean    The 2D ocean grid.
     * @param {number}     numRows
     * @param {number}     numCols
     * @returns {boolean}
     */
    isValidExpansion(row, col, ocean, numRows, numCols) {

        // Rule 1: bounds check
        if (row < 0 || row >= numRows || col < 0 || col >= numCols) return false;

        // Rule 2: the cell must be open water (0).  Pits (2) and land (1) both fail.
        if (ocean[row][col] !== 0) return false;

        // Rule 3: scan all 8 neighbors for land that belongs to a DIFFERENT island.
        //         If a neighbor is land (== 1) and NOT part of THIS island → reject.
        for (let d = 0; d < 8; d++) {
            const nr = row + SWIsland.DR8[d];
            const nc = col + SWIsland.DC8[d];
            if (nr >= 0 && nr < numRows && nc >= 0 && nc < numCols) {
                if (ocean[nr][nc] === 1 && !this.contains(nr, nc)) {
                    return false;  // foreign island land nearby — reject
                }
            }
        }

        return true;  // All three rules passed
    }//end isValidExpansion

    // ── Helper: _alreadyCandidate ─────────────────────────────────────────────

    /**
     * Returns true if (row, col) already appears in the candidates list.
     * Prevents duplicate candidates when two island cells share a common neighbor.
     * Mirrors Island.alreadyCandidate() in Java.
     *
     * @param {number}   row
     * @param {number}   col
     * @param {number[][]} candidates  Array of [row, col] pairs.
     * @returns {boolean}
     */
    _alreadyCandidate(row, col, candidates) {
        return candidates.some(c => c[0] === row && c[1] === col);
    }//end _alreadyCandidate

    // ── Helper: _shuffleCandidates ────────────────────────────────────────────

    /**
     * Randomly shuffles the candidates list in-place using the Fisher-Yates algorithm.
     * Mirrors Island.shuffleCandidates() in Java.
     *
     * Without shuffling, grow() would always try candidates in the same order,
     * producing predictable, grid-aligned shapes.  Shuffling gives each island a
     * unique, organic-looking form on every run.
     *
     * @param {{ row: number, col: number }[]} list
     */
    _shuffleCandidates(list) {
        for (let i = list.length - 1; i > 0; i--) {
            const j = Math.floor(Math.random() * (i + 1));
            const tmp = list[i];
            list[i]   = list[j];
            list[j]   = tmp;
        }
    }//end _shuffleCandidates

    // ── Core: grow ────────────────────────────────────────────────────────────

    /**
     * Recursively grows this island to targetSize cells using backtracking.
     * Records every ADD and BACKTRACK decision in this._stepQueue.
     *
     * Mirrors Island.grow() in Java, with:
     *   - Coordinates instances used instead of int arrays for cells.
     *   - Step recording (ADD / BACKTRACK) written to this._stepQueue.
     *   - A maxSteps safety limit that sets this._buildAborted and returns false
     *     if the step queue grows too large (prevents browser hangs).
     *
     * ═══════════════════════════════════════════════════════════
     *  RECURSIVE BACKTRACKING — the big idea:
     *
     *  We solve the problem by making a choice (ADD a cell), then
     *  recursing to see if that choice leads to a full solution.
     *  If the recursion reports failure, we UNDO the choice
     *  (BACKTRACK) and try the next option.
     * ═══════════════════════════════════════════════════════════
     *
     * BASE CASE  : cells.length >= targetSize → return true (island complete).
     * RECURSIVE  :
     *   1. Collect valid orthogonal neighbors (passes isValidExpansion).
     *   2. Shuffle (or sort) them.
     *   3. For each candidate:
     *        a. ADD   — append to _cells, stamp ocean[r][c]=1, record 'ADD'.
     *        b. RECURSE — call grow().
     *        c. SUCCESS → propagate true.
     *        d. FAILURE → BACKTRACK: pop _cells, restore ocean, record 'BACKTRACK'.
     *   4. No candidates worked → return false.
     *
     * @param {number}     targetSize  Desired total cell count.
     * @param {number[][]} ocean       Mutated during growth; restored on backtrack.
     * @param {number}     numRows
     * @param {number}     numCols
     * @param {boolean}    useRandom   true = Fisher-Yates shuffle; false = sorted order.
     * @param {number}     maxSteps    Safety limit on total step-queue size.
     * @returns {boolean}  true on success; false if the island could not reach targetSize.
     */
    grow(targetSize, ocean, numRows, numCols, useRandom = true, maxSteps = 150_000) {

        if (this._buildAborted) return false;

        // ── BASE CASE ────────────────────────────────────────────────────────
        if (this._cells.length >= targetSize) return true;

        // ── BUILD CANDIDATE LIST ─────────────────────────────────────────────
        // Collect every valid orthogonal neighbor of every current island cell.
        const candidates = [];
        for (const cell of this._cells) {
            for (let d = 0; d < 4; d++) {
                const nr = cell.getRow() + SWIsland.DR4[d];
                const nc = cell.getCol() + SWIsland.DC4[d];
                if (this.isValidExpansion(nr, nc, ocean, numRows, numCols) &&
                        !this._alreadyCandidate(nr, nc, candidates)) {
                    candidates.push([nr, nc]);
                }
            }
        }

        // ── DEAD END ─────────────────────────────────────────────────────────
        if (candidates.length === 0) return false;

        // ── SHUFFLE (or sort) ────────────────────────────────────────────────
        if (useRandom) {
            this._shuffleCandidates(candidates);
        } else {
            // Deterministic: top-to-bottom, then left-to-right
            candidates.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
        }

        // ── TRY EACH CANDIDATE (with backtracking) ────────────────────────────
        for (const [r, c] of candidates) {

            if (this._buildAborted) return false;

            // STEP A: ADD — commit to this cell
            this._cells.push(new Coordinates(r, c));
            ocean[r][c] = 1;
            this._stepQueue.push({ type: 'ADD', row: r, col: c });

            // Safety: abort if step queue reaches the limit
            if (this._stepQueue.length >= maxSteps) {
                this._cells.pop();
                ocean[r][c] = 0;
                this._buildAborted = true;
                return false;
            }

            // STEP B: RECURSE — attempt to finish growing from here
            if (this.grow(targetSize, ocean, numRows, numCols, useRandom, maxSteps)) {
                return true;   // Propagate success all the way up!
            }

            // STEP C: BACKTRACK — this path failed; undo and try the next candidate
            this._cells.pop();
            ocean[r][c] = 0;
            if (!this._buildAborted) {
                this._stepQueue.push({ type: 'BACKTRACK', row: r, col: c });
            }
            if (this._buildAborted) return false;
        }

        // Every candidate was tried and none worked — signal backtrack to caller.
        return false;
    }//end grow

    // ── Static utility: countReachableCells ──────────────────────────────────

    /**
     * BFS count of open-water cells reachable from (seedRow, seedCol).
     * Used by buildIsland() to fast-fail configurations where there are not
     * enough reachable cells to fill the target size — skips those seeds without
     * attempting expensive recursion.
     *
     * NOTE: The seed cell must already be stamped as land (ocean=1) before calling.
     *       The seed itself counts as 1 reachable cell (it is the starting point).
     *
     * @param {number}     seedRow
     * @param {number}     seedCol
     * @param {number[][]} ocean
     * @param {number}     numRows
     * @param {number}     numCols
     * @returns {number}
     */
    static countReachableCells(seedRow, seedCol, ocean, numRows, numCols) {
        const visited = new Set();
        const queue   = [[seedRow, seedCol]];
        visited.add(`${seedRow},${seedCol}`);
        while (queue.length > 0) {
            const [r, c] = queue.shift();
            for (let d = 0; d < 4; d++) {
                const nr = r + SWIsland.DR4[d];
                const nc = c + SWIsland.DC4[d];
                if (nr < 0 || nr >= numRows || nc < 0 || nc >= numCols) continue;
                const key = `${nr},${nc}`;
                if (visited.has(key)) continue;
                if (ocean[nr][nc] === 0) {   // open water only (not pits)
                    visited.add(key);
                    queue.push([nr, nc]);
                }
            }
        }
        return visited.size;  // includes the seed itself
    }//end countReachableCells

    // ── Static factory: buildIsland ───────────────────────────────────────────

    /**
     * Attempts to place and grow a complete island of targetSize cells
     * somewhere in the ocean.  Mirrors Island.buildIsland() in Java, with
     * a BFS reachability pre-check added for browser safety.
     *
     * Algorithm (mirrors Java steps 1–6):
     *   Try up to numRows * numCols random seed positions:
     *     Step 1: Skip if the cell is not open water (ocean !== 0).
     *     Step 2: Skip if any of 8 neighbors is already island land (=== 1).
     *             (A seed here would violate the separation rule immediately.)
     *     Step 3: BFS pre-check — skip if not enough reachable open water.
     *             (JS addition; Java does not have this step.)
     *     Step 4: Plant the seed (ocean[r][c] = 1) and call grow().
     *     Step 5: If grow() succeeds → return the finished SWIsland.
     *     Step 6: If grow() fails → restore seed to water and try a new position.
     *             If grow() was aborted (TOOSLOW) → return the partial island so
     *             the sketch can display the TOOSLOW message.
     *   All attempts exhausted → return null.
     *
     * @param {number[][]} ocean
     * @param {number}     targetSize
     * @param {number}     numRows
     * @param {number}     numCols
     * @param {boolean}    useRandom    true = Fisher-Yates; false = sorted.
     * @param {number}     maxSteps     Safety limit forwarded to grow().
     * @returns {SWIsland|null}  Fully grown island, aborted island, or null.
     */
    static buildIsland(ocean, targetSize, numRows, numCols,
                        useRandom = true, maxSteps = 150_000) {

        const maxAttempts = numRows * numCols;

        for (let attempt = 0; attempt < maxAttempts; attempt++) {

            // Step 1: choose a random seed location
            const startRow = Math.floor(Math.random() * numRows);
            const startCol = Math.floor(Math.random() * numCols);

            // Step 1 check: must be open water
            if (ocean[startRow][startCol] !== 0) continue;

            // Step 2: all 8 neighbors must be water — no neighboring island land.
            let clearArea = true;
            for (let d = 0; d < 8; d++) {
                const nr = startRow + SWIsland.DR8[d];
                const nc = startCol + SWIsland.DC8[d];
                if (nr >= 0 && nr < numRows && nc >= 0 && nc < numCols) {
                    if (ocean[nr][nc] === 1) { clearArea = false; break; }
                }
            }
            if (!clearArea) continue;

            // Step 3: BFS reachability pre-check.
            // Temporarily stamp the seed so the BFS can start from it.
            ocean[startRow][startCol] = 1;
            const reachable = SWIsland.countReachableCells(
                startRow, startCol, ocean, numRows, numCols
            );
            if (reachable < targetSize) {
                // Not enough open water reachable from this seed — skip it.
                ocean[startRow][startCol] = 0;
                continue;
            }
            // Leave the seed stamped; buildIsland keeps ocean[startRow][startCol]=1.

            // Step 4: create the island and attempt recursive growth.
            const island = new SWIsland(new Coordinates(startRow, startCol));

            if (island.grow(targetSize, ocean, numRows, numCols, useRandom, maxSteps)) {
                return island;  // Step 5: SUCCESS — return the fully grown island.
            }

            // Step 6: growth failed or was aborted — restore seed to water.
            ocean[startRow][startCol] = 0;

            // If the build was aborted by the step limit, return the partial island
            // so the sketch can display the TOOSLOW warning.
            if (island.wasAborted()) return island;

            // Otherwise: continue trying new seed positions.
        }

        // All seed attempts exhausted — the ocean has no room for this island.
        return null;
    }//end buildIsland

    // ── toString ──────────────────────────────────────────────────────────────

    /**
     * Returns a human-readable description of this island.
     * Mirrors Island.toString() in Java: shows size and all (row, col) coordinates.
     *
     * Example: "SWIsland [size=5]: (3, 4) -> (3, 5) -> (4, 5) -> (5, 5) -> (5, 4)"
     */
    toString() {
        return `SWIsland [size=${this._cells.length}]: ` +
               this._cells.map(c => c.toString()).join(' -> ');
    }//end toString

}//end class SWIsland
