29 #ifndef __FASTJET_CLOSESTPAIR2D__HH__ 30 #define __FASTJET_CLOSESTPAIR2D__HH__ 35 #include "fastjet/internal/ClosestPair2DBase.hh" 36 #include "fastjet/internal/SearchTree.hh" 37 #include "fastjet/internal/MinHeap.hh" 39 FASTJET_BEGIN_NAMESPACE
48 class ClosestPair2D :
public ClosestPair2DBase {
54 ClosestPair2D(
const std::vector<Coord2D> & positions,
55 const Coord2D & left_corner,
const Coord2D & right_corner) {
56 _initialize(positions, left_corner, right_corner, positions.size());
61 ClosestPair2D(
const std::vector<Coord2D> & positions,
62 const Coord2D & left_corner,
const Coord2D & right_corner,
63 const unsigned int max_size) {
64 _initialize(positions, left_corner, right_corner, max_size);
69 void closest_pair(
unsigned int & ID1,
unsigned int & ID2,
70 double & distance2)
const;
73 void remove(
unsigned int ID);
77 unsigned int insert(
const Coord2D &);
81 virtual unsigned int replace(
unsigned int ID1,
unsigned int ID2,
82 const Coord2D & position);
86 virtual void replace_many(
const std::vector<unsigned int> & IDs_to_remove,
87 const std::vector<Coord2D> & new_positions,
88 std::vector<unsigned int> & new_IDs);
91 inline void print_tree_depths(std::ostream & outdev)
const {
92 outdev << _trees[0]->max_depth() <<
" " 93 << _trees[1]->max_depth() <<
" " 94 << _trees[2]->max_depth() <<
"\n";
101 void _initialize(
const std::vector<Coord2D> & positions,
102 const Coord2D & left_corner,
const Coord2D & right_corner,
103 const unsigned int max_size);
105 static const unsigned int _nshift = 3;
111 template<
class T>
class triplet {
113 inline const T & operator[](
unsigned int i)
const {
return _contents[i];};
114 inline T & operator[](
unsigned int i) {
return _contents[i];};
116 T _contents[_nshift];
126 void operator+=(
unsigned int shift) {x += shift; y+= shift;};
129 typedef SearchTree<Shuffle> Tree;
130 typedef Tree::circulator circulator;
131 typedef Tree::const_circulator const_circulator;
134 triplet<std::auto_ptr<Tree> > _trees;
135 std::auto_ptr<MinHeap> _heap;
136 std::vector<Point> _points;
137 std::stack<Point *> _available_points;
140 std::vector<Point *> _points_under_review;
143 static const unsigned int _remove_heap_entry = 1;
144 static const unsigned int _review_heap_entry = 2;
145 static const unsigned int _review_neighbour = 4;
150 void _add_label(Point * point,
unsigned int review_flag);
155 void _set_label(Point * point,
unsigned int review_flag);
161 void _deal_with_points_to_review();
164 void _remove_from_search_tree(Point * point_to_remove);
167 void _insert_into_search_tree(Point * new_point);
170 void _point2shuffle(Point & , Shuffle & ,
unsigned int shift);
173 Coord2D _left_corner;
176 int _ID(
const Point *)
const;
178 triplet<unsigned int> _shifts;
179 triplet<unsigned int> _rel_shifts;
181 unsigned int _cp_search_range;
191 class ClosestPair2D::Point {
198 double neighbour_dist2;
200 triplet<circulator> circ;
203 unsigned int review_flag;
206 double distance2(
const Point & other)
const {
207 return coord.distance2(other.coord);
219 if (x>y)
return false;
226 inline int ClosestPair2D::_ID(
const Point * point)
const {
227 return point - &(_points[0]);
232 inline unsigned int ClosestPair2D::size() {
233 return _points.size() - _available_points.size();
238 FASTJET_END_NAMESPACE
240 #endif // __FASTJET_CLOSESTPAIR2D__HH__ bool floor_ln2_less(unsigned x, unsigned y)
returns true if floor(ln_base2(x)) < floor(ln_base2(y)), using Chan's neat trick...
bool operator<(SharedPtr< T > const &t, SharedPtr< U > const &u)
comparison: orgering