<commit_before>/**
 * @file cover_tree.hpp
 * @author <NAME>
 *
 * Definition of CoverTree, which can be used in place of the BinarySpaceTree.
 */
#ifndef __MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
#define __MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP

#include <mlpack/core.hpp>
#include <mlpack/core/metrics/lmetric.hpp>
#include "first_point_is_root.hpp"
#include "../statistic.hpp"

namespace mlpack {
namespace tree {

/**
 * A cover tree is a tree specifically designed to speed up nearest-neighbor
 * computation in high-dimensional spaces.  Each non-leaf node references a
 * point and has a nonzero number of children, including a "self-child" which
 * references the same point.  A leaf node represents only one point.
 *
 * The tree can be thought of as a hierarchy with the root node at the top level
 * and the leaf nodes at the bottom level.  Each level in the tree has an
 * assigned 'scale' i.  The tree follows these three conditions:
 *
 * - nesting: the level C_i is a subset of the level C_{i - 1}.
 * - covering: all node in level C_{i - 1} have at least one node in the
 *     level C_i with distance less than or equal to EC^i (exactly one of these
 *     is a parent of the point in level C_{i - 1}.
 * - separation: all nodes in level C_i have distance greater than EC^i to all
 *     other nodes in level C_i.
 *
 * The value 'EC' refers to the base, which is a parameter of the
 * tree.  These three properties make the cover tree very good for fast,
 * high-dimensional nearest-neighbor search.
 *
 * The theoretical structure of the tree contains many 'implicit' nodes which
 * only have a "self-child" (a child referencing the same point, but at a lower
 * scale level).  This practical implementation only constructs explicit nodes
 * -- non-leaf nodes with more than one child.  A leaf node has no children, and
 * its scale level is INT_MIN.
 *
 * For more information on cover trees, see
 *
 * @code
 * @inproceedings{
 *   author = {Beygelzimer, Alina and <NAME> and Langford, John},
 *   title = {Cover trees for nearest neighbor},
 *   booktitle = {Proceedings of the 23rd International Conference on Machine
 *     Learning},
 *   series = {ICML '06},
 *   year = {2006},
 *   pages = {97--104]
 * }
 * @endcode
 *
 * For information on runtime bounds of the nearest-neighbor computation using
 * cover trees, see the following paper, presented at NIPS 2009:
 *
 * @code
 * @inproceedings{
 *   author = {<NAME>., and <NAME>., and <NAME>., and <NAME>.},
 *   title = {Linear-time Algorithms for Pairwise Statistical Problems},
 *   booktitle = {Advances in Neural Information Processing Systems 22},
 *   editor = {<NAME> and <NAME> and <NAME> and <NAME>
 *     and <NAME>},
 *   pages = {1527--1535},
 *   year = {2009}
 * }
 * @endcode
 *
 * The CoverTree class offers three template parameters; a custom metric type
 * can be used with MetricType (this class defaults to the L2-squared metric).
 * The root node's point can be chosen with the RootPointPolicy; by default, the
 * FirstPointIsRoot policy is used, meaning the first point in the dataset is
 * used.  The StatisticType policy allows you to define statistics which can be
 * gathered during the creation of the tree.
 *
 * @tparam MetricType Metric type to use during tree construction.
 * @tparam RootPointPolicy Determines which point to use as the root node.
 * @tparam StatisticType Statistic to be used during tree creation.
 */
template<typename MetricType = metric::LMetric<2>,
         typename RootPointPolicy = FirstPointIsRoot,
         typename StatisticType = EmptyStatistic>
class CoverTree<commit_msg>Must used square rooted distance to be a valid metric.<commit_after>/**
 * @file cover_tree.hpp
 * @author <NAME>
 *
 * Definition of CoverTree, which can be used in place of the BinarySpaceTree.
 */
#ifndef __MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
#define __MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP

#include <mlpack/core.hpp>
#include <mlpack/core/metrics/lmetric.hpp>
#include "first_point_is_root.hpp"
#include "../statistic.hpp"

namespace mlpack {
namespace tree {

/**
 * A cover tree is a tree specifically designed to speed up nearest-neighbor
 * computation in high-dimensional spaces.  Each non-leaf node references a
 * point and has a nonzero number of children, including a "self-child" which
 * references the same point.  A leaf node represents only one point.
 *
 * The tree can be thought of as a hierarchy with the root node at the top level
 * and the leaf nodes at the bottom level.  Each level in the tree has an
 * assigned 'scale' i.  The tree follows these three conditions:
 *
 * - nesting: the level C_i is a subset of the level C_{i - 1}.
 * - covering: all node in level C_{i - 1} have at least one node in the
 *     level C_i with distance less than or equal to EC^i (exactly one of these
 *     is a parent of the point in level C_{i - 1}.
 * - separation: all nodes in level C_i have distance greater than EC^i to all
 *     other nodes in level C_i.
 *
 * The value 'EC' refers to the base, which is a parameter of the
 * tree.  These three properties make the cover tree very good for fast,
 * high-dimensional nearest-neighbor search.
 *
 * The theoretical structure of the tree contains many 'implicit' nodes which
 * only have a "self-child" (a child referencing the same point, but at a lower
 * scale level).  This practical implementation only constructs explicit nodes
 * -- non-leaf nodes with more than one child.  A leaf node has no children, and
 * its scale level is INT_MIN.
 *
 * For more information on cover trees, see
 *
 * @code
 * @inproceedings{
 *   author = {Beygelzimer, Alina and <NAME> and <NAME>},
 *   title = {Cover trees for nearest neighbor},
 *   booktitle = {Proceedings of the 23rd International Conference on Machine
 *     Learning},
 *   series = {ICML '06},
 *   year = {2006},
 *   pages = {97--104]
 * }
 * @endcode
 *
 * For information on runtime bounds of the nearest-neighbor computation using
 * cover trees, see the following paper, presented at NIPS 2009:
 *
 * @code
 * @inproceedings{
 *   author = {<NAME>., and <NAME>., and <NAME>., and <NAME>.},
 *   title = {Linear-time Algorithms for Pairwise Statistical Problems},
 *   booktitle = {Advances in Neural Information Processing Systems 22},
 *   editor = {<NAME> and <NAME> and <NAME> and <NAME>
 *     and <NAME>},
 *   pages = {1527--1535},
 *   year = {2009}
 * }
 * @endcode
 *
 * The CoverTree class offers three template parameters; a custom metric type
 * can be used with MetricType (this class defaults to the L2-squared metric).
 * The root node's point can be chosen with the RootPointPolicy; by default, the
 * FirstPointIsRoot policy is used, meaning the first point in the dataset is
 * used.  The StatisticType policy allows you to define statistics which can be
 * gathered during the creation of the tree.
 *
 * @tparam MetricType Metric type to use during tree construction.
 * @tparam RootPointPolicy Determines which point to use as the root node.
 * @tparam StatisticType Statistic to be used during tree creation.
 */
template<typename MetricType = metric::LMetric<2, true>,
         typename RootPointPolicy = FirstPointIsRoot,
         typename StatisticType = EmptyStatistic>
class CoverTree
{'fraction_non_alphanumeric': 0.08256628657782662, 'fraction_numerical': 0.00989146860832532, 'mean_word_length': 3.639898024219248, 'pattern_counts': {'":': 0, '<': 34, '<?xml version=': 0, '>': 34, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4884018', 'n_tokens_mistral': 2144, 'n_tokens_neox': 2052, 'n_words': 958}