import math, decimal, random
import numpy as np
import scipy.spatial.distance as distance
import scipy.stats as stats
import networkx as nx
import collections
import csv

import sklearn.metrics as metrics
##import sklearn.metrics.cluster.supervised as supervised
#import Pycluster as pc


#clustering distance metrics - variation of information and information distance
CLUSTERING_DISTANCE_METRICS = ['ID','NID','AID','ARI']


def convert_clustering_to_dict_format(cluster_data):
    """
    Convert clustering from the list format observation=>cluster_number to the dictionary cluster_number=>observations
    """

    if isinstance(cluster_data, dict):
        return cluster_data

    clustering = dict()

    for i in range(0,len(cluster_data)):
        if clustering.has_key(cluster_data[i]):
            clustering[cluster_data[i]].append(i)
        else:
            clustering[cluster_data[i]]=[i]

    return clustering


def get_number_of_clusters(clustering):
    """
    Get number of clusters in a clustering
    """
    clustering = convert_clustering_to_dict_format(clustering)
    return len(clustering.keys())

def get_largest_cluster(clustering):
    """
    Get the largest clustering in a clustering
    """
    clustering = convert_clustering_to_dict_format(clustering)
    largest_cluster = []
    temp = -1
    for k in clustering.keys():
        if len(clustering[k])>temp:
            temp = len(clustering[k])
            largest_cluster = clustering[k]

    return largest_cluster

def get_smallest_cluster(clustering):
    """
    Get the smallest clustering in a clustering
    """
    n = len(clustering)
    clustering = convert_clustering_to_dict_format(clustering)
    smallest_cluster = []
    temp = n
    for k in clustering.keys():
        if len(clustering[k])<temp:
            temp = len(clustering[k])
            smallest_cluster = clustering[k]

    return smallest_cluster

def get_cluster_sizes(clustering):
    """
    Get list of cluster sizes
    Example: [1,1,1,2,2] => [2,3]
    """
    clustering = convert_clustering_to_dict_format(clustering)
    return sorted([len(clustering[c]) for c in clustering.keys()])


def get_clustering_distance(clustering1,clustering2, metric):
    """
    Calculate distance between two clusterings
    """

    if metric == 'ID':
        return get_id_clustering_distance(clustering1,clustering2, normalized = False)
    if metric == 'NID':
        return get_id_clustering_distance(clustering1,clustering2, normalized = True)
    if metric == 'AID':
        return get_id_clustering_distance(clustering1,clustering2, adjusted_for_chance = True)
    if metric == 'ARI':
        return 1-metrics.adjusted_rand_score(clustering1,clustering2)
    return None

def get_id_clustering_distance(clustering1, clustering2, normalized = True, adjusted_for_chance = False):
    """
    Distance between two clustering based on the information distance (normalized)
    (see http://jmlr.org/papers/volume11/vinh10a/vinh10a.pdf)

    :param clustering1:
    :param clustering2:
    """
    if not adjusted_for_chance:

        h1 = supervised.entropy(clustering1)
        h2 = supervised.entropy(clustering2)
        if normalized:
            return 1 - metrics.mutual_info_score(clustering1,clustering2)/max(h1,h2)
        else:
            return max(h1,h2) - metrics.mutual_info_score(clustering1,clustering2)
    else:
        return 1 - metrics.adjusted_mutual_info_score(clustering1, clustering2)

def get_correlation_between_distance_matrices(distance_matrix1, distance_matrix2):
    """
    Get Pearson correlation between distance matrices
    """

    #convert matrices to vectors
    vector1 = distance.squareform(distance_matrix1)
    vector2 = distance.squareform(distance_matrix2)

    value, p_value = stats.pearsonr(vector1,vector2)

    return value

def generate_random_clustering(n, cluster_count=None, cluster_sizes=None):
    """
    Generate random clustering of n elements
    :param n: Number of elements
    :param cluster_count: Number of clusters
    :param cluster_sizes: Distribution of cluster sizes
    """

    data = []

    if cluster_sizes is None:
        if cluster_count is None:
            cluster_count = random.randint(1,n)
        temp = [0] + sorted(random.sample(range(n),cluster_count-1)) +[n]
        cluster_sizes = []
        for i in range(cluster_count):
            cluster_sizes.append(temp[i+1]-temp[i])

    current_cluster = 1
    for i in cluster_sizes:
        data += [current_cluster] * i
        current_cluster+=1

    random.shuffle(data)
    return data

