package com.basicalgorithms.jiuzhang.chapter04_breadth_first_search;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Given a boolean 2D matrix, 0 is represented as the sea, 1 is represented as the island.
 * If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.
 * Find the number of islands.
 * Example
 * Given graph:
 * [
 * [1, 1, 0, 0, 0],
 * [0, 1, 0, 0, 1],
 * [0, 0, 0, 1, 1],
 * [0, 0, 0, 0, 0],
 * [0, 0, 0, 0, 1]
 * ]
 * return 3.
 */

public class NumberOfIslands {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    public int numIslands(boolean[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int count = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (foundIsland(grid, i, j)) {
                    count++;
                }
            }
        }
        return count;
    }

    private static class GridPoint {
        private boolean[][] grid;
        private int rowIndex;
        private int columnIndex;

        public GridPoint(boolean[][] grid, final int rowIndex, final int columnIndex) {
            this.grid = grid;
            this.rowIndex = rowIndex;
            this.columnIndex = columnIndex;
        }


        public GridPoint getLeft() {
            if (columnIndex <= 0) {
                return null;
            }
            return new GridPoint(grid, rowIndex, columnIndex - 1);
        }


        public GridPoint getRight() {
            if (columnIndex >= grid[0].length - 1) {
                return null;
            }
            return new GridPoint(grid, rowIndex, columnIndex + 1);
        }

        public GridPoint getUp() {
            if (rowIndex <= 0) {
                return null;
            }
            return new GridPoint(grid, rowIndex - 1, columnIndex);
        }

        public GridPoint getDown() {
            if (rowIndex >= grid.length - 1) {
                return null;
            }
            return new GridPoint(grid, rowIndex + 1, columnIndex);
        }

        @Override
        public boolean equals(final Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            final GridPoint gridPoint = (GridPoint) o;

            if (rowIndex != gridPoint.rowIndex) return false;
            return columnIndex == gridPoint.columnIndex;

        }

        @Override
        public int hashCode() {
            int result = rowIndex;
            result = 31 * result + columnIndex;
            return result;
        }
    }

    private boolean foundIsland(final boolean[][] grid, int row, int column) {
        if (!grid[row][column]) {
            return false;
        }


        Queue<GridPoint> queue = new ArrayDeque<>();
        queue.offer(new GridPoint(grid, row, column));
        while (!queue.isEmpty()) {
            GridPoint gridPoint = queue.poll();
            removePoint(grid, gridPoint);

            if (gridPoint.getUp() != null && getIsland(grid, gridPoint.getUp())) {
                queue.offer(gridPoint.getUp());
            }

            if (gridPoint.getDown() != null && getIsland(grid, gridPoint.getDown())) {
                queue.offer(gridPoint.getDown());
            }

            if (gridPoint.getLeft() != null && getIsland(grid, gridPoint.getLeft())) {
                queue.offer(gridPoint.getLeft());
            }

            if (gridPoint.getRight() != null && getIsland(grid, gridPoint.getRight())) {
                queue.offer(gridPoint.getRight());
            }
        }
        return true;
    }

    private boolean getIsland(final boolean[][] grid, final GridPoint gridPoint) {
        return grid[gridPoint.rowIndex][gridPoint.columnIndex];
    }

    private void removePoint(final boolean[][] grid, final GridPoint gridPoint) {
        grid[gridPoint.rowIndex][gridPoint.columnIndex] = false;
    }

    @Test
    public void test1() throws Exception {
        boolean[][] source = {
                {
                        true, true, false, false, false
                },
                {
                        false, true, false, false, true
                },
                {
                        false, false, false, true, true
                },
                {
                        false, false, false, false, false
                },
                {
                        false, false, false, false, true
                }
        };

        int num = numIslands(source);
        Assert.assertEquals(num, 3);

    }


    /**
     * 本代码由九章算法编辑提供。版权所有，转发请注明出处。
     * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
     * - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，Big Data 项目实战班，
     * - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
     */

