#(c) 2013-2014 by Authors
#This file is a part of Ragout program.
#Released under the BSD license (see LICENSE file)

"""
This module implements a breakpoint graph
which is widely used in Ragout
"""

from __future__ import absolute_import
from __future__ import division
from itertools import chain
import os
import logging
from copy import copy
from collections import namedtuple

import networkx as nx

from ragout.shared.debug import DebugConfig
from ragout.six.moves import map
from ragout.six.moves import zip

logger = logging.getLogger()
debugger = DebugConfig.get_instance()

GenChrPair = namedtuple("GenChrPair", ["genome", "chr"])

class BreakpointGraph(object):
    """
    Breakpoint graph implementation
    """
    def __init__(self, perm_container=None):
        self.bp_graph = nx.MultiGraph()
        self.target = None
        self.references = []
        self.debug_nodes = set()
        if perm_container is not None:
            self.build_from(perm_container)

    def connected_component_subgraphs(self,G):
        for c in nx.connected_components(G):
            yield G.subgraph(c)

    def build_from(self, perm_container):
        """
        Builds breakpoint graph from permutations
        """
        for perm in perm_container.ref_perms:
            if perm.genome_name not in self.references:
                self.references.append(perm.genome_name)
        self.target = perm_container.target_perms[0].genome_name

        self.contig_ends = []
        for perm in perm_container.target_perms:
            self.contig_ends.append((perm.blocks[0].signed_id(),
                                     -perm.blocks[-1].signed_id()))

        for perm in chain(perm_container.ref_perms,
                          perm_container.target_perms):
            assert perm.blocks
            for prev_block, next_block in perm.iter_pairs():
                self.bp_graph.add_node(-prev_block.signed_id())
                self.bp_graph.add_node(next_block.signed_id())

                self.bp_graph.add_edge(-prev_block.signed_id(),
                                       next_block.signed_id(),
                                       genome_id=perm.genome_name,
                                       chr_name=perm.chr_name,
                                       start=prev_block.end,
                                       end=next_block.start,
                                       infinity=False)

            if perm.genome_name in self.references and not perm.draft:
                self.bp_graph.add_edge(-perm.blocks[-1].signed_id(),
                                       perm.blocks[0].signed_id(),
                                       genome_id=perm.genome_name,
                                       chr_name=perm.chr_name,
                                       infinity=True)

        logger.debug("Built breakpoint graph with %d nodes", len(self.bp_graph))

    def connected_components(self):
        #subgraphs = nx.connected_component_subgraphs(self.bp_graph)
        subgraphs = self.connected_component_subgraphs(self.bp_graph)
        bp_graphs = []
        for subgr in subgraphs:
            bg = BreakpointGraph()
            bg.target = self.target
            bg.references = copy(self.references)
            bg.bp_graph = subgr
            bp_graphs.append(bg)
        return bp_graphs

    def genomes_chrs_support(self, node_1, node_2):
        if not self.bp_graph.has_edge(node_1, node_2):
            return []
        return [GenChrPair(e["genome_id"], e["chr_name"]) for e in
                self.bp_graph[node_1][node_2].values()]

    def genomes_support(self, node_1, node_2):
        return [gp.genome for gp in self.genomes_chrs_support(node_1, node_2)]

    def to_weighted_graph(self, phylogeny):
        """
        Converts a breakpoint graph into a weighted adjacency graph
        using half-breakpoint state parsimony problem
        """
        assert len(self.bp_graph) >= 2
        g = nx.Graph()
        g.add_nodes_from(self.bp_graph.nodes)

        for node in self.bp_graph.nodes:
            adjacencies = {}
            for neighbor in self.bp_graph.neighbors(node):
                for edge in self.bp_graph[node][neighbor].values():
                    adjacencies[edge["genome_id"]] = neighbor

            for ref_id in self.references:
                if ref_id not in adjacencies:
                    adjacencies[ref_id] = None  #"void" state in paper

            break_weights = {}
            for neighbor in self.bp_graph.neighbors(node):
                adjacencies[self.target] = neighbor
                break_weights[neighbor] = phylogeny.estimate_tree(adjacencies)

            #normalization
            total_weights = sum(break_weights.values())
            for neighbor in self.bp_graph.neighbors(node):
                weight = (break_weights[neighbor] / total_weights
                          if total_weights != 0 else 0)
                _update_edge(g, node, neighbor, weight)

        return g

    #def add_debug_node(self, node):
    #    self.debug_nodes.add(node)

    def alternating_cycle(self, node_1, node_2):
        """
        Determines if there is a cycle of alternating colors
        that goes through the given red-supported (!) edge
        """
        def get_genome_ids(xxx_todo_changeme):
            (u, v) = xxx_todo_changeme
            return self.genomes_support(u, v)

        good_path = False
        path = None
        for path in self._alternating_paths(node_1, node_2):
            assert len(path) % 2 == 0
            if len(path) == 2:
                continue

            edges = list(zip(path[:-1], path[1:]))
            even_colors = list(map(get_genome_ids, edges[1::2]))
            even_good = all([set(e) == set([self.target]) for e in even_colors])
            if not even_good:
                continue

            odd_colors = [get_genome_ids(e) for e in edges[0::2]]
            common_genomes = set(odd_colors[0])
            for edge_colors in odd_colors:
                common_genomes = common_genomes.intersection(edge_colors)

            if common_genomes:
                #self._check_distances(path)
                good_path = True
                break

        return len(path) // 2 if good_path else None

    #def _check_distances(self, path):
    #    assert len(path) % 2 == 0
    #    path.append(path[0])
    #    edges = list(zip(path[:-1], path[1:]))
    #    even_dist = list(map(lambda (n1, n2): self.get_distance(n1, n2),
    #                         edges[1::2]))
    #    odd_dist = list(map(lambda (n1, n2): self.get_distance(n1, n2),
    #                        edges[0::2]))
    #    diff = abs(sum(even_dist) - sum(odd_dist))
    #    coeff = float(diff) / (sum(even_dist) + sum(odd_dist))
    #    logger.debug(coeff)

    def is_infinity(self, node_1, node_2):
        if not self.bp_graph.has_edge(node_1, node_2):
            return False

        for edge_data in self.bp_graph[node_1][node_2].values():
            if edge_data["infinity"]:
                return True
        return False

    def get_distance(self, node_1, node_2, phylogeny):
        """
        Tries to guess the distance between synteny blocks
        in a target genome
        """
        DEFAULT_DISTANCE = 0
        if not self.bp_graph.has_edge(node_1, node_2):
            return DEFAULT_DISTANCE
        distances = {e["genome_id"] : e["end"] - e["start"]
                     for e in self.bp_graph[node_1][node_2].values()}

        genomes_order = phylogeny.leaves_by_distance(self.target)
        for g in genomes_order:
            if g in distances:
                return distances[g]

        raise Exception("Distance function error")

    def debug_output(self):
        if not debugger.debugging:
            return

        graph_out = os.path.join(debugger.debug_dir, "breakpoint_graph.dot")
        _output_graph(self.bp_graph, graph_out)

    def _alternating_paths(self, src, dst):
        """
        Finds a path of alternating colors between two nodes
        """
        completed_paths = []
        visited = set()
        dfs_stack = [(src, True, [src])]

        #def rec_helper(node, colored):
        while dfs_stack:
            node, colored, cur_path = dfs_stack.pop()

            if node == dst:
                completed_paths.append(cur_path)
                continue
                #return [[dst]]

            visited.add(node)
            #paths = []
            for neighbor in self.bp_graph.neighbors(node):
                if neighbor in visited:
                    continue

                ##
                genomes = self.genomes_support(node, neighbor)
                #non_target = set(filter(lambda g: g != self.target, genomes))
                non_target = set([g for g in genomes if g != self.target])
                if colored and len(non_target) == 0:
                    continue
                if not colored and self.target not in genomes:
                    continue
                ##

                #far_paths = rec_helper(neighbor, not colored)
                dfs_stack.append((neighbor, not colored, cur_path + [neighbor]))
                #map(lambda p: p.append(node), far_paths)
                #paths.extend(far_paths)
            #visited.remove(node)
            #return paths

        #paths = list(map(lambda p: p[::-1], rec_helper(src, True)))
        return completed_paths


def _update_edge(graph, v1, v2, weight):
    """
    Helper function to update edge's weight
    """
    if not graph.has_edge(v1, v2):
        graph.add_edge(v1, v2, weight=weight)
    else:
        graph[v1][v2]["weight"] += weight


def _output_graph(graph, out_file):
    """
    Outputs graph in dot format
    """
    with open(out_file, "w") as fout:
        fout.write("graph {\n")
        for v1, v2, data in graph.edges(data=True):
            fout.write("{0} -- {1}".format(v1, v2))
            if len(data):
                extra = ["{0}=\"{1}\"".format(k, v) for (k, v) in data.items()]
                fout.write(" [" + ", ".join(extra) + "]")
            fout.write(";\n")
        fout.write("}")