#!/usr/bin/python
# -*- coding: utf-8 -*-

# Copyright (C) 2014 Rod Engerstad

from __future__ import division

import math
from math import sqrt
import random
from random import randint
import Tkinter as tk
import tkColorChooser
# import sys

from pzl_lib import PzlG
from pzl_lib import SettingsB
from pzl_lib import Preferences
from pzl_lib import MenuItem
from pzl_lib import ViewB
from pzl_lib import Flasher
from pzl_lib import ScreenShot
from pzl_lib import Toolbar
from pzl_lib import Menu
from pzl_lib import ClockBox
from pzl_lib import EntryBox
from tetrofit_data import ModelData


class Vec2D(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, v):
        return Vec2D(self.x + v.x, self.y + v.y)

    def __sub__(self, v):
        return Vec2D(self.x - v.x, self.y - v.y)

    # nb Scalar multiply and divide!

    def __mul__(self, s):
        return Vec2D(self.x * s, self.y * s)

    def __truediv__(self, s):
        return Vec2D(self.x / s, self.y / s)

    def __abs__(self):
        return sqrt(self.x ** 2 + self.y ** 2)

    def __str__(self):
        return '(%g, %g)' % (self.x, self.y)


class Sgg(object):
    """
    Game globals
    """

    logger = None

    puzzle_width = 8
    puzzle_height = 5
    tetro_count = puzzle_width * puzzle_height / 4
    SQUARE_SIZE = 24

    # square units
    SOURCE_WIDTH = 10
    MARGIN = 1
    SQUARES_ACROSS = SOURCE_WIDTH + MARGIN * 2

    # pixels

    canvas_height = None
    canvas_width = None


class Settings(SettingsB):

    def __init__(self):
        SettingsB.__init__(self)
        self.max_ani_time = None
        self.dic = {}
        self.dic['set_colour'] = 'O'
        self.dic['O'] = '#00FDFF'
        self.dic['I'] = '#FFFF00'
        self.dic['T'] = '#FF00FF'
        self.dic['J'] = '#0000FF'
        self.dic['L'] = '#FF8000'
        self.dic['S'] = '#00FF00'
        self.dic['Z'] = '#FF0000'
        self.dic['Table_Colour'] = '#D3D7CF'
        self.dic['Source_Colour'] = '#888A85'
        self.dic['Target_Colour'] = '#2c2c2c'
        self.dic['Grid_Colour'] = 'grey'
        self.dic['font_size'] = '1'
        self.dic['set_square_size'] = '24'
        self.counter_font_size = -20
        self.entry_box_width = 14
        self.original_entry_box_width = 14
        self.plot_width = None
        self.plot_height = None
        self.menu_items = []
        self.dic['size_nine_width'] = '6'

        self.preferences = Preferences(self.dic)
        self.preferences.load()
        Sgg.SQUARE_SIZE = int(self.dic['set_square_size'])
        self.load_menus()
        self.count = len(self.menu_items)
        self.set_fonts()
        self.make_help()
        self.make_tooltip()

    def make_tooltip(self):
        self.tooltip_text = [
            _('New game'),
            _('Show solution')
            ]

    def make_help(self):
        self.help_text = _("At the top of the display is a Toolbar. The jigsaw icon at the left is a menu which has options for counting the number of solutions, setting the tetromino size and the width for 9 tetromino puzzles, changing the colours and for saving the current settings. To the right of the jigsaw icon is a diamond shaped icon. A left click on this will randomly select a built-in puzzle for a new game, and a right click will choose the next puzzle. If you give up on solving the puzzle, a click on the sad smiley icon will show a solution. To the right of the sad smiley is an entry box. This can be used to select the number of a built-in puzzle or for entering the symbols (IJLOTSZ) for a new puzzle. The allowed numbers of symbols are: 4, 6, 7, 8, 9 and 10. Once they are entered the program will try to find a solution. Finish puzzle numbers and sets of new puzzle symbols using the Enter key. Below the Toolbar are two rectangular grids. The top, called the target, is used to build the solution, and the lower is the source and contains the moveable tetrominoes. During the game the tetrominoes are moved using the mouse. Grab a tetromino with the left mouse button. Drop it by releasing the button. Right-clicking will rotate it 90 degrees. Tetrominoes dropped in the source grid will immediately return to their starting slot. Those dropped completely inside the target grid will be snapped into alignment with the the nearest intersection of the grid. There are 50 built-in puzzles for each of the grid sizes 5x4, 6x4, 7x4, 8x4, 6x6, 9x4 and 8x5. Within each 50 the puzzles are sorted in order of difficulty, hardest last.")

    def load_menus(self):
        self.menu_items.append(MenuItem(
            _('Tetro Size'),
            [
                '16',
                '24',
                '32',
                '40',
            ],
            '',
            [
                '16',
                '24',
                '32',
                '40',
            ],
            'set_square_size'
        ))

        self.menu_items.append(MenuItem(
            _('Size Nine Width'),
            [
                '6',
                '9',
            ],
            '',
            [
                '6',
                '9',
            ],
            'size_nine_width'
        ))

        self.menu_items.append(MenuItem(
            _('Set Colour'),
            [_('I'),
             _('J'),
             _('L'),
             _('O'),
             _('S'),
             _('T'),
             _('Z'),
             _('Table_Colour'),
             _('Source_Colour'),
             _('Target_Colour'),
             _('Grid_Colour'),
            ],
            'N',
            ['I',
             'J',
             'L',
             'O',
             'S',
             'T',
             'Z',
             'Table_Colour',
             'Source_Colour',
             'Target_Colour',
             'Grid_Colour',
            ],
            'set_colour'
        ))

        self.menu_items.append(MenuItem(
            _('Count Solutions'),
            '',
            '',
            '',
            'count_solutions'
        ))

        self.menu_items.append(MenuItem(
            _('Save Settings'),
            '',
            '',
            '',
            'save_settings'
        ))
        self.menu_items.append(MenuItem(
            _('Help'),
            '',
            '',
            '',
            'help'
        ))
        self.menu_items.append(MenuItem(
            _('About'),
            '',
            '',
            '',
            'about'
        ))


