def test_error_different_signature_lengths(self):
     first_signature = np.array([6.0, 1.0, 9.0])
     second_signature = np.array([1.0, 7.0])
     distance_matrix = np.array([[0.0, 1.0],
                                 [1.0, 0.0]])
     with self.assertRaises(ValueError):
         emd(first_signature, second_signature, distance_matrix)

def test_emd_validate_larger_signatures_1():
    first_signature = np.array([0.0, 1.0, 2.0])
    second_signature = np.array([5.0, 3.0, 3.0])
    distance_matrix = np.array([[0.0, 0.5],
                                [0.5, 0.0]])
    with pytest.raises(ValueError):
        emd(first_signature, second_signature, distance_matrix)

 def test_error_wrong_distance_matrix_ndim(self):
     first_signature = np.array([6.0, 1.0])
     second_signature = np.array([1.0, 7.0])
     distance_matrix = np.array([[[0.0, 1.0],
                                 [1.0, 0.0]]])
     with self.assertRaises(ValueError):
         emd(first_signature, second_signature, distance_matrix)

def test_symmetric_distance_matrix():
    first_signature = np.array([0.0, 1.0])
    second_signature = np.array([5.0, 3.0])
    distance_matrix = np.array([[0.0, 0.5, 3.0],
                                [0.5, 0.0]])
    with pytest.raises(ValueError):
        emd(first_signature, second_signature, distance_matrix)

def test_emd_validate_different_signature_dims():
    first_signature = np.array([0.0, 1.0])
    second_signature = np.array([5.0, 3.0, 3.0])
    distance_matrix = np.array([[0.0, 0.5, 0.0],
                                [0.5, 0.0, 0.0],
                                [0.5, 0.0, 0.0]])
    with pytest.raises(ValueError):
        emd(first_signature, second_signature, distance_matrix)

def wordMoverDistance(d1, d2):
    ###d1 list
    ###d2 list
    # Rule out words that not in vocabulary
    d1 = " ".join([w for w in d1 if w in vocab_dict])
    d2 = " ".join([w for w in d2 if w in vocab_dict])
    #print d1
    #print d2
    vect = CountVectorizer().fit([d1,d2])
    feature_names = vect.get_feature_names()
    W_ = W[[vocab_dict[w] for w in vect.get_feature_names()]] #Word Matrix
    D_ = euclidean_distances(W_) # Distance Matrix
    D_ = D_.astype(np.double)
    #D_ /= D_.max()  # Normalize for comparison
    v_1, v_2 = vect.transform([d1, d2])
    v_1 = v_1.toarray().ravel()
    v_2 = v_2.toarray().ravel()
    ### EMD
    v_1 = v_1.astype(np.double)
    v_2 = v_2.astype(np.double)
    v_1 /= v_1.sum()
    v_2 /= v_2.sum()
    #print("d(doc_1, doc_2) = {:.2f}".format(emd(v_1, v_2, D_)))
    emd_d = emd(v_1, v_2, D_) ## WMD
    #print emd_d
    return emd_d

def score_word2vec_wmd(src, dst, wv):
	b1 = []
	b2 = []
	lines = 0
	with open(src) as p:
		for i, line in enumerate(p):
			s = line.split('\t')
			b1.append(s[0])
			b2.append(s[1][:-1]) #remove \n
			lines = i + 1

	vectorizer = CountVectorizer()
	vectors=vectorizer.fit_transform(b1 + b2)
	common = [word for word in vectorizer.get_feature_names() if word in wv]
	W_common = [wv[w] for w in common]
	vectorizer = CountVectorizer(vocabulary=common, dtype=np.double)
	b1_v = vectorizer.transform(b1)
	b2_v = vectorizer.transform(b2)

	D_ = sklearn.metrics.euclidean_distances(W_common)
	D_ = D_.astype(np.double)
	D_ /= D_.max()

	b1_vecs = b1_v.toarray()
	b2_vecs = b1_v.toarray()
	b1_vecs /= b1_v.sum()
	b2_vecs /= b2_v.sum()
	b1_vecs = b1_vecs.astype(np.double)
	b2_vecs = b2_vecs.astype(np.double)

	res = [round(emd(b1_vecs[i], b2_vecs[i], D_),2) for i in range(lines)]
	
	with open(dst, 'w') as thefile:
		thefile.write("\n".join(str(i) for i in res))
	print src + ' finished!'

