#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Ported to Python from https://gist.github.com/856138
# to render to PDF
#
# --------------------------------------------------------------------
# An implementation of a "weave" maze generator. Weave mazes are those
# with passages that pass both over and under other passages. The
# technique used in this program was described to me by Robin Houston,
# and works by first decorating the blank grid with the over/under
# crossings, and then using Kruskal's algorithm to fill out the rest
# of the grid. (Kruskal's is very well-suited to this approach, since
# it treats the cells as separate sets and joins them together.)
# --------------------------------------------------------------------

from random import shuffle, seed, randint
import argparse
import sys


def maze(width=10,
         height=10,
         density=50,
         _seed=None,
         draw_with_curves=True,
         filename='my_maze.pdf',
         use_A4=True,
         render_to='pdf',
         dislay_to_screen=False,
         generate_canvas_js=False,
         generate_js=False,
         return_pdf=False):

    # random, or not
    if _seed is None:
        _seed = randint(0, 90010000)
    seed(_seed)

    # constants to aid with describing the passage directions
    N, S, E, W, U = 0x1, 0x2, 0x4, 0x8, 0x10
    DX = {E: 1, W: -1, N: 0, S: 0}
    DY = {E: 0, W:  0, N: -1, S: 1}
    OPPOSITE = {E: W, W: E, N: S, S: N}

    #
    class Tree(object):

        def __init__(self):
            self.parent = None

        def root(self):
            if self.parent:
                return self.parent.root()
            return self

        def connected(self, tree):
            return(self.root() == tree.root())

        def connect(self, tree):
            tree.root().parent = self

    # structures to hold the maze
    grid = [[0 for x in range(width)] for x in range(height)]
    sets = [[Tree() for x in range(width)] for x in range(height)]

    # build the list of edges
    edges = []
    for y in range(height):
        for x in range(width):
            if y > 0:
                edges.append([x, y, N])
            if x > 0:
                edges.append([x, y, W])

    shuffle(edges)

    # build the over/under locations
    for cy in range(height - 2):
        cy += 1
        for cx in range(width - 2):
            cx += 1

            if randint(0, 99) < density:
                continue

            nx, ny = cx, cy - 1
            wx, wy = cx - 1, cy
            ex, ey = cx + 1, cy
            sx, sy = cx, cy + 1

            if (grid[cy][cx] != 0 or
                sets[ny][nx].connected(sets[sy][sx]) or
                sets[ey][ex].connected(sets[wy][wx])):
                continue

            sets[ny][nx].connect(sets[sy][sx])
            sets[ey][ex].connect(sets[wy][wx])

            if randint(0, 1) == 0:
                grid[cy][cx] = E | W | U
            else:
                grid[cy][cx] = N | S | U

            grid[ny][nx] |= S
            grid[wy][wx] |= E
            grid[ey][ex] |= W
            grid[sy][sx] |= N

            edges[:] = [(x, y, d) for (x, y, d) in edges if not (
              (x == cx and y == cy) or
              (x == ex and y == ey and d == W) or
              (x == sx and y == sy and d == N)
            )]

    # Kruskal's algorithm
    while edges:
        x, y, direction = edges.pop()
        nx, ny = x + DX[direction], y + DY[direction]

        set1, set2 = sets[y][x], sets[ny][nx]

        if not set1.connected(set2):
            set1.connect(set2)
            grid[y][x] |= direction
            grid[ny][nx] |= OPPOSITE[direction]

    # render options
    render_options = {'filename': filename,
                      'draw_with_curves': draw_with_curves,
                      'use_A4': use_A4,
                      'width': width,
                      'height': height}

    return_data = {}
    # to pdf, if we have a filename
    if filename or return_pdf:

        # TODO: this import isn't right
        try:
            from renderers.pdf import render
        except ImportError:
            from maze.renderers.pdf import render  # NOQA

        return_data['pdf'] = render(grid, render_options)

    # to screen
    if dislay_to_screen:
        try:
            from renderers.text import render
        except ImportError:
            from maze.renderers.text import render  # NOQA

        render(grid, render_options)

    if generate_canvas_js:
        try:
            from renderers.canvas import render
        except ImportError:
            from maze.renderers.canvas import render  # NOQA

        return_data['canvas'] = render(grid, render_options)

    if generate_js:
        try:
            from renderers.js import render
        except ImportError:
            from maze.renderers.js import render  # NOQA

        return_data['js'] = render(grid, render_options)

    return return_data


if __name__ == "__main__":

    parser = argparse.ArgumentParser(description='Generate a maze')

    parser.add_argument('-W', dest="width", type=int,
        help='width (default=21)', default=21)

    parser.add_argument('-H', dest="height", type=int,
        help='height (default=30)', default=30)

    parser.add_argument('-D', dest="density", type=int,
        help='density (default=50)', default=50)

    parser.add_argument('-C', dest="draw_with_curves", type=int,
        help='Draw with curves -C 1, 0 is all straight lines', default=1)

    parser.add_argument('-A', dest="use_A4", type=int,
    help='Select A4 page size 1 selects A4 (default), 0 selects 8.5x11 inches',
        default=1)

    parser.add_argument('-f', dest="filename", type=str, default='',
        help='PDF filename')

    parser.add_argument('-t', dest="dislay_to_screen", action='store_true',
        help='Displays maze as text output')

    parser.add_argument('-x', dest="generate_canvas_js", action='store_true',
        help='returns canvas html paths in a python dictionary')

    parser.add_argument('-j', dest="generate_js", action='store_true',
        help='returns canvas js commands in a python dictonary')

    parser.add_argument('-p', dest="return_pdf", action='store_true',
        help='returns pdf data in a python dictionary')

    args = parser.parse_args()

    if len(sys.argv) == 1:
        parser.print_help()

    else:
        maze(**vars(args))

#
