<commit_before>/*

    Copyright <NAME> and <NAME>, 2011, 2012

    This file is part of Lasercake.

    Lasercake is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Lasercake is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Lasercake.  If not, see <http://www.gnu.org/licenses/>.

*/

#ifndef LASERCAKE_PATRICIA_TRIE_HPP__
#define LASERCAKE_PATRICIA_TRIE_HPP__

#include "numbers.hpp"


typedef int32_t num_bits_type;
typedef int32_t num_coordinates_type;
class trivial_monoid {
public:
  // Default-constructor is monoid identity operator.
  trivial_monoid() {}
  // operator+ is monoid binary operator.
  friend inline trivial_monoid operator+(trivial_monoid, trivial_monoid) { return trivial_monoid(); }
  friend inline bool operator==(trivial_monoid, trivial_monoid) { return true; }
};
template<typename T1, typename T2>
class monoid_pair {
public:
  T1 first;
  T2 second;
  // Explicitly initialize the members ("value-initialize" in standard)
  // so that ints can be used as monoids under addition.
  monoid_pair() : first(), second() {}
  monoid_pair(T1 const& a, T1 const& b) : first(a), second(b) {}
  friend inline monoid_pair operator+(monoid_pair const& a, monoid_pair const& b) {
    return monoid_pair(a.first + b.first, a.second + b.second);
  }
  friend inline bool operator==(monoid_pair const& a, monoid_pair const& b) {
    return a.first == b.first && a.second == b.second;
  }
};
class noop_deleter {
public:
  template<typename T>
  void operator()(T const*)const {}
};
class default_deleter {
public:
  template<typename T>
  void operator()(T const* ptr)const {
    sizeof(*ptr); // Prevent deleting incomplete types,
                  // so that we are sure to call the destructor.
    delete ptr;
  }
};


template<num_coordinates_type Dims, typename Coord, typename T, typename Traits>
class pow2_radix_patricia_trie_node;

template<num_coordinates_type Dims, typename Coord>
class power_of_two_bounding_cube {
public:
  typedef std::array<Coord, Dims> loc_type;
  power_of_two_bounding_cube() : min_(), size_exponent_in_each_dimension_() {}
  power_of_two_bounding_cube(loc_type const& min, num_bits_type size_exponent_in_each_dimension)
   : min_(min), size_exponent_in_each_dimension_(size_exponent_in_each_dimension) {}
  power_of_two_bounding_cube(loc_type&& min, num_bits_type size_exponent_in_each_dimension)
   : min_(std::move(min)), size_exponent_in_each_dimension_(size_exponent_in_each_dimension) {}

  power_of_two_bounding_cube(power_of_two_bounding_cube const& other) = default;
  power_of_two_bounding_cube& operator=(power_of_two_bounding_cube const& other) = default;
  power_of_two_bounding_cube(power_of_two_bounding_cube&& other) = default;
  power_of_two_bounding_cube& operator=(power_of_two_bounding_cube&& other) = default;

  num_bits_type size_exponent_in_each_dimension()const { return size_exponent_in_each_dimension_; }
  loc_type const& min()const { return min_; }
  // TODO offer more methods
  
private:
  // Friend patricia_trie so that it can be more paranoid about
  // exception-safety, specifically the order in which the data members
  // are changed in move-assignment.
  template<num_coordinates_type Dims2, typename Coord2, typename T, typename Traits>
  friend class pow2_radix_patricia_trie_node;

  loc_type min_;
  // 0 for ptr-to-leaf node, nonzero for ptr-to-sub-nodes nodes,
  // doesn't matter for nullptr nodes:
  num_bits_type size_exponent_in_each_dimension_;
};

// Exception safety:
//
// Member deleters and destructors,
// and Coord move-assignment and move-construction,
// must be nothrow or else the tree may be left in an
// inconsistent state.
//
// If any monoid operation can throw, then the monoids may
// be left in an inconsistent state but the strong guarantee*
// holds for all aspects of the tree except the monoids.
// (*every operation completely succeeds, or has no effect
// and throws an exception).
//
// 'insert' can throw errors from node_allocator.
//   If it does, insert() had no side-effects.
//
// 'insert' and 'erase' can throw errors from 'monoid'.
//   If they do, the tree's monoids may be incorrect
//   but there are no other side-effects.
//
// The default-constructor can only throw errors from
//   Coord's and monoid's default-constructors.
//
// Non-mutating operations cannot throw exceptions.
struct default_pow2_radix_patricia_trie_traits {
  typedef trivial_monoid monoid;
  typedef default_deleter leaf_deleter;
  typedef lasercake_nice_allocator<int>::type node_allocator;
};