def calc_wmd(d1, d2, dm, vob_index_dict):

    u1 = set(d1)
    u2 = set(d2)
    du = u1.union(u2)

    f1 = np.array(nBOW(d1, du))
    f2 = np.array(nBOW(d2, du))


    dul = len(du)
    dum = np.zeros((dul, dul), dtype=np.float)
    du_list = list(du)
    processed_list = []
    for i, t1 in enumerate(du_list):
        processed_list.append(i)

        for j, t2 in enumerate(du_list):
            if j in processed_list:
                continue

            dist_matrix_x = vob_index_dict[t1]
            dist_matrix_y = vob_index_dict[t2]
            dist = dm[dist_matrix_x, dist_matrix_y]

            dum[i][j] = dist
            dum[j][i] = dist

    return emd(f1, f2, dum)

def test_emd_1():
    first_signature = np.array([0.0, 1.0])
    second_signature = np.array([5.0, 3.0])
    distance_matrix = np.array([[0.0, 0.5],
                                [0.5, 0.0]])
    emd_assert(
        emd(first_signature, second_signature, distance_matrix),
        3.5
    )

def test_emd_3():
    first_signature = np.array([6.0, 1.0])
    second_signature = np.array([1.0, 7.0])
    distance_matrix = np.array([[0.0, 0.0],
                                [0.0, 0.0]])
    emd_assert(
        emd(first_signature, second_signature, distance_matrix),
        0.0
    )

    def _wh_ne_distance(self, other, w):
        c1 = getattr(self, w)
        c2 = getattr(other, w)
        
        if not len(c1) or not len(c2):
            # one of them has nothing to compare; distance is np.nan
            return np.nan

        s1 = sorted(c1.keys(), key=lambda k: c1[k], reverse=True)
        s2 = sorted(c2.keys(), key=lambda k: c2[k], reverse=True)

        if self.max_nes > 0:
            penalty = max(
                sum(
                    c1[w] 
                    for w in s1[self.max_nes:]
                ), sum(
                    c2[w]
                    for w in s2[self.max_nes:]
                )
            )

            s1 = s1[:self.max_nes]
            s2 = s2[:self.max_nes]
        else:
            penalty = 0

        # penalty will make up for those documents that have low-scoring
        # NEs, meaning they should not be compared with other news items
        # since this method would not have meaning with them

        matrix, nes = NE.matrix(set(s1).union(set(s2)))
        
        if not nes:
            # Not a single NE to compare; distance is np.nan
            return np.nan
        
        nes = [ne.lower() for ne in nes] # NE.matrix returns Titles
        v1 = np.array([ c1[ne] for ne in nes ])
        v2 = np.array([ c2[ne] for ne in nes ])

        # Make it sum 1
        s = v1.sum()
        if s > 0:
            v1 /= s

        s = v2.sum()
        if s > 0:
            v2 /= s

        # Now compute emd of the two vectors.
        # That distance is in [0, 1]
        # By multiplying per (1 - penalty) and adding penalty,
        # you ensure distance is in [penalty, 1],
        # penalty being the maximum uncertainty there is in each of the vectors.
        return (1 - penalty) * emd(v1, v2, matrix) + penalty

def dist_hist(X,Y,distance_matrices) :
    start=0
    size=0
    l=[]
    for M in distance_matrices :
        size=M.shape[0]
        l.append(emd(X[start:(start+size)],Y[start:(start+size)],M))

        start+=size
    return np.linalg.norm(l)

def hamming_emd(d1, d2):
    """Return the Earth Mover's Distance between two distributions (indexed
    by state, one dimension per node).

    Singleton dimensions are sqeezed out.
    """
    d1, d2 = d1.squeeze(), d2.squeeze()
    # Compute the EMD with Hamming distance between states as the
    # transportation cost function.
    return emd(d1.ravel(), d2.ravel(), _hamming_matrix(d1.ndim))

def hamming_emd(d1, d2):
    """Return the Earth Mover's Distance between two distributions (indexed
    by state, one dimension per node) using the Hamming distance between states
    as the transportation cost function.

    Singleton dimensions are sqeezed out.
    """
    N = d1.squeeze().ndim
    d1, d2 = flatten(d1), flatten(d2)
    return emd(d1, d2, _hamming_matrix(N))