class Tetros(object):
    """
    There are 7 tertrominoes: Z, S, L, J, T, O, I
    Their simple x,y coords in one orientation are in tetro_dic.
    For drawing we need tetro outlines and they are laboriously
    calculated from the simple coords by to_outline.
    Puzzle solutions are produced in simple form and also need
    to be filled out for drawing.
    """
    tetro_dic = {
        'I': [[0, 0], [1, 0], [2, 0], [3, 0]],
        'J': [[0, 0], [1, 0], [2, 0], [2, 1]],
        'L': [[2, 0], [2, 1], [0, 1], [1, 1]],
        'O': [[0, 0], [1, 0], [1, 1], [0, 1]],
        'S': [[1, 0], [2, 0], [0, 1], [1, 1]],
        'T': [[0, 0], [1, 0], [2, 0], [1, 1]],
        'Z': [[0, 0], [1, 0], [1, 1], [2, 1]]}

    names = ['I', 'J', 'L', 'O', 'S', 'T', 'Z']

    def __init__(self):
        self.outline_dic = {}
        self.make_all_outlines()

    def make_all_outlines(self):
        names = ['O', 'T', 'I', 'Z', 'J', 'L', 'S']
        for name in names:
            coords = Tetros.tetro_dic[name]
            self.outline_dic[name] = self.make_outline(coords)

    def make_outline(self, coords):
        """
        Generate the outlines of the tetrominoes ready for drawing.
        Surely there's a simpler way!
        """
        incs = [(-0.5, -0.5), (0.5, -0.5), (0.5, 0.5), (-0.5, 0.5)]
        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        right = [1, 2, 3, 0]
        left = [3, 0, 1, 2]

        coords = sorted(coords)
        solid_0 = set([])
        for coord in coords:
            for i in range(4):
                inc = incs[i]
                solid_0.add((coord[0] + inc[0] + 0.5,
                             coord[1] + inc[1] + 0.5))

        # get top left

        x_min = 99.
        y_min = 99.
        delta = 0.1
        for item in solid_0:
            y_min = min(item[1], y_min)
        item_0 = None
        for item in solid_0:
            if item[1] + delta > y_min and\
               item[1] - delta < y_min and\
               item[0] < x_min:
                x_min = item[0]
                item_0 = item

        solid_1 = set([])
        for item in solid_0:
            solid_1.add((int(item[0]), int(item[1])))

        top_left = [int(item_0[0]), int(item_0[1])]

        """
        If we count neighbours of items in solid we find that
        items with 2 and 4 neighbours lie on the outside and
        that if we are following the outside clockwise, having
        2 neighbours signifies a right turn and 4 a left turn,
        otherwise we continue in the current direction.
        """
        turn_dic = {}
        for item in solid_1:
            nbrs = 0
            for direction in dirs:
                tmp = item[0] + direction[0], item[1] + direction[1]
                if tmp in solid_1:
                    nbrs += 1
            if nbrs == 2:
                turn_dic[tuple(item)] = 'right'
            elif nbrs == 4:
                turn_dic[tuple(item)] = 'left'
            else:
                turn_dic[tuple(item)] = ' '

        """
        Starting at top_left as the first corner we track clockwise
        through turn_dic to find the corner coordinates of
        the tetro outlines needed for drawing.
        """
        coord = top_left
        dir_i = 0
        corners = []
        corner = tuple(coord)
        corners.append(corner)
        direction = dirs[dir_i]
        while True:
            coord = [coord[0] + direction[0], coord[1] + direction[1]]

            tn = tuple(coord)
            td = turn_dic[tn]

            if td == 'right':
                corners.append(tn)
                dir_i = right[dir_i]
                direction = dirs[dir_i]
            elif td == 'left':
                corners.append(tn)
                dir_i = left[dir_i]
                direction = dirs[dir_i]
            if coord == top_left:
                break

        corners.pop()
        return corners


class AlgorithmX(object):
    """
    http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
    """

    def solve(self, X, Y, solution=[]):
        def select(X, Y, r):
            cols = []
            for j in Y[r]:
                for i in X[j]:
                    for k in Y[i]:
                        if k != j:
                            X[k].remove(i)
                cols.append(X.pop(j))
            return cols

        def deselect(X, Y, r, cols):
            for j in reversed(Y[r]):
                X[j] = cols.pop()
                for i in X[j]:
                    for k in Y[i]:
                        if k != j:
                            X[k].add(i)

        if not X:
            yield list(solution)
        else:
            c = min(X, key=lambda c: len(X[c]))
            for r in list(X[c]):
                solution.append(r)
                cols = select(X, Y, r)
                for s in self.solve(X, Y, solution):
                    yield s
                deselect(X, Y, r, cols)
                solution.pop()

    def exact_cover(self, X, Y):
        X = {j: set() for j in X}
        for i in Y:
            for j in Y[i]:
                X[j].add(i)
        return X


