'''This is a program which plays cross-naughts'''

# The cell value constants
EMPTY   = 0
CROSS   = 1
NAUGHT  = 2

CELL_VALUE_DICT = {
    EMPTY   : 'empty',
    CROSS   : 'cross',
    NAUGHT  : 'naught'
    }

class CellFullException(Exception):
    '''Raised when we want to write cross or naught on already non-empty cell'''
    pass

class CellEmptyException(Exception):
    '''Raised when we want to clear already empty cell'''
    pass

def sign(n):
    '''Standard mathematical function sign, returning sign of a number'''
    if n < 0:
        return -1
    elif n == 0:
        return 0
    else:
        return 1

def seq(start,end):
    '''Works like range function but autodetects direction (ASC or DESC)'''
    if start < end:
        return range(start, end + 1)
    else:
        return range(start, end - 1, -1)

class Board:
    '''Class which implements cross-and-naughts board'''
    
    def __init__(self, width, height):
        '''Initializes a Board object.
        Raises TypeError if height or width is not integer'''
        if not isinstance(width,int):
            raise TypeError('Width must be integer')
        if not isinstance(height,int):
            raise TypeError('Height must be integer')
        self.height = height
        self.width  = width
        self.__cells  = [EMPTY for i in range(width*height)]

    def flatten_index(self,row,column):
        '''Converts row, column pair to a "flat" index.
        Raises TypeError if row or column is not integer.
        Raises IndexError if row or column is out of range'''
        if not isinstance(row,int):
            raise TypeError('Row must be integer')
        if not isinstance(column,int):
            raise TypeError('Column must be integer')
        if not (row in range(self.height)):
            raise IndexError('Row number is out of range (row = %s, height = %s)' % (row + 1, self.height))
        if not (column in range(self.width)):
            raise IndexError('Column number is out of range (column = %s, width = %s)' % (column + 1,self.width))
        return row * self.width + column

    def unflatten_index(self,i):
        '''Converts "flat" index to row, column tuple
        Raises TypeError if index is inappropriate type.
        Raises IndexError if index is out of range'''
        if not isinstance(i, int):
            raise TypeError('Index must be integer')
        if not i in range(self.width * self.height):
            raise IndexError('Index must be in range (0,%s)' % (self.width * self.heigth - 1,))
        return (i // self.width, i % self.width)

    def getcell(self,row,column):
        '''Returns cell at address specified by row and column'''
        i = self.flatten_index(row, column)
        return self.__cells[i]

    def getslice(self, r1, c1, r2, c2):
        '''Returns a slice between cells (r1,c1) and (r2,c2), endpoins included
        cells must be on 1 line (vertical, horizontal or diagonal)
        Raises IndexError if indices do not satisfy condition above'''
        # Checking whether on one line
        rdist = abs(r1 - r2)
        cdist = abs(c1 - c2)
        if ((rdist !=0) and (cdist != 0) and (rdist != cdist)):
            # checking whether cells on 1 line
            raise IndexError('points must be on one line')
        rows = seq(r1, r2)
        cols = seq(c1, c2)
        if rdist == 0:
            rows = rows * (cdist + 1)
        if cdist == 0:
            cols = cols * (rdist + 1)
        r = []
        for cell in zip(rows, cols):
            r.append(self.getcell(*cell))
        return r

    def setcell(self,row,column,value):
        '''Sets the value of specified cell to given value
        Raises TypeError if value is non-integer
        Raises IndexError if value is out of range
        Raises CellFullException if written cell is already non-empty
        Raises CellEmptyException if cleaned cell is already empty'''
        i = self.flatten_index(row, column)
        if not isinstance(value,int):
            raise TypeError('Cell value must be integer')
        if not (value in range(3)): # 0, 1 or 2
            raise ValueError('Cell value number is out of range (column = %s while 0, 1 or 2 is allowed)' % (value,self.width))
        # If figure != EMPTY then cell must be empty, if
        # figure == EMPTY (clearing) cell MUST be non-empty
        if (self.__cells[i] != EMPTY) and (value != EMPTY):
            raise CellFullException('Cell at (%s,%s) is not empty' % (row, column))
        if (self.__cells[i] == EMPTY) and (value == EMPTY):
            raise CellEmptyException('Cell at (%s,%s) is empty' % (row, column))
        self.__cells[i] = value

    def clearcell(self,row,column):
        '''A shortcut which sets current cell to empty. This method is not to be
        used to fill board with empty cells, because already empty cell cannot be
        cleared. Use new board instead'''
        self.setcell(row,column,EMPTY)

    def get_board_data(self):
        '''Returns board data (width, height and cell data)'''
        return (self.width, self.height, self.__cells[:])

class WrongTurnError(Exception):
    pass

class BadCellError(Exception):
    pass

class Game:
    '''Class that implements the rules of the game, detects the status
    of the game, accepts or rejects the moves'''

    def __init__(self, board = None, to_move = None, in_row = None):
        '''Initializes the object.
        Optional parameter "board" is used to set up the position different
        from empty board.
        Optional parameter "to_move" is used to determine whose move is now'''
        if board:
            if isinstance(board, Board):
                self.board = board
            else:
                raise TypeError('board must be Board type')
        else:
            self.board = Board(3,3) # default 3x3 board

        if to_move:
            if not isinstance(to_move,int):
                raise TypeError('to_move must be integer')
            if not (to_move in (CROSS, NAUGHT)):
                raise ValueError('to_move must be equal to 1 or 2')
            self.to_move = to_move
        else:
            self.to_move = CROSS

        if in_row:
            if not isinstance(in_row, int):
                raise TypeError('in_row must be integer')
            if (in_row > self.board.width) or (in_row > self.board.height):
                raise ValueError('in_row cannot be bigger than width of height')
            if in_row <= 0:
                raise ValueError('in_row cannot be less than or equal to zero')
            self.in_row = in_row
        else:
            self.in_row = 3
            
        self.moves = [] # list of moves to replay
        self.move_number = 0

    def toggle_turn(self):
        '''Swaps to_move variable from CROSS to NAUGHT and vice-versa'''
        if self.to_move == CROSS:
            self.to_move = NAUGHT
        else:
            self.to_move == CROSS
        
    def move(row, column, figure):
        '''Makes move on a board.
        figure is cross or naught
        row and column designate row and column of the board respectively
        Raises TypeError if figure is inappropriate type.
        Raises ValueError if figure is not in (CROSS, NAUGHT)
        Raises WrongTurnError if supplied figure is wrong'''
        if not isinstance(figure, int):
            raise TypeError('figure must be integer type')
        if not (figure in (CROSS, NAUGHT)):
            raise ValueError('figure must be equal to 1 or 2')
        if figure != self.to_move:
            raise WrongTurnError('It is %s to move now' % (CELL_VALUE_DICT[self.to_move],))
        self.board.setcell(row,column,figure) # if exception occurs it will be passed further
        self.moves[self.move_number + 1:] = [] # truncate the rest moves
        self.moves[self.move_number] = (row, column, figure)
        self.move_number += 1
        self.toggle_turn()

    def undo_move(self):
        '''Returns to previous move, if that exists. It does not erase the move
        from which the game is undone, for ability to redo move
        Raises IndexError if already at the beginning'''
        if self.move_number == 0:
            raise IndexError("Cannot undo, already at the beginning")
        last_move = self.moves[self.move_number - 1]
        row, column = last_move[0:2]
        self.board.clearcell(row,column)
        self.move_number -= 1
        self.toggle_turn()

    def redo_move(self):
        '''Goes to next move, if that exists.
        Raises IndexError if already at the end'''
        if self.move_number == len(self.moves):
            raise IndexError('Cannot redo already at the end')
        next_move = self.moves[self.move_number]
        self.board.setcell(*next_move)
        self.move_number += 1
        self.toggle_turn()

    def slices_for(row, column):
        '''Returns all slices for given cell according to in_row
        Raises IndexError if row or column is out of range'''
        if not row in range(height):
            raise IndexError('row is out of range (' + row + ')')
        if not column in range(width):
            raise IndexError('column is out of range (' + column + ')')
        
        ltl = column                        # length to left
        ltr = self.width - column - 1       # length to right
        ltt = row                           # length to top
        ltb = self.height - row - 1         # length to bottom

        # horizontal slice
        len1 = min((ltl,self.in_row - 1))
        len2 = min((ltr,self.in_row - 1))
        hor_slice = self.board.getslice(row,
                                        column - len1,
                                        row,
                                        column + len2)

        # vertical slice
        len1 = min((ltt,self.in_row - 1))
        len2 = min((ltb,self.in_row - 1))
        ver_slice = self.board.getslice(column,
                                        row - len1,
                                        column,
                                        row + len2)

        # diagonal left-to-right top-to-bottom slice
        len1 = min((ltl, ltt, self.in_row - 1))
        len2 = min((ltr, ltb, self.in_row - 1))
        dia1_slice = self.board.getslice(row - len1,
                                         column - len1,
                                         row + len2,
                                         column + len2)

        # diagonal left-to-right bottom-to-top slice
        len1 = min((ltl, ltb, self.in_row - 1))
        len2 = min((ltr, ltt, self.in_row - 1))
        dia2_slice = self.board.getslice(row - len1,
                                         column + len1,
                                         row + len2,
                                         column - len2)
        
        return (hor_slice,ver_slice,dia1_slice,dia2_slice)

if __name__ == "__main__":
    b = Board(20,20)
    import timeit
    t = timeit.Timer('b.getslice(0,0,15,0)','from __main__ import *')
    print t.timeit(number = 50000)