<commit_before>"""
Function Reference
------------------

These functions cut hierarchical clusterings into flat clusterings
or find the roots of the forest formed by a cut by providing the flat
cluster ids of each observation.

+------------------+-------------------------------------------------+
|*Function*        | *Description*                                   |
+------------------+-------------------------------------------------+
|fcluster          |forms flat clusters from hierarchical clusters.  |
+------------------+-------------------------------------------------+
|fclusterdata      |forms flat clusters directly from data.          |
+------------------+-------------------------------------------------+
|leaders           |singleton root nodes for flat cluster.           |
+------------------+-------------------------------------------------+

These are routines for agglomerative clustering.

+------------------+-------------------------------------------------+
|*Function*        | *Description*                                   |
+------------------+-------------------------------------------------+
|linkage           |agglomeratively clusters original observations.  |
+------------------+-------------------------------------------------+
|single            |the single/min/nearest algorithm. (alias)        |
+------------------+-------------------------------------------------+
|complete          |the complete/max/farthest algorithm. (alias)     |
+------------------+-------------------------------------------------+
|average           |the average/UPGMA algorithm. (alias)             |
+------------------+-------------------------------------------------+
|weighted          |the weighted/WPGMA algorithm. (alias)            |
+------------------+-------------------------------------------------+
|centroid          |the centroid/UPGMC algorithm. (alias)            |
+------------------+-------------------------------------------------+
|median            |the median/WPGMC algorithm. (alias)              |
+------------------+-------------------------------------------------+
|ward              |the Ward/incremental algorithm. (alias)          |
+------------------+-------------------------------------------------+

These routines compute statistics on hierarchies.

+------------------+-------------------------------------------------+
|*Function*        | *Description*                                   |
+------------------+-------------------------------------------------+
|cophenet          |computes the cophenetic distance between leaves. |
+------------------+-------------------------------------------------+
|from_mlab_linkage |converts a linkage produced by MATLAB(TM).       |
+------------------+-------------------------------------------------+
|inconsistent      |the inconsistency coefficients for cluster.      |
+------------------+-------------------------------------------------+
|maxinconsts       |the maximum inconsistency coefficient for each   |
|                  |cluster.                                         |
+------------------+-------------------------------------------------+
|maxdists          |the maximum distance for each cluster.           |
+------------------+-------------------------------------------------+
|maxRstat          |the maximum specific statistic for each cluster. |
+------------------+-------------------------------------------------+
|to_mlab_linkage   |converts a linkage to one MATLAB(TM) can         |
|                  |understand.                                      |
+------------------+-------------------------------------------------+

Routines for visualizing flat clusters.

+------------------+-------------------------------------------------+
|*Function*        | *Description*                                   |
+------------------+-------------------------------------------------+
|dendrogram        |visualizes linkages (requires matplotlib).       |
+------------------+-------------------------------------------------+

These are data structures and routines for representing hierarchies as
tree objects.

+------------------+-------------------------------------------------+
|*Function*        | *Description*                                   |
+------------------+-------------------------------------------------+
|ClusterNode       |represents cluster nodes in a cluster hierarchy. |
+------------------+-------------------------------------------------+
|leaves_list       |a left-to-right traversal of the leaves.         |
+------------------+-------------------------------------------------+
|to_tree           |represents a linkage matrix as a tree object.    |
+------------------+-------------------------------------------------+

These are predicates for checking the validity of linkage and
inconsistency matrices as well as for checking isomorphism of two
flat cluster assignments.

+------------------+-------------------------------------------------+
|*Function*        | *Description*                                   |
+------------------+-------------------------------------------------+
|is_valid_im       |checks for a valid inconsistency matrix.         |
+------------------+-------------------------------------------------+
|is_valid_linkage  |checks for a valid hierarchical clustering.      |
+------------------+-------------------------------------------------+
|is_isomorphic     |checks if two flat clusterings are isomorphic.   |
+------------------+-------------------------------------------------+
|is_monotonic      |checks if a linkage is monotonic.                |
+------------------+-------------------------------------------------+
|correspond        |checks whether a condensed distance matrix       |
|                  |corresponds with a linkage                       |
+------------------+-------------------------------------------------+
|num_obs_linkage   |the number of observations corresponding to a    |
|                  |linkage matrix.                                  |
+------------------+-------------------------------------------------+


* MATLAB and MathWorks are registered trademarks of The MathWorks, Inc.

* Mathematica is a registered trademark of The Wolfram Research, Inc.


References
----------

.. [Sta07] "Statistics toolbox." API Reference Documentation. The MathWorks.
   http://www.mathworks.com/access/helpdesk/help/toolbox/stats/.
   Accessed October 1, 2007.

.. [Mti07] "Hierarchical clustering." API Reference Documentation.
   The Wolfram Research, Inc.
   http://reference.wolfram.com/mathematica/HierarchicalClustering/tutorial/HierarchicalClustering.html.
   Accessed October 1, 2007.

.. [Gow69] Gower, JC and Ross, GJS. "Minimum Spanning Trees and Single Linkage
   Cluster Analysis." Applied Statistics. 18(1): pp. 54--64. 1969.

.. [War63] <NAME>, JH. "Hierarchical grouping to optimize an objective
   function." Journal of the American Statistical Association. 58(301):
   pp. 236--44. 1963.

.. [Joh66] Johnson, SC. "Hierarchical clustering schemes." Psychometrika.
   32(2): pp. 241--54. 1966.

.. [Sne62] Sneath, PH and Sokal, RR. "Numerical taxonomy." Nature. 193: pp.
   855--60. 1962.

.. [Bat95] Batagelj, V. "Comparing resemblance measures." Journal of
   Classification. 12: pp. 73--90. 1995.

.. [Sok58] Sokal, RR and Michener, CD. "A statistical method for evaluating
   systematic relationships." Scientific Bulletins. 38(22):
   pp. 1409--38. 1958.

.. [Ede79] Edelbrock, C. "Mixture model tests of hierarchical clustering
   algorithms: the problem of classifying everybody." Multivariate
   Behavioral Research. 14: pp. 367--84. 1979.

.. [Jai88] <NAME>., and <NAME>., "Algorithms for Clustering Data."
   Prentice-Hall. Englewood Cliffs, NJ. 1988.

.. [Fis36] Fisher, RA "The use of multiple measurements in taxonomic
   problems." Annals of Eugenics, 7(2): 179-188. 1936

Copyright Notice
----------------

Copyright (C) <NAME>, 2007-2008. New BSD License.

"""


