import re
import time
import datetime
import networkx as nx
from os import makedirs
import cStringIO as Buffer
import Alignments.Query as Qry
import Alignments.Utility as Ut
from os.path import join, isdir, isfile
from Alignments.Utility import confusion_matrix
from Alignments.Utility import get_uri_local_name_plus as local_name
from Alignments.UserActivities.Clustering import links_clustering
from Alignments.UserActivities.Plots import metric
# from sys import stderr


# CLUSTER ID
# CLUSTER SIZE
# MACHINE EVAL
# HUMAN EVAL
# RESOURCES


# **************************************************************************************
# THIS FUNCTION BUILDS CONTEXTUAL INFORMATION ON A [SET OF PROVIDED RESOURCES] BASED ON
# [DATASETS] AND [MANDATORY OR OPTIONAL PROPERTIES] OF INTEREST
# **************************************************************************************
def investigate_resources(data, resources):

    # DATASET AND THE PROPERTIES OF INTEREST. EACH PROPERTY CAN BE PROVIDED WITH AN ALTERNATIVE NAME
    # data = {
    #     'dataset-1': {
    #         'mandatory': [('property-1', 'name'), ('property-10', ""), ('property-15', '')],
    #         'optional': [('property-00', 'country'), ]
    #     },
    #     'dataset-2': {
    #         'mandatory': [('property-2', 'name'), ('property-23', ""), ('property-30', "")],
    #         'optional': []
    #     },
    #     'dataset-3': {
    #         'mandatory': [('property-3', 'name'), ('property-36', ""), ('property-33', "")],
    #         'optional': []
    #     }
    # }

    # THE LIST OF RESOURCES TO INVESTIGATE
    # resource = ['resource-1', 'resource-2', 'resource-3']

    # QUERY TEMPLE EXAMPLE
    """
    SELECT *
    {
        # LIST OR RESOURCES TO INVESTIGATE
        VALUES ?resource { resource-1 resource-2 resource-3 }

        {
            GRAPH <dataset-2>
            {
                BIND( <dataset-2> as ?dataset)
                ?resource <property-2> ?name .
                ?resource <property-23> ?dataset-2_property-23 .
                ?resource <property-30> ?dataset-2_property-30 .
            }
        }	UNION

        {
            GRAPH <dataset-3>
            {
                BIND( <dataset-3> as ?dataset)
                ?resource <property-3> ?name .
                ?resource <property-36> ?dataset-3_property-36 .
                ?resource <property-33> ?dataset-3_property-33 .
            }
        }	UNION

        {
            GRAPH <dataset-1>
            {
                BIND( <dataset-1> as ?dataset)
                ?resource <property-1> ?name .
                ?resource <property-10> ?dataset-1_property-10 .
                ?resource <property-15> ?dataset-1_property-15 .
                OPTIONAL { ?resource <property-00> ?country . }
            }
        }
    }
    """

    count_union = 0
    sub_query = ""

    template_1 = """\t{}
        {{
            GRAPH {}
            {{ \n\t\t\t\t{}\n{}{}
            }}
        }}"""

    template_2 = """
    SELECT DISTINCT *
    {{
        # LIST OR RESOURCES TO INVESTIGATE
        VALUES ?resource {{ {} }}
        {}
    }} ORDER BY ?dataset ?resource

    """

    # CONVERTING THE LIST INTO A SPACE SEPARATED LIST
    resource_enumeration = " ".join(Ut.to_nt_format(item) for item in resources)

    for dataset, dictionary in data.items():

        mandatory = dictionary['mandatory']
        optional = dictionary['optional']

        # GENERATE THE SUB-QUERY FOR MANDATORY PROPERTIES
        sub_mandatory = "\n".join(
            "\t\t\t\t?resource {0} ?{1} .".format(
                Ut.to_nt_format(uri), alternative if len(alternative) > 0 else
                "{}_{}".format(local_name(dataset), local_name(uri))) for uri, alternative in mandatory)

        # GENERATE THE SUB-QUERY FOR OPTIONAL PROPERTIES
        if len(optional) > 0:
            sub_optional = "\n".join(
                "\n\t\t\t\tOPTIONAL {{ ?resource {0} ?{1} . }}".format(
                    Ut.to_nt_format(uri), alternative if len(alternative) > 0 else
                    "{}_{}".format(local_name(dataset), local_name(uri))) for uri, alternative in optional)
        else:
            sub_optional = ""

        # BIND THE DATASET TO HAVE IT IN THE SELECT
        bind = "BIND( {} as ?dataset)".format(Ut.to_nt_format(dataset))

        # ACCUMULATE THE SUB-QUERIES
        sub_query += template_1.format(
            "UNION\n" if count_union > 0 else "", Ut.to_nt_format(dataset), bind, sub_mandatory, sub_optional)
        count_union += 1

    # THE FINAL QUERY
    query = template_2.format(resource_enumeration, sub_query)
    # print query
    # Qry.display_result(query, is_activated=True)

    response = Qry.sparql_xml_to_matrix(query)

    if response is None:
        return None
    else:
        return response['result']


# **************************************************************************************
# THIS FUNCTION CONVERTS THE CONTEXTUAL INFORMATION GENERATED BY THE FUNCTION:
# investigate_resources(data, resources) INTO PLAIN LINES SEPARATED BY |
# **************************************************************************************
def get_context(matrix, separator_size=40):

    count = 0
    writer = Buffer.StringIO()
    writer.write("\n")
    format_template = "{{:{}}}".format(separator_size)
    # print format_template

    if matrix is not None:
        for record in matrix:
            count += 1
            record_line = " | ".join(
                format_template.format("") if item is None or len(item) == 0
                else format_template.format(local_name(item.upper())) for item in record)
            writer.write("{}\n".format(record_line))

    else:
        print "THE MATRIX IS EMPTY"

    return writer.getvalue()


