def get_permute(W_r, H_r, W, H, coeff):
    T_0 = W_r.shape[1]
    T = W.shape[1]
    comp = zeros((T_0, T))
    for t in xrange(T):
        p = sqrt(W_r) - sqrt(tile(W[:, t], (T_0, 1))).T
        comp[:, t] = sum(p ** 2, 0)
    if T < T_0:
        t = array(linear_assignment(comp.T))[:, [1, 0]]
        # http://stackoverflow.com/questions/2828059/sorting-arrays-in-numpy-by-column
        return t[t[:, 0].argsort()]
    else:
        return array(linear_assignment(comp))

    def track(self, original_img, filtered_img, prev_data):
        n_objects = self.nObjectsSpinBox.value()
        distance_threshold = self.distanceThresholdSpinBox.value()

        if self.k_means is None:
            self.k_means = cluster.KMeans(n_clusters=n_objects)

        non_zero_pos = np.transpose(np.nonzero(filtered_img.T))
        try:
            center_pos = self.k_means.fit(non_zero_pos).cluster_centers_
        except:
            if self.ret_pos_old is None:
                return {'position': np.full((n_objects, 2), np.nan)}
            else:
                return {'position': self.ret_pos_old}

        if self.ret_pos_old is None:
            self.ret_pos_old = center_pos.copy()
            self.ret_pos = center_pos
        else:
            ret_pos_old_repeated = np.repeat(self.ret_pos_old, n_objects, axis=0)
            center_pos_tiled = np.tile(center_pos, (n_objects, 1))
            cost_mtx = np.linalg.norm(ret_pos_old_repeated - center_pos_tiled, axis=1)
            cost_mtx = cost_mtx.reshape((n_objects, n_objects))

            idx = linear_assignment(cost_mtx)
            idx = idx[cost_mtx[idx[:,0], idx[:,1]]<=distance_threshold]

            self.ret_pos[:] = self.ret_pos_old[:]
            self.ret_pos[idx[:, 0], :] = center_pos[idx[:, 1], :]

            self.ret_pos_old[:] = self.ret_pos[:].copy()

        return {'position': self.ret_pos}

def get_indexList(coord, coord_prev, indexListPrev, totWorms, max_allow_dist = 10.0):
    #get the indexes of the next worms from their nearest neightbors using the hungarian algorithm
    
    if coord_prev.size!=0:
        costMatrix = cdist(coord_prev, coord);
        assigment = linear_assignment(costMatrix)
        
        indexList = np.zeros(coord.shape[0]);
        speed = np.zeros(coord.shape[0])

        for row, column in assigment: #ll = 1:numel(indexList)
            if costMatrix[row,column] < max_allow_dist:
                indexList[column] = indexListPrev[row];
                speed[column] = costMatrix[row][column];
            elif column < coord.shape[0]:
                totWorms = totWorms +1;
                indexList[column] = totWorms;
        
        for rep_ind in list_duplicates(indexList):
            totWorms = totWorms +1; #assign new worm_index to joined trajectories
            indexList[rep_ind] = totWorms;
        
    else:
        indexList = totWorms + np.arange(1,coord.shape[0]+1);
        totWorms = indexList[-1]
        speed = totWorms*[None]
        #print costMatrix[-1,-1]
    return (totWorms, indexList, speed)

def best_map(l1, l2):
    """
    Permute labels of l2 to match l1 as much as possible
    """
    if len(l1) != len(l2):
        print "L1.shape must == L2.shape"
        exit(0)

    label1 = np.unique(l1)
    n_class1 = len(label1)

    label2 = np.unique(l2)
    n_class2 = len(label2)

    n_class = max(n_class1, n_class2)
    G = np.zeros((n_class, n_class))

    for i in range(0, n_class1):
        for j in range(0, n_class2):
            ss = l1 == label1[i]
            tt = l2 == label2[j]
            G[i, j] = np.count_nonzero(ss & tt)

    A = la.linear_assignment(-G)

    new_l2 = np.zeros(l2.shape)
    for i in range(0, n_class2):
        new_l2[l2 == label2[A[i][1]]] = label1[A[i][0]]
    return new_l2.astype(int)