# hierarchy.py (derived from cluster.py, http://scipy-cluster.googlecode.com)
#
# Author: <NAME>
# Date:   September 22, 2007
#
# Copyright (c) 2007, 2008, <NAME>
#
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
#   - Redistributions of source code must retain the above
#     copyright notice, this list of conditions and the
#     following disclaimer.
#   - Redistributions in binary form must reproduce the above copyright
#     notice, this list of conditions and the following disclaimer
#     in the documentation and/or other materials provided with the
#     distribution.
#   - Neither the name of the author nor the names of its
#     contributors may be used to endorse or promote products derived
#     from this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

import numpy as np
import _hierarchy_wrap, types
import scipy.spatial.distance as distance

_cpy_non_euclid_methods = {'single': 0, 'complete': 1, 'average': 2,
                           'weighted': 6}
_cpy_euclid_methods = {'centroid': 3, 'median': 4, 'ward': 5}
_cpy_linkage_methods = set(_cpy_non_euclid_methods.keys()).union(
    set(_cpy_euclid_methods.keys()))

try:
    import warnings
    def _warning(s):
        warnings.warn('scipy.cluster: %s' % s, stacklevel=3)
except:
    def _warning(s):
        print ('[WARNING] scipy.cluster: %s' % s)

def _copy_array_if_base_present(a):
    """
    Copies the array if its base points to a parent array.<commit_msg>REF: move types import on top.<commit_after>"""
Function Reference
------------------