# **************************************************************************************
# THIS FUNCTION CONVERTS THE CONTEXTUAL INFORMATION GENERATED BY THE FUNCTION:
# investigate_resources(data, resources) INTO PLAIN LINES LINES SEPARATED BY |
# BUT INSERTS THE LINES INTO A BIGGER FRAME FOR VALIDATION INVESTIGATION.
# THE DATA IS FINALLY WRITTEN TO FILE
# **************************************************************************************
def write_record(count_record, size, record_format, matrix, writer, cluster_id="",
                 separator_size=40, machine_decision="", weighted_decision=None, has_cycle='no', node_in_cycle=None):

    count = 0
    format_template = "{{:{}}}".format(separator_size)
    # print >> stderr, count_record, '\r',
    # TRAILING COMMA FORCES THE COUNT TO REMAIN ON THE SAME LINE
    print "{:>5}".format(count_record),

    if matrix is not None:
        for record in matrix:
            count += 1

            # print record_line
            if count == 1:
                record_line = " | ".join(
                    format_template.format("") if item is None or len(item) == 0
                    else format_template.format(local_name(item.upper())) for item in record)

                writer.write(record_format.format(
                    count_record, cluster_id, size, "-{}-".format(machine_decision),
                    "-{}-".format(weighted_decision["min"]), "-{}-".format(weighted_decision["avg"]),
                    "-{}-".format(weighted_decision["bcd"]), "- -", has_cycle, "", "", "", record_line))
            else:

                if node_in_cycle is not None:
                    # print local_name(record[0])
                    node = "-X-" if Ut.to_nt_format(record[0]) in node_in_cycle else "- -"
                    group = "-1-" if Ut.to_nt_format(record[0]) in node_in_cycle else "- -"
                else:
                    node = "- -"
                    group = "- -"

                record_line = " | ".join(
                    format_template.format("") if item is None or len(item) == 0
                    else format_template.format(local_name(item)) for item in record)

                writer.write(record_format.format("", "", "", "", "", "", "", "", "", group, node, "", record_line))

    else:
        print "THE MATRIX IS EMPTY"


def rewrite_record(count_record, size, record_format, matrix, writer, evaluation, cluster_id="",
                 separator_size=40, has_cycle='no', node_in_cycle=None):

    count = 0
    format_template = "{{:{}}}".format(separator_size)
    # print >> stderr, count_record, '\r',
    # TRAILING COMMA FORCES THE COUNT TO REMAIN ON THE SAME LINE
    # print "{:>5}".format(count_record),

    if matrix is not None:
        for record in matrix:
            count += 1

            # print record_line
            if count == 1:
                # print record


                status = "-{}-".format(evaluation['NOT GOOD']) if 'NOT GOOD' in evaluation else ""

                print record_format.format(
                    count_record, cluster_id, size, "-{}-".format(evaluation['original']),
                    "-{}-".format(evaluation["min"]), "-{}-".format(evaluation["avg"]),
                    "-{}-".format(evaluation["bcd"]), "-{}-".format(evaluation["human"]), has_cycle, status, "", "", record)

                writer.write(record_format.format(
                    count_record, cluster_id, size, "-{}-".format(evaluation['original']),
                    "-{}-".format(evaluation["min"]), "-{}-".format(evaluation["avg"]),
                    "-{}-".format(evaluation["bcd"]), "-{}-".format(evaluation["human"]), has_cycle, status, "", "", record))
            else:

                node = "-{}-".format(record[1])
                group = "-{}-".format(record[0])

                # print record
                print record_format.format("", "", "", "", "", "", "", "", "", group, node, "", record[2])

                writer.write(record_format.format("", "", "", "", "", "", "", "", "", group, node, "", record[2]))

    else:
        print "THE MATRIX IS EMPTY"