def assignment(costMatrix, costOfNonAssignment=140):
    Assignment = namedtuple('Assignment', 'trackIndex detectionIndex')
    assignments = []
    unmatchedTracks = []
    unmatchedDetections = []

    # print(costMatrix)

    # If matrix is rectangular, then pad
    rows, cols = costMatrix.shape
    diff = rows - cols
    if diff != 0:
        padValue = costOfNonAssignment + 1
        if diff < 0:
            pad_width = [(0, np.abs(diff)), (0, 0)]
        if diff > 0:
            pad_width = [(0, 0), (0, diff)]
        costMatrix = np.pad(costMatrix, pad_width, mode='constant',
            constant_values=(padValue, padValue))
    # Compute the optimal assignment
    assign = linear_assignment(costMatrix)

    # Throw out any assignments that cost more than the costOfNonAssingment
    for row in assign:
        trackIndex = row[0]
        detectionIndex =  row[1]
        if costMatrix[trackIndex, detectionIndex] > costOfNonAssignment:
            if trackIndex < rows:
                unmatchedTracks.append(trackIndex)
            if detectionIndex < cols:
                unmatchedDetections.append(detectionIndex)
        else:
            assignments.append(Assignment(trackIndex, detectionIndex))

    return assignments, unmatchedTracks, unmatchedDetections

 def syntax_similarity_conversation(self, documents1, average=False): #syntax similarity of each document with its before and after document
     global numnodes
     documents1parsed = []
     for d1 in range(len(documents1)):
         sys.stderr.write(str(d1)+"\n")
         # print documents1[d1]
         tempsents = (self.sent_detector.tokenize(documents1[d1].strip()))
         for s in tempsents:
             if len(s.split())>100:
                 documents1parsed.append("NA")
                 break
         else:
             temp = list(self.parser.raw_parse_sents((tempsents)))
             for i in range(len(temp)):
                 temp[i] = list(temp[i])[0]
                 temp[i] = ParentedTree.convert(temp[i])
             documents1parsed.append(list(temp))
     results = OrderedDict()
     for d1 in range(len(documents1parsed)):
         d2 = d1+1
         if d2 == len(documents1parsed):
             break
         if documents1parsed[d1] == "NA" or documents1parsed[d2]=="NA":
             continue
         costMatrix = []
         for i in range(len(documents1parsed[d1])):
             numnodes = 0
             tempnode = Node(documents1parsed[d1][i].root().label())
             new_sentencedoc1 = self.convert_mytree(documents1parsed[d1][i],tempnode)
             temp_costMatrix = []
             sen1nodes = numnodes
             for j in range(len(documents1parsed[d2])):
                 numnodes=0.0
                 tempnode = Node(documents1parsed[d2][j].root().label())
                 new_sentencedoc2 = self.convert_mytree(documents1parsed[d2][j],tempnode)
                 ED = simple_distance(new_sentencedoc1, new_sentencedoc2)
                 ED = ED / (numnodes + sen1nodes)
                 temp_costMatrix.append(ED)
             costMatrix.append(temp_costMatrix)
         costMatrix = np.array(costMatrix)
         if average==True:
             return 1-np.mean(costMatrix)
         else:
             indexes = su.linear_assignment(costMatrix)
             total = 0
             rowMarked = [0] * len(documents1parsed[d1])
             colMarked = [0] * len(documents1parsed[d2])
             for row, column in indexes:
                 total += costMatrix[row][column]
                 rowMarked[row] = 1
                 colMarked [column] = 1
             for k in range(len(rowMarked)):
                 if rowMarked[k]==0:
                     total+= np.min(costMatrix[k])
             for c in range(len(colMarked)):
                 if colMarked[c]==0:
                     total+= np.min(costMatrix[:,c])
             maxlengraph = max(len(documents1parsed[d1]),len(documents1parsed[d2]))
             results[(d1,d2)] = 1-total/maxlengraph#, minWeight/minlengraph, randtotal/lengraph
     return results

 def syntax_similarity_two_documents(self, doc1, doc2, average=False): #syntax similarity of two single documents
     global numnodes
     doc1sents = self.sent_detector.tokenize(doc1.strip())
     doc2sents = self.sent_detector.tokenize(doc2.strip())
     for s in doc1sents: # to handle unusual long sentences.
         if len(s.split())>100:
             return "NA"
     for s in doc2sents:
         if len(s.split())>100:
             return "NA"
     try: #to handle parse errors. Parser errors might happen in cases where there is an unsuall long word in the sentence.
         doc1parsed = self.parser.raw_parse_sents((doc1sents))
         doc2parsed = self.parser.raw_parse_sents((doc2sents))
     except Exception as e:
         sys.stderr.write(str(e))
         return "NA"
     costMatrix = []
     doc1parsed = list(doc1parsed)
     for i in range(len(doc1parsed)):
         doc1parsed[i] = list(doc1parsed[i])[0]
     doc2parsed = list(doc2parsed)
     for i in range(len(doc2parsed)):
         doc2parsed[i] = list(doc2parsed[i])[0]
     for i in range(len(doc1parsed)):
         numnodes = 0
         sentencedoc1 = ParentedTree.convert(doc1parsed[i])
         tempnode = Node(sentencedoc1.root().label())
         new_sentencedoc1 = self.convert_mytree(sentencedoc1,tempnode)
         temp_costMatrix = []
         sen1nodes = numnodes
         for j in range(len(doc2parsed)):
             numnodes=0.0
             sentencedoc2 = ParentedTree.convert(doc2parsed[j])
             tempnode = Node(sentencedoc2.root().label())
             new_sentencedoc2 = self.convert_mytree(sentencedoc2,tempnode)
             ED = simple_distance(new_sentencedoc1, new_sentencedoc2)
             ED = ED / (numnodes + sen1nodes)
             temp_costMatrix.append(ED)
         costMatrix.append(temp_costMatrix)
     costMatrix = np.array(costMatrix)
     if average==True:
         return 1-np.mean(costMatrix)
     else:
         indexes = su.linear_assignment(costMatrix)
         total = 0
         rowMarked = [0] * len(doc1parsed)
         colMarked = [0] * len(doc2parsed)
         for row, column in indexes:
             total += costMatrix[row][column]
             rowMarked[row] = 1
             colMarked [column] = 1
         for k in range(len(rowMarked)):
             if rowMarked[k]==0:
                 total+= np.min(costMatrix[k])
         for c in range(len(colMarked)):
             if colMarked[c]==0:
                 total+= np.min(costMatrix[:,c])
         maxlengraph = max(len(doc1parsed),len(doc2parsed))
         return 1-(total/maxlengraph)