These functions cut hierarchical clusterings into flat clusterings
or find the roots of the forest formed by a cut by providing the flat
cluster ids of each observation.

+------------------+-------------------------------------------------+
|*Function*        | *Description*                                   |
+------------------+-------------------------------------------------+
|fcluster          |forms flat clusters from hierarchical clusters.  |
+------------------+-------------------------------------------------+
|fclusterdata      |forms flat clusters directly from data.          |
+------------------+-------------------------------------------------+
|leaders           |singleton root nodes for flat cluster.           |
+------------------+-------------------------------------------------+

These are routines for agglomerative clustering.

+------------------+-------------------------------------------------+
|*Function*        | *Description*                                   |
+------------------+-------------------------------------------------+
|linkage           |agglomeratively clusters original observations.  |
+------------------+-------------------------------------------------+
|single            |the single/min/nearest algorithm. (alias)        |
+------------------+-------------------------------------------------+
|complete          |the complete/max/farthest algorithm. (alias)     |
+------------------+-------------------------------------------------+
|average           |the average/UPGMA algorithm. (alias)             |
+------------------+-------------------------------------------------+
|weighted          |the weighted/WPGMA algorithm. (alias)            |
+------------------+-------------------------------------------------+
|centroid          |the centroid/UPGMC algorithm. (alias)            |
+------------------+-------------------------------------------------+
|median            |the median/WPGMC algorithm. (alias)              |
+------------------+-------------------------------------------------+
|ward              |the Ward/incremental algorithm. (alias)          |
+------------------+-------------------------------------------------+

These routines compute statistics on hierarchies.

+------------------+-------------------------------------------------+
|*Function*        | *Description*                                   |
+------------------+-------------------------------------------------+
|cophenet          |computes the cophenetic distance between leaves. |
+------------------+-------------------------------------------------+
|from_mlab_linkage |converts a linkage produced by MATLAB(TM).       |
+------------------+-------------------------------------------------+
|inconsistent      |the inconsistency coefficients for cluster.      |
+------------------+-------------------------------------------------+
|maxinconsts       |the maximum inconsistency coefficient for each   |
|                  |cluster.                                         |
+------------------+-------------------------------------------------+
|maxdists          |the maximum distance for each cluster.           |
+------------------+-------------------------------------------------+
|maxRstat          |the maximum specific statistic for each cluster. |
+------------------+-------------------------------------------------+
|to_mlab_linkage   |converts a linkage to one MATLAB(TM) can         |
|                  |understand.                                      |
+------------------+-------------------------------------------------+

Routines for visualizing flat clusters.

+------------------+-------------------------------------------------+
|*Function*        | *Description*                                   |
+------------------+-------------------------------------------------+
|dendrogram        |visualizes linkages (requires matplotlib).       |
+------------------+-------------------------------------------------+

These are data structures and routines for representing hierarchies as
tree objects.

+------------------+-------------------------------------------------+
|*Function*        | *Description*                                   |
+------------------+-------------------------------------------------+
|ClusterNode       |represents cluster nodes in a cluster hierarchy. |
+------------------+-------------------------------------------------+
|leaves_list       |a left-to-right traversal of the leaves.         |
+------------------+-------------------------------------------------+
|to_tree           |represents a linkage matrix as a tree object.    |
+------------------+-------------------------------------------------+

These are predicates for checking the validity of linkage and
inconsistency matrices as well as for checking isomorphism of two
flat cluster assignments.

+------------------+-------------------------------------------------+
|*Function*        | *Description*                                   |
+------------------+-------------------------------------------------+
|is_valid_im       |checks for a valid inconsistency matrix.         |
+------------------+-------------------------------------------------+
|is_valid_linkage  |checks for a valid hierarchical clustering.      |
+------------------+-------------------------------------------------+
|is_isomorphic     |checks if two flat clusterings are isomorphic.   |
+------------------+-------------------------------------------------+
|is_monotonic      |checks if a linkage is monotonic.                |
+------------------+-------------------------------------------------+
|correspond        |checks whether a condensed distance matrix       |
|                  |corresponds with a linkage                       |
+------------------+-------------------------------------------------+
|num_obs_linkage   |the number of observations corresponding to a    |
|                  |linkage matrix.                                  |
+------------------+-------------------------------------------------+


