'''
Created on Mar 19, 2016
@author: Brett Paufler
(c) Copyright Brett Paufler


#TODO - how to test???

TODO: Need to refactor again
    
'''

import random
from random import choice, shuffle, randint
from collections import deque

from maze_squares import checkered_grid
from skimage import io




def random_wall_code():
    '''Returns a random wall code.'''
    
    return choice('NSEW')


def opposite_wall(wall):
    '''Returns the code for the opposite wall.   
        S for N, N for S, E for W, W for E.'''
    
    opposite = {'N':'S', 'S':'N', 'E':'W', 'W':'E' }
    return opposite[wall]



class Cell():
    '''Individual cell (space) in the maze (grid).'''
    
    def __init__(self, row, col):
        '''Each row/col pair taken together form an ID and must be unique.
        
        N, S, E, W are walls and initialized to zero, which means a wall is present
            0 = black, 0 = wall
            1 = white, 1 = open space.''' 
        
        self.row = row
        self.col = col
        self.N = 0
        self.S = 0
        self.E = 0
        self.W = 0
    
    
    def __repr__(self):
        text = 'CELL (%d, %d): N:%d, S:%d, E:%d, W:%d' % (
                    self.row, self.col, self.N, self.S, self.E, self.W)
        return text
    
    
    def __str__(self):
        '''Returns wall values as text ('NSEW')
            '0000' would be starting default return value.'''
        return str(self.N) + str(self.S) + str(self.E) + str(self.W)


    def sum(self):
        '''Returns the summed value of the wall/passages.
        
        0 = no passages (all walls)
        4 = all passages (i.e. a room, so no walls).'''
        
        return self.N + self.S + self.E + self.W


    #def is_all_black(self):
    #    '''True there are no passages, all walls.'''
    #    
    #    return self.sum() == 0
    
    
    #def is_all_white(self):
    #    '''True if there are no walls, all passages.'''
    #    
    #    return self.sum() == 4
    
    
    def checkered_code(self):
        '''Returns 'pattern' for this cell as needed to feed into checkered_tile.
        
        This might be an ideal place to implement special img types.'''
        
        if self.sum() == 0:
            return '000000000'
        if self.sum() == 4:
            return '111111111'
        return '0%d0%d1%d0%d0' % (self.N, self.W, self.E, self.S)


    def set_solid(self, val=0):
        '''Sets all of the cells wall to val.'''

        for w in 'NSEW':
            setattr(self, w, val)