def accuracy(l,lg):
    profitMatrix = confusion_matrix(lg, l)
    costMatrix = lg.shape[0] - profitMatrix
    ind = linear_assignment(costMatrix)
    total = 0.0
    for i in ind:
        total += profitMatrix[i[0],i[1]]
    return total / lg.shape[0]

 def get_deci_map(self, state_map, w, dnum, tnum):
     score_mat = state_map.dot(w)
     match_idxs = linear_assignment(-score_mat)
     deci_map = np.zeros_like(score_mat)
     for m in match_idxs:
         if m[0]<dnum or m[1]<tnum:
             deci_map[m[0],m[1]] = 1
     return match_idxs, deci_map

def accuracy(l,lg):
    profitMatrix = confusion_matrix(lg,l)
    costMatrix = np.iinfo(np.int64).max - profitMatrix
    ind = linear_assignment(costMatrix)
    total = 0.0
    for i in ind:
        total += profitMatrix[tuple(i)]
    return total / lg.shape[0]

    def calcAssignMtx(self):
        idx = linear_assignment(self.costMtx)

        if self.assignMtx is None:
            self.assignMtx = np.zeros((self.N, self.M))
        else:
            self.assignMtx[:] = 0
        self.assignMtx[idx[:, 0], idx[:,1]] = 1

