import json
import math
import random

from tour import Tour


def euclidean_distance(pt1, pt2):
    return math.sqrt((pt1[0] - pt2[0]) ** 2 + (pt1[1] - pt2[1]) ** 2)


def generate_matchings(L):
    if len(L) == 0:
        yield []

    for (index, i2) in enumerate(L[1:]):
        for other_part in generate_matchings(
            [L[ind] for ind in range(1, len(L)) if ind != index + 1]
        ):
            yield [(L[0], i2)] + other_part


def one_random_matching(L):
    match = []
    L = list(L)

    while len(L) > 0:
        ind1 = random.randint(0, len(L) - 1)
        pt1 = L.pop(ind1)
        ind2 = random.randint(0, len(L) - 1)
        pt2 = L.pop(ind2)
        match.append([pt1, pt2])

    return match



class TSP:
    def __init__(self, cities):
        self.cities = list(map(tuple, cities))

    @staticmethod
    def random_cities(N):
        return [
            (round(random.random(), 2), round(random.random(), 2)) for _ in range(N)
        ]

    @staticmethod
    def from_file(file_name):
        return TSP(json.loads(open(file_name, "r").read()))

    def score(self, tour):
        return sum(euclidean_distance(v1, v2) for (v1, v2) in tour.edges.items())

    def tweak(self):
        pass

    def random_tour(self):
        vertices_left = set(self.cities)
        edges = dict()

        source = random.sample(vertices_left, 1)[0]
        start = source
        vertices_left.remove(source)

        while len(vertices_left) > 0:
            sink = random.sample(vertices_left, 1)[0]
            vertices_left.remove(sink)
            edges[source] = sink
            source = sink

        edges[source] = start

        return Tour(edges)

    def random_grasp_tour(self, alpha):
        """
        pick a random greedyish tour for the GRASP metaheuristic
        at each step, we look at the distance to all possible next cities, then we
        pick randomly from those that add a distance <= c, where
        c = min + alpha * (max - min)
        """
        vertices_left = set(self.cities)
        edges = dict()

        source = random.sample(vertices_left, 1)[0]
        start = source
        vertices_left.remove(source)

        while len(vertices_left) > 0:
            dist_dict = {
                city: euclidean_distance(source, city) for city in vertices_left
            }
            c_max = max(dist_dict.values())
            c_min = min(dist_dict.values())
            cutoff = c_min + alpha * (c_max - c_min)
            sink = random.choice([c for c in vertices_left if dist_dict[c] <= cutoff])
            vertices_left.remove(sink)
            edges[source] = sink
            source = sink
        edges[source] = start
        return Tour(edges)

    def k_opt(self, tour, k, try_only_random_matching=False):
        # print("starting with: ",tour.edges)
        vertices = list(tour.edges.keys())

        sources_to_break = random.sample(vertices, k)
        sinks_to_break = [tour.edges[v] for v in sources_to_break]

        # print("sources:",sources_to_break)
        # print("sinks:",sinks_to_break)

        partial_edges = tour.edges.copy()
        score_loss = sum(
            euclidean_distance(source, partial_edges[source])
            for source in sources_to_break
        )
        for source in sources_to_break:
            del partial_edges[source]

        open_vertices = sources_to_break + sinks_to_break

        if try_only_random_matching:
            matchings = [one_random_matching(open_vertices)]
        else:
            matchings = list(generate_matchings(open_vertices))

        best_score_change = None
        best_edges = None

        while len(matchings) > 0:
            matching = matchings.pop(0)
            score_gain = sum(euclidean_distance(v1, v2) for (v1, v2) in matching)
            # print("matching: ", matching)

            edge_list = list(partial_edges.items())
            edge_list += matching

            # print("edge list: ", edge_list)

            # we now have a bunch of pairs (v_i. v_j) that we have to try to
            # reconstruct into a tour, if possible

            new_edges = []
            active = edge_list[0][0]
            # print("\tactive =", active)
            start = active
            new_edges.append(active)
            valid_edges = True

            while len(edge_list) > 0:
                relevant_edges = [e for e in edge_list if active in e]
                # print("\trelevant =", relevant_edges)
                assert len(relevant_edges) > 0
                next_vertex = [v for v in relevant_edges[0] if v != active][0]
                # print("\tnext_vertex =", next_vertex)
                new_edges.append(next_vertex)
                active = next_vertex
                edge_list.remove(relevant_edges[0])

                if active == start:
                    # print("done. len =",len(edge_list))
                    if len(edge_list) > 0:
                        valid_edges = False
                    break

            valid_one_random = False
            if valid_edges:
                score_change = score_gain - score_loss
                if best_score_change is None or score_change < best_score_change:
                    # print("new best edges =", new_edges)
                    best_score_change = score_change
                    best_edges = new_edges
                    if try_only_random_matching:
                        valid_one_random = True

            if try_only_random_matching:
                if valid_one_random:
                    break
                else:
                    matchings.append(one_random_matching(open_vertices))

        new_dict = {}
        for i in range(len(best_edges) - 1):
            new_dict[best_edges[i]] = best_edges[i + 1]
        # new_dict[best_edges[-1]] = best_edges[0]
        return Tour(new_dict)  # , best_score_change

    @staticmethod
    def partially_mapped_crossover(tour1, tour2):
        assert len(tour1.edges) == len(tour2.edges)
        n = len(tour1.edges)
        city_list = list(tour1.edges.keys())

        # build tours into list form because it will be easier
        T1 = [random.choice(city_list)]
        while len(T1) < n:
            T1.append(tour1.edges[T1[-1]])
        T2 = [random.choice(city_list)]
        while len(T2) < n:
            T2.append(tour2.edges[T2[-1]])

        cutpoints = sorted(random.sample(list(range(n + 1)), 2))
        child = [None for _ in range(n)]

        # copy part between cutpoints from parent #2 into child
        for index in range(cutpoints[0], cutpoints[1]):
            child[index] = T2[index]

        # build the map that fixes duplicates
        middle_map = {T2[i]: T1[i] for i in range(cutpoints[0], cutpoints[1])}

        # now try to build the rest from T1
        for index in range(n):
            if index >= cutpoints[0] and index < cutpoints[1]:
                # we're in the middle, do nothing
                assert child[index] is not None
                continue
            child[index] = T1[index]
            while child[index] in middle_map:
                child[index] = middle_map[child[index]]

        # now child is done, convert back to dict form
        child_dict = {child[i]: child[i + 1] for i in range(n - 1)}
        child_dict[child[-1]] = child[0]
        return Tour(child_dict)

    @staticmethod
    def order_crossover(tour1, tour2):
        assert len(tour1.edges) == len(tour2.edges)
        n = len(tour1.edges)
        city_list = list(tour1.edges.keys())

        # build tours into list form because it will be easier
        T1 = [random.choice(city_list)]
        # T1 = [(1, 1)]
        while len(T1) < n:
            T1.append(tour1.edges[T1[-1]])
        T2 = [random.choice(city_list)]
        # T2 = [(1, 1)]
        while len(T2) < n:
            T2.append(tour2.edges[T2[-1]])

        cutpoints = sorted(random.sample(list(range(n + 1)), 2))
        # cutpoints = [3, 6]
        # print(cutpoints)
        child = [None for _ in range(n)]

        # copy part between cutpoints from parent #2 into child
        for index in range(cutpoints[0], cutpoints[1]):
            child[index] = T2[index]
        # print(child)

        # now we put in entries of T1 in the order they apppear, after the second
        # cutpoint
        placement_index = cutpoints[1] % n
        T1_index = cutpoints[1] % n
        while any(c is None for c in child):
            while T1[T1_index] in child:
                T1_index = (T1_index + 1) % n
            child[placement_index] = T1[T1_index]
            placement_index = (placement_index + 1) % n

        # now child is done, convert back to dict form
        child_dict = {child[i]: child[i + 1] for i in range(n - 1)}
        child_dict[child[-1]] = child[0]
        return Tour(child_dict)

    @staticmethod
    def cycle_crossover(tour1, tour2):
        assert len(tour1.edges) == len(tour2.edges)
        n = len(tour1.edges)
        city_list = list(tour1.edges.keys())

        # build tours into list form because it will be easier
        # T1 = [random.choice(city_list)]
        # T1 = [(1, 1)]
        T1 = [min(city_list)]
        while len(T1) < n:
            T1.append(tour1.edges[T1[-1]])
        # T2 = [random.choice(city_list)]
        T2 = [min(city_list)]
        while len(T2) < n:
            T2.append(tour2.edges[T2[-1]])

        child = [None for _ in range(n)]

        while any(c is None for c in child):

            active_index = min(i for i in range(n) if child[i] is None)
            # print("new loop: AI=", active_index)

            if random.randint(0, 1) == 0:
                active_parent = T1
                non_active_parent = T2
            else:
                active_parent = T2
                non_active_parent = T1

            child[active_index] = active_parent[active_index]
            # print(f"taking {active_parent[active_index]}")
            other_entry = non_active_parent[active_index]

            while other_entry not in child:
                active_index = active_parent.index(other_entry)
                child[active_index] = other_entry
                other_entry = non_active_parent[active_index]
                # print(active_index)
                # print(f"taking {other_entry}")

        # now child is done, convert back to dict form
        child_dict = {child[i]: child[i + 1] for i in range(n - 1)}
        child_dict[child[-1]] = child[0]
        return Tour(child_dict)

    @staticmethod
    def graph_partitioning_crossover(tour1, tour2):
        pass

    @staticmethod
    def _graph_partition(tour1, tour2):

        vertices = set(tour1.edges.values())
        print(vertices)
        cities = set(vertices)
        checked = set()

        t1_neighbor_dict = {
            c: {tour1.edges[c], [k for k in cities if tour1.edges[k] == c][0]}
            for c in cities
        }
        t2_neighbor_dict = {
            c: {tour2.edges[c], [k for k in cities if tour2.edges[k] == c][0]}
            for c in cities
        }

        components = []
        while len(vertices) > 0:
            # find one component
            to_check = {vertices.pop()}
            active_component = []
            print("new component")
            while len(to_check) > 0:
                active = to_check.pop()
                print(active)
                if active in checked:
                    continue
                checked.add(active)
                active_component.append(active)
                if active in vertices:
                    vertices.remove(active)
                # need to find the neighbors of "active" that
                # (1) don't go through edges in both tours
                # (2) ... something about vertices of degree 4???
                #     I think don't go through them at all?

                # if active is a vertex of degree 4 itself, we do not go anywhere from
                # here, it's a dead end
                if (
                    len(
                        set(t1_neighbor_dict[active]).union(
                            set(t2_neighbor_dict[active])
                        )
                    )
                    == 4
                ):
                    continue

                # now we want to look at neighbors that are not neighbors of both and
                # look there as well

                # find the two cities that "active" points to in tour1, and then
                # restrict to only those that have not been considered yet
                t1_neighbors = [
                    t1n for t1n in t1_neighbor_dict[active] if t1n in vertices
                ]

                # find the two cities that "active" points to in tour2, and then
                # restrict to only those that have not been considered yet
                t2_neighbors = [
                    t2n for t2n in t2_neighbor_dict[active] if t2n in vertices
                ]

                for N1 in t1_neighbors:
                    if N1 not in t2_neighbors:
                        # allowed to explore N1 as part of this component
                        to_check.add(N1)
                for N2 in t2_neighbors:
                    if N2 not in t1_neighbors:
                        # allowed to explore N2 as part of this component
                        to_check.add(N2)
            components.append(active_component)

        return components