def get_distances_from_random_clusterings_to_clustering(clustering = None, number_of_experiments = 1000, metric = 'AID',
                                                        cluster_count = None, cluster_sizes = None, object_count = None):
    """
    Get list of distances from randomly generated clusterings to the clustering
    :param clustering: Clustering to compare with, if None - a random clustering is generated for each experiment (that is, the output is the list of distances between two random clusterings)
    :param number_of_experiments:
    :param metric:
    :param cluster_count:
    :param cluster_sizes:
    :param object_count: Number of objects - if clustering is not None, can be obtained from it
    """
    n= len(clustering) if object_count is None else object_count
    compare_two_random_clusterings = clustering is None
    dist_list = []

    for i in range(number_of_experiments):
        random_clustering = generate_random_clustering(n,cluster_count, cluster_sizes)
        if compare_two_random_clusterings:
            clustering = generate_random_clustering(n,cluster_count, cluster_sizes)
        dist_list.append(get_clustering_distance(random_clustering,clustering,metric))

    return dist_list

def get_stat_significant_clustering_threshold(clustering = None, p_value = 0.05, number_of_experiments = 1000,
                                              metric = 'AID',
                                              cluster_count = None, cluster_sizes = None, object_count = None):
    """
    Get statistical significance threshold for a distance metric according to the clustering and p-value.
    That is, for randomly generated clustering there is only 100%*p-value chance to be closer to the clustering than this threshold
    :param object_count: Number of objects - if clustering is not None, can be obtained from it
    :param clustering:
    :param p_value:
    :param number_of_experiments:
    :param metric:
    :param cluster_count: Number of clusters
    :param cluster_sizes: Cluster size distribution
    :return:
    """


    dist_list  = get_distances_from_random_clusterings_to_clustering(clustering = clustering,
                                                                          number_of_experiments=number_of_experiments,
                                                                          metric = metric,
                                                                          cluster_count = cluster_count,
                                                                          cluster_sizes = cluster_sizes,
                                                                          object_count = object_count)
    threshold = stats.scoreatpercentile(dist_list,p_value*100)
    print 'Out of %s randomly generated clusterings, %s%% had %s distance more than %s' % (number_of_experiments,p_value*100,metric,threshold)
    return threshold

def get_clustering_description_string(clustering, item_labels = None):
    """
    Get clustering description string in the form  [[elements of cluster1], [elements of cluster2],...]
    """
    clustering = convert_clustering_to_dict_format(clustering)
    output = '[ '
    for cluster in clustering:
        if item_labels is not None:
           item_descriptions = [item_labels[item] for item in clustering[cluster]]
        else:
            item_descriptions = [str(item) for item in clustering[cluster]]
        output += '[' + ', '.join(item_descriptions) + '] '
    output += ']'
    return output


def get_clustering_similarity_per_cluster(clustering, similarity_matrix, labels = None):
    """
    For each cluster, get avg and std of similarities between its elements
    @param clustering:
    @param similarity_matrix:
    @param labels:
    @return:
    """
    clustering = convert_clustering_to_dict_format(clustering)
    output = ""

    for key in clustering:
        c = clustering[key]

        #only for clusters with more than 3 elements
        if len(c)<3:
            continue

        cluster_similarities = []

        i_range = range(len(c))
        for i in i_range:
            for j in i_range[i+1:]:
                cluster_similarities.append(similarity_matrix[c[i],c[j]])

        avg = np.average(cluster_similarities)
        std = np.std(cluster_similarities)
        min = np.min(cluster_similarities)
        max = np.max(cluster_similarities)

        descr = c if labels == None else [labels[el] for el in c]

        output += "%s - avg: %.2f, std: %.2f, min: %.2f, max: %.2f\n" % (descr,avg,std,min,max)
    return output

def get_clustering_value_per_cluster(clustering, values, labels = None):
    """
    Get avg./std. values per cluster (e.g., Arousal for images)
    @param clustering:
    @param labels: Labels of elements for output (e.g., image descriptions)
    @param cluster:
    @param values: List of values for the elements (e.g., list of arousal values for images)
    @return:
    """
    clustering = convert_clustering_to_dict_format(clustering)
    output = ""

    for key in clustering:
        c = clustering[key]

        #only for clusters with more than 3 elements
        if len(c)<3:
            continue

        cluster_values = [values[el]  for el in c ]
        avg = np.average(cluster_values)
        std = np.std(cluster_values)
        descr = c if labels == None else [labels[el] for el in c]

        output += "%s - avg: %.2f, std: %.2f\n" % (descr,avg,std)
    return output