* MATLAB and MathWorks are registered trademarks of The MathWorks, Inc.

* Mathematica is a registered trademark of The Wolfram Research, Inc.


References
----------

.. [Sta07] "Statistics toolbox." API Reference Documentation. The MathWorks.
   http://www.mathworks.com/access/helpdesk/help/toolbox/stats/.
   Accessed October 1, 2007.

.. [Mti07] "Hierarchical clustering." API Reference Documentation.
   The Wolfram Research, Inc.
   http://reference.wolfram.com/mathematica/HierarchicalClustering/tutorial/HierarchicalClustering.html.
   Accessed October 1, 2007.

.. [Gow69] Gower, JC and Ross, GJS. "Minimum Spanning Trees and Single Linkage
   Cluster Analysis." Applied Statistics. 18(1): pp. 54--64. 1969.

.. [War63] <NAME>, JH. "Hierarchical grouping to optimize an objective
   function." Journal of the American Statistical Association. 58(301):
   pp. 236--44. 1963.

.. [Joh66] Johnson, SC. "Hierarchical clustering schemes." Psychometrika.
   32(2): pp. 241--54. 1966.

.. [Sne62] Sneath, PH and Sokal, RR. "Numerical taxonomy." Nature. 193: pp.
   855--60. 1962.

.. [Bat95] <NAME>. "Comparing resemblance measures." Journal of
   Classification. 12: pp. 73--90. 1995.

.. [Sok58] Sokal, RR and Michener, CD. "A statistical method for evaluating
   systematic relationships." Scientific Bulletins. 38(22):
   pp. 1409--38. 1958.

.. [Ede79] <NAME>. "Mixture model tests of hierarchical clustering
   algorithms: the problem of classifying everybody." Multivariate
   Behavioral Research. 14: pp. 367--84. 1979.

.. [Jai88] <NAME>., and <NAME>., "Algorithms for Clustering Data."
   Prentice-Hall. Englewood Cliffs, NJ. 1988.

.. [Fis36] Fisher, RA "The use of multiple measurements in taxonomic
   problems." Annals of Eugenics, 7(2): 179-188. 1936

Copyright Notice
----------------

Copyright (C) <NAME>, 2007-2008. New BSD License.

"""


# hierarchy.py (derived from cluster.py, http://scipy-cluster.googlecode.com)
#
# Author: <NAME>
# Date:   September 22, 2007
#
# Copyright (c) 2007, 2008, <NAME>
#
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
#   - Redistributions of source code must retain the above
#     copyright notice, this list of conditions and the
#     following disclaimer.
#   - Redistributions in binary form must reproduce the above copyright
#     notice, this list of conditions and the following disclaimer
#     in the documentation and/or other materials provided with the
#     distribution.
#   - Neither the name of the author nor the names of its
#     contributors may be used to endorse or promote products derived
#     from this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
import types

import numpy as np
import _hierarchy_wrap
import scipy.spatial.distance as distance

_cpy_non_euclid_methods = {'single': 0, 'complete': 1, 'average': 2,
                           'weighted': 6}
_cpy_euclid_methods = {'centroid': 3, 'median': 4, 'ward': 5}
_cpy_linkage_methods = set(_cpy_non_euclid_methods.keys()).union(
    set(_cpy_euclid_methods.keys()))

try:
    import warnings
    def _warning(s):
        warnings.warn('scipy.cluster: %s' % s, stacklevel=3)
except:
    def _warning(s):
        print ('[WARNING] scipy.cluster: %s' % s)

def _copy_array_if_base_present(a):
    """
    Copies the array if its base points to a parent array.
{'fraction_non_alphanumeric': 0.332643633913964, 'fraction_numerical': 0.015590414782022905, 'mean_word_length': 1.1372891814068284, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1751093', 'n_tokens_mistral': 4867, 'n_tokens_neox': 4196, 'n_words': 1571}