class Maze():
    '''Cell holding structure that forms a maze/grid.'''
    
    def __init__(self, width=10, height=10, lines=True):
        '''Maze/Grid holding structure.
        
        width: (internally cols) number of cell units wide
        height: (internally rows): number of cell units tall
            cells will ultimately equal tiles in maze_squares
        
        lines: if true, white areas will be drawn with grids
            used as a pass-through to checkered_tiles.lines
         '''

        self.rows = height
        self.cols = width
        self.lines = lines
        
        self.cells = []
        self.init_cells(self.rows, self.cols)
        
    def init_cells(self, rows, cols):
        '''Rebuilds cells list, zeroing out all cells in process.'''
        self.cells = []
        for row in range(rows):
            for col in range(cols):
                self.cells.append(Cell(row, col))


    #def cell_text_list(self):
    #    '''Returns a list of cell wall values as text.
    #        
    #        ['0101', '1111', '0000'...]'''
    #    
    #    return [str(cell) for cell in self.cells]

    
    def __repr__(self):
        '''Looks good... limited to mazes in sort order.'''
        
        m_text = [str(cell) for cell in self.cells]
        text = []
        
        for r in range(0, self.rows * self.cols, self.cols):
            text.append(' '.join(m_text[r:r+self.cols]))
        
        return '\N'.join(text)
    
    
    #Cells don't have nums, nodes do
    #def cell_by_num(self, num):
    #    return [cell for cell in self.cells if cell.num == num][0]
    
    def cell_by_index(self, row, col):
        '''Given row, col, returns corresponding cell.
        
        No check for uniqueness at this time.'''
        
        return [cell for cell in self.cells if 
                    cell.row == row and cell.col == col][0]
    
    
    def set_all_walls(self, val=0):
        '''Set all walls in maze to the same value.
        
        val = 0, sets all to black, walls
              1, sets to white, open'''
        
        for cell in self.cells:
            for c in 'NSEW':
                setattr(cell, c, val)


    def random(self, val=None, num_cells=None, num_walls=None, safety=True):
        '''Randomizes the maze to some random extent.
        
        For all parameters if None is passed,
            defaults to most random
        
        val = 0 for black, wall
              1 for white, open
              None = random
              
        num_cells = any positive integer
                    None = all
                    
        num_walls = 1-4 
                    None = all four walls'''
        
        #cells to be effected
        if num_cells:
            row_col = [(randint(0, self.rows - 1), randint(0, self.cols - 1))
                   for _ in range(num_cells)]
        else:
            row_col = [(r,c) for r in range(self.rows) for c in range(self.cols)] 
        
        for r, c in row_col:
            walls = ['N', 'S', 'E', 'W']
            shuffle(walls)
            if num_walls:
                walls = walls[:num_walls]
        
            for w in walls:
                v = val if val else choice([0, 1])
                setattr(self.cell_by_index(r, c), w, v)
        
        #because how many times do you need to deal with this error
        #Prevents off the board run aways
        if safety:
            self.edges_black()
            

    def save_image(self, sN='./output/Maze_Test.png'):
        '''Saves Maze to disk.
        
        sN = output name complete with path.'''
        
        pattern_list = [cell.checkered_code() for cell in self.cells]
        img = checkered_grid(pattern_list, (self.cols, self.rows), lines=self.lines)
        io.imsave(sN, img)


    def edges_black(self):
        '''Makes sure all the walls that touch edges are all black (0).'''
        
        for cell in self.cells:
            if cell.row == 0:
                cell.N = 0
            if cell.row == self.rows - 1:
                cell.S = 0
            if cell.col == 0:
                cell.W = 0
            if cell.col == self.cols - 1:
                cell.E = 0
    
    #Could use a test
    def neighbors(self, cell, val=None):
        '''Returns list of cells that are adjacent to passed coordinates.
        
        val:
            None = returns all neighbors
            1 = returns only white, passage ways
            0 = returns only black, walls
        '''
        
        neighbours = []

        if cell.row - 1 >= 0:
            neighbours.append(self.cell_by_index(cell.row - 1, cell.col))
        if cell.row + 1 <= self.rows - 1:
            neighbours.append(self.cell_by_index(cell.row +1, cell.col))
        if cell.col - 1 >= 0:
            neighbours.append(self.cell_by_index(cell.row, cell.col - 1))
        if cell.col + 1 <= self.cols - 1:
            neighbours.append(self.cell_by_index(cell.row, cell.col + 1))
        
        if val is not None:
            #print 'Fires', val
            neighbours = [cell for cell in neighbours if cell.sum() == val]
        #else:
            #print 'No Fires', val
        
        return neighbours


    #Included in Neighbors
    #def neighbors_black(self, cell):
    #    '''Returns neighbors_all that are have no passages,
    #    (i.e. that sum to 0).'''
    #    
    # #   return [i for i in self.neighbors_all(cell) if i.sum() == 0]
    
    
    def wall_between(self, cell_1, cell_2, no_wall=True):
        '''Adds (or eliminates) the walls between two cells.
            
        cell_1, cell_2 are the two cells in question
            No error checking
            Presumes cells are next to each other.
        
        no_wall:
            True = eliminates any wall if present
            False = adds a wall if none present'''
        
        if cell_1.row != cell_2.row:
            if cell_1.row < cell_2.row:
                cell_1.S = 1 if no_wall else 0
                cell_2.N = 1 if no_wall else 0
            else:
                cell_1.N = 1 if no_wall else 0
                cell_2.S = 1 if no_wall else 0
        if cell_1.col != cell_2.col:
            if cell_1.col < cell_2.col:
                cell_1.E = 1 if no_wall else 0
                cell_2.W = 1 if no_wall else 0
            else:
                cell_1.W = 1 if no_wall else 0
                cell_2.E = 1 if no_wall else 0
    

    def maze_stack(self):
        '''Uses the 'Stack' Algorithm to make a maze.
        
        Start at random
        If can, connect to random adjoining cell,
            add adjoining to stack, repeat while can
        if no can, pop value off stack,
            and see if can
        When  nada on the stack, everything is connected.'''
        
        stack = [] #deque()
        r = random.randint(0, self.rows - 1)
        c = random.randint(0, self.cols - 1)
        current = self.cell_by_index(r, c)
        stack.append(current)
        
        while stack:
            black_neighbors = self.neighbors(current, val=0)
            #print current
            #print black_neighbors
            if black_neighbors:
                next_move = choice(black_neighbors)
                #print next_move
                self.wall_between(current, next_move)
                stack.append(next_move)
            else:
                current = stack.pop()


    def kill_spurs(self, both=False, safe_list=None):
        '''Turns 1 entry (sum =1) cells to 0 entry (sum=0) cells.
        
        both = True, removes the spur from the connecting cell, as well
            which has the effect of removing rooms.'''
        
        for cell in (cell for cell in self.cells if cell not in safe_list):
            if cell.sum() == 1:
                if cell.N == 1:
                    cell.N = 0
                    if both:
                        setattr(self.cell_by_index(cell.row - 1, cell.col), 'S', 0)
                elif cell.S == 1:
                    cell.S = 0
                    if both:
                        setattr(self.cell_by_index(cell.row + 1, cell.col), 'N', 0)
                elif cell.E == 1:
                    cell.E = 0
                    if both:
                        setattr(self.cell_by_index(cell.row, cell.col + 1), 'W', 0)               
                elif cell.W == 1:
                    cell.W = 0
                    if both:
                        setattr(self.cell_by_index(cell.row, cell.col - 1), 'E', 0)                
    
    
    def neighbor_cell(self, cell, wall):
        '''Returns the neighbor cell beyond the indicated wall.
        
        cell, 'N' returns the cell to the north of cell.
        
        No error checking, presumes neighbor is on the board.
            One of the many reasons black_edges to important.'''
        
        row = cell.row
        col = cell.col
        if wall == 'N':
            row -= 1
        elif wall == 'S':
            row += 1
        elif wall == 'E':
            col += 1
        elif wall == 'W':
            col -= 1
        else:
            assert wall in 'NSEW'
            
        return self.cell_by_index(row, col)


    def kill_deadends(self, safe_list=None):
        '''Removes passages that do not terminate in rooms.'''
        
        for cell in (cell for cell in self.cells if cell not in safe_list):
            if cell.sum() != 4: #skip rooms
                for wall in 'NSEW':
                    wall_value = getattr(cell, wall)
                    if wall_value == 1:
                        neighbor_cell = self.neighbor_cell(cell, wall)
                        neighbor_wall = opposite_wall(wall)
                        neighbor_wall_value = getattr(neighbor_cell, neighbor_wall)
                        if neighbor_wall_value == 0:
                            setattr(cell, wall, 0) 

    
    def connected_list(self, cell):
        '''Returns list of all cells cell is connected to.
        
        Note: a cell is always connected to itself.'''
        
        to_visit = [cell]
        visited = set()
        
        while to_visit:
            current = to_visit.pop()
            visited.add(current)
            for wall in 'NSEW':
                
                #1 is a passage leading out, 0 is a wall
                if 1 == getattr(current, wall):
                    cell_next_door = self.neighbor_cell(current, wall)
                    
                    #cell_next_door must have a corresponding passage back (i.e. a 1)
                    if 1 == getattr(cell_next_door, opposite_wall(wall)):
                        if cell_next_door not in visited:
                            to_visit.append(cell_next_door)
        return visited
        
    def is_connected(self, cell_1, cell_2):
        '''True if a path from cell_1 leads to cell_2.'''
        
        return cell_2 in self.connected_list(cell_1)


    def kill_small_areas(self, cut_off=10):
        '''Kill areas that link to less than cut_off value.'''
        
        #no need process all black (0 value cells)
        cells = [cell for cell in self.cells if cell.sum() != 0]
        
        #cells is the stack
        while cells:

            #get a list of connecgted cells and process
            connected = self.connected_list(cells[0])
            for c in connected:
                #set to black if a small area
                if len(connected) < 10:
                    c.set_solid(val=0)
                #either way, this cell (c) has been processed
                cells.remove(c)
            
    
    def pattern_loops(self):
        '''Adds the loop pattern to existing maze.
        
        Note: if only want loops, need to clear first.'''
        
        for row in range(self.rows):
            for col in range(self.cols):
                cell = self.cell_by_index(row, col)
                if row % 2 == 0:
                    cell.S = 1
                else:
                    cell.N = 1
                if col % 2 == 0:
                    cell.E = 1
                else:
                    cell.W = 1

            
    def pattern_rows(self):
        '''Adds horizontal rows to existing maze.
        
        Note: if only want horizontal rows, need to clear first.'''
        
        for cell in self.cells:
            if cell.col != 0:
                cell.W = 1
            if cell.col != self.cols - 1:
                cell.E = 1
                
    
    def pattern_cols(self):
        '''Adds vertical columns to existing maze.
        
        Note: if only want vertical columns, need to clear first.'''
        
        for cell in self.cells:
            if cell.row != 0:
                cell.N = 1
            if cell.row != self.rows - 1:
                cell.S = 1


    def pattern_rooms(self, num, edge_black=True):
        '''Places num random rooms (all white walls) in maze.'''
        
        for _ in range(num):
            cell = choice(self.cells)
            cell.set_solid(val=1)
        if edge_black:
            self.edges_black()


    def maze_connected(self, target=None):
        '''Uses the 'Connected' Algorithm to make a maze.
        
        target: is minimum lenght of connected maze
        
        This selectes a random cell to build from each time.
            So, different effect if each cell only chosen once.
        '''
        
        #target correction
        max_size = self.rows * self.cols
        target = target if target else max_size
        target = target if target <= max_size else max_size

        current = choice(self.cells)
        while target > len(self.connected_list(current)):
            
            #next iteration cell is randomly selected
            current = choice(self.cells)
            
            #random neighbor
            neighbor = choice(self.neighbors(current))
            self.wall_between(current, neighbor, no_wall=True)
 
        self.edges_black()

    
    def clean_up(self, safe_list=None, two_corners=False):
        '''Runs kill_dead end kill_spur multiple times.
        
        safe_list are cells not to kill
        two_corners adds upper_left, lower_right to safe_list.'''
        
        safe_list = safe_list if safe_list else []
        
        #adds upper_left and lower_right to safe_list (default)
        if two_corners:
            safe_list.append(self.cell_by_index(0, 0))
            safe_list.append(self.cell_by_index(self.rows - 1, self.cols - 1))
        
        for _ in range(50):
            self.kill_deadends(safe_list=safe_list)
            self.kill_spurs(safe_list=safe_list)


    #THIS IS STILL SORT OF WEAK
    #Effectively punches a hole, but maze rarely connected afterwards
    def pattern_hole_punch(self, val=0):
        '''Punches hole in center of maze, sets all values in center to val'''
        r = self.rows / 4
        c = self.cols / 4
        
        hole_cells = [cell for cell in self.cells if 
                        (r < cell.row < r * 3)
                        and
                        (c < cell.col and cell.col < c * 3)]
       
        print len(hole_cells)
        for cell in hole_cells:
            cell.set_solid(val=val)
    
    def passage_horizontal(self, row, col_start, col_finish):
        
        #automatic reversal
        if col_start > col_finish:
            col_start, col_finish = col_finish, col_start
        
        for col in range(col_start, col_finish):
            self.cell_by_index(row, col).E = 1
        for col in range(1 + col_start, 1 + col_finish):
            self.cell_by_index(row, col).W = 1


    def passage_vertical(self, col, row_start, row_finish):
        
        #automatic reversal
        if row_start > row_finish:
            row_start, row_finish = row_finish, row_start
        
        for row in range(row_start, row_finish):
            self.cell_by_index(row, col).S = 1
        for row in range(1 + row_start, 1 + row_finish):
            self.cell_by_index(row, col).N = 1

