<commit_before>/**
 * @file binary_space_tree.hpp
 *
 * Definition of generalized binary space partitioning tree (BinarySpaceTree).
 */
#ifndef __MLPACK_CORE_TREE_BINARY_SPACE_TREE_HPP
#define __MLPACK_CORE_TREE_BINARY_SPACE_TREE_HPP

#include <mlpack/core.hpp>

#include "statistic.hpp"

namespace mlpack {
namespace tree /** Trees and tree-building procedures. */ {

/**
 * A binary space partitioning tree, such as a KD-tree or a ball tree.  Once the
 * bound and type of dataset is defined, the tree will construct itself.  Call
 * the constructor with the dataset to build the tree on, and the entire tree
 * will be built.
 *
 * This particular tree does not allow growth, so you cannot add or delete nodes
 * from it.  If you need to add or delete a node, the better procedure is to
 * rebuild the tree entirely.
 *
 * This tree does take one parameter, which is the leaf size to be used.  You
 * can set this at runtime with --tree/leaf_size [leaf_size].  You can also set
 * it in your program using CLI:
 *
 * @code
 * CLI::GetParam<int>("tree/leaf_size") = target_leaf_size;
 * @endcode
 *
 * @param leaf_size Maximum number of points allowed in each leaf.
 *
 * @tparam BoundType The bound used for each node.  The valid types of bounds
 *     and the necessary skeleton interface for this class can be found in
 *     bounds/.
 * @tparam StatisticType Extra data contained in the node.  See statistic.hpp
 *     for the necessary skeleton interface.
 */
template<typename BoundType,
         typename StatisticType = EmptyStatistic,
         typename MatType = arma::mat>
class BinarySpaceTree
{
 private:
  //! The left child node.
  BinarySpaceTree *left;
  //! The right child node.
  BinarySpaceTree *right;
  //! The index of the first point in the dataset contained in this node (and
  //! its children).
  size_t begin;
  //! The number of points of the dataset contained in this node (and its
  //! children).
  size_t count;
  //! The bound object for this node.
  BoundType bound;
  //! Any extra data contained in the node.
  StatisticType stat;
  //! The leaf size.
  size_t leafSize;

 public:
  /**
   * Construct this as the root node of a binary space tree using the given
   * dataset.  This will modify the ordering of the points in the dataset!
   *
   * @param data Dataset to create tree from.  This will be modified!
   * @param leafSize Size of each leaf in the tree.
   */
  BinarySpaceTree(MatType& data, const size_t leafSize = 20);

  /**
   * Construct this as the root node of a binary space tree using the given
   * dataset.  This will modify the ordering of points in the dataset!  A
   * mapping of the old point indices to the new point indices is filled.
   *
   * @param data Dataset to create tree from.  This will be modified!
   * @param oldFromNew Vector which will be filled with the old positions for
   *     each new point.
   * @param leafSize Size of each leaf in the tree.
   */
  BinarySpaceTree(MatType& data,
                  std::vector<size_t>& oldFromNew,
                  const size_t leafSize = 20);

  /**
   * Construct this as the root node of a binary space tree using the given
   * dataset.  This will modify the ordering of points in the dataset!  A
   * mapping of the old point indices to the new point indices is filled, as
   * well as a mapping of the new point indices to the old point indices.
   *<commit_msg>A typedef so other types that depend on the matrix type can use it.<commit_after>/**
 * @file binary_space_tree.hpp
 *
 * Definition of generalized binary space partitioning tree (BinarySpaceTree).
 */
#ifndef __MLPACK_CORE_TREE_BINARY_SPACE_TREE_HPP
#define __MLPACK_CORE_TREE_BINARY_SPACE_TREE_HPP

#include <mlpack/core.hpp>

#include "statistic.hpp"

namespace mlpack {
namespace tree /** Trees and tree-building procedures. */ {

/**
 * A binary space partitioning tree, such as a KD-tree or a ball tree.  Once the
 * bound and type of dataset is defined, the tree will construct itself.  Call
 * the constructor with the dataset to build the tree on, and the entire tree
 * will be built.
 *
 * This particular tree does not allow growth, so you cannot add or delete nodes
 * from it.  If you need to add or delete a node, the better procedure is to
 * rebuild the tree entirely.
 *
 * This tree does take one parameter, which is the leaf size to be used.  You
 * can set this at runtime with --tree/leaf_size [leaf_size].  You can also set
 * it in your program using CLI:
 *
 * @code
 * CLI::GetParam<int>("tree/leaf_size") = target_leaf_size;
 * @endcode
 *
 * @param leaf_size Maximum number of points allowed in each leaf.
 *
 * @tparam BoundType The bound used for each node.  The valid types of bounds
 *     and the necessary skeleton interface for this class can be found in
 *     bounds/.
 * @tparam StatisticType Extra data contained in the node.  See statistic.hpp
 *     for the necessary skeleton interface.
 */
template<typename BoundType,
         typename StatisticType = EmptyStatistic,
         typename MatType = arma::mat>
class BinarySpaceTree
{
 private:
  //! The left child node.
  BinarySpaceTree *left;
  //! The right child node.
  BinarySpaceTree *right;
  //! The index of the first point in the dataset contained in this node (and
  //! its children).
  size_t begin;
  //! The number of points of the dataset contained in this node (and its
  //! children).
  size_t count;
  //! The bound object for this node.
  BoundType bound;
  //! Any extra data contained in the node.
  StatisticType stat;
  //! The leaf size.
  size_t leafSize;

 public:
  //! So other classes can use TreeType::Mat.
  typedef MatType Mat;

  /**
   * Construct this as the root node of a binary space tree using the given
   * dataset.  This will modify the ordering of the points in the dataset!
   *
   * @param data Dataset to create tree from.  This will be modified!
   * @param leafSize Size of each leaf in the tree.
   */
  BinarySpaceTree(MatType& data, const size_t leafSize = 20);

  /**
   * Construct this as the root node of a binary space tree using the given
   * dataset.  This will modify the ordering of points in the dataset!  A
   * mapping of the old point indices to the new point indices is filled.
   *
   * @param data Dataset to create tree from.  This will be modified!
   * @param oldFromNew Vector which will be filled with the old positions for
   *     each new point.
   * @param leafSize Size of each leaf in the tree.
   */
  BinarySpaceTree(MatType& data,
                  std::vector<size_t>& oldFromNew,
                  const size_t leafSize = 20);

  /**
   * Construct this as the root node of a binary space tree using the given
   * dataset.  This will modify the ordering of points in the dataset!  A
   * mapping of the old point indices to the new point indices is filled, as
   * well as a mapping of the new point indices to the old point indices.
   *
{'fraction_non_alphanumeric': 0.06944444444444445, 'fraction_numerical': 0.0011574074074074073, 'mean_word_length': 3.088113542282673, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, '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': '5820097', 'n_tokens_mistral': 1955, 'n_tokens_neox': 1901, 'n_words': 948}