import heapq
import random
from itertools import tee, izip

from simulation.direction import ALL_DIRECTIONS
from simulation.location import Location
from simulation.world_map import Cell, WorldMap


def generate_map(height, width, obstacle_ratio):
    grid = [[Cell(Location(x, y)) for y in xrange(height)] for x in xrange(width)]
    world_map = WorldMap(grid)

    # We designate one (non-corner) edge cell as empty, to ensure that the map can be expanded
    always_empty_edge_x, always_empty_edge_y = get_random_edge_index(height, width)

    for x, y in shuffled(_get_edge_coordinates(height, width)):
        if (x, y) != (always_empty_edge_x, always_empty_edge_y) and random.random() < obstacle_ratio:
            cell = grid[x][y]
            cell.habitable = False
            #   So long as all neighbours can still reach other, then the map cannot get bisected
            if not _all_habitable_neighbours_can_reach_each_other(cell, world_map):
                cell.habitable = True

    return world_map


def _get_edge_coordinates(height, width):
    for x in xrange(width):
        for y in xrange(height):
            yield x, y


def shuffled(iterable):
    values = list(iterable)
    random.shuffle(values)
    return iter(values)


def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)


def _all_habitable_neighbours_can_reach_each_other(cell, world_map):
    neighbours = get_adjacent_habitable_cells(cell, world_map)

    assert len(neighbours) >= 1
    return all(get_shortest_path_between(n1, n2, world_map) is not None for n1, n2 in pairwise(neighbours))


def get_shortest_path_between(cell1, cell2, world_map):

    def manhattan_distance_to_cell2(this_branch):
        branch_tip_location = this_branch[-1].location
        abs(branch_tip_location.x - cell2.location.x) + abs(branch_tip_location.y - cell2.location.y) + len(this_branch)

    branches = PriorityQueue(key=manhattan_distance_to_cell2, init_items=[[cell1]])
    visited_cells = set()

    while branches:
        branch = branches.pop()

        for cell in get_adjacent_habitable_cells(branch[-1], world_map):
            if cell in visited_cells:
                continue

            visited_cells.add(cell)

            new_branch = branch + [cell]

            if cell == cell2:
                return new_branch

            branches.push(new_branch)

    return None


def get_random_edge_index(height, width, rng=random):
    assert height >= 2 and width >= 2

    num_row_cells = width - 2
    num_col_cells = height - 2
    num_edge_cells = 2*num_row_cells + 2*num_col_cells
    random_cell = rng.randint(0, num_edge_cells-1)

    if 0 <= random_cell < num_row_cells:
        # random non-corner cell on the first row
        return random_cell+1, 0
    elif num_row_cells <= random_cell < 2*num_row_cells:
        # random non-corner cell on the last row
        random_cell -= num_row_cells
        return random_cell + 1, height - 1

    random_cell -= 2*num_row_cells

    if 0 <= random_cell < num_col_cells:
        # random non-corner cell on the first column
        return 0, random_cell + 1
    elif num_col_cells <= random_cell < 2*num_col_cells:
        # random non-corner cell on the last column
        random_cell -= num_col_cells
        return width - 1, random_cell + 1

    raise ValueError('Should not be reachable')


def get_adjacent_habitable_cells(cell, world_map):
    return [c for c in (world_map.get_cell(cell.location + d) for d in ALL_DIRECTIONS) if c and c.habitable]


class PriorityQueue(object):
    def __init__(self, key, init_items=tuple()):
        self.key = key
        self.heap = [self._build_tuple(i) for i in init_items]
        heapq.heapify(self.heap)

    def _build_tuple(self, item):
        return self.key(item), item

    def push(self, item):
        to_push = self._build_tuple(item)
        heapq.heappush(self.heap, to_push)

    def pop(self):
        _, item = heapq.heappop(self.heap)
        return item

    def __len__(self):
        return len(self.heap)


@@ -1687,20 +1687,37 @@
 een(
+source_
 cell
-1
 , 
+destination_
 cell
-2
 , wo
@@ -1757,21 +1757,32 @@
 ance_to_
+destination_
 cell
-2
 (this_br
@@ -1879,21 +1879,32 @@
 ion.x - 
+destination_
 cell
-2
 .locatio
@@ -1938,21 +1938,32 @@
 ion.y - 
+destination_
 cell
-2
 .locatio
@@ -2042,21 +2042,32 @@
 ance_to_
+destination_
 cell
-2
 , init_i
@@ -2077,13 +2077,19 @@
 s=%5B%5B
+source_
 cell
-1
 %5D%5D)%0A
@@ -2411,13 +2411,24 @@
  == 
+destination_
 cell
-2
 :%0A  

Rename variables