def ceafe(clusters, gold_clusters):
    clusters = [c for c in clusters if len(c) != 1]
    scores = np.zeros((len(gold_clusters), len(clusters)))
    for i in range(len(gold_clusters)):
        for j in range(len(clusters)):
            scores[i, j] = phi4(gold_clusters[i], clusters[j])
    matching = linear_assignment(-scores)
    similarity = sum(scores[matching[:, 0], matching[:, 1]])
    return similarity, len(clusters), similarity, len(gold_clusters)

def cluster_acc(Y_pred, Y):
  from sklearn.utils.linear_assignment_ import linear_assignment
  assert Y_pred.size == Y.size
  D = max(Y_pred.max(), Y.max())+1
  w = np.zeros((D,D), dtype=np.int64)
  for i in range(Y_pred.size):
    w[Y_pred[i], Y[i]] += 1
  ind = linear_assignment(w.max() - w)
  return sum([w[i,j] for i,j in ind])*1.0/Y_pred.size, w

 def match_detections(self, old_dets, new_dets, iou_threshold):
     if len(old_dets) == 0 or len(new_dets) == 0:
         return []
     iou_cost = np.array(
         [[iou(old, new) for new in new_dets] for old in old_dets],
         'float32'
     )
     match_pairs = linear_assignment(-iou_cost)
     return match_pairs

def linear_assignment(df):
    """Wrapper of sklearn linear assignment algorithm for DataFrame cost matrix. Returns
    DataFrame with columns for matched labels. Minimizes cost.
    """
    from sklearn.utils.linear_assignment_ import linear_assignment

    x = linear_assignment(df.as_matrix())
    y = zip(df.index[x[:, 0]], df.columns[x[:, 1]])
    df_out = pd.DataFrame(y, columns=[df.index.name, df.columns.name])
    return df_out

def solve_matching(num_cluster, old_cluster, new_cluster):
  """Solves the hungarian matching based on the non-overlapping words."""
  cost_matrix = np.array([[.0]*num_cluster]*num_cluster)
  # cost_matrix = cost_matrix.astype(np.float32)
  for i in old_cluster:
    for j in new_cluster:
      cost_matrix[i][j] = count_non_overlapping(old_cluster[i], new_cluster[j])
  # import ipdb; ipdb.set_trace()
  assignments = hungarian.linear_assignment(cost_matrix)
  mapping = {}
  for i in xrange(assignments.shape[0]):
    # mapping[i] = assignments[i, 1]
    mapping[assignments[i, 1]] = i
  return mapping

def associate_detections_to_trackers(detections, trackers, iou_threshold=0.3):
    """
    Assigns detections to tracked object (both represented as bounding boxes)
    Returns 3 lists of matches, unmatched_detections and unmatched_trackers
    """
    if (len(trackers) == 0):
        return np.empty((0, 2), dtype=int), np.arange(len(detections)), \
               np.empty((0, 5), dtype=int)
    iou_matrix = np.zeros((len(detections), len(trackers)), dtype=np.float32)

    for d, det in enumerate(detections):
        for t, trk in enumerate(trackers):
            iou_matrix[d, t] = iou(det, trk)
    matched_indices = linear_assignment(-iou_matrix)

    unmatched_detections = []
    for d, det in enumerate(detections):
        if (d not in matched_indices[:, 0]):
            unmatched_detections.append(d)
    unmatched_trackers = []
    for t, trk in enumerate(trackers):
        if (t not in matched_indices[:, 1]):
            unmatched_trackers.append(t)

    # filter out matched with low IOU
    matches = []
    for m in matched_indices:
        is_matched = (iou_matrix[m[0], m[1]] < iou_threshold)

        # @mhsung
        if (detections.shape[1] >= 6 and trackers.shape[1] >= 6):
            # det: [x0, y0, x1, y2, score, class_index, ...]
            # If class indices are given, bboxes with the same class index are
            # only matched.
            det_cls = detections[m[0], 5]
            trk_cls = trackers[m[0], 5]
            is_matched = is_matched and (det_cls == trk_cls)

        if is_matched:
            unmatched_detections.append(m[0])
            unmatched_trackers.append(m[1])
        else:
            matches.append(m.reshape(1, 2))
    if (len(matches) == 0):
        matches = np.empty((0, 2), dtype=int)
    else:
        matches = np.concatenate(matches, axis=0)

    return matches, np.array(unmatched_detections), np.array(unmatched_trackers)

