from __future__ import division

from weakref import ref

class Constraint(object):
    """Represents any group of cells in a grid that cannot repeat a digit."""

    ### Accessors

    # True iff a constraint consists of a straight line of cells.  Used to
    # quickly skip over pairs of constraints that cannot possibly have more
    # than one cell in common.
    is_linear = False

    # NOTE: _cells is a list of refs; _grid is a ref
    # XXX document this
    cells = property(lambda self: [ x() for x in self._cells ])
    grid = property(lambda self: self._grid())

    ### Methods
    # XXX inherited __init__ to init _grid/_cells

    def find_value(self, value):
        """Returns the cells that can be a specific value."""
        possible_cells = []
        for cell in self.cells:
            if value in cell._values:
                possible_cells.append(cell)

        if len(possible_cells) == 0:
            raise Exception  # XXX

        return possible_cells

    def resolve_uniques(self):
        """Searches for values that can only appear in one cell, and sets them
        appropriately.

        Returns the number of cell changes.
        """

        cell_changes = 0

        for value in xrange(self.grid.size):
            # XXX cache values that are taken care of
            possible_cells = self.find_value(value)

            if len(possible_cells) > 1:
                # Not unique
                continue

            target_cell = possible_cells[0]
            if target_cell.solved:
                # Already seen this
                # XXX this is what cache is for
                continue

            # Only cell in the group that can be value
            cell_changes += target_cell.set(value)

        return cell_changes


class Box(Constraint):
    def _get_box_row(self):
        return self._pos // self.grid.box_width
    box_row = property(_get_box_row)

    def _get_box_column(self):
        return self._pos % self.grid.box_height
    box_column = property(_get_box_column)

    def __init__(self, grid, position):
        self._grid = ref(grid)
        self._pos = position

        self._cells = []
        for row in xrange(self.grid.box_height):
            for col in xrange(self.grid.box_width):
                cell_row = row + self.box_row * self.grid.box_height
                cell_col = col + self.box_column * self.grid.box_width
                self._cells.append(ref(self.grid.cell(cell_row, cell_col)))


class Row(Constraint):
    is_linear = True

    def __init__(self, grid, position):
        self._grid = ref(grid)
        self._pos = position

        self._cells = []
        for col in xrange(self.grid.size):
            self._cells.append(ref(self.grid.cell(self._pos, col)))

class Column(Constraint):
    is_linear = True

    def __init__(self, grid, position):
        self._grid = ref(grid)
        self._pos = position

        self._cells = []
        for row in xrange(self.grid.size):
            self._cells.append(ref(self.grid.cell(row, self._pos)))

class Diagonal(Constraint):
    is_linear = True

    def __init__(self, grid, direction='down', offset=0):
        self._grid = ref(grid)
        self._direction = direction
        self._offset = offset

        if direction == 'down':
            coords = {'row': 0, 'column': 0}
            increment = 1
        elif direction == 'up':
            coords = {'row': 0, 'column': grid.size - 1}
            increment = -1
        else:
            raise Exception # XXX

        # XXX
        if offset != 0:
            raise NotImplementedError

        self._cells = []
        for i in xrange(self.grid.size):
            self._cells.append(ref(self.grid.cell(coords['row'], coords['column'])))
            coords['row'] += 1
            coords['column'] += increment