if __name__ == '__main__':
    
    for N in range(1, 3):
        #hole punch
        width = 25
        height = 25
        m = Maze(width=width, height=height)
        m.maze_stack()
        m.random(val=1, num_cells=100, num_walls=1)
        m.pattern_hole_punch()
        #m.clean_up()
        #m.maze_stack()
        #m.pattern_hole_punch()
        #m.clean_up()
        #m.maze_stack()
        #m.pattern_hole_punch()
        m.clean_up()
        m.kill_small_areas()
        m.save_image('./output/maze_banner_hole_%d.png' % (N))
    
    '''
    for N in range(1, 2):
        m = Maze(width=10, height=10, lines=True)
        print
        print m
        m.pattern_rows()
        print
        print m
        m.pattern_rooms(num=10, edge_black=True)
        print
        print m
        m.maze_connected()
        print
        print m
        m.clean_up(two_corners=True)
        m.save_image('./output/maze_rows_connected_%d.png' % N)
        print
        print m
    '''
    '''
    m.kill_small_areas(cut_off=25)
    m.save_image('./output/maze_3_kil_small.png')
    print
    print m
    m.clean_up()
    m.save_image('./output/maze_4_clean_final.png')
    print
    print m
    '''
    
    '''
    #CAN KILL - THIS IS IN maze_output
    #Random Walls, +/- clean_up
    m = Maze()
    for N in range(6):
        m.random(val=1, num_cells=None, num_walls=1)
        m.edges_black()
        this = deepcopy(m)
        this.clean_up()
        sM = './output/maze_random_%d.png' % N
        sThis = './output/maze_random_clean_%d.png' % N
        m.save_image(sM)
        this.save_image(sThis)
    print m
    '''