// version 1: BFS
    class Coordinate {
        int x, y;

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public class Solution01 {
        /**
         * @param grid a boolean 2D matrix
         * @return an integer
         */
        public int numIslands(boolean[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) {
                return 0;
            }

            int n = grid.length;
            int m = grid[0].length;
            int islands = 0;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j]) {
                        markByBFS(grid, i, j);
                        islands++;
                    }
                }
            }

            return islands;
        }

        private void markByBFS(boolean[][] grid, int x, int y) {
            // magic numbers!
            int[] directionX = {0, 1, -1, 0};
            int[] directionY = {1, 0, 0, -1};

            Queue<Coordinate> queue = new LinkedList<>();

            queue.offer(new Coordinate(x, y));
            grid[x][y] = false;

            while (!queue.isEmpty()) {
                Coordinate coor = queue.poll();
                for (int i = 0; i < 4; i++) {
                    Coordinate adj = new Coordinate(
                            coor.x + directionX[i],
                            coor.y + directionY[i]
                    );
                    if (!inBound(adj, grid)) {
                        continue;
                    }
                    if (grid[adj.x][adj.y]) {
                        grid[adj.x][adj.y] = false;
                        queue.offer(adj);
                    }
                }
            }
        }

        private boolean inBound(Coordinate coor, boolean[][] grid) {
            int n = grid.length;
            int m = grid[0].length;

            return coor.x >= 0 && coor.x < n && coor.y >= 0 && coor.y < m;
        }
    }

    // version 2: Union Find
    class UnionFind {

        private int[] father = null;
        private int count;

        private int find(int x) {
            if (father[x] == x) {
                return x;
            }
            return father[x] = find(father[x]);
        }

        public UnionFind(int n) {
            // initialize your data structure here.
            father = new int[n];
            for (int i = 0; i < n; ++i) {
                father[i] = i;
            }
        }

        public void connect(int a, int b) {
            // Write your code here
            int root_a = find(a);
            int root_b = find(b);
            if (root_a != root_b) {
                father[root_a] = root_b;
                count--;
            }
        }

        public int query() {
            // Write your code here
            return count;
        }

        public void set_count(int total) {
            count = total;
        }
    }

    public class Solution02 {
        /**
         * @param grid a boolean 2D matrix
         * @return an integer
         */
        public int numIslands(boolean[][] grid) {
            int count = 0;
            int n = grid.length;
            if (n == 0)
                return 0;
            int m = grid[0].length;
            if (m == 0)
                return 0;
            UnionFind union_find = new UnionFind(n * m);

            int total = 0;
            for (int i = 0; i < grid.length; ++i)
                for (int j = 0; j < grid[0].length; ++j)
                    if (grid[i][j])
                        total++;

            union_find.set_count(total);
            for (int i = 0; i < grid.length; ++i)
                for (int j = 0; j < grid[0].length; ++j)
                    if (grid[i][j]) {
                        if (i > 0 && grid[i - 1][j]) {
                            union_find.connect(i * m + j, (i - 1) * m + j);
                        }
                        if (i < n - 1 && grid[i + 1][j]) {
                            union_find.connect(i * m + j, (i + 1) * m + j);
                        }
                        if (j > 0 && grid[i][j - 1]) {
                            union_find.connect(i * m + j, i * m + j - 1);
                        }
                        if (j < m - 1 && grid[i][j + 1]) {
                            union_find.connect(i * m + j, i * m + j + 1);
                        }
                    }
            return union_find.query();
        }
    }

    // version 3: DFS (not recommended)
    public class Solution03 {
        /**
         * @param grid a boolean 2D matrix
         * @return an integer
         */
        private int m, n;

        public void dfs(boolean[][] grid, int i, int j) {
            if (i < 0 || i >= m || j < 0 || j >= n) return;

            if (grid[i][j]) {
                grid[i][j] = false;
                dfs(grid, i - 1, j);
                dfs(grid, i + 1, j);
                dfs(grid, i, j - 1);
                dfs(grid, i, j + 1);
            }
        }

        public int numIslands(boolean[][] grid) {
            // Write your code here
            m = grid.length;
            if (m == 0) return 0;
            n = grid[0].length;
            if (n == 0) return 0;

            int ans = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (!grid[i][j]) continue;
                    ans++;
                    dfs(grid, i, j);
                }
            }
            return ans;
        }
    }
}
