<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_BBOX_COLLISION_DETECTOR_HPP__
#define LASERCAKE_BBOX_COLLISION_DETECTOR_HPP__

#include <boost/integer.hpp>
#include <unordered_map>
#include <unordered_set>
#include <array>
#include <cassert>
#include <cstdlib>
#include <boost/scoped_ptr.hpp>

using std::unordered_map;
using std::unordered_set;

typedef size_t num_bits_type;
typedef size_t num_coordinates_type;

// ObjectIdentifier needs hash and == and to be freely copiable. So, ints will do, pointers will do...
// coordinate_bits should usually be 32 or 64. I don't know if it works for other values.
template<typename ObjectIdentifier, num_bits_type coordinate_bits, num_coordinates_type num_dimensions>
class bbox_collision_detector {
  static_assert(num_dimensions >= 0, "You can't make a space with negative dimensions!");
  static_assert(coordinate_bits >= 0, "You can't have an int type with negative bits!");
  friend class zbox_tester;

public:
  typedef typename boost::uint_t<coordinate_bits>::fast Coordinate;
  struct bounding_box {
    std::array<Coordinate, num_dimensions> min, size;
    bool overlaps(bounding_box const& other)const {
      for (num_coordinates_type i = 0; i < num_dimensions; ++i) {
        // this should correctly handle zboxes' "size=0" when all bits are ignored
        if (other.min[i] + (other.size[i] - 1) <       min[i]) return false;
        if (      min[i] + (      size[i] - 1) < other.min[i]) return false;
      }
      return true;
    }
  };
  
  bbox_collision_detector():objects_tree(nullptr){}
  
private:
  static const num_bits_type total_bits = coordinate_bits * num_dimensions;
  
  static Coordinate safe_left_shift_one(num_bits_type shift) {
    if (shift >= 8*sizeof(Coordinate)) return 0;
    return Coordinate(1) << shift; // TODO address the fact that this could put bits higher than the appropriate amount if coordinate_bits isn't the number of bits of the type
  }
  
  struct zbox {
    // We ensure that every bit except the ones specifically supposed to be on is off.
    std::array<Coordinate, num_dimensions> coords;
    std::array<Coordinate, num_dimensions> interleaved_bits;
    num_bits_type num_low_bits_ignored;
    
    zbox():num_low_bits_ignored(total_bits){ for (num_coordinates_type i = 0; i < num_dimensions; ++i) interleaved_bits[i] = 0; }
    
    bool subsumes(zbox const& other)const {
      if (other.num_low_bits_ignored > num_low_bits_ignored) return false;
      for (num_coordinates_type i = num_low_bits_ignored / coordinate_bits; i < num_dimensions; ++i) {
        Coordinate mask = ~Coordinate(0);
        if (i == num_low_bits_ignored / coordinate_bits) {
          mask &= ~(safe_left_shift_one(num_low_bits_ignored % coordinate_bits) - 1);
        }
        if ((interleaved_bits[i] & mask) != (other.interleaved_bits[i] & mask)) return false;
      }
      return true;
    }
    bool get_bit(num_bits_type bit)const {
      return interleaved_bits[bit / coordinate_bits] & safe_left_shift_one(bit % coordinate_bits);
    }
    num_bits_type num_bits_ignored_by_dimension(num_coordinates_type dim)const {
      return (num_low_bits_ignored + (num_dimensions - 1) - dim) / num_dimensions;
    }
    // note: gives "size=0" for max-sized things
    bounding_box get_bbox()const {
      bounding_box result;
      result.min = coords;
      for (num_coordinates_type i = 0; i < num_dimensions; ++i) {
        result.size[i] = safe_left_shift_one(num_bits_ignored_by_dimension(i));
      }
      return result;
    }
  };
  
  static int idx_of_highest_bit(Coordinate i) {
    int upper_bound = coordinate_bits;
    int lower_bound = -1;
    while(true) {
      int halfway_bit_idx = (upper_bound + lower_bound) >> 1;
      if (halfway_bit_idx == lower_bound) return lower_bound;
      
      if (i & ~(safe_left_shift_one(halfway_bit_idx) - 1)) lower_bound = halfway_bit_idx;
      else                                                 upper_bound = halfway_bit_idx;
    }
  }
  
  struct ztree_node;
  typedef boost::scoped_ptr<ztree_node> ztree_node_ptr;
  struct ztree_node {
    zbox here;
    ztree_node_ptr child0;
    ztree_node_ptr child1;
    unordered_set<ObjectIdentifier> objects_here;
    