# **************************************************************************************
#  THIS FUNCTION COMBINES
#   - investigate_resources(data, resources)
#   - write_record( size, record_format, matrix, writer, cluster_id="",
#                   separator_size=40, machine_decision="", has_cycle='no')
#
# TO GENERATE AN EVALUATION SHEET BASED ON THE FOLLOWING RETRIEVED/GENERATED INFORMATION:
#   "CLUSTER-ID", "CLUSTER-SIZE", "MACHINE-EVAL", "HUMAN-EVAL",
#   "HAS-CYCLE", "NOT GOOD", "CYCLE", "RESOURCES"
# **************************************************************************************
def generate_sheet(data, directory, graph, serialisation_dir,
                   related_alignment=None, separator_size=40, size=None, activated=False):

    """
    :param data: DICTIONARY PROVIDING INFO ON DATASET AND THE PROPERTIES OF INTEREST. EACH PROPERTY
        CAN BE PROVIDED WITH AN ALTERNATIVE NAME. SEE COMMENT IN investigate_resources(data, resources)
    :param directory: THE DIRECTORY WHERE THE SHEET WOULD BE SAVED
    :param graph: THE ALIGNMENT GRAPH WITH MATCHED INSTANCES TO BE CLUSTERED
    :param serialisation_dir: THE SERIALISATION DIRECTORY IN THE EVEN THE CLUSTER HAS ALREADY PROCESSED
    :param related_alignment:
    :param separator_size: ATTRIBUTE SEPARATOR WHITE SPACE FOR EVAL SHEET FORMATTING
    :param size: CLUSTER SIZE
    :param activated: activation boolean argument
    :return:
    """

    if activated is False:
        print "\n>>> THE FUNCTION [generate_sheet] IS NOT ACTIVATED."
        return

    start = time.time()
    count = 0
    count_c = 0
    count_b = 0
    count_nc = 0
    cycles = None
    # extended = None
    header_separator_size = 23

    # FILE DATE
    # date = datetime.date.isoformat(datetime.date.today()).replace('-', '')
    date = (str(datetime.datetime.utcnow())[:-7]).replace('-', '').replace(':', '').replace(' ', '-')
    hashed = Ut.hash_it(graph)
    directory = join(directory, hashed)

    if isdir(directory) is False:
        makedirs(directory)

    # THE WRITER
    writer_cycle = open(join(directory, "EvalSheet_{}_{}_cycle.txt".format(hashed, date)), 'wb')
    writer_no_cycle = open(join(directory, "EvalSheet_{}_{}_noCycle.txt".format(hashed, date)), 'wb')
    writer_2 = open(join(directory, "EvalSheet_{}_{}_biggerThan_{}.txt".format(hashed, date, size)), 'wb')

    # RECORD FORMAT
    record_format = "{{:<7}}{{:<{0}}}{{:<14}}|{{:<{0}}}" \
                    "|{{:<{0}}}|{{:<{0}}}|{{:<{0}}}|{{:<12}}|{{:<12}}" \
                    "{{:<10}}{{:<7}}|{{:<{0}}}|{{:<{0}}}\n".format(header_separator_size)
    # print record_format

    # RECORD HEADER
    header = record_format.format(
        "COUNT", "CLUSTER-ID", "CLUSTER-SIZE", "MACHINE-EVAL", "MACHINE-MIN-EVAL", "MACHINE-AVG-EVAL",
        "MACHINE-ALL-EVAL", "HUMAN-EVAL", "HAS-CYCLE", "NOT GOOD", "CYCLE", "COMMENT", "RESOURCES")

    # WRITING THE FILE HEADER
    writer_cycle.write(header)
    writer_no_cycle.write(header)
    writer_2.write(header)

    # **************************************************************************************
    # 1. GENERATING / EXTRACTING CLUSTERS, EXTENDED CLUSTERS AND LIST OF CLUSTERS IN A CYCLE
    # **************************************************************************************
    # 1.1 IF THE RELATED ALIGNMENT IS NOT PROVIDED, ONLY THE CLUSTERS DICTIONARY IS RETURNED
    if related_alignment is None:
        clusters = links_clustering(graph=graph, serialisation_dir=serialisation_dir)
        cycle_paths = None

    # 1.2 IF THE RELATED ALIGNMENT IS PROVIDED, THEN THE EXTENDED CLUSTERS AND CLUSTERS IN A CYCLE
    # IS COMPUTED IF NT SERIALISED OR READ FROM FILE IF SERIALISED
    else:
        results = links_clustering(
            graph=graph, serialisation_dir=serialisation_dir, related_linkset=related_alignment)

        if type(results) is tuple:
            clusters, extended = results
            cycles = extended['list_extended_clusters_cycle']
            if 'cycle_paths' in extended:
                cycle_paths = extended['cycle_paths']
            else:
                cycle_paths = None

        else:
            clusters = results
            cycles = None
            cycle_paths = None

        # print "\n", extended

    print ""
    # **************************************************************************************
    # 2. ITERATE THROUGH EACH CLUSTER FOR GENERATING CONTEXTUAL INFORMATION FOR VALIDATION
    # **************************************************************************************
    for cluster_id, cluster in clusters.items():

        count += 1
        nodes = cluster['nodes']
        cluster_size = len(nodes)

        if cycles is None:
            contain_cycle = "no"
        else:
            contain_cycle = 'yes' if cluster_id in cycles else 'no'

        # COMPUTE THE MACHINE EVALUATION
        if cluster_size > 500:
            decision = "NOT COMPUTED [NA]"
            weighted_decision = {"min": "NA", "avg": "NA", "bcd": "na"}
        else:
            estimations = metric(cluster['links'], strengths=cluster['strengths'])
            decision = estimations["AUTOMATED_DECISION"]
            weighted_decision = estimations["WEIGHTED_DECISION"]

        if size is None or cluster_size <= size:

            # FETCH DATA ABOUT THE PROVIDED RESOURCES
            matrix = investigate_resources(data, resources=nodes)

            if contain_cycle == 'yes':

                final = set()
                if cycle_paths is not None:
                    start_end_paths = cycle_paths[cluster_id]
                    for start_node, end_node, strength in start_end_paths:
                        path_nodes = shortest_paths(cluster["links"], start_node, end_node)
                        for path_list in path_nodes:
                            for node in path_list:
                                final.add(node)

                final = list(final) if len(final) > 0 else None

                # print "NODES IN CYCLE:", final

                count_c += 1

                # WRITE THE FETCHED DATA TO SOURCE
                # THE FUNCTION HAS A TRAILING COMMA FORCING THE COUNT TO REMAIN ON THE SAME LINE
                write_record(count_c, cluster_size, record_format=record_format, matrix=matrix, writer=writer_cycle,
                             cluster_id=cluster_id, machine_decision=decision, separator_size=separator_size,
                             has_cycle=contain_cycle, node_in_cycle=final, weighted_decision=weighted_decision)

                # ADD A NEW LINE
                writer_cycle.write("\n")

            else:

                count_nc += 1

                # WRITE THE FETCHED DATA TO SOURCE
                # THE FUNCTION HAS A TRAILING COMMA FORCING THE COUNT TO REMAIN ON THE SAME LINE
                write_record(count_nc, cluster_size, record_format=record_format, matrix=matrix, writer=writer_no_cycle,
                             cluster_id=cluster_id, machine_decision=decision, separator_size=separator_size,
                             has_cycle=contain_cycle, weighted_decision=weighted_decision)

                # ADD A NEW LINE
                writer_no_cycle.write("\n")

            # if count % 10 == 0 or count == 1:
            if count % 10 == 0:
                print "{:6} {:25}{:6}".format(count, cluster_id, decision), \
                    "so far {} has passed".format(datetime.timedelta(seconds=time.time() - start))

        else:
            count_b += 1
            writer_2.write(record_format.format(
                count_b, cluster_id, cluster_size, decision, "", contain_cycle, "", "", ""))

        if count == 500:
            break

    writer_cycle.close()
    writer_no_cycle.close()
    writer_2.close()

    print "RESULT CAN BE FOUND IN {}.".format(directory)
    print "\nJob Done in {}".format(datetime.timedelta(seconds=time.time() - start))