class TetroSolver(object):
    """
    Takes a board width and height and a list of tetro names
    and uses algorithm_x to find solutions.
    Based on http://rtomas.web.cern.ch/rtomas/Tetrominoes/
    which uses
    http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
    """
    def __init__(self, puzzle_width, puzzle_height, names,
                 single_only, max_solutions):
        self.puzzle_width = puzzle_width
        self.puzzle_height = puzzle_height
        self.names = names
        self.single_only = single_only
        self.max_solutions = max_solutions
        if max_solutions is None:
            self.max_solutions = 9999999
        self.X = {}
        self.Y = {}
        self.tetro_index = 0
        self.the_solution = []
        self.solution_count = None

    def prep_solver(self):
        self.X = set([])
        self.Y = {}
        self.tetro_index = 0
        self.init_X()
        self.generate_Y()

    def init_X(self):
        """
        Make set containing board x,y and tetro labels
        eg:
        ['L1', (0, 0), (0, 1), (0, 2), (1, 2)]
        ['L3', (0, 3), (1, 3), (2, 3), (2, 2)]
        ['L2', (3, 3), (3, 2), (3, 1), (2, 1)]
        ['L4', (3, 0), (2, 0), (1, 0), (1, 1)]
        for a 4x4 board and 4 L tetrominoes labelled L1, L2, L3, L4
        """
        X = set([])
        for i in range(self.puzzle_width):
            for j in range(self.puzzle_height):
                X.add((i, j))
        for name in self.names:
            X.add(name)
        self.X = X

    def generate_Y(self):
        """
        Make a dictionary of all the subsets of X
        containing tetro labels and their x,y's
        eg:
        0 ['L1', (0, 0), (0, 1), (0, 2), (1, 2)]
        1 ['L1', (0, 1), (0, 2), (0, 3), (1, 3)]
        ...
        23 ['L1', (1, 3), (2, 3), (3, 3), (3, 2)]
        24 ['L2', (0, 0), (0, 1), (0, 2), (1, 2)]
        ...
        94 ['L4', (1, 2), (2, 2), (3, 2), (3, 1)]
        95 ['L4', (1, 3), (2, 3), (3, 3), (3, 2)]
        for a 4x4 board and 4 L tetrominoes
        ie 96 of them
        """
        for name in self.names:
            self.do_tetros(name)

    def add_tetro(self, tetro, label):
        x_max = 0
        y_max = 0
        for c in tetro:
            if c[0] > x_max:
                x_max = c[0]
            if c[1] > y_max:
                y_max = c[1]
        x_max = self.puzzle_width - x_max
        y_max = self.puzzle_height - y_max

        for i in range(x_max):
            for j in range(y_max):
                tiles = []
                for t in range(4):
                    tiles.append((tetro[t][0] + i, tetro[t][1] + j))

                self.Y[self.tetro_index] = [label] + tiles
                self.tetro_index += 1

    def do_tetros(self, label):
        """
        Generate the tetros and their symmetry-relatives
        """

        def transpose(x):
            y = []
            for c in x:
                y.append([c[1], c[0]])
            return y

        def mirror(x, xory=0):
            x_max = 0
            y = []
            for c in x:
                if c[xory] > x_max:
                    x_max = c[xory]
            for c in x:
                if xory == 0:
                    y.append([x_max - c[0], c[1]])
                if xory == 1:
                    y.append([c[0], x_max - c[1]])
            return y

        tetro_dic = Tetros.tetro_dic
        name = label[0]
        tetro = tetro_dic[name]
        if name == 'I':
            self.add_tetro(tetro, label)
            self.add_tetro(transpose(tetro), label)
        elif name == 'J':
            self.add_tetro(tetro, label)
            self.add_tetro(mirror(transpose(tetro), 0), label)
            self.add_tetro(mirror(mirror(tetro, 0), 1), label)
            self.add_tetro(mirror(transpose(tetro), 1), label)
        elif name == 'L':
            self.add_tetro(tetro, label)
            self.add_tetro(mirror(transpose(tetro), 0), label)
            self.add_tetro(mirror(mirror(tetro, 0), 1), label)
            self.add_tetro(mirror(transpose(tetro), 1), label)
        elif name == 'O':
            self.add_tetro(tetro, label)
        elif name == 'S':
            self.add_tetro(tetro, label)
            self.add_tetro(mirror(transpose(tetro), 0), label)
        elif name == 'T':
            self.add_tetro(tetro, label)
            self.add_tetro(mirror(tetro, 1), label)
            self.add_tetro(transpose(tetro), label)
            self.add_tetro(mirror(transpose(tetro), 0), label)
        elif name == 'Z':
            self.add_tetro(tetro, label)
            self.add_tetro(mirror(transpose(tetro), 0), label)

    def solve_puzzle(self):
        the_solution = []
        self.prep_solver()
        alg_x = AlgorithmX()
        self.X = alg_x.exact_cover(self.X, self.Y)
        good = 0
        for solution in alg_x.solve(self.X, self.Y, []):
            for tetro in solution:
                the_solution.append(self.Y[tetro])
            good += 1
            if self.single_only:
                self.the_solution = the_solution
                return
            elif good >= self.max_solutions:
                return
        if good > 0 and good <= self.max_solutions:
            self.the_solution = the_solution
            self.solution_count = good
            return


class BoundObjects(object):
    """
    Manage our own bindings.
    Tell them how to behave but let the controller control.
    0 = pick up tile
    1 = move tile
    2 = release tile
    3 = rotate tile
    """
    def __init__(self, widget):
        self.widget = widget
        self.events = [('<ButtonPress-1>', 0),
                       ('<B1-Motion>', 1),
                       ('<ButtonRelease-1>', 2),
                       ('<ButtonRelease-3>', 3)]
        self.func = None

    def add_callback(self, func):
        self.func = func

    def add_bindings(self):
        tag = 'tile'
        for events in self.events[0:4]:
            event = events[0]
            event_code = events[1]
            self.add_binding(tag, event, event_code)

    def add_binding(self, tag, event, event_code):
        def handler(event, self=self, event_code=event_code):
            return self.despatcher(event_code, event)
        self.widget.tag_bind(tag, event, handler)

    def despatcher(self, event_code, event):
        self.func(event_code, event)


class Board(tk.Canvas):
    def __init__(self, parent, settings):
        self.parent = parent
        self.settings = settings
        self.datum = None
        tk.Canvas.__init__(self, self.parent, width=Sgg.canvas_width,
                           height=Sgg.canvas_height,
                           bg=self.settings.dic['Table_Colour'])
        self.grid(row=0, column=0)
        self.update_idletasks()