def associate_detections_to_trackers(
        detections, trackers, distance_threshold=0.3):
    """
    Assigns detections to tracked object (both represented as bounding boxes)

    Returns 3 lists of matches, unmatched_detections and unmatched_trackers
    """
    if(len(trackers) == 0):
        return np.empty((0, 2), dtype=int), np.arange(
            len(detections)), np.empty((0, 6), dtype=int)
    distance_matrix = np.zeros(
        (len(detections), len(trackers)), dtype=np.float32)

    for d, det in enumerate(detections):
        for t, trk in enumerate(trackers):
            distance_matrix[d, t] = distance(det, trk)
            print('distance of new det:{} to tracker {} = {}'.format(
                d, t, distance_matrix[d, t]))

    # warnings.warn(str(distance_matrix))
    # warnings.warn('tracking')

    matched_indices = linear_assignment(-distance_matrix)

    unmatched_detections = []
    for d, det in enumerate(detections):
        if(d not in matched_indices[:, 0]):
            unmatched_detections.append(d)
    unmatched_trackers = []
    for t, trk in enumerate(trackers):
        if(t not in matched_indices[:, 1]):
            unmatched_trackers.append(t)

    # filter out matched with low distance
    matches = []
    for m in matched_indices:
        if(distance_matrix[m[0], m[1]] < distance_threshold):
            unmatched_detections.append(m[0])
            unmatched_trackers.append(m[1])
        else:
            matches.append(m.reshape(1, 2))
    if(len(matches) == 0):
        matches = np.empty((0, 2), dtype=int)
    else:
        matches = np.concatenate(matches, axis=0)

    return matches, np.array(
        unmatched_detections), np.array(unmatched_trackers)

    def ceafe(clusters, gold_clusters):
        """
        Computes the  Constrained EntityAlignment F-Measure (CEAF) for evaluating coreference.
        Gold and predicted mentions are aligned into clusterings which maximise a metric - in
        this case, the F measure between gold and predicted clusters.

        <https://www.semanticscholar.org/paper/On-Coreference-Resolution-Performance-Metrics-Luo/de133c1f22d0dfe12539e25dda70f28672459b99>
        """
        clusters = [cluster for cluster in clusters if len(cluster) != 1]
        scores = np.zeros((len(gold_clusters), len(clusters)))
        for i, gold_cluster in enumerate(gold_clusters):
            for j, cluster in enumerate(clusters):
                scores[i, j] = Scorer.phi4(gold_cluster, cluster)
        matching = linear_assignment(-scores)
        similarity = sum(scores[matching[:, 0], matching[:, 1]])
        return similarity, len(clusters), similarity, len(gold_clusters)

    def __init__(self, boxes1, boxes2, labels1=None, labels2=None):
        self._boxes1 = boxes1
        self._boxes2 = boxes2

        if len(boxes1) == 0 or len(boxes2) == 0:
            pass
        else:
            
            if labels1 is None or labels2 is None:
                self._iou_matrix = self._calc(boxes1,
                                              boxes2,
                                              np.ones((len(boxes1),)),
                                              np.ones((len(boxes2),)))
            else:
                self._iou_matrix = self._calc(boxes1, boxes2, labels1, labels2)
            self._match_pairs = linear_assignment(-1*self._iou_matrix)