def generate_sheet_cyc(data, directory, graph, serialisation_dir, related_alignment=None, separator_size=40, size=None):

    start = time.time()
    count = 0
    count_c = 0
    count_b = 0
    count_nc = 0
    cycles = None
    # extended = None
    header_separator_size = 23

    # FILE DATE
    # date = datetime.date.isoformat(datetime.date.today()).replace('-', '')
    date = (str(datetime.datetime.utcnow())[:-7]).replace('-', '').replace(':', '').replace(' ', '-')
    hashed = Ut.hash_it(graph)
    directory = join(directory, hashed)

    if isdir(directory) is False:
        makedirs(directory)

    # THE WRITER
    writer_cycle = open(join(directory, "EvalSheet_{}_{}_cycle.txt".format(hashed, date)), 'wb')
    writer_no_cycle = open(join(directory, "EvalSheet_{}_{}_noCycle.txt".format(hashed, date)), 'wb')
    writer_2 = open(join(directory, "EvalSheet_{}_{}_biggerThan_{}.txt".format(hashed, date, size)), 'wb')

    # RECORD FORMAT
    record_format = "{{:<7}}{{:<{0}}}{{:<14}}{{:<{0}}}{{:<12}}{{:<12}}{{:<10}}{{:<7}}{{:<{0}}}\n".format(
        header_separator_size)
    print record_format

    # RECORD HEADER
    header = record_format.format(
        "COUNT", "CLUSTER-ID", "CLUSTER-SIZE", "MACHINE-EVAL", "HUMAN-EVAL", "HAS-CYCLE", "NOT GOOD", "CYCLE",
        "RESOURCES")

    # **************************************************************************************
    # 1. GENERATING / EXTRACTING CLUSTERS, EXTENDED CLUSTERS AND LIST OF CLUSTERS IN A CYCLE
    # **************************************************************************************
    # 1.1 IF THE RELATED ALIGNMENT IS NOT PROVIDED, ONLY THE CLUSTERS DICTIONARY IS RETURNED
    if related_alignment is None:
        clusters = links_clustering(graph=graph, serialisation_dir=serialisation_dir)

    # 1.2 IF THE RELATED ALIGNMENT IS PROVIDED, THEN THE EXTENDED CLUSTERS AND CLUSTERS IN A CYCLE
    # IS COMPUTED IF NT SERIALISED OR READ FROM FILE IF SERIALISED
    else:
        clusters, extended = links_clustering(
            graph=graph, serialisation_dir=serialisation_dir, related_linkset=related_alignment)
        cycles = extended['list_extended_clusters_cycle']

        # print "\n", extended

    print ""
    # **************************************************************************************
    # 2. ITERATE THROUGH EACH CLUSTER FOR GENERATING CONTEXTUAL INFORMATION FOR VALIDATION
    # **************************************************************************************
    for cluster_id, cluster in clusters.items():

        count += 1
        nodes = cluster['nodes']
        cluster_size = len(nodes)

        if cycles is None:
            contain_cycle = "no"
        else:
            contain_cycle = 'yes' if cluster_id in cycles else 'no'

        # COMPUTE THE MACHINE EVALUATION
        if cluster_size > 500:
            decision = "NOT COMPUTED [NA]"
        else:
            decision = metric(cluster['links'])["AUTOMATED_DECISION"]

        if size is None or cluster_size <= size:

            # FETCH DATA ABOUT THE PROVIDED RESOURCES
            matrix = investigate_resources(data, resources=nodes)

            if contain_cycle == 'yes':

                count_c += 1
                # WRITING THE FILE HEADER
                writer_cycle.write(header)

                # WRITE THE FETCHED DATA TO SOURCE
                write_record(count_c, cluster_size, record_format=record_format, matrix=matrix, writer=writer_cycle,
                             cluster_id=cluster_id, machine_decision=decision, separator_size=separator_size,
                             has_cycle=contain_cycle)

                # ADD A NEW LINE
                writer_cycle.write("\n")

                if count_c == 150:
                    break

            else:

                count_nc += 1

                # ****************************************
                # WRITING THE FILE HEADER FOR CONVENIENCE
                # ****************************************
                writer_no_cycle.write(header)

                # WRITE THE FETCHED DATA TO SOURCE
                write_record(count_nc, cluster_size, record_format=record_format, matrix=matrix, writer=writer_no_cycle,
                             cluster_id=cluster_id, machine_decision=decision, separator_size=separator_size,
                             has_cycle=contain_cycle)

                # ADD A NEW LINE
                writer_no_cycle.write("\n")

            # if count % 10 == 0 or count == 1:
            if count % 10 == 0:
                print "{:6} {:25}{:6}".format(count, cluster_id, decision), \
                    "so far {} has passed".format(datetime.timedelta(seconds=time.time() - start))

        else:
            count_b += 1
            # WRITING THE FILE HEADER
            writer_2.write(header)
            writer_2.write(
                record_format.format(count_b, cluster_id, cluster_size, decision, "", contain_cycle, "", "", ""))

        # if count == 50:
        #     break

    writer_cycle.close()
    writer_no_cycle.close()
    writer_2.close()

    print "\nJob Done in {}".format(datetime.timedelta(seconds=time.time() - start))


# **************************************************************************************
# GIVEN TWO NODES, FIND THE SHORTEST PATHS
# THE LINK NETWORK INPUT IS A LIST OF TUPLES WHERE A TUPLE REPRESENTS LINKS BETWEEN
# A PAIR OF NODES. THE FUNCTION MAKES USE OF THE NETWORKS LIBRARY
# **************************************************************************************
def shortest_paths(link_network, start_node, end_node):

    print "COMPUTING PATH..."

    # EXTRACT THE NODES FROM THE NETWORK OF LINKS
    nodes = set([n1 for n1, n2 in link_network] + [n2 for n1, n2 in link_network])

    # INSTANTIATE THE GRAPH
    g = nx.Graph()

    # add nodes
    for node in nodes:
        g.add_node(node)

    # add edges
    for edge in link_network:
        g.add_edge(edge[0], edge[1])

    # GET THE LIT OF PATHS
    # results = list(nx.shortest_simple_paths(g, source=start_node, target=end_node))
    results = shortest_paths_lite(g, source=start_node, target=end_node)

    # EXTRACT THE SHORTEST PATH  OF THE SMALLEST SIZE
    # for item in results:
    #
    #     if len(item) == len(results[0]):
    #         final += [item]
    #
    #     else:
    #         break

    print "DONE COMPUTING PATH!"
    return results


def shortest_path_nodes(link_network, start_node, end_node):

    final = set()

    # EXTRACT THE NODES FROM THE NETWORK OF LINKS
    nodes = set([n1 for n1, n2 in link_network] + [n2 for n1, n2 in link_network])

    # INSTANTIATE THE GRAPH
    g = nx.Graph()

    # add nodes
    for node in nodes:
        g.add_node(node)

    # add edges
    for edge in link_network:
        g.add_edge(edge[0], edge[1])

    # GET THE LIT OF PATHS
    results = list(nx.shortest_simple_paths(g, source=start_node, target=end_node))

    # EXTRACT THE SHORTEST PATH
    for item in results:

        if len(item) == len(results[0]):
            for data in item:
                final.add(data)

        else:
            break

    return list(final)


