def test_is_valid_linkage_4_and_up(self):
     # Tests is_valid_linkage(Z) on linkage on observation sets between
     # sizes 4 and 15 (step size 3).
     for i in xrange(4, 15, 3):
         y = np.random.rand(i*(i-1)//2)
         Z = linkage(y)
         assert_(is_valid_linkage(Z) == True)

 def check_is_valid_linkage_various_size(self, nrow, ncol, valid):
     # Tests is_valid_linkage(Z) with linkage matrics of various sizes
     Z = np.asarray([[0, 1, 3.0, 2, 5], [3, 2, 4.0, 3, 3]], dtype=np.double)
     Z = Z[:nrow, :ncol]
     assert_(is_valid_linkage(Z) == valid)
     if not valid:
         assert_raises(ValueError, is_valid_linkage, Z, throw=True)

 def test_is_valid_linkage_4_and_up_neg_counts(self):
     # Tests is_valid_linkage(Z) on linkage on observation sets between
     # sizes 4 and 15 (step size 3) with negative counts.
     for i in xrange(4, 15, 3):
         y = np.random.rand(i*(i-1)//2)
         Z = linkage(y)
         Z[i//2,3] = -2
         assert_(is_valid_linkage(Z) == False)
         assert_raises(ValueError, is_valid_linkage, Z, throw=True)

 def test_is_valid_linkage_empty(self):
     # Tests is_valid_linkage(Z) with empty linkage.
     Z = np.zeros((0, 4), dtype=np.double)
     assert_(is_valid_linkage(Z) == False)
     assert_raises(ValueError, is_valid_linkage, Z, throw=True)

 def test_is_valid_linkage_int_type(self):
     # Tests is_valid_linkage(Z) with integer type.
     Z = np.asarray([[0, 1, 3.0, 2],
                     [3, 2, 4.0, 3]], dtype=np.int)
     assert_(is_valid_linkage(Z) == False)
     assert_raises(TypeError, is_valid_linkage, Z, throw=True)

def _to_dtw_tree(linkage, hierarchical_clustering_object, prototypes, prototyping_function='mean'):
    """
    Converts a hierarchical clustering linkage matrix `linkage` to hierarchy of `DTWClusterNode`s.
    This is a modification of `scipy.cluster.hierarchy.to_tree` function and the code is mostly taken from it.

    :param linkage: linkage matrix to convert to the DTW Tree
    :param hierarchical_clustering_object: hierarchical clustering object to work with
    :param prototyping_function: "reduce" function for prototype calculation, or "mean" to simply use data mean
    """

    # Validation
    linkage = np.asarray(linkage, order='c')
    hierarchy.is_valid_linkage(linkage, throw=True, name='Z')

    data = hierarchical_clustering_object.data
    labels = data.items
    values = data.ix

    n = linkage.shape[0] + 1

    # Create a list full of None's to store the node objects
    d = [None] * (n * 2 - 1)

    # Create the nodes corresponding to the n original objects.
    for i in xrange(0, n):
        index = labels[i]
        d[i] = DTWClusterNode(id=index, hierarchical_clustering_object=hierarchical_clustering_object,
                              prototype=values[index])

    nd = None

    for i in xrange(0, n - 1):
        fi = int(linkage[i, 0])
        fj = int(linkage[i, 1])

        assert(fi <= i + n)
        assert(fj <= i + n)

        id = i + n
        left = d[fi]
        right = d[fj]
        dist = linkage[i, 2]

        if prototypes:
            prototype = prototypes[id]

            nd = DTWClusterNode(id=id, hierarchical_clustering_object=hierarchical_clustering_object,
                                prototype=prototype,
                                left=left, right=right,
                                dist=linkage[i, 2])

        elif callable(prototyping_function):
            prototype = prototyping_function(left.prototype.values, right.prototype.values, left.count, right.count)

            nd = DTWClusterNode(id=id, hierarchical_clustering_object=hierarchical_clustering_object,
                                prototype=prototype,
                                left=left, right=right,
                                dist=linkage[i, 2])

        elif prototyping_function == 'mean':
            nd = DTWClusterNode(id=id, hierarchical_clustering_object=hierarchical_clustering_object,
                                prototype=None,
                                left=left, right=right,
                                dist=linkage[i, 2])

            # A bit hacky, but does job. Doing this as to get to use nd.data
            nd._prototype = nd.data.mean()

        assert(linkage[i, 3] == nd.count)
        d[n + i] = nd

    return nd, d