# -*- coding: utf-8 -*-
from scipy.misc import toimage
from random import randint

# plot a tiling for a 2*n by 2*n grid with missing square (mx, my)
def plot_tiling(n, mx, my):
    if mx < 0 or mx > 2**n or my < 0 or my > 2**n:
        print "Empty square is outside the grid"
        return
    g = Grid(n)
    g.tile(mx, my)
    g.plot_tiling()

class Grid:
    def __init__(self, n):
        self.n = n
        self.N = 2**n
        self.tiling = [[0] * self.N for i in range(self.N)]
        self.num_colors = 256
        self.next_tile = self._random_tile_color()
    
    # compute a tiling of the grid with missing square mx, my
    def tile(self, mx, my):    
        Subgrid(self, 0, 0, self.n).tile(mx, my)
             
    # add a tile with bottom left corner at (x, y) of a given shape
    # rx, ry indicates the removed corner position (0, 0), (0, 1), (1, 0) or (1, 1)
    def add_tile(self, x, y, rx, ry):
        for i in range(0, 2):
            for j in range(0, 2):
                if (i != rx or j != ry):
                    self.tiling[x + i][y + j] = self.next_tile
        self.next_tile = self._random_tile_color()
    
    # display the computed tiling
    def plot_tiling(self):
        dim = 512
        if self.n > 9:
            print "Image is too large to display"
        else:
            # calculate the scaling ratio
            ratio = dim / self.N
            
            # instantiate an array for the image
            image = [[0] * dim for i in range(dim)]

            # scale the tiling                
            for x in range(dim):
                for y in range(dim):
                    x0 = x/ratio
                    y0 = y/ratio
                    
                    if self.tiling[x0][y0] != 0:                    
                        image[x][y] = self.tiling[x/ratio][y/ratio]            
                    else:
                        image[x][y] = self.num_colors * ((x + y) % 2) 
                
        toimage(image).show()
        
    def _random_tile_color(self):
        return randint(1, self.num_colors)



class Subgrid(Grid):
    # instantiate a subgrid of grid with bottom left corner (x0, y0) and dimension 2**n by 2**n
    def __init__(self, grid, x0, y0, n):
        self.parent = grid
        self.x0 = x0
        self.y0 = y0
        self.n = n
        
    def tile(self, mx, my):
        if self.n == 1:
            self.add_tile(0, 0, mx, my)
        else:
            halfN = 2**(self.n - 1)

            # removed corner of central tile
            rx = mx / halfN
            ry = my / halfN
 
            for i in range(0, 2):
                for j in range(0, 2):
                    s = Subgrid(self, halfN * i, halfN * j, self.n - 1)
                    if i == rx and j == ry:
                        # tile quadrant containing removed square
                        s.tile(mx - halfN * i, my - halfN * j)
                    else:
                        # tile other quadrants
                        s.tile((1 - i) * (halfN - 1), (1 - j) * (halfN - 1))
            
            # cover central squares
            self.add_tile(halfN - 1, halfN - 1, rx, ry)
        
    def add_tile(self, x, y, rx, ry):
        self.parent.add_tile(x + self.x0, y + self.y0, rx, ry)