def shortest_paths_lite(g, source, target):

    # print g

    # get the shortest but not necessarily unique path
    result = nx.shortest_path(g, source=source, target=target)
    results = []

    # if result is a path, add it to the list and try to find other pathts of same size
    if result is not None:
        results = [result]
        size = len(result)

        # for each of the results of same size found, remove edges to try and find other paths
        for result in results:
            # print result
            partials = []

            # for each pair in the path, remove the link and check the shortest path and add it again
            for i in range(len(result)-1):
                # print "removing ", result[i], ', ', result[i+1]
                g.remove_edge(result[i], result[i+1])
                try:
                    partial = nx.shortest_path(g, source=source, target=target)

                except IOError:
                    partial = []

                except nx.NetworkXNoPath:
                    partial = []

                except Exception:
                    partial = []

                # if there is a path of same size, keep it in a set (there can be repetition)
                if len(partial) == size:
                    if partial not in partials:
                        partials += [partial]

                g.add_edge(result[i], result[i+1])

            # add whatever paht found if so
            for p in partials:
                if p not in results:
                    results += [p]
            # print 'new paths: ', partials

    return results


def nodes_in_cycle(specs):

    # specs = {
    #     'investigated_cluster': {"network": links_ve, "start": "Al", 'end': "oladele"},
    #     'extended_cluster': {"network": links_al, "start": "Al", 'end': "oladele"}
    # }

    investigated_cluster = specs["investigated_cluster"]
    extended_cluster = specs["extended_cluster"]
    source = shortest_paths(investigated_cluster["network"], investigated_cluster["start"], investigated_cluster["end"])
    target = shortest_paths(extended_cluster["network"], extended_cluster["start"], extended_cluster["end"])

    nodes = []

    for item in source:
        for element in target:
            nodes += [item + element]

    for item in nodes:
        print item


def reconciliation_strength(investigated_diameter, evidence_diameter, penalty_percentage=10):

    penalty = (100 - penalty_percentage * (evidence_diameter - 1)) / float(100)
    return 0 if penalty < 0 else (1 / float(investigated_diameter)) * penalty


def path_factorial(paths):

    size = len(paths)
    for i in range(0, size):
        print paths[i]

        for j in range(i+1, size):
            print "\t", paths[i], paths[j]


def print_tuple(tuple_list, return_print=False):

    if return_print is False:
        print " | ".join(tuple_list)
        return ""

    else:
        return " | ".join(tuple_list)


def print_list(data_list, comment="", return_print=False):

    builder = Buffer.StringIO()
    if return_print is True:

        for item in data_list:
            try:
                if type(item) == tuple:
                    builder.write("{}\n".format(print_tuple(item, return_print=return_print)))

                elif type(item) == list:
                    builder.write("{}\n".format(print_list(item)))

                else:
                    builder.write("{}\n".format(item))

            except IOError:
                print "PROBLEM!!!"

        builder.write(Ut.headings("\n{}\nDICTIONARY SIZE : {}".format(comment, len(data_list))) + "\n\n")
        return builder.getvalue()

    print ""
    for item in data_list:
        try:
            if type(item) == tuple:
                print_tuple(item)

            elif type(item) == list:
                print_list(item)

            else:
                print item

        except IOError:
            print "PROBLEM!!!"

    if len(comment) == 0:
        "\n{}\nLIST SIZE : {}".format(comment, len(data_list))

    else:
        print Ut.headings("\n{}\nLIST SIZE : {}".format(comment, len(data_list)))

    return ""


def print_dict(data_dict, comment="", return_print=False):

    if return_print is True:
        builder = Buffer.StringIO()
        for key, value in data_dict.items():
            try:
                builder.write("KEY: {:<10}  ITEM SIZE: {:<6} ITEM: {}\n".format(key, len(value), str(value)))

            except IOError:
                print "PROBLEM!!!"

        builder.write(Ut.headings("\n{}\nDICTIONARY SIZE : {}".format(comment, len(data_dict))) + "\n\n")
        return builder.getvalue()

    print ""
    for key, value in data_dict.items():
        try:
            print "KEY: {:<6}  SIZE: {:<6} ITEM: {}".format(key, len(value), str(value))

        except IOError:
            print "PROBLEM!!!"

    print Ut.headings("\n{}\nDICTIONARY SIZE : {}".format(comment, len(data_dict)))