class View(ViewB):
    """
    Stick blobs on the screen and respond to callbacks
    """

    def __init__(self, master, settings):
        ViewB.__init__(self, master, settings)
        self.model = None
        self.settings = settings
        self.target_box = []
        self.source_box = []
        self.target_pixel_box = []
        self.source_pixel_box = []
        self.source_origin = []
        self.target_origin = []
        self.datum = None
        self.board_frame = None
        self.image_dic = {}
        self.make_image_dic()
        self.do_layout(self)
        self.entry_box.activate()

    def add_model(self, model):
        self.model = model
        self.model.board = self.board

    def make_empty_board(self):
        """
        make board
        """
        self.board = Board(self.board_frame, self.settings)
        self.board_frame.update_idletasks()

    def make_image_dic(self):
        """
        image, button_index, start
        """
        dic = {}
        dic['start'] = [self.images.start_tetrofit, 0, True]
        dic['show_solution'] = [self.images.smiley, 1, True]
        dic['length'] = [None, 2, False]
        self.image_dic = dic

    def do_layout(self, root):
        bg = self.settings.green
        self.outer_frame = tk.Frame(root, bg=bg)
        self.outer_frame.grid(sticky='NSEW')
        bg = self.settings.green
        self.control_frame = tk.Frame(self.outer_frame,
                                      bd=2, bg=bg, relief='raised')
        self.control_frame.grid(row=0, column=0, sticky='EW')
        self.menu_bar = tk.Frame(self.control_frame, relief='raised',
                                 bd=1, bg=bg)
        self.menu_bar.grid(row=0, column=0, sticky='W')
        self.menu = Menu(self.settings, self.menu_bar, self.images.file)
        self.toolbar = Toolbar(self.settings, self.image_dic,
                               self.control_frame)
        self.toolbar.grid(row=0, column=1, sticky='W')

        self.number_frame = tk.Frame(self.control_frame, relief='raised',
                                     bg=bg)

        self.number_frame.grid(row=0, column=2, sticky='NS')
        self.entry_box = EntryBox(self.number_frame,
                                  self.settings)
        self.clock_box = ClockBox(self, self.number_frame)
        self.clock_box.grid(row=0, column=2)
        self.top_frame = tk.Frame(self.outer_frame, relief='flat',
                                  bd=1, bg=bg)

        self.top_frame.grid(row=1, column=0)
        self.board_frame = tk.Frame(self.top_frame, relief='raised',
                                    bd=2, bg=bg)
        self.board_frame.grid(row=0, column=0)

    def new_game(self):
        self.clock_init()
        self.clock_restart()

    def make_empty_board(self):
        if self.board:
            self.board.destroy()
        self.board = Board(self.board_frame, self.settings)
        self.board_frame.update_idletasks()

    def do_grid(self, pixel_box, fill):
        y = pixel_box[1]
        while y < pixel_box[3]:
            line = self.board.create_line(pixel_box[0], y,
                                          pixel_box[2], y, fill=fill)
            y += Sgg.SQUARE_SIZE
        x = pixel_box[0]
        while x < pixel_box[2]:
            line = self.board.create_line(x, pixel_box[1],
                                          x, pixel_box[3], fill=fill)
            x += Sgg.SQUARE_SIZE

    def do_areas(self):
        box = self.model.target_box
        pixel_box = []
        for item in box:
            pixel_box.append(item * Sgg.SQUARE_SIZE)
        self.model.target_pixel_box = pixel_box
        fill = self.settings.dic['Target_Colour']
        area = self.board.create_rectangle(pixel_box, fill=fill)
        fill = self.settings.dic['Grid_Colour']
        self.do_grid(pixel_box, fill)

        box = self.model.source_box
        pixel_box = []
        for item in box:
            pixel_box.append(item * Sgg.SQUARE_SIZE)
        self.model.source_pixel_box = pixel_box

        fill = self.settings.dic['Source_Colour']
        area = self.board.create_rectangle(pixel_box, fill=fill)
        fill = self.settings.dic['Grid_Colour']
        self.do_grid(pixel_box, fill)