template<num_coordinates_type Dims, typename Coord, typename T, typename Traits = default_pow2_radix_patricia_trie_traits>
class pow2_radix_patricia_trie_node {
public:
  static const num_coordinates_type dimensions = Dims;
  static const size_t radix = size_t(1) << dimensions;
  typedef pow2_radix_patricia_trie_node node_type;
  typedef std::array<node_type, radix> sub_nodes_type;
  typedef std::array<Coord, dimensions> loc_type;
  typedef power_of_two_bounding_cube<dimensions, Coord> power_of_two_bounding_cube_type;
  typedef typename Traits::monoid monoid_type;
  typedef typename Traits::leaf_deleter leaf_deleter;
  typedef typename Traits::node_allocator::template rebind<sub_nodes_type>::other node_allocator;

  pow2_radix_patricia_trie_node() : ptr_(), parent_(), siblings_(), box_(), monoid_() {}
  ~pow2_radix_patricia_trie_node() { delete_ptr_(); }

  // TODO maybe implement copy-constructor that copies whole tree? or subtree?
  pow2_radix_patricia_trie_node(pow2_radix_patricia_trie_node const& other) = delete;
  pow2_radix_patricia_trie_node& operator=(pow2_radix_patricia_trie_node const& other) = delete;

  // monoid operations might conceivably throw, but destructors shouldn't
  // and Coord assignment shouldn't and primitive assignment can't.
  pow2_radix_patricia_trie_node(pow2_radix_patricia_trie_node&& other)
          : ptr_(nullptr), monoid_(std::move(other.monoid_)) {
    // It was too hard to exception-safe-ly move-construct
    // monoid and box_.min and ptr in the right orders,
    // so we default-construct them and then move-assign some,
    // potentially alas.
    box_.min_ = std::move(other.box_.min_);
    move_initialize_from_except_userdata_(other);
  }
  pow2_radix_patricia_trie_node& operator=(pow2_radix_patricia_trie_node&& other) {
    monoid_ = std::move(other.monoid_);
    box_.min_ = std::move(other.box_.min_);
    delete_ptr_();
    move_initialize_from_except_userdata_(other);
  }

  // It is possible for the root node to also be a ptr-to-leaf node.
  bool is_root_node()const { return !parent_; }
  bool points_to_leaf()const { return ptr_ && box_.size_exponent_in_each_dimension_ == 0; }
  bool points_to_sub_nodes()const { return ptr_ && box_.size_exponent_in_each_dimension_ != 0; }
  bool is_empty()const { return !ptr_; }
  sub_nodes_type* sub_nodes() { return points_to_sub_nodes() ? static_cast<sub_nodes_type*>(ptr_) : nullptr; }
  sub_nodes_type const* sub_nodes()const { return points_to_sub_nodes() ? static_cast<sub_nodes_type*>(ptr_) : nullptr; }
  T* leaf() { return points_to_leaf() ? static_cast<T*>(ptr_) : nullptr; }
  T const* leaf()const { return points_to_leaf() ? static_cast<T*>(ptr_) : nullptr; }