    ztree_node(zbox box):here(box),child0(nullptr),child1(nullptr){}
  };
  
  static zbox smallest_joint_parent(zbox zb1, zbox zb2) {
    zbox new_box;
    for (int /* hack... TODO, should possibly be num_coordinates_type, but signed? */ i = num_dimensions - 1; i >= 0; --i) {
      const int highest_bit_idx = idx_of_highest_bit(zb1.interleaved_bits[i] ^ zb2.interleaved_bits[i]);
      assert((zb1.interleaved_bits[i] & ~((safe_left_shift_one(highest_bit_idx+1)) - 1)) == (zb2.interleaved_bits[i] & ~((safe_left_shift_one(highest_bit_idx+1)) - 1)));
      new_box.interleaved_bits[i] = (zb1.interleaved_bits[i]) & (~((safe_left_shift_one(highest_bit_idx + 1)) - 1));
      if (highest_bit_idx >= 0) {
        new_box.num_low_bits_ignored = highest_bit_idx+1 + i * coordinate_bits;
        for (num_coordinates_type j = 0; j < num_dimensions; ++j) {
          assert(             (zb1.coords[j] & ~(safe_left_shift_one(new_box.num_bits_ignored_by_dimension(j)) - 1))
                           == (zb2.coords[j] & ~(safe_left_shift_one(new_box.num_bits_ignored_by_dimension(j)) - 1)));
          new_box.coords[j] = zb1.coords[j] & ~(safe_left_shift_one(new_box.num_bits_ignored_by_dimension(j)) - 1);
        }
        return new_box;
      }
    }
    new_box.num_low_bits_ignored = 0;<commit_msg>Make bbox_collision_detectors copy-constructable/assignable,<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_BBOX_COLLISION_DETECTOR_HPP__
#define LASERCAKE_BBOX_COLLISION_DETECTOR_HPP__

#include <boost/integer.hpp>
#include <unordered_map>
#include <unordered_set>
#include <array>
#include <cassert>
#include <cstdlib>
#include <boost/scoped_ptr.hpp>

using std::unordered_map;
using std::unordered_set;

typedef size_t num_bits_type;
typedef size_t num_coordinates_type;

// ObjectIdentifier needs hash and == and to be freely copiable. So, ints will do, pointers will do...
// coordinate_bits should usually be 32 or 64. I don't know if it works for other values.
template<typename ObjectIdentifier, num_bits_type coordinate_bits, num_coordinates_type num_dimensions>
class bbox_collision_detector {
  static_assert(num_dimensions >= 0, "You can't make a space with negative dimensions!");
  static_assert(coordinate_bits >= 0, "You can't have an int type with negative bits!");
  friend class zbox_tester;

public:
  typedef typename boost::uint_t<coordinate_bits>::fast Coordinate;
  struct bounding_box {
    std::array<Coordinate, num_dimensions> min, size;
    bool overlaps(bounding_box const& other)const {
      for (num_coordinates_type i = 0; i < num_dimensions; ++i) {
        // this should correctly handle zboxes' "size=0" when all bits are ignored
        if (other.min[i] + (other.size[i] - 1) <       min[i]) return false;
        if (      min[i] + (      size[i] - 1) < other.min[i]) return false;
      }
      return true;
    }
  };
  
  bbox_collision_detector():objects_tree(nullptr){}
  bbox_collision_detector(bbox_collision_detector const& other) { *this = other; }
  bbox_collision_detector& operator=(bbox_collision_detector const& other) {
    bboxes_by_object = other.bboxes_by_object;
    if(other.objects_tree) objects_tree.reset(new ztree_node(*other.objects_tree));
    return *this;
  }
  
private:
  static const num_bits_type total_bits = coordinate_bits * num_dimensions;
  
  static Coordinate safe_left_shift_one(num_bits_type shift) {
    if (shift >= 8*sizeof(Coordinate)) return 0;
    return Coordinate(1) << shift; // TODO address the fact that this could put bits higher than the appropriate amount if coordinate_bits isn't the number of bits of the type
  }
  
  struct zbox {
    // We ensure that every bit except the ones specifically supposed to be on is off.
    std::array<Coordinate, num_dimensions> coords;
    std::array<Coordinate, num_dimensions> interleaved_bits;
    num_bits_type num_low_bits_ignored;
    
    zbox():num_low_bits_ignored(total_bits){ for (num_coordinates_type i = 0; i < num_dimensions; ++i) interleaved_bits[i] = 0; }
    
    bool subsumes(zbox const& other)const {
      if (other.num_low_bits_ignored > num_low_bits_ignored) return false;
      for (num_coordinates_type i = num_low_bits_ignored / coordinate_bits; i < num_dimensions; ++i) {
        Coordinate mask = ~Coordinate(0);
        if (i == num_low_bits_ignored / coordinate_bits) {
          mask &= ~(safe_left_shift_one(num_low_bits_ignored % coordinate_bits) - 1);
        }
        if ((interleaved_bits[i] & mask) != (other.interleaved_bits[i] & mask)) return false;
      }
      return true;
    }
    bool get_bit(num_bits_type bit)const {
      return interleaved_bits[bit / coordinate_bits] & safe_left_shift_one(bit % coordinate_bits);
    }
    num_bits_type num_bits_ignored_by_dimension(num_coordinates_type dim)const {
      return (num_low_bits_ignored + (num_dimensions - 1) - dim) / num_dimensions;
    }
    // note: gives "size=0" for max-sized things
    bounding_box get_bbox()const {
      bounding_box result;
      result.min = coords;
      for (num_coordinates_type i = 0; i < num_dimensions; ++i) {
        result.size[i] = safe_left_shift_one(num_bits_ignored_by_dimension(i));
      }
      return result;
    }
  };
  
  static int idx_of_highest_bit(Coordinate i) {
    int upper_bound = coordinate_bits;
    int lower_bound = -1;
    while(true) {
      int halfway_bit_idx = (upper_bound + lower_bound) >> 1;
      if (halfway_bit_idx == lower_bound) return lower_bound;
      
      if (i & ~(safe_left_shift_one(halfway_bit_idx) - 1)) lower_bound = halfway_bit_idx;
      else                                                 upper_bound = halfway_bit_idx;
    }
  }
  
  struct ztree_node;
  typedef boost::scoped_ptr<ztree_node> ztree_node_ptr;
  struct ztree_node {
    zbox here;
    ztree_node_ptr child0;
    ztree_node_ptr child1;
    unordered_set<ObjectIdentifier> objects_here;
    
    ztree_node(zbox box):here(box),child0(nullptr),child1(nullptr){}
    ztree_node(ztree_node const& other) { *this = other; }
    ztree_node& operator=(ztree_node const& other) {
      here = other.here;
      if(other.child0) child0.reset(new ztree_node(*other.child0));
      if(other.child1) child1.reset(new ztree_node(*other.child1));
      return *this;
    }
  };
  
  static zbox smallest_joint_parent(zbox zb1, zbox zb2) {
    zbox new_box;
    for (int /* hack... TODO, should possibly be num_coordinates_type, but signed? */ i = num_dimensions - 1; i >= 0; --i) {
      const int highest_bit_idx = idx_of_highest_bit(zb1.interleaved_bits[i] ^ zb2.interleaved_bits[i]);
      assert((zb1.interleaved_bits[i] & ~((safe_left_shift_one(highest_bit_idx+1)) - 1)) == (zb2.interleaved_bits[i] & ~((safe_left_shift_one(highest_bit_idx+1)) - 1)));
      new_box.interleaved_bits[i] = (zb1.interleaved_bits[i]) & (~((safe_left_shift_one(highest_bit_idx + 1)) - 1));
      if (highest_bit_idx >= 0) {
        new_box.num_low_bits_ignored = highest_bit_idx+1 + i * coordinate_bits;
        for (num_coordinates_type j = 0; j < num_dimensions; ++j) {
          assert(             (zb1.coords[j] & ~(safe_left_shift_one(new_box.num_bits_ignored_by_dimension(j)) - 1))
                           == (zb2.coords[j] & ~(safe_left_shift_one(new_box.num_bits_ignored_by_dimension(j)) - 1)));
          new_box.coords[j] = zb1.coords[j] & ~(safe_left_shift_one(new_box.num_bits_ignored_by_dimension(j)) - 1);
        }
        return new_box;
      }
    }
    new_box.num_low_bits_ignored = 0;
{'fraction_non_alphanumeric': 0.0992756385817766, 'fraction_numerical': 0.009759817003431186, 'mean_word_length': 3.558915537017727, 'pattern_counts': {'":': 0, '<': 55, '<?xml version=': 0, '>': 53, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4121742', 'n_tokens_mistral': 4548, 'n_tokens_neox': 4387, 'n_words': 1080}