def dist_hist_withoutnullhist(X,Y,distance_matrices) :
    start=0
    size=0
    l=[]
    for M in distance_matrices :
        size=M.shape[0]
        if sum(X[start:(start+size)]) != 0.0 and sum(Y[start:(start+size)]) != 0.0 :
            l.append(emd(X[start:(start+size)],Y[start:(start+size)],M))
        start+=size
    return np.linalg.norm(l)

 def _wmd(self, i, row, X_train):
     """Compute the WMD between training sample i and given test row.
     
     Assumes that `row` and train samples are sparse BOW vectors summing to 1.
     """
     union_idx = np.union1d(X_train[i].indices, row.indices) - 1
     W_minimal = self.W_embed[union_idx]
     W_dist = euclidean_distances(W_minimal)
     bow_i = X_train[i, union_idx].A.ravel()
     bow_j = row[:, union_idx].A.ravel()
     return emd(bow_i, bow_j, W_dist)

def test_emd_extra_mass_penalty():
    first_signature = np.array([0.0, 2.0, 1.0, 2.0])
    second_signature = np.array([2.0, 1.0, 2.0, 1.0])
    distance_matrix = np.array([[0.0, 1.0, 1.0, 2.0],
                                [1.0, 0.0, 2.0, 1.0],
                                [1.0, 2.0, 0.0, 1.0],
                                [2.0, 1.0, 1.0, 0.0]])
    emd_assert(
        emd(first_signature, second_signature, distance_matrix,
            extra_mass_penalty=2.5),
        4.5
    )

def hist_emd(reference_hist_df, compare_hist_df, key, distance_matrix=None):
    #Merge the two columns on the union of delays
    merged_df = pd.merge(reference_hist_df, compare_hist_df, how='outer', left_index=True, right_index=True)
    merged_df.fillna(0., inplace=True) #Treat missing values as zero

    ref_merged_key = key + '_x'
    comp_merged_key = key + '_y'

    if distance_matrix == None:
        #Unspecified, calculate
        distance_matrix = calc_distance_matrix(merged_df.index, merged_df.index)

    return emd(merged_df[ref_merged_key].values, merged_df[comp_merged_key].values, distance_matrix)

 def __sub__(self, other):
     """
     Earth-mover's distance (EMD) between two histograms.
     Calculated for channels separately and summed up.
     """
     result = sum([
         emd(
             pair[0].astype(np.float),
             pair[1].astype(np.float),
             Histogram._L1_DISTANCE_MATRIX
         )
         for pair in zip(self.channels, other.channels)
     ])
     return result

def word_movers(doc1, doc2, metric='cosine'):
    """
    Measure the semantic similarity between two documents using Word Movers
    Distance.

    Args:
        doc1 (``textacy.Doc`` or ``spacy.Doc``)
        doc2 (``textacy.Doc`` or ``spacy.Doc``)
        metric ({'cosine', 'euclidean', 'l1', 'l2', 'manhattan'})

    Returns:
        float: similarity between `doc1` and `doc2` in the interval [0.0, 1.0],
            where larger values correspond to more similar documents

    References:
        Ofir Pele and Michael Werman, "A linear time histogram metric for improved
            SIFT matching," in Computer Vision - ECCV 2008, Marseille, France, 2008.
        Ofir Pele and Michael Werman, "Fast and robust earth mover's distances,"
            in Proc. 2009 IEEE 12th Int. Conf. on Computer Vision, Kyoto, Japan, 2009.
        Kusner, Matt J., et al. "From word embeddings to document distances."
            Proceedings of the 32nd International Conference on Machine Learning
            (ICML 2015). 2015. http://jmlr.org/proceedings/papers/v37/kusnerb15.pdf
    """
    stringstore = StringStore()

    n = 0
    word_vecs = []
    for word in itertoolz.concatv(extract.words(doc1), extract.words(doc2)):
        if word.has_vector:
            if stringstore[word.text] - 1 == n:  # stringstore[0] always empty space
                word_vecs.append(word.vector)
                n += 1
    distance_mat = pairwise_distances(np.array(word_vecs), metric=metric).astype(np.double)
    distance_mat /= distance_mat.max()

    vec1 = collections.Counter(
        stringstore[word.text] - 1
        for word in extract.words(doc1)
        if word.has_vector)
    vec1 = np.array([vec1[word_idx] for word_idx in range(len(stringstore))]).astype(np.double)
    vec1 /= vec1.sum()  # normalize word counts

    vec2 = collections.Counter(
        stringstore[word.text] - 1
        for word in extract.words(doc2)
        if word.has_vector)
    vec2 = np.array([vec2[word_idx] for word_idx in range(len(stringstore))]).astype(np.double)
    vec2 /= vec2.sum()  # normalize word counts

    return 1.0 - emd(vec1, vec2, distance_mat)