  bool contains(loc_type const& loc)const {
    if (!shift_value_is_safe_for_type<Coord>(box_.size_exponent_in_each_dimension_)) {
      // Avoid left-shifting by an invalidly large amount.
      return true;
    }
    const Coord mask = (~Coord(0) << box_.size_exponent_in_each_dimension_);
    for (num_coordinates_type dim = 0; dim != dimensions; ++dim) {
      if ((box_.min_[dim] & mask) != (loc[dim] & mask)) { return false; }
    }
    return true;<commit_msg>add patricia_trie_node accessors<commit_after>/*

    Copyright <NAME> and <NAME>, 2011, 2012

    This file is part of Lasercake.

    Lasercake is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Lasercake is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Lasercake.  If not, see <http://www.gnu.org/licenses/>.

*/

#ifndef LASERCAKE_PATRICIA_TRIE_HPP__
#define LASERCAKE_PATRICIA_TRIE_HPP__

#include "numbers.hpp"


typedef int32_t num_bits_type;
typedef int32_t num_coordinates_type;
class trivial_monoid {
public:
  // Default-constructor is monoid identity operator.
  trivial_monoid() {}
  // operator+ is monoid binary operator.
  friend inline trivial_monoid operator+(trivial_monoid, trivial_monoid) { return trivial_monoid(); }
  friend inline bool operator==(trivial_monoid, trivial_monoid) { return true; }
};
template<typename T1, typename T2>
class monoid_pair {
public:
  T1 first;
  T2 second;
  // Explicitly initialize the members ("value-initialize" in standard)
  // so that ints can be used as monoids under addition.
  monoid_pair() : first(), second() {}
  monoid_pair(T1 const& a, T1 const& b) : first(a), second(b) {}
  friend inline monoid_pair operator+(monoid_pair const& a, monoid_pair const& b) {
    return monoid_pair(a.first + b.first, a.second + b.second);
  }
  friend inline bool operator==(monoid_pair const& a, monoid_pair const& b) {
    return a.first == b.first && a.second == b.second;
  }
};
class noop_deleter {
public:
  template<typename T>
  void operator()(T const*)const {}
};
class default_deleter {
public:
  template<typename T>
  void operator()(T const* ptr)const {
    sizeof(*ptr); // Prevent deleting incomplete types,
                  // so that we are sure to call the destructor.
    delete ptr;
  }
};


template<num_coordinates_type Dims, typename Coord, typename T, typename Traits>
class pow2_radix_patricia_trie_node;

template<num_coordinates_type Dims, typename Coord>
class power_of_two_bounding_cube {
public:
  typedef std::array<Coord, Dims> loc_type;
  power_of_two_bounding_cube() : min_(), size_exponent_in_each_dimension_() {}
  power_of_two_bounding_cube(loc_type const& min, num_bits_type size_exponent_in_each_dimension)
   : min_(min), size_exponent_in_each_dimension_(size_exponent_in_each_dimension) {}
  power_of_two_bounding_cube(loc_type&& min, num_bits_type size_exponent_in_each_dimension)
   : min_(std::move(min)), size_exponent_in_each_dimension_(size_exponent_in_each_dimension) {}

  power_of_two_bounding_cube(power_of_two_bounding_cube const& other) = default;
  power_of_two_bounding_cube& operator=(power_of_two_bounding_cube const& other) = default;
  power_of_two_bounding_cube(power_of_two_bounding_cube&& other) = default;
  power_of_two_bounding_cube& operator=(power_of_two_bounding_cube&& other) = default;

  num_bits_type size_exponent_in_each_dimension()const { return size_exponent_in_each_dimension_; }
  loc_type const& min()const { return min_; }
  // TODO offer more methods
  
private:
  // Friend patricia_trie so that it can be more paranoid about
  // exception-safety, specifically the order in which the data members
  // are changed in move-assignment.
  template<num_coordinates_type Dims2, typename Coord2, typename T, typename Traits>
  friend class pow2_radix_patricia_trie_node;

  loc_type min_;
  // 0 for ptr-to-leaf node, nonzero for ptr-to-sub-nodes nodes,
  // doesn't matter for nullptr nodes:
  num_bits_type size_exponent_in_each_dimension_;
};

// Exception safety:
//
// Member deleters and destructors,
// and Coord move-assignment and move-construction,
// must be nothrow or else the tree may be left in an
// inconsistent state.
//
// If any monoid operation can throw, then the monoids may
// be left in an inconsistent state but the strong guarantee*
// holds for all aspects of the tree except the monoids.
// (*every operation completely succeeds, or has no effect
// and throws an exception).
//
// 'insert' can throw errors from node_allocator.
//   If it does, insert() had no side-effects.
//
// 'insert' and 'erase' can throw errors from 'monoid'.
//   If they do, the tree's monoids may be incorrect
//   but there are no other side-effects.
//
// The default-constructor can only throw errors from
//   Coord's and monoid's default-constructors.
//
// Non-mutating operations cannot throw exceptions.
struct default_pow2_radix_patricia_trie_traits {
  typedef trivial_monoid monoid;
  typedef default_deleter leaf_deleter;
  typedef lasercake_nice_allocator<int>::type node_allocator;
};

template<num_coordinates_type Dims, typename Coord, typename T, typename Traits = default_pow2_radix_patricia_trie_traits>
class pow2_radix_patricia_trie_node {
public:
  static const num_coordinates_type dimensions = Dims;
  static const size_t radix = size_t(1) << dimensions;
  typedef pow2_radix_patricia_trie_node node_type;
  typedef std::array<node_type, radix> sub_nodes_type;
  typedef std::array<Coord, dimensions> loc_type;
  typedef power_of_two_bounding_cube<dimensions, Coord> power_of_two_bounding_cube_type;
  typedef typename Traits::monoid monoid_type;
  typedef typename Traits::leaf_deleter leaf_deleter;
  typedef typename Traits::node_allocator::template rebind<sub_nodes_type>::other node_allocator;

  pow2_radix_patricia_trie_node() : ptr_(), parent_(), siblings_(), box_(), monoid_() {}
  ~pow2_radix_patricia_trie_node() { delete_ptr_(); }

  // TODO maybe implement copy-constructor that copies whole tree? or subtree?
  pow2_radix_patricia_trie_node(pow2_radix_patricia_trie_node const& other) = delete;
  pow2_radix_patricia_trie_node& operator=(pow2_radix_patricia_trie_node const& other) = delete;

  // monoid operations might conceivably throw, but destructors shouldn't
  // and Coord assignment shouldn't and primitive assignment can't.
  pow2_radix_patricia_trie_node(pow2_radix_patricia_trie_node&& other)
          : ptr_(nullptr), monoid_(std::move(other.monoid_)) {
    // It was too hard to exception-safe-ly move-construct
    // monoid and box_.min and ptr in the right orders,
    // so we default-construct them and then move-assign some,
    // potentially alas.
    box_.min_ = std::move(other.box_.min_);
    move_initialize_from_except_userdata_(other);
  }
  pow2_radix_patricia_trie_node& operator=(pow2_radix_patricia_trie_node&& other) {
    monoid_ = std::move(other.monoid_);
    box_.min_ = std::move(other.box_.min_);
    delete_ptr_();
    move_initialize_from_except_userdata_(other);
  }

  // It is possible for the root node to also be a ptr-to-leaf node.
  bool is_root_node()const { return !parent_; }
  bool points_to_leaf()const { return ptr_ && box_.size_exponent_in_each_dimension_ == 0; }
  bool points_to_sub_nodes()const { return ptr_ && box_.size_exponent_in_each_dimension_ != 0; }
  bool is_empty()const { return !ptr_; }
  sub_nodes_type* sub_nodes() { return points_to_sub_nodes() ? static_cast<sub_nodes_type*>(ptr_) : nullptr; }
  sub_nodes_type const* sub_nodes()const { return points_to_sub_nodes() ? static_cast<sub_nodes_type*>(ptr_) : nullptr; }
  T* leaf() { return points_to_leaf() ? static_cast<T*>(ptr_) : nullptr; }
  T const* leaf()const { return points_to_leaf() ? static_cast<T*>(ptr_) : nullptr; }
  node_type* parent() { return parent_; }
  node_type const* parent()const { return parent_; }
  sub_nodes_type* siblings() { return siblings_; }
  sub_nodes_type const* siblings()const { return siblings_; }

  bool contains(loc_type const& loc)const {
    if (!shift_value_is_safe_for_type<Coord>(box_.size_exponent_in_each_dimension_)) {
      // Avoid left-shifting by an invalidly large amount.
      return true;
    }
    const Coord mask = (~Coord(0) << box_.size_exponent_in_each_dimension_);
    for (num_coordinates_type dim = 0; dim != dimensions; ++dim) {
      if ((box_.min_[dim] & mask) != (loc[dim] & mask)) { return false; }
    }
    return true;
{'fraction_non_alphanumeric': 0.09304300357857706, 'fraction_numerical': 0.005216230969855037, 'mean_word_length': 4.754973821989529, 'pattern_counts': {'":': 0, '<': 53, '<?xml version=': 0, '>': 45, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, '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': '6417626', 'n_tokens_mistral': 5517, 'n_tokens_neox': 5300, 'n_words': 1477}