class Datum(object):
    """
    """
    def __init__(self, source_coords, solution_coords,
                 name, my_index, colour,
                 board):
        self.source_coords = source_coords
        self.solution_coords = solution_coords
        self.name = name
        self.orientation = 0
        self.index = my_index
        self.colour = colour
        self.board = board
        self.tile_vector = []
        self.canvas_id = None
        self.top_left = None
        self.xmin = None
        self.xmax = None
        self.ymin = None
        self.ymax = None
        self.slot = []
        self.make_tile()

    def get_top_left(self):
        """
        Convenient to know the position of the top left corner
        """
        delta = 1
        x_min = 9999.
        x_max = -9999.
        y_min = 9999.
        y_max = -9999.
        for poly in self.tile_vector:
            x_min = min(x_min, poly.x)
            x_max = max(x_max, poly.x)
            y_min = min(y_min, poly.y)
            y_max = max(y_max, poly.y)
        self.xmin = x_min
        self.xmax = x_max
        self.ymin = y_min
        self.ymax = y_max
        x_min = 9999.
        for poly in self.tile_vector:
            if poly.y + delta > y_min and\
               poly.y - delta < y_min and\
               poly.x < x_min:
                x_min = poly.x
                vec = poly
        self.top_left = vec

    def make_tile(self):
        for coord in self.source_coords:
            self.tile_vector.append(Vec2D(coord[0], coord[1]))
        self.get_top_left()
        # make slot coords
        self.slot = [coord for coord in self.tile_vector]
        outline = 'white'
        fill = 'black'
        tags = 'slot'
        canvas_id = self.board.create_polygon(self.source_coords,
                                              tags=tags,
                                              outline=outline,
                                              fill=fill)
        tags = 'tile'
        outline = 'black'
        fill = self.colour
        self.canvas_id = self.board.create_polygon(self.source_coords,
                                                   tags=tags,
                                                   outline=outline,
                                                   fill=fill)
        tags = 'solution'
        outline = 'black'
        fill = self.colour
        canvas_id = self.board.create_polygon(self.solution_coords,
                                              tags=tags,
                                              outline=outline,
                                              state='hidden',
                                              fill=fill)

    def rotate(self, turns):
        """

        """
        def get_centroid(coords_in):
            """
            get centroid using https://en.wikipedia.org/wiki/Centroid
            """
            coords = []
            for coord in coords_in:
                coords.append(coord)
            # do area using shoelace formula
            # even though we know it!
            n = len(coords)
            coords.append(coords[0])
            area = 0.
            for i in range(n):
                v0 = coords[i]
                v1 = coords[i + 1]
                area += v0.x * v1.y - v1.x * v0.y
            area /= 2.0
            # get Cx, Cy
            cx = 0.
            cy = 0.
            for i in range(n):
                v0 = coords[i]
                v1 = coords[i + 1]
                cx += (v0.x + v1.x) * (v0.x * v1.y - v1.x * v0.y)
                cy += (v0.y + v1.y) * (v0.x * v1.y - v1.x * v0.y)
            cx /= 6 * area
            cy /= 6 * area
            return Vec2D(cx, cy)

        def rotate_poly(poly, degrees, centroid):
            """
            Rotate poly by the given angle,
            relative to the centroid.
            """
            angle = math.radians(degrees)
            new_coords = []
            canvas_coords = []
            cos_theta = math.cos(angle)
            sin_theta = math.sin(angle)
            for v in poly:
                v0 = v - centroid

                nx = v0.x * cos_theta - v0.y * sin_theta
                ny = v0.x * sin_theta + v0.y * cos_theta

                v1 = Vec2D(nx, ny) + centroid

                canvas_coords.append(v1.x)
                canvas_coords.append(v1.y)
                new_coords.append(v1)
            return new_coords, canvas_coords

        self.orientation += turns
        self.orientation %= 4
        centroid = get_centroid(self.tile_vector)
        degrees = 90.0
        new_coords, canvas_coords = rotate_poly(self.tile_vector,
                                                degrees, centroid)
        # coords functions needs odd format
        self.board.coords(self.canvas_id, *canvas_coords)
        self.tile_vector = new_coords
        self.get_top_left()

    def move_to_slot(self):
        new_coords = []
        self.tile_vector = []
        for item in self.slot:
            new_coords.append(item.x)
            new_coords.append(item.y)
            self.tile_vector.append(item)
            self.board.coords(self.canvas_id, *new_coords)
        self.orientation = 0
        self.get_top_left()

    def update_coords(self, distance):
        new_coords = []
        for tcoord in self.tile_vector:
            new_coords.append(tcoord - distance)
        self.tile_vector = new_coords
        self.get_top_left()


