from model import DIRECTION_UP, DIRECTION_DOWN, DIRECTION_LEFT, DIRECTION_RIGHT, DIRECTION_UPLEFT, DIRECTION_UPRIGHT, DIRECTION_DOWNLEFT, DIRECTION_DOWNRIGHT

# A class that checks if there's an alignment of X objects on the grid
class Alignment:
    def __init__(self, comp, count):
        self.comp = comp
        self.count = count

    def check(self, start):
        def check_rec(start, dir):
            if start == None:
                return []
            
            # If we have a neighbor
            if start.sector.neighbors[dir]:
                # ... and there's a marble on it
                if start.sector.neighbors[dir].occupant:
                    # ... and we are of the same color
                    if start.sector.neighbors[dir].occupant.type == start.type:
                        res = check_rec(start.sector.neighbors[dir].occupant, dir)
                        if res != []:
                            return [start.sector.neighbors[dir]] + res
                        else:
                            return [start.sector.neighbors[dir]]

            return []

        # Vertical alignment ?
        r = check_rec(start, DIRECTION_UP) + check_rec(start, DIRECTION_DOWN) + [start.sector]
        print r
        if len(r) >= self.count:
            return r

        # Horizontal alignment ?
        r = check_rec(start, DIRECTION_LEFT) + check_rec(start, DIRECTION_RIGHT) + [start.sector]
        if len(r) >= self.count:
            return r

        # Riht Diagonal alignment ?
        r = check_rec(start, DIRECTION_UPLEFT) + check_rec(start, DIRECTION_DOWNRIGHT) + [start.sector]
        if len(r) >= self.count:
            return r

        # Left Diagonal alignment ?
        r = check_rec(start, DIRECTION_UPRIGHT) + check_rec(start, DIRECTION_DOWNLEFT) + [start.sector]
        if len(r) >= self.count:
            return r

        return []


class Dijkstra:
    def __init__(self, walltype):
        self.walltype = walltype

    def eval(self, start, notes={}):
        notes[start] = 0
        opened = [start]

        def get_min(l):
            min = l[0]
            for i in l:
                if notes[i] < notes[min]:
                    min = i

            return min


        while len(opened) != 0:

            cur = get_min(opened)
            opened.remove(cur)

            for succ in cur.get_neighbors():

                if succ.occupant == None or (not isinstance(succ.occupant, self.walltype)):
                    note_tmp = notes[cur] + 1

                    # Already rated
                    if succ in notes:
                        # We have a shorter path
                        if note_tmp < notes[succ]:
                            notes[succ] = note_tmp
                            # Reopen path
                            opened.append(succ)
                    # First rating
                    else:
                        notes[succ] = note_tmp
                        opened.append(succ)

        return notes


# A class that implements a greedy algorithm to find a path
# It supposes it's always possible to find a path
class GreedyPath:
    def __init__(self, heur):
        self.heur = heur

    def find_path(self, start, goal, goal_type=None):
        print "find path..."
        closed = [start]
        path = []

        cur = start

        while cur != goal:
            notes = {}
            # note adjacent sectors
            for n in cur.get_neighbors():
                if n in closed:
                    continue

                if n.occupant == None or (goal_type != None and isinstance(n.occupant, goal_type)):
                    notes[n] = self.heur(n, goal)

            if len(notes) == 0:
                return None

            # Choose best move
            best = notes.keys()[0]
            for s in notes:
                if notes[s] < notes[best]:
                    best = s

            closed.append(best)
            path.append(best)
            cur = best

        return path
            

# A class that implements A* algorithm with fixed distance of 1
# between two sectors
class AStar:
    def __init__(self, heur=lambda x, y: 0):
        self.heur = heur

    def path_exists(self, start, goal):
        x = self.find_path(start, goal)
        if x:
            return True
        else:
            return False

    def find_path(self, start, goal):
        opened = []
        closed = []
        parents = {}

        g_n = {start : 0}
        f_n = {start : self.heur(start, goal)}

        opened.append(start)

        def get_min(l):
            min = l[0]
            for i in l:
                if f_n[i] < f_n[min]:
                    min = i

            return min

        i = 0
        while len(opened) != 0:
            i += 1
            n = get_min(opened)
            opened.remove(n)

            if n == goal:
                # generate path
                path = [goal]
                my = goal
                while my in parents:
                    path.append(parents[my])
                    my = parents[my]
                
                path.reverse()

                print "A* :", i

                return path[1:]
            else:
                closed.append(n)

            for succ in n.get_neighbors():
                if succ.occupant:
                    continue

                h = self.heur(succ, goal)

                g_tmp = g_n[n] + 1
                f_tmp = g_tmp + h

                if succ in opened:
                    if f_n[succ] < f_tmp:
                        continue

                if succ in closed:
                    if f_n[succ] < f_tmp:
                        continue
                    
                parents[succ] = n
                g_n[succ] = g_tmp            
                f_n[succ] = f_tmp

                if succ in opened:
                    opened.remove(succ)
                if succ in closed:
                    closed.remove(succ)
                opened.append(succ)

        return None

class ConstrainedAStar(AStar):
    def find_path(self, start, goal, map, zero=False):
        opened = []
        closed = []
        parents = {}

        g_n = {start : 0}
        f_n = {start : self.heur(start, goal)}

        opened.append(start)

        def get_path_len(node):
            count = 0
            while node in parents:
                node = parents[node]
                count += 1

            return count
        
        def get_min(l):
            min = l[0]
            for i in l:
                if f_n[i] < f_n[min]:
                    min = i

            return min

        while len(opened) != 0:
            n = get_min(opened)
            opened.remove(n)

            if n == goal:
                # generate path
                path = [goal]
                my = goal
                while my in parents:
                    path.append(parents[my])
                    my = parents[my]
                
                path.reverse()

                return path[1:]
            else:
                closed.append(n)

            for succ in n.get_neighbors():
                if succ.occupant:
                    continue

                if zero == True:
                    delta = map[succ] - get_path_len(n)
                    if delta < -3:
                        continue

                if zero == False:
                    if (map[succ] - get_path_len(n) + 1) <= 0:
                        continue

                h = self.heur(succ, goal)

                g_tmp = g_n[n] + 1
                f_tmp = g_tmp + h

                if succ in opened:
                    if f_n[succ] < f_tmp:
                        continue

                if succ in closed:
                    if f_n[succ] < f_tmp:
                        continue
                    
                parents[succ] = n
                g_n[succ] = g_tmp            
                f_n[succ] = f_tmp

                if succ in opened:
                    opened.remove(succ)
                if succ in closed:
                    closed.remove(succ)
                opened.append(succ)

        return None