def get_clustering_overlap_with_ground_truth_per_cluster(clustering,ground_truth_clustering, labels=None):
    """
    For each cluster, count how many of its elements come from different ground truth clusters
    @param clustering:
    @param ground_truth_clustering:
    @param labels:
    @return:
    """
    clustering = convert_clustering_to_dict_format(clustering)
    output = ""

    for key in clustering:
        c = clustering[key]

        #only for clusters with more than 3 elements
        if len(c)<3:
            continue

        descr = c if labels == None else [labels[el] for el in c]
        output += "%s - " % descr

        counts = collections.Counter([ground_truth_clustering[el] for el in c ])
        for gc_cluster in counts:
            output += '%s: %.2f%%, ' % (gc_cluster, 100.0 * counts[gc_cluster] / len(c))

        output += '\n'
    return output

def get_inter_intra_cluster_similarity(clustering, similarity_matrix):
    """
    Get inter- and intra- cluster similarity vectors
    """
    clustering = convert_clustering_to_dict_format(clustering)

    intra_cluster_similarity = []
    inter_cluster_similarity = []

    clustering_keys = clustering.keys()
    c_range = range(len(clustering_keys))

    for c1 in c_range:
        cluster1 = clustering[clustering_keys[c1]]
        #intra cluster similarity
        i_range = range(len(cluster1))
        for i in i_range:
            for j in i_range[i+1:]:
                intra_cluster_similarity.append(similarity_matrix[cluster1[i],cluster1[j]])
        #inter cluster similarity
        for c2 in c_range[c1+1:]:
            cluster2 = clustering[clustering_keys[c2]]
            for i in range(len(cluster1)):
                for j in range(len(cluster2)):
                    inter_cluster_similarity.append(similarity_matrix[cluster1[i],cluster2[j]])

    return np.array(intra_cluster_similarity), np.array(inter_cluster_similarity)

def get_clustering_intra_inter_similarity_description_list(clustering, similarity_matrix):
    """
    Get list of descriptions of clustering inter/intra similarity
    """
    intra_cluster_similarity, inter_cluster_similarity = get_inter_intra_cluster_similarity(clustering,similarity_matrix)

    if len(intra_cluster_similarity)>0:
        avg_intra = np.average(intra_cluster_similarity)
        median_intra = np.median(intra_cluster_similarity)
        std_intra = np.std(intra_cluster_similarity)
    else:
        avg_intra = 0
        median_intra = 0
        std_intra = 0

    if len(inter_cluster_similarity)>0:
        avg_inter = np.average(inter_cluster_similarity)
        median_inter = np.median(inter_cluster_similarity)
        std_inter = np.std(inter_cluster_similarity)
    else:
        avg_inter = 0
        median_inter = 0
        std_inter = 0

    if len(intra_cluster_similarity)>0 and len(inter_cluster_similarity)>0:
        ranksums = stats.ranksums(intra_cluster_similarity, inter_cluster_similarity)
    elif len(intra_cluster_similarity)==0:
        ranksums = (0,0)
    elif len(inter_cluster_similarity)==0:
        ranksums = (0,1)

    return [
                len(intra_cluster_similarity),
                avg_intra,
                median_intra,
                std_intra,
                len(inter_cluster_similarity),
                avg_inter,
                median_inter,
                std_inter,
                ranksums[0],
                ranksums[1],
    ]

def kmedoids(distance_matrix, k, npass=100):
    """
    K-medoids clustering
    :param distance_matrix:
    :param k: Number of clusters
    Returns:
        clustering_list - clustering solution
        error
        nfound - number of times the solution was found
    """
    print 'kmedoids is running'
    clustering_list, error, nfound = pc.kmedoids(distance_matrix, k, npass=npass)
    return clustering_list, error, nfound


def saveToFile(clustering, filename):
    clustering = convert_clustering_to_dict_format(clustering)
    clustering_file = open(filename , 'wb')
    for c_key in clustering:
        c = clustering[c_key]
        clustering_file.write('%s: %s\n' % (c_key, ';'.join(c)))
    clustering_file.close()

def loadFromFile(filename):
    clustering = dict()
    for line in open(filename).readlines():
        values = line.split(': ')
        clustering[values[0]] = values[1].split(';')
    return clustering