# THIS FUNCTION COMPUTES THE CONFUSION MATRIX FOR VALIDATED SHEETS AND PROVIDES SOME ADDITIONAL STATS.
def extract_eval(
        eval_sheet_path, metric_index, save_in, keyword=1, zero_rule=False, print_stats=False, activated=False):

    evidence = True

    if activated is False:
        print "\n>>> THE FUNCTION [extract_eval] IS NOT ACTIVATED."
        return

    if isfile(eval_sheet_path) is False:
        print "\n>>> THE FILE {}\nDOES NOT EXITS".format(eval_sheet_path)
        return

    description = str(keyword).replace(" ", "_")

    size_two_clusters = []
    machine_good_results = []
    machine_bad_results = []
    metric_result_pattern = "-(\w+) \[\d.\d+\]-"
    line_pattern = "(\d+) +([NP]\d+) +(\d+) +\|{0} +\|{0} +\|{0} +\|{0} +\|-(.)- +\|(\w+)".format(metric_result_pattern)
    m_good_frequency = {}
    m_bad_frequency = {}
    true_positive = []
    false_positive = []
    true_negative = []
    false_negative = []
    good_size_two = []
    bad_size_two = []
    positive_ground_truth = []
    # print line_pattern

    true_pos_two = 0
    false_pos_two = 0
    false_neg_two = 0
    true_neg_two = 0

    count = 0
    count_clusters = 0
    print ""
    with open(eval_sheet_path, 'rb') as reader:

        for line in reader:

            count += 1
            print '\r', ">>> Line {:<6}".format(count),

            # EXTRACT THE EVALUATION LINE
            matched = re.findall(line_pattern, line)
            if len(matched) > 0:

                count_clusters += 1
                # if count <= 9:
                #     print "\n", matched
                # good = filter(lambda x : x.upper() == "GOOD", matched[0])

                cluster = matched[0][1]
                size = matched[0][2]
                eval_machine = matched[0][2 + metric_index]
                eval_human = matched[0][7]
                has_cycle = matched[0][8]
                output = [(cluster, eval_machine, eval_human, has_cycle)]

                # print "{:15} {:15}".format(eval_machine, eval_human)
                # print "{:<15} {:<15} {:<15}".format(matched[0][2], matched[0][3], matched[0][4])

                if size != "2":

                    # MACHINE EVALUATED GOOD
                    if eval_machine == "GOOD":

                        # DOCUMENTING GOOD RESULTS
                        machine_good_results += matched

                        # COMPUTE CLUSTER SIZE FREQUENCY
                        if size not in m_good_frequency:
                            m_good_frequency[size] = output
                        else:
                            m_good_frequency[size] += output

                        # HUMAN EVALUATION
                        if eval_human.upper() == "G":
                            positive_ground_truth += output
                            true_positive += output
                        else:
                            false_positive += output

                    # MACHINE EVALUATED BAD
                    else:

                        # DOCUMENTING BAD RESULTS
                        machine_bad_results += matched

                        # COMPUTE CLUSTER SIZE FREQUENCY
                        if size not in m_bad_frequency:
                            m_bad_frequency[size] = output
                        else:
                            m_bad_frequency[size] += output

                        # HUMAN EVALUATION
                        if eval_human.upper() == "B":
                            true_negative += output
                        else:
                            positive_ground_truth += output
                            false_negative += output

                # SIZE TWO CLUSTERS
                else:
                    # DOCUMENTING CLUSTERS OF SIZE 6

                    size_two_clusters += output
                    if eval_human.upper() == "G":
                        good_size_two += output
                        if evidence is True:
                            true_pos_two += 1
                        else:
                            false_pos_two +=1

                    else:
                        bad_size_two += output
                        if evidence is True:
                            false_neg_two += 1
                        else:
                            true_neg_two +=1


    true_pos = len(true_positive)
    true_neg = len(true_negative)
    false_pos = len(false_positive)
    false_neg = len(false_negative)


    pos_ground_truth = len(positive_ground_truth)
    observed = len(machine_good_results) + len(machine_bad_results)

    with open(join(save_in, "ANALYSIS-{}.txt".format(description)), 'wb') as writer:

        if print_stats:
            writer.write(print_dict(m_good_frequency,
                                    "FREQUENCY OF MACHINE GOOD", return_print=True) if print_stats else "")
            writer.write(print_dict(m_bad_frequency,
                                    "FREQUENCY OF MACHINE BAD", return_print=True) if print_stats else "")
            writer.write(print_list(true_positive, "TRUE POSITIVE", return_print=True) if print_stats else "")
            writer.write(print_list(false_positive, "FALSE POSITIVE", return_print=True) if print_stats else "")
            writer.write(print_list(true_negative, "TRUE NEGATIVE", return_print=True) if print_stats else "")
            writer.write(print_list(false_negative, "FALSE NEGATIVE", return_print=True) if print_stats else "")
            writer.write(print_list(good_size_two, "GOOD SIZE 2", return_print=True) if print_stats else "")
            writer.write(print_list(bad_size_two, "BAD SIZE 2", return_print=True) if print_stats else "")



        confusion_2 = confusion_matrix(true_pos_two, false_pos_two, true_neg_two, false_neg_two, len(good_size_two),
                                     observations=len(good_size_two) + len(bad_size_two), latex=False,
                                       zero_rule=zero_rule)

        confusion_bigger = confusion_matrix(true_pos, false_pos, true_neg, false_neg, pos_ground_truth,
                                     observations=observed, latex=False, zero_rule=zero_rule)

        # print "\nlength", len(confusion)
        # for data in confusion:
        #     for val in data:
        #         print val

        writer.write("{}\n".format(confusion_bigger[0][0]))
        smaller = len(size_two_clusters)
        smaller_per = round((smaller/float(count_clusters)) * 100, 3)
        bigger = count_clusters - smaller
        bigger_per = round((bigger / float(count_clusters)) * 100, 3)

        stats = "\nWITH A TOTAL OF {} CLUSTERS COMPOSED of : " \
                "\n\t- {:>6} ({}%) CLUSTERS OF SIZE 2 AND \n\t- {:>6} ({}%) " \
                "OF SIZE 3 AND BIGGER.".format(count_clusters, smaller, smaller_per, bigger, bigger_per)

        if zero_rule is True:
            writer.write("{}\n".format(confusion_2[1][0]))
            writer.write("{}\n".format(confusion_bigger[1][0]))

        writer.write("\n{}".format(stats))

        print stats