class Model(object):
    """
    Datums and dics plus board from View
    """

    def __init__(self, model_data, settings):
        self.model_data = model_data
        self.settings = settings
        self.tetro_stuff = Tetros()
        self.outline_dic = self.tetro_stuff.outline_dic
        self.puzzle = None
        self.names = []
        self.view = None
        self.board = None
        self.target = None
        self.source_box = []
        self.target_box = []
        self.source_pixel_box = []
        self.target_pixel_box = []
        self.datum = []
        self.canvas_move_start = None
        self.move_origin = None
        self.id_dic = {}
        self.index_dic = {}
        self.zero_canvas_move_start()
        self.moving_tile = None
        self.finished = False
        self.finished_callback = False
        self.anchors = []
        self.anchor_set = set([])
        self.the_solution = []
        self.solution_count = None
        self.X = set([])
        self.Y = {}
        self.tetro_index = 0

    def do_sizing(self):
        """
        Do sizing for Board.
        Source is 10 x ((tetro_count + 1)/2) * 3 + 1 squares
        Target is puzzle_width x puzzle_height squares
        The board has a margin of 1 square all round and
        1 square between source and target
        """
        Sgg.tetro_count = Sgg.puzzle_width * Sgg.puzzle_height / 4
        target_height = Sgg.puzzle_height
        target_max = target_height * Sgg.SQUARE_SIZE
        source_height = 1 + int(((Sgg.tetro_count + 1) / 2)) * 3
        source_min = target_max + Sgg.SQUARE_SIZE
        source_max = source_min + (1 + source_height) * Sgg.SQUARE_SIZE
        Sgg.canvas_height = source_max + Sgg.SQUARE_SIZE
        Sgg.canvas_width = Sgg.SQUARES_ACROSS * Sgg.SQUARE_SIZE
        x_margin = int(Sgg.SQUARES_ACROSS / 2 - Sgg.puzzle_width / 2)
        y_margin = 1
        self.target_box = [x_margin, y_margin,
                           x_margin + Sgg.puzzle_width,
                           y_margin + Sgg.puzzle_height]

        # do source
        x_margin = 1
        y_margin = Sgg.puzzle_height + 2
        self.source_box = [x_margin, y_margin,
                           x_margin + Sgg.SOURCE_WIDTH,
                           y_margin + source_height]

    def add_callback(self, func):
        self.finished_callback = func

    def add_view(self, view):
        self.view = view
        self.board = view.board

    def make_anchors(self):
        anchors = []
        anchor_set = set([])
        pixel_box = self.target_pixel_box
        y = pixel_box[1]
        while y < pixel_box[3]:
            x = int(pixel_box[0])
            while x < pixel_box[2]:
                anchor = Vec2D(x, y)
                anchors.append(anchor)
                anchor_set.add((x, y))
                x += Sgg.SQUARE_SIZE
            y += Sgg.SQUARE_SIZE
        self.anchor_set = anchor_set
        self.anchors = anchors

    def make_tile_coords(self, name, x0, y0):
        outline = self.outline_dic[name[0]]
        coords = []
        for p in outline:
            x = x0 + p[0] * Sgg.SQUARE_SIZE
            y = y0 + p[1] * Sgg.SQUARE_SIZE
            coords.append((x, y))
        return coords

    def make_tiles(self):
        self.make_anchors()
        x_start = self.source_pixel_box[0]
        y_start = self.source_pixel_box[1]
        self.datum = []
        solution_coords_dic = self.make_solution_coords()
        for count, item in enumerate(self.names):
            name = item[0]
            x0 = x_start + (1 + 5 * (count % 2)) * Sgg.SQUARE_SIZE
            y0 = y_start + (1 + 3 * ((int(count / 2)))) * Sgg.SQUARE_SIZE

            tile_coords = self.make_tile_coords(name, x0, y0)
            colour = self.settings.dic[name]
            datum = Datum(tile_coords, solution_coords_dic[item],
                          name, count, colour,
                          self.view.board)
            self.datum.append(datum)

    def make_solution_coords(self):
        x_start = self.target_pixel_box[0]
        y_start = self.target_pixel_box[1]
        solution_coords_dic = {}
        for item in self.the_solution:
            coords = self.tetro_stuff.make_outline(item[1:])
            outline = []
            for coord in coords:
                outline.append((x_start + coord[0] * Sgg.SQUARE_SIZE,
                                y_start + coord[1] * Sgg.SQUARE_SIZE))
            solution_coords_dic[item[0]] = outline
        return solution_coords_dic

    def in_box(self, box, datum):
        ret = False
        if datum.xmin >= box[0] and\
           datum.xmax <= box[2] and\
           datum.ymin >= box[1] and\
           datum.ymax <= box[3]:
            ret = True
        return ret

    def is_finished(self):
        """
        1. are all tetros in target area?
        2. are all squares covered by a polygon?
        """

        ret = True
        for datum in self.datum:
            if not self.in_box(self.target_pixel_box, datum):
                ret = False
                break

        if ret:
            ret = True
            delta_1 = int(Sgg.SQUARE_SIZE / 3.)
            delta_2 = 2 * int(Sgg.SQUARE_SIZE / 3.)
            for y in range(self.target_pixel_box[1],
                           self.target_pixel_box[3],
                           Sgg.SQUARE_SIZE):
                for x in range(self.target_pixel_box[0],
                               self.target_pixel_box[2],
                               Sgg.SQUARE_SIZE):
                    x1 = x + delta_1
                    x2 = x + delta_2
                    y1 = y + delta_1
                    y2 = y + delta_2
                    if len(self.board.find_overlapping(x1, y1, x2, y2)) != 2:
                        ret = False
                        break
                if not ret:
                    break

        self.finished = ret
        if ret:
            self.finished_callback(ret)

    def make_id_dic(self):
        """
        Make a dic equating canvas_id to datum.index
        Given a canvas id we get a datum index
        """
        id_dic = {}
        for datum in self.datum:
            id_dic[datum.canvas_id] = datum.index
        self.id_dic = id_dic

    def make_index_dic(self):
        """
        Make a dic equating datum.index to canvas_id
        Given a datum.index we get a canvas id
        """
        id_dic = {}
        for datum in self.datum:
            id_dic[datum.index] = datum.canvas_id
        self.index_dic = id_dic

    def zero_canvas_move_start(self):
        self.canvas_move_start = Vec2D(0, 0)

    def rotate(self, canvas_id_in):
        """
        Rotate a tile by 90 degrees
        and update its coordinates accordingly.
        """
        datum_index = self.id_dic[canvas_id_in]
        datum = self.datum[datum_index]
        datum.rotate(1)

    def start_drag(self, canvas_id, old_x, old_y):
        """
        Initialise a drag event
        oldx,y is cursor position (its all relative)
        """
        drag_datum_index = self.id_dic[canvas_id]
        self.canvas_move_start = Vec2D(old_x, old_y)
        self.move_origin = Vec2D(old_x, old_y)
        self.moving_tile = drag_datum_index

    def end_drag(self, new_x, new_y):
        """
        Finalise a drag event by updating the coordinates
        """

        new = Vec2D(new_x, new_y)
        distance = self.move_origin - new
        datum = self.datum[self.moving_tile]
        datum.update_coords(distance)

        if self.in_box(self.target_pixel_box, datum):
            delta = Sgg.SQUARE_SIZE / 2
            canvas_id = datum.canvas_id
            for anchor in self.anchors:
                if abs(datum.top_left.x - anchor.x) < delta and\
                   abs(datum.top_left.y - anchor.y) < delta:
                    new = anchor
                    distance = new - datum.top_left
                    self.view.board.move(canvas_id, distance.x, distance.y)
                    datum.top_left += distance
                    distance *= -1.
                    datum.update_coords(distance)
                    break
        else:
            if self.in_box(self.source_pixel_box, datum):
                datum.move_to_slot()

    def raise_moving_tile(self):
        canvas_id = self.index_dic[self.moving_tile]
        self.board.tag_raise(canvas_id)

    def bad_tile(self):
        self.canvas_move_start = None
        self.move_origin = None
        self.moving_tile = None

    def make_names(self):
        counter_dic = {k: 0 for k in Tetros.names}
        names = self.puzzle[1]
        new_names = []
        for name in names:
            new_names.append((name + str(counter_dic[name])))
            counter_dic[name] += 1
        self.names = new_names

    def init_puzzle(self, puzzle):
        ret = True
        self.puzzle = puzzle
        Sgg.puzzle_width = puzzle[0][0]
        Sgg.puzzle_height = puzzle[0][1]
        self.make_names()
        self.view.config(cursor='watch')
        self.view.update_idletasks()
        tetro_solver = TetroSolver(Sgg.puzzle_width,
                                   Sgg.puzzle_height,
                                   self.names,
                                   True, None)
        tetro_solver.solve_puzzle()
        self.the_solution = tetro_solver.the_solution
        if self.the_solution:
            self.do_sizing()
            self.view.make_empty_board()
            self.board = self.view.board
            self.view.do_areas()
            self.make_tiles()
            self.make_id_dic()
            self.make_index_dic()
        else:
            ret = False
        self.view.config(cursor='arrow')
        self.view.update_idletasks()
        return ret

    def count_solutions(self):
        self.view.config(cursor='watch')
        self.view.update_idletasks()
        tetro_solver = TetroSolver(Sgg.puzzle_width,
                                   Sgg.puzzle_height,
                                   self.names,
                                   False, None)
        tetro_solver.solve_puzzle()
        self.solution_count = tetro_solver.solution_count
        self.view.config(cursor='arrow')
        self.view.update_idletasks()


