__author__ = 'haowu'
import numpy as np
import random


def chunks(l, k):
    """ Yield successive n-sized chunks from l.
    :param l: list to chunk
    :param n: chunk num
    """
    ret = []
    for i in range(k):
        ret.append([])
    idx = 0
    for x in l:
        ret[idx].append(x)
        idx = (idx + 1) % k
    return ret


class ClusterEmptyError(Exception):
    def __init__(self, value):
        self.value = value

    def __str__(self):
        return repr(self.value)


class Network:
    def __init__(self, matrixs, nodes):
        """
        :param matrixs: numpy matrix objects in array  [self.Wxx,self.Wxy,self.Wyx,self.Wyy]
                        so the whole matrix looks like
                        Wxx Wxy
                        Wyx Wyy
                        that is really the edges of the graph
        :param nodes:   detail information of nodes
                        ie. the text info of nodes
                            the detail info of users
                        Since it is an bi-type network
                        we made it as an array of [X,Y]

        :param k:       the clustering number
        """
        [self.Wxx, self.Wxy, self.Wyx, self.Wyy] = matrixs

        self.m = len(self.Wxx)

        self.n = len(self.Wyy)

        self.weight = np.bmat([[self.Wxx, self.Wxy], [self.Wyx, self.Wyy]])

        # store the following for only printing result
        self.nodes = nodes
        self.nodesA = self.nodes[0]
        self.nodesB = self.nodes[1]

    def getSubGraph(self, t):
        """
        :return: the subgraph giving cluster# t
                in format of [wxx,wxy,wyx,wyy]
                the size won't change,since other wise we will lost idx info.
        """

        subNodes = self.cluster[t]
        subM = len(subNodes)
        m = len(self.Wxx)
        self.m = m
        n = len(self.Wyy)
        self.n = n
        wxx = np.zeros((m, m))
        wxy = np.zeros((m, n))
        wyx = np.zeros((n, m))
        wyy = np.zeros((n, n))

        for idx in subNodes:
            wxx[:, idx] = self.Wxx[:, idx]
            wxy[idx, 0:] = self.Wxy[idx, 0:]
            wyx[:, idx] = self.Wyx[:, idx]

        wyy = self.Wyy

        return [[wxx, wxy, wyx, wyy], subNodes]

    def init_cluster(self, k):
        """
        The first step of RankClus

        init the cluster
        need to make sure no cluster is empty after calling this function
        if k is larger than the size of nodes, raise Error
        """

        print "Step 0 Initiation the cluster"

        self.k = k

        # find out thread (X) count
        m = len(self.Wxx)
        tmp_list = []

        for i in range(0, m):
            tmp_list.append(i)

        # shuffle
        random.shuffle(tmp_list)

        # chunk into clustering
        self.cluster = chunks(tmp_list, k)
        self.printClusterList()
    
    
    def printClusterList(self):
        # for debug use !
        print ""
        print "Cluster initilized in the following way"
        for i in range(len(self.cluster)):
            print "[", i, "-Cluster]:", self.cluster[i]
        print "finish print init Cluster configure"
        print ""

    def rank(self, Ranker):
        """
        The second step of RankClus

        :param Ranker: The Ranking function we want to run on all the cluster,
                        We will pass the subnet with the index list to this function
                        and it will generated Ranking socre of each nodes in the giving list
                        the result will be hold in an array of objects "self.rankingResult"
                        the obj is generated by the ranker

                        See Ranker class to find out how to write an Ranker

        """

        # first we need a quick look at clusters, if there are some cluster empty we need to raise an error
        # so we can catch that and re-init the clusters
        for i in range(self.k):
            nodes = self.cluster[i]
            if len(nodes) == 0:
                raise ClusterEmptyError("Cluster %s is empty, need to re-init the cluster" % i)

        self.rankMatrix = np.zeros((self.k, self.m))
        self.rankingResult = []
        for i in range(self.k):
            #
            # the result is an RankDistribution object

            [subNet, indexs] = self.getSubGraph(i)
            result = Ranker.rank(subNet, indexs)

            # the ranker will only return rx_i and rY
            # so we need to do rX = W_xy * rY
            result.genRX(self.Wxy)
            self.rankingResult.append(result)

            # for debug use, print the ranking distribution at each round
            # print "Ranking on %s-th Clluster :\n" % i
            # print str(result)

    def estimateParameter(self):
        """
        The third step of RankClus
        estimate the big theta
        after this funtion, it will be in self.bigTheta
        which is an m*k matrix
        """
        # construct bigTheta matrix (m by k)
        bigTheta = np.ones((self.m, self.k))
        bigTheta = bigTheta / self.k
        # and init it to 1/k

        # do the same for p(z=k)
        pz = np.ones((1, self.k))
        pz = pz / self.k

        # the base for p(z=k)
        base = self.Wxy.sum()

        # EM-loop:
        it = 0
        while True:
            it += 1

            #go over each entry
            print "EM-ITERATION %s" % it
            for t in range(self.k):
                numerator = 0.0
                dis = self.rankingResult[t]
                for i in range(self.m):
                    rankX = dis.getXscore(i)
                    for j in range(self.n):
                        rankY = dis.getYscore(j)
                        # calcuated equation [7] in 5.1.2

                        # print "!!!",rankX
                        # print "!!!",rankY
                        # print "!!!",pz[0,t]

                        pzk_giving_xyt = rankX * rankY * pz[0, t]
                        product = self.Wxy[i][j] * pzk_giving_xyt

                        #update the numerator in equation [8] for (i,j,t) tuple
                        numerator += product

                #update p(z=t), t \in [1,k]
                pz[:, t] = numerator / base

            # finished equation [7,8], then we go to equation [9]
            # we need to update every pi(i,k)
            newbigTheta = np.ones((self.k, self.m))
            newbigTheta = newbigTheta / self.k

            for t in range(self.k):
                dis = self.rankingResult[t]
                for i in range(self.m):
                    pkx = dis.getXscore(i)
                    pzk = pz[0, t]

                    denominator = 0.0
                    for tmp in range(self.k):
                        tmp_pzk = pz[0, tmp]
                        tmp_pkx = self.rankingResult[tmp].getXscore(i)
                        # print "!!!",tmp_pzk
                        # print "!!!",tmp_pkx
                        denominator += tmp_pzk * tmp_pkx
                    numerator = pkx * pzk
                    # print t,",",i
                    newbigTheta[t, i] = numerator / denominator

            # so when we reach here, we finished one round of EM, if we reach 5 round, we exit
            # but don't forget to update the pointer of bit Theta
            bigTheta = newbigTheta
            if it > 5:
                break
                # put this into network
        # print bigTheta
        self.bigTheta = bigTheta


    def do_cluster(self):
        self.getClusterCenters()


    def getClusterCenters(self):
        """
        Get the center of each cluster
        """
        centers = [0] * self.k
        for t in range(self.k):
            nodes = self.cluster[t]
            length = len(nodes)
            sxk = np.zeros((1, self.k))
            for idx in nodes:
                sxk += self.bigTheta[:, idx]

            sxk /= length
            centers[t] = sxk
        # print centers
        self.centers = centers

    def adjustCluster(self):
        """
        Step 3 of the framework, adjust the cluster based on the new center of this round
        """
        # first empty the cluster
        new_cluster = []
        for t in range(self.k):
            new_cluster.append([])

        for i in range(self.m):
            target_cluster_idx = 0
            min_dis = 0
            flag = True
            for t in range(self.k):

                distance_x_to_k = self.measureDistance(t, i)

                if distance_x_to_k < min_dis or flag:
                    flag = False
                    min_dis = distance_x_to_k
                    target_cluster_idx = t

            # now the target_cluster_idx is the new idx, we need to append it to there
            new_cluster[target_cluster_idx].append(i)

        # then we have the new_cluster and old one,
        # we need to calculated the epsilon
        epsilon = 0.0
        for t in range(self.k):
            newlist = new_cluster[t]
            oldlist = self.cluster[t]
            epsilon += len(list(set(newlist) - set(oldlist)))
            epsilon += len(list(set(oldlist) - set(newlist)))

        epsilon /= float(len(self.Wxx))
        self.cluster = new_cluster
        # print self.cluster
        self.printClusterList()
        print "epsilon %s " % epsilon
        return epsilon

    def measureDistance(self, cluster_idx, x_idx):
        sx = self.bigTheta[:, x_idx]
        center_k = self.centers[cluster_idx]
        numerator = np.vdot(sx, center_k)
        left = np.linalg.norm(np.transpose(sx))
        right = np.linalg.norm(np.transpose(center_k))
        denominator = np.vdot(left, right)
        # print numerator
        # print denominator
        ret = 1.0 - numerator / denominator

        # print "distance from %s to cluster %s is %s" % (x_idx, cluster_idx, ret)
        return ret

    #method for print usage

    def getNodesInfo(self, idx, type):
        """

        :param idx: the idx of node you want
        :param type: type is 0 for type A
                            1 for Type B

        :return: return the ifo of idx-th node
        """
        return str(self.nodes[type][idx])

    def __repr__(self):
        """
        :return: return the deatil info of the network
        """
        return self.__str__()

    def __str__(self):
        """

        :return: The String repr of the network
        """
        basic_info = "Type A: %s Type B: %s \n" % (+self.m, self.n)
        ret = "Matrix:\n" + str(self.weight) + "\n"
        helperText = "in WYY, Wyy[i][j] is how many " \
                     "times user i is quoting user j (i reply to j)"
        return basic_info + ret + helperText

    def getSize(self):
        """
        :return: [#of nodes Type A, # of Type B ]
        """
        return [self.m, self.n]

    def reset(self):
        """
        Reset the network, used if there are exceptions. (ie. empty clustering )
        """
        pass

    def clusterView(self, limit=None):
        """
        print the detail of results
        :param limit: the top-k nodes you want to print out
        """
        print "Cluster :",self.cluster

        for i in range(self.k):
            print "Cluster %s : \n %s \n" % (i,self.cluster[i])


            single_cluster = self.cluster[i]
            ranking = self.rankingResult[i]
            # print ranking
            higest_x = ranking.getHighestX(limit)
            higest_x = higest_x.tolist()[0]
            higest_y = ranking.getHighestY(limit)
            higest_y = higest_y.tolist()[0]
            print "Higest ranking Type A:"
            print "NODE_IDX\tSCORE\tDetail"
            for idx in higest_x:
                if idx in single_cluster:
                    print "%s\t%s\t%s" % (idx,ranking.getXscore(idx),self.getNodesInfo(idx,0))



            print "Higest ranking Type B:"
            print "NODE_IDX\tSCORE\tDetail"

            for idx in higest_y:
                print "%s\t%s\t%s" % (idx,ranking.getYscore(idx),self.getNodesInfo(idx,1))
            # print higest_y