# REEVALUATES AN EVALUATION SHEET BASED ON NEW THRESHOLD AND EXISTENT MEASURES
def machine_reevaluation(file_path, threshold = 0.90):

    clusters = {}
    # file_path = "C:\Productivity\\1 - GA - VALIDATION\N1689818117\EvalSheet_N1689818117_20181031-213340_noCycle.txt"
    metric_pattern = "\w+ \[(\d.\d+)\]"
    metric_result_pattern = "-(\w+ \[\d.\d+\])-"
    line_pattern = "(\d+) +([NP]\d+) +(\d+) +\|{0} +\|{0} +\|{0} +\|{0} +\|-(.)- +\|(\w+)".format(metric_result_pattern)
    line_pattern_3 = "(\d+) +([NP]\d+) +(\d+) +\|{0} +\|{0} +\|{0} +\|{0} +\|-(.)- +\|(\w+) +-(.)-".format(
        metric_result_pattern)
    line_pattern_2 = " +-(.)- +-(.)-".format(metric_result_pattern)
    count = 0


    header_separator_size = 23
    record_format = "{{:<7}}{{:<{0}}}{{:<14}}|{{:<{0}}}" \
                    "|{{:<{0}}}|{{:<{0}}}|{{:<{0}}}|{{:<12}}|{{:<12}}" \
                    "{{:<10}}{{:<7}}|{{:<{0}}}|{{:<{0}}}\n".format(header_separator_size)
    header = record_format.format(
        "COUNT", "CLUSTER-ID", "CLUSTER-SIZE", "MACHINE-EVAL", "MACHINE-MIN-EVAL", "MACHINE-AVG-EVAL",
        "MACHINE-ALL-EVAL", "HUMAN-EVAL", "HAS-CYCLE", "NOT GOOD", "CYCLE", "COMMENT", "RESOURCES")

    def reevaluation(metric_result):

        matched = re.findall(metric_pattern, metric_result)

        if float(matched[0]) >= threshold:
            return "GOOD [{}]".format(matched[0])
        return "BAD [{}]".format(matched[0])

    file_rewrote = file_path.replace(".txt", "-reevaluated.txt")
    writer = open(file_rewrote, 'wb')
    writer.write(header)

    with open(file_path, "rb") as info:

        start = False
        matrix = []
        cluster_id = ""
        for line in info:

            match2 = re.findall(line_pattern_3, line)
            match = re.findall(line_pattern, line) if len(match2) == 0 else match2

            if len(match) > 0:
                # print match, len(match)

                if len(matrix) > 0 and start is True:
                    count += 1
                    # Ut.print_list(matrix)
                    clusters[cluster_id]['matrix'] = matrix
                    evaluation = {"min": clusters[cluster_id]['MACHINE-MIN-EVAL'],
                                  "avg": clusters[cluster_id]['MACHINE-AVG-EVAL'],
                                  "bcd": clusters[cluster_id]['MACHINE-ALL-EVAL'],
                                  "human": clusters[cluster_id]['HUMAN-EVAL'],
                                  "original": clusters[cluster_id]['MACHINE-EVAL']}
                    if 'NOT GOOD' in clusters[cluster_id]:
                        print "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!", match[0], len(match[0])
                        evaluation['NOT GOOD'] = clusters[cluster_id]['NOT GOOD']
                    rewrite_record(count_record=count, size=clusters[cluster_id]['CLUSTER-SIZE'],
                                   record_format=record_format, matrix=matrix, writer=writer, cluster_id=cluster_id,
                                   separator_size=40, evaluation=evaluation, has_cycle='no', node_in_cycle=None)
                    writer.write("\n")

                start = True
                matrix = [line[183:].rstrip()]
                cluster_id = match[0][1]
                clusters[match[0][1]] = {
                    'CLUSTER-SIZE': match[0][2],
                    'MACHINE-EVAL': reevaluation(match[0][3]),
                    'MACHINE-MIN-EVAL': reevaluation(match[0][4]),
                    'MACHINE-AVG-EVAL': reevaluation(match[0][5]),
                    'MACHINE-ALL-EVAL': reevaluation(match[0][6]),
                    'HUMAN-EVAL': match[0][7],
                    'HAS-CYCLE': match[0][8]

                }

                if len(match[0]) == 10:
                    clusters[match[0][1]]['NOT GOOD'] = match[0][9]

            else:
                input = line[183:].rstrip()
                match = re.findall(line_pattern_2, line)
                # if len(match) > 0:
                #     evaluation['NOT GOOD'] = match[0][0]
                #     evaluation['CYCLE'] = match[0][1]

                if len(input) > 0 and len(match) > 0:
                    # print "INPUT:", input, len(input)
                    matrix += [(match[0][0], match[0][1], input)]

                elif len(input) > 0 and len(match) == 0 and start is True:
                    print "PROBLEM:", line
                    exit(0)

            # if count == 20:
            #     break


        # LOAD THE LEFT OVERS
        if len(matrix) > 0 and start is True:
            count += 1
            # Ut.print_list(matrix)
            clusters[cluster_id]['matrix'] = matrix
            evaluation = {"min": clusters[cluster_id]['MACHINE-MIN-EVAL'],
                          "avg": clusters[cluster_id]['MACHINE-AVG-EVAL'],
                          "bcd": clusters[cluster_id]['MACHINE-ALL-EVAL'],
                          "human": clusters[cluster_id]['HUMAN-EVAL'],
                          "original": clusters[cluster_id]['MACHINE-EVAL']}
            if 'NOT GOOD' in clusters[cluster_id]:
                # print match[0], len(match[0])
                evaluation['NOT GOOD'] = clusters[cluster_id]['NOT GOOD']
            rewrite_record(count_record=count, size=clusters[cluster_id]['CLUSTER-SIZE'],
                           record_format=record_format, matrix=matrix, writer=writer, cluster_id=cluster_id,
                           separator_size=40, evaluation=evaluation, has_cycle='no', node_in_cycle=None)
            writer.write("\n")
    # Ut.print_dict(clusters)

    return file_rewrote


