"""
Bucket Fill Exercise

Imagine you are working on an image editing application. You need to implement a bucket fill tool similar to the one
in paint. The user will use the tool by selecting a color and clicking on the canvas. The tool fills the selected
region of color with the new color.

When a pixel is filled, all of its neighbors (above, below, left, or right) of the same color must also be filled,
as well as their neighbors, and so on, until the entire region has been filled with the new color.

In this exercise, you must write *TWO* implementations of the tool. Each implementation must be different. It is not
required that you invent the solutions yourself. You are encouraged to research the problem. Please write documentation
explaining the difference of each implementation, such as when one solution might be more appropriate than the other.
Don't forget to validate input. There is one existing test, however, you might consider adding some more. Keep in mind
that although the given canvas is small, the solution should be applicable for a real canvas that could have huge
resolutions.

Please use python3 to complete this assignment.
"""
import queue
from scipy.ndimage.measurements import label
import numpy as np



class Canvas(object):
    def __init__(self, pixels):
        self.pixels = pixels

    def __str__(self):
        return '\n'.join(map(lambda row: ''.join(row), self.pixels))

    def fill(self, x, y, color):
        """
        Fills a region of color at a given location with a given color.

        :param x:  the x coordinate where the user clicked
        :param y: the y coordinate where the user clicked
        :param color: the specified color to change the region to
        """
        raise NotImplementedError  # Override this function in the Solution classes


class Solution1(Canvas):
    # TODO write documentation

    def fill(self, x, y, color):
        bucket = self.pixels

        b_height = len(bucket)
        b_width = len(bucket[0])

        start = bucket[x][y]
        bucket[x][y] = color

        q = queue.Queue()
        q.put([x, y])

        visited = set()
        visited.add((x, y))

        while not q.empty():
            i, j = q.get(0)

            # color bucket position (i, j-1) with color
            if (0 <= i < b_height) and (0 <= (j-1) < b_width) and ((i, j-1) not in visited):
                    visited.add((i, j-1))
                    if (bucket[i][j-1] == start):
                        bucket[i][j-1] = color
                        q.put([i, j-1])

            # color bucket position (i, j+1) with color
            if (0 <= i < b_height) and (0 <= (j+1) < b_width) and ((i, j+1) not in visited):
                    visited.add((i, j+1))
                    if (bucket[i][j+1] == start):
                        bucket[i][j+1] = color
                        q.put([i, j+1])

            # color_bucket (i+1, j) position
            if (0 <= (i+1) < b_height) and (0 <= j < b_width) and ((i+1, j) not in visited):
                    visited.add((i+1, j))
                    if (bucket[i+1][j] == start):
                        bucket[i+1][j] = color
                        q.put([i+1, j])

            # color_bucket (i-1, j) position
            if (0 <= (i-1) < b_height) and (0 <= j < b_width) and ((i-1, j) not in visited):
                    visited.add((i-1, j))
                    if (bucket[i-1][j] == start):
                        bucket[i-1][j] = color
                        q.put([i-1, j])

        self.pixels = bucket



class Solution2(Canvas):
    # TODO write documentation

    def color_bucket(self, x, y, start, color):
        # print(x,y, start, color)
        if (start == color):
            return

        if (0 <= x < len(self.pixels)) and (0 <= y < len(self.pixels[0])) and self.pixels[x][y] == start:
            self.pixels[x][y] = color
        else:
            return

        self.color_bucket(x, y - 1, start, color)
        self.color_bucket(x, y + 1, start, color)
        self.color_bucket(x + 1, y, start, color)
        self.color_bucket(x - 1, y, start, color)

    def fill(self, x, y, color):
        start = self.pixels[x][y]
        self.color_bucket(x, y, start, color)



def test_solution(impl):
    s = impl([
        ['O', 'X', 'X', 'X', 'X'],
        ['X', 'O', 'O', 'O', 'X'],
        ['X', 'O', '#', 'O', 'X'],
        ['X', 'O', 'O', 'O', 'X'],
        ['X', 'X', 'X', 'X', 'X'],
        ['X', 'X', 'X', '#', '#'],
        ['X', 'X', 'X', 'X', 'X']
    ])
    s.fill(0, 1, '*')
    # print(s)
    s.fill(5, 4, 'O')
    # print(s)
    s.fill(2, 2, '@')
    # print(s)
    #
    assert str(s) == 'O****\n*OOO*\n*O@O*\n*OOO*\n*****\n***OO\n*****'


    a = impl([
        ['O', 'X', 'O', 'X', 'O']
    ])

    a.fill(0, 0, 'X')
    # print(a)
    # Output(BFS): XXOXO
    # Output(DFS): XXOXO

    a.fill(0, 4, '#')
    # print(a)
    # Output(BFS): XXOX#
    # Output(DFS): XXOX#

    assert str(a) == 'XXOX#'


#-------------------------------------------------------------


    b = impl([
        ['O', 'O', 'O', 'O', 'O']
    ])

    b.fill(0, 0, 'X')
    # print(b)
    # # Output(BFS): XXXXX
    # # Output(DFS): XXXXX
    #
    b.fill(0, 2, 'X')
    # print(b)
    # # Output(BFS): XXXXX
    # # Output(DFS): XXXXX
    #
    b.fill(0, 4, 'X')
    # print(b)
    # Output(BFS): XXXXX
    # Output(DFS: XXXXX

    assert str(b) == 'XXXXX'


#---------------------------------------------------------------

    c = impl([
        ['O']
    ])

    c.fill(0, 0, 'X')
    # print(c)
    # Output(BFS): X
    # Output(DFS): X

    assert str(c) == 'X'



# ---------------------------------------------------------------


    d = impl([
        ['X'],
        ['X'],
        ['X'],
        ['X'],
        ['X']
    ])

    d.fill(0, 0, '#')
    # print(d)
    # # Output(BFS):
    # # #
    # # #
    # # #
    # # #
    # # #
    #
    # # Output(DFS):
    # # #
    # # #
    # # #
    # # #
    # # #
    #
    d.fill(2, 0, '#')
    # print(d)
    # # Output(BFS):
    # # #
    # # #
    # # #
    # # #
    # # #
    #
    # # Output(DFS):
    # # #
    # # #
    # # #
    # # #
    # # #

    assert str(d) == '#\n#\n#\n#\n#'



# ---------------------------------------------------------------

    e = impl([
        ['X', '#'],
        ['X', '#']
    ])

    e.fill(1, 1, 'X')
    # print(e)
    # # Output(BFS):
    # # XX
    # # XX
    #
    # # Output(DFS):
    # # XX
    # # XX
    #
    e.fill(1, 0, '#')
    # print(e)
    # # Output(BFS):
    # # ##
    # # ##
    # #
    # # Output(DFS):
    # # ##
    # # ##

    assert str(e) == '##\n##'



if __name__ == '__main__':
    test_solution(Solution1)
    test_solution(Solution2)