class Controller(object):
    """
    Set up and control
    """

    def __init__(self, root):
        self.master = root
        self.flasher = None
        self.settings = Settings()
        self.model = None
        self.model_data = ModelData()
        self.view = View(root, self.settings)
        self.bound_objects = None
        self.finger_trouble = False
        self.finished = True
        self.puzzle_number = None
        puzzle_number = None
        # if len(sys.argv) > 1:
        #    puzzle_number = int(sys.argv[1])
        self.start_game(puzzle_number, [])

    def start_game(self, puzzle_number, puzzle):
        self.view.clock_init()
        self.view.clock_restart()
        self.view.game_over()
        self.model = None
        #self.generate()
        self.model = Model(self.model_data, self.settings)
        self.view.add_model(self.model)
        self.model.add_view(self.view)
        self.add_model_callback()
        self.view.new_game()
        self.finger_trouble = False
        self.flasher = Flasher(self.view.clock.box.label,
                               self.master, self.settings)
        if puzzle_number != -1:
            puzzle = self.get_internal_puzzle(puzzle_number)
        else:
            self.puzzle_number = puzzle_number

        good_puzzle = self.model.init_puzzle(puzzle)
        if good_puzzle:
            self.finished = False
            self.view.game_on()
            if self.puzzle_number != -1:
                self.view.entry_box.clear()
                self.view.entry_box.write_box(str(self.puzzle_number))
            self.set_bound_objects()
            self.add_callbacks()
        else:
            text = "".join(puzzle[1])
            text_plus = text + '\nNo solution found'
            self.view.show_message('Bad puzzle', text_plus)

    def service_menu(self, *args):
        """
        Respond to menu choices
        """
        strargs = ''
        for item in args:
            strargs += ' ' + item
        PzlG.logger.logger.info("service_menu " + strargs)
        name = args[0]
        if name == 'set_colour':
            choice = args[1]
            self.set_colour(choice)
        elif name == 'set_square_size':
            self.set_square_size()
        elif name == 'count_solutions':
            self.count_solutions()
        elif name == 'save_settings':
            self.settings.preferences.save()
        elif name == 'about':
            self.view.about()
        elif name == 'help':
            self.view.help()

    def service_toolbar(self, button_index, mouse_index):
        PzlG.logger.logger.info("service_toolbar " +
                                str(button_index) +
                                ' ' +
                                str(mouse_index))

        if mouse_index == 2:
            self.view.do_tooltip(button_index, None)

        elif mouse_index == 3:
            if button_index == 0:
                self.puzzle_number += 1
                self.start_game(self.puzzle_number, [])

        elif mouse_index == 1:
            if button_index == 0:
                self.start_game(None, [])
            elif button_index == 1:
                self.show_solution()

    def event_handler(self, event_index, event):
        """
        Tiles are moved by button-press, motion, button-release.
        On button press the canvas will give us the nearest tile id
        but we need to work using tile_sets.
        Datum store the x,y of the tile corner.
        Canvas events return the x,y of the mouse.
        When we start to drag the canvas will tell us the nearest tile.
        We record the initial mouse x,y as model.move_origin for Datums
        and self.model.canvas_move_start. The latter is reset each time
        we invoke the canvas.move function on a tile so we can tell the
        canvas how far to move the image, but the former is only used to
        work out the total distance moved when the move is completed.
        At this point we update the Datum x,y.

        self.func = None
        self.events = [('<ButtonPress-1>', 0),
                       ('<B1-Motion>', 1),
                       ('<ButtonRelease-1>', 2),
                       ('<ButtonRelease-3>', 3),
                       ('<ButtonRelease-2>', 4)]

        """

        def is_tile(id_dic, canvas_id):
            ret = False
            if canvas_id in id_dic:
                ret = True
            return ret

        if event_index == 0 and not self.finished:
            # button press
            # start drag of an object
            # record the tile and its location
            canvas_id = self.view.board.find_closest(event.x, event.y)[0]
            # check it's a tile
            if is_tile(self.model.id_dic, canvas_id):
                self.model.start_drag(canvas_id, event.x, event.y)
                self.model.raise_moving_tile()
                self.finger_trouble = False
            else:
                self.model.bad_tile()
                self.finger_trouble = True

        elif event_index == 1 and not self.finger_trouble and not self.finished:
            # motion
            # here we just manage the movement and keep track
            # of the new coords.
            # Only when the movement ends with mouse release
            # do we update the tile positions.
            # how much has tile moved?
            delta = Vec2D(event.x, event.y) - self.model.canvas_move_start
            # tell the canvas to move the polygon
            # the appropriate amount
            index_dic = self.model.index_dic
            canvas_id = index_dic[self.model.moving_tile]
            self.view.board.move(canvas_id, delta.x, delta.y)

            # record the new canvas position
            self.model.canvas_move_start = Vec2D(event.x, event.y)
        elif event_index == 2 and not self.finger_trouble and not self.finished:
            # button 1 release
            # end drag of an object
            # so now we update the tile coordinates
            # reset the drag data
            self.model.zero_canvas_move_start()
            self.model.end_drag(event.x, event.y)
            self.model.is_finished()
        elif event_index == 3 and not self.finished:
            canvas_id = self.view.board.find_closest(event.x, event.y)[0]

            # check it's a tile
            if is_tile(self.model.id_dic, canvas_id):
                self.model.rotate(canvas_id)

    def get_internal_puzzle(self, puzzle_number):
        if puzzle_number is None or puzzle_number < 0 or \
           puzzle_number > self.model_data.puzzle_count - 1:
            puzzle_number = randint(0, self.model_data.puzzle_count - 1)
        self.puzzle_number = puzzle_number
        return self.model_data.get_puzzle(puzzle_number)

    def set_bound_objects(self):
        self.bound_objects = BoundObjects(self.view.board)
        self.bound_objects.add_callback(self.event_handler)
        self.bound_objects.add_bindings()

    def add_callbacks(self):
        self.view.add_menu_callback(self.service_menu)
        self.view.add_toolbar_callback(self.service_toolbar)
        self.view.entry_box.add_callback(self.get_puzzle)

    def add_model_callback(self):
        self.model.add_callback(self.service_model)

    def service_model(self, finished):
        self.finished = finished
        if self.finished:
            self.view.game_over()
            self.view.clock_stop()
            self.flasher.flash()

    def get_puzzle(self, text):

        def is_string(text):
            ret = True
            for item in text:
                if item not in Tetros.tetro_dic:
                    ret = False
                    break
            return ret

        size_dic = {4: [4, 4], 5: [5, 4], 6: [6, 4], 7: [7, 4],
                    8: [8, 4], 9: [[6, 6], [9, 4]], 10: [8, 5]}
        good = False
        if not text:
            self.view.entry_box.clear()
            return
        try:
            puzzle_number = int(text)
            if puzzle_number < 0:
                puzzle_number = None
            good = True
            self.start_game(puzzle_number, [])
        except ValueError:
            text = text.upper()
            if text.find('XYZZY') != -1:
                self.view.xyzzy()
            else:
                if len(text) < 11 and is_string(text):
                    new_text = [i for i in text]
                    syms = len(text)
                    if syms == 9:
                        if self.settings.dic['size_nine_width'] == '6':
                            size_nine = 0
                        else:
                            size_nine = 1
                        puzzle = [size_dic[9][size_nine], new_text]
                    else:
                        puzzle = [size_dic[syms], new_text]
                    puzzle_number = -1
                    good = True
                    self.start_game(puzzle_number, puzzle)
                else:
                    text_plus = text + '\nWrong size or illegal symbol'
                    self.view.show_message('Bad puzzle', text_plus)
        if not good:
            self.view.entry_box.clear()

    def show_solution(self):
        dels = self.view.board.find_withtag('tile')
        raisers = self.view.board.find_withtag('solution')
        for item in dels:
            self.view.board.delete(item)
        for item in raisers:
            self.view.board.itemconfigure(item, state='normal')
        self.view.game_over()
        self.view.clock_stop()

    def set_colour(self, choice):
        try:
            bg_colour = self.settings.dic[choice]
            result = tkColorChooser.askcolor(bg_colour)
            if result[1] is not None:
                self.settings.dic[choice] = result[1]
        except KeyError:
            PzlG.logger.logger.error("set_colour " + choice)

    def set_square_size(self):
        Sgg.SQUARE_SIZE = int(self.settings.dic['set_square_size'])

    def count_solutions(self):
        self.model.count_solutions()
        text = str(self.model.solution_count)
        text_plus = '\nNumber of solutions ' + text
        self.view.show_message('Count Solutions', text_plus)

    def generate(self):
        def make_names(names):
            counter_dic = {k: 0 for k in Tetros.names}
            new_names = []
            for name in names:
                new_names.append((name + str(counter_dic[name[0]])))
                counter_dic[name[0]] += 1
            count = 1
            for k, c in list(counter_dic.items()):
                count *= max(c, 1)
            return new_names, count

        def is_new(done_dic, comb):
            ret = False
            tmp = "".join(sorted(comb))
            if tmp not in done_dic:
                ret = True
            return ret

        pairs = [[5, 4, 9], [6, 4, 16], [7, 4, 8],
                 [8, 4, 9], [9, 4, 64], [6, 6, 64], [8, 5, 1024]]

        seed = 1
        random.seed(seed)
        tot = 0
        good = 0

        names = Tetros.names
        name_len = len(names)
        min_puzzle = 100
        min_puzzle = 50
        results = []
        for pair in pairs[4:5]:
            count = 0
            height = pair[1]
            width = pair[0]
            mult = pair[2]
            pp = [width, height]

            tetro_count = int(width * height / 4)
            done_dic = {}
            this_result = []
            while count < min_puzzle:
                tot += 1
                comb = ''
                for i in range(tetro_count):
                    j = names[random.randrange(name_len)]
                    comb += j

                if is_new(done_dic, comb):
                    self.model = Model(self.model_data, self.settings)
                    labels, factor = make_names(comb)
                    tetro_solver = TetroSolver(width,
                                               height,
                                               labels,
                                               False,
                                               factor * mult)
                    tetro_solver.solve_puzzle()
                    the_solution = tetro_solver.the_solution
                    if the_solution:
                        res = [pp, comb]
                        this_result.append([tetro_solver.solution_count / factor, res])
                        done_dic["".join(sorted(comb))] = True
                        good += 1
                        count += 1
            this_result = sorted(this_result, reverse=True)
            for item in this_result:
                results.append(item[1])
        """
        for item in results:
            print item

        print 'tot, good', tot, good
        exit(1)
        """


INITIALISE = PzlG()
if __name__ == '__main__':
    try:
        ROOT = tk.Tk()
        ROOT.withdraw()
        APP = Controller(ROOT)
        ROOT.mainloop()
        PzlG.logger.logger.info("Stop program")
    except:
        PzlG.logger.logger.info("Failure!")
        PzlG.logger.logger.exception("Unhandled exception during main")