# TRANSFERS VALIDATIONS OF FILE 1 TO FILES 2 WITCH IS YET TO BE VALIDATED
def transfer(file_1, file_2, save_in):

    clusters_1 = {}
    clusters_2 = {}
    metric_result_pattern = "-(\w+ \[\d.\d+\])-"
    line_pattern = "(\d+) +([NP]\d+) +(\d+) +\|{0} +\|{0} +\|{0} +\|{0} +\|-(.)- +\|(\w+)".format(metric_result_pattern)
    line_pattern_2 = " +-(.)- +-(.)-".format(metric_result_pattern)
    line_pattern_3 = "(\d+) +([NP]\d+) +(\d+) +\|{0} +\|{0} +\|{0} +\|{0} +\|-(.)- +\|(\w+) +-(.)-".format(
        metric_result_pattern)
    header_separator_size = 23
    record_format = "{{:<7}}{{:<{0}}}{{:<14}}|{{:<{0}}}" \
                    "|{{:<{0}}}|{{:<{0}}}|{{:<{0}}}|{{:<12}}|{{:<12}}" \
                    "{{:<10}}{{:<7}}|{{:<{0}}}|{{:<{0}}}\n".format(header_separator_size)
    header = record_format.format(
        "COUNT", "CLUSTER-ID", "CLUSTER-SIZE", "MACHINE-EVAL", "MACHINE-MIN-EVAL", "MACHINE-AVG-EVAL",
        "MACHINE-ALL-EVAL", "HUMAN-EVAL", "HAS-CYCLE", "NOT GOOD", "CYCLE", "COMMENT", "RESOURCES")
    file_rewrote = file_2.replace(".txt", "-transferred.txt")
    writer = open(file_rewrote, 'wb')
    writer.write(header)

    def load_dictionary(clusters, cur_file):

        count = 0
        with open(cur_file, "rb") as info:

            start = False
            matrix = []
            cluster_id = ""
            for line in info:

                match2 = re.findall(line_pattern_3, line)
                match = re.findall(line_pattern, line) if len(match2) == 0 else match2

                if len(match) > 0:
                    # print match, len(match)

                    if len(matrix) > 0 and start is True:
                        count += 1
                        # Ut.print_list(matrix)
                        clusters[cluster_id]['matrix'] = matrix

                    start = True
                    matrix = [line[183:].rstrip()]
                    cluster_id = match[0][1]
                    clusters[match[0][1]] = {
                        'CLUSTER-SIZE': match[0][2],
                        'MACHINE-EVAL': match[0][3],
                        'MACHINE-MIN-EVAL': match[0][4],
                        'MACHINE-AVG-EVAL': match[0][5],
                        'MACHINE-ALL-EVAL': match[0][6],
                        'HUMAN-EVAL': match[0][7],
                        'HAS-CYCLE': match[0][8]
                    }

                    if len(match[0]) == 10:
                        clusters[match[0][1]]['NOT GOOD'] = match[0][9]

                else:
                    input = line[183:].rstrip()
                    match = re.findall(line_pattern_2, line)
                    # if len(match) > 0:
                    #     evaluation['NOT GOOD'] = match[0][0]
                    #     evaluation['CYCLE'] = match[0][1]

                    if len(input) > 0 and len(match) > 0:
                        # print "INPUT:", input, len(input)
                        matrix += [(match[0][0], match[0][1], input)]

                    elif len(input) > 0 and len(match) == 0 and start is True:
                        print "PROBLEM:", line
                        exit(0)

            # if count == 20:
            #     break


        # LOAD THE LEFT OVERS
        if len(matrix) > 0 and start is True:
            count += 1
            # Ut.print_list(matrix)
            clusters[cluster_id]['matrix'] = matrix
            # evaluation = {"min": clusters[cluster_id]['MACHINE-MIN-EVAL'],
            #               "avg": clusters[cluster_id]['MACHINE-AVG-EVAL'],
            #               "bcd": clusters[cluster_id]['MACHINE-ALL-EVAL'],
            #               "human": clusters[cluster_id]['HUMAN-EVAL'],
            #               "original": clusters[cluster_id]['MACHINE-EVAL']}
            # if 'NOT GOOD' in clusters[cluster_id]:
            #     # print match[0], len(match[0])
            #     evaluation['NOT GOOD'] = clusters[cluster_id]['NOT GOOD']
            # rewrite_record(count_record=count, size=clusters[cluster_id]['CLUSTER-SIZE'],
            #                record_format=record_format, matrix=matrix, writer=writer, cluster_id=cluster_id,
            #                separator_size=40, evaluation=evaluation, has_cycle='no', node_in_cycle=None)
            # writer.write("\n")



    load_dictionary(clusters_1, file_1)
    load_dictionary(clusters_2, file_2)

    new_clusters = 0
    for cluster in clusters_2:
        if cluster not in clusters_1:
            new_clusters += 1

    print "STATISTICS\n\t{:39}: {}".format("VALIDATED CLUSTER", len(clusters_1))
    print "\t{:39}: {}".format("NOT VALIDATED VALIDATED CLUSTER", len(clusters_2))
    print "\t{:39}: {}".format("TOTAL OF NEW CLUSTERS", new_clusters)

    with open(file_2, 'rb') as data:
        for line in data:
            match = re.findall('(\d+) +([NP]\d+)', line)

            if len(match) > 0:
                id = match[0][1]
                count = match[0][0]
                if id in clusters_2:


                    if id in clusters_1:
                        evaluation = {"min": clusters_1[id]['MACHINE-MIN-EVAL'],
                                      "avg": clusters_1[id]['MACHINE-AVG-EVAL'],
                                      "bcd": clusters_1[id]['MACHINE-ALL-EVAL'],
                                      "human": clusters_1[id]['HUMAN-EVAL'],
                                      "original": clusters_1[id]['MACHINE-EVAL']}

                        if 'NOT GOOD' in clusters_1[id]:
                            evaluation['NOT GOOD'] = clusters_1[id]['NOT GOOD']
                        rewrite_record(count_record=count, size=clusters_1[id]['CLUSTER-SIZE'],
                                       record_format=record_format, matrix=clusters_1[id]['matrix'], writer=writer,
                                       cluster_id=id, separator_size=40, evaluation=evaluation,
                                       has_cycle=clusters_1[id]['HAS-CYCLE'],
                                       node_in_cycle=None)
                        writer.write("\n")
                    else:
                        # print match
                        evaluation = {"min": clusters_2[id]['MACHINE-MIN-EVAL'],
                                      "avg": clusters_2[id]['MACHINE-AVG-EVAL'],
                                      "bcd": clusters_2[id]['MACHINE-ALL-EVAL'],
                                      "human": clusters_2[id]['HUMAN-EVAL'],
                                      "original": clusters_2[id]['MACHINE-EVAL']}

                        if 'NOT GOOD' in clusters_2[id]:
                            evaluation['NOT GOOD'] = clusters_2[id]['NOT GOOD']
                        rewrite_record(count_record=count, size=clusters_2[id]['CLUSTER-SIZE'],
                                       record_format=record_format, matrix=clusters_2[id]['matrix'], writer=writer,
                                       cluster_id=id, separator_size=40, evaluation=evaluation,
                                       has_cycle=clusters_2[id]['HAS-CYCLE'],
                                       node_in_cycle=None)
                        writer.write("\n")


directoty = "C:\Users\Al\Dropbox\@VU\Ve\Golden Agents\Transfering"
file_1 = join(directoty, "EvalSheet_P2400376587025266230_20181026-112130_cycle.txt")
file_2 = join(directoty, "EvalSheet_P2400376587025266230_20181102-163153_cycle_new.txt")
# transfer(file_1, file_2, directoty)

# sequence = ['<http://risis.eu/MatchingExample/resource/1_6>', '<http://risis.eu/MatchingExample/resource/1_1>',
#             '<http://risis.eu/MatchingExample/resource/1_4>', '<http://risis.eu/MatchingExample/resource/1_7>']

sequence = [(1,2), (3,1), (1,4), (2,3), (2,4), (3,4),
            (2,1), (1,3), (4,1), (3,2), (4,2), (4,3)]

# graph = nx.Graph()
# nodes = set([n1 for n1, n2 in sequence] + [n2 for n1, n2  in sequence])
# for node in nodes:
#     graph.add_node(node)

search = (2,3)
# print Ut.ordered_combinations(sequence)

# for data in sequence:
#     if data != search and (search[0] in data) or (search[1] in data):
#         print data

G = nx.DiGraph(sequence)
# G = nx.DiGraph([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)])
# print list(nx.simple_cycles(G))

# G=nx.path_graph(80)
# print list(G)
# paths = list(nx.all_simple_paths(G, 2, 3))
#
# print filter(lambda x: len(x) == 3, paths)
#
# import matplotlib.pyplot as plt
# nx.draw(G)
# plt.show()