FastJet  3.0.6
DynamicNearestNeighbours.hh
1 //STARTHEADER
2 // $Id: DynamicNearestNeighbours.hh 2687 2011-11-14 11:17:51Z soyez $
3 //
4 // Copyright (c) 2005-2011, Matteo Cacciari, Gavin P. Salam and Gregory Soyez
5 //
6 //----------------------------------------------------------------------
7 // This file is part of FastJet.
8 //
9 // FastJet is free software; you can redistribute it and/or modify
10 // it under the terms of the GNU General Public License as published by
11 // the Free Software Foundation; either version 2 of the License, or
12 // (at your option) any later version.
13 //
14 // The algorithms that underlie FastJet have required considerable
15 // development and are described in hep-ph/0512210. If you use
16 // FastJet as part of work towards a scientific publication, please
17 // include a citation to the FastJet paper.
18 //
19 // FastJet is distributed in the hope that it will be useful,
20 // but WITHOUT ANY WARRANTY; without even the implied warranty of
21 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 // GNU General Public License for more details.
23 //
24 // You should have received a copy of the GNU General Public License
25 // along with FastJet. If not, see <http://www.gnu.org/licenses/>.
26 //----------------------------------------------------------------------
27 //ENDHEADER
28 
29 
30 #ifndef __FASTJET_DYNAMICNEARESTNEIGHBOURS_HH__
31 #define __FASTJET_DYNAMICNEARESTNEIGHBOURS_HH__
32 
33 #include<vector>
34 #include<string>
35 #include<iostream>
36 #include<sstream>
37 #include<cassert>
38 #include "fastjet/internal/numconsts.hh"
39 
40 FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh
41 
42 /// Shortcut for dealing with eta-phi coordinates.
43 //typedef std::pair<double,double> EtaPhi;
44 
45 /// \if internal_doc
46 /// @ingroup internal
47 /// \class EtaPhi
48 /// use a class instead of a pair so that phi can be sanitized
49 /// and put into proper range on initialization.
50 /// \endif
51 class EtaPhi {
52 public:
53  double first, second;
54  EtaPhi() {}
55  EtaPhi(double a, double b) {first = a; second = b;}
56  /// put things into the desired range.
57  void sanitize() {
58  if (second < 0) second += twopi;
59  if (second >= twopi) second -= twopi;
60  }
61 
62 };
63 
64 /// \if internal_doc
65 /// @ingroup internal
66 /// \class DnnError
67 /// class corresponding to errors that will be thrown by Dynamic
68 /// Nearest Neighbours code
69 /// \endif
70 class DnnError {
71 public:
72  // constructors
73  DnnError() {;};
74  DnnError(const std::string & message_in) {
75  _message = message_in; std::cerr << message_in << std::endl;};
76 
77  std::string message() const {return _message;};
78 
79 private:
80  std::string _message;
81 };
82 
83 
84 /// \if internal_doc
85 /// @ingroup internal
86 /// \class DynamicNearestNeighbours
87 /// Abstract base class for quick location of nearest neighbours in a set of
88 /// points.
89 ///
90 /// Abstract base class for quick location of nearest neighbours in a set of
91 /// points, with facilities for adding and removing points from the
92 /// set after initialisation. Derived classes will be
93 /// named according to the convention DnnSomeName (e.g. DnnPlane).
94 ///
95 /// The main purpose of this abstract base class is to define the
96 /// general interface of a whole set of classes that deal with
97 /// nearest-neighbour location on different 2-d geometries and with
98 /// various underlying data structures and algorithms.
99 ///
100 /// \endif
101 class DynamicNearestNeighbours {
102 
103 public:
104  /// Dummy initialiser --- does nothing!
105  //virtual DynamicNearestNeighbours() {};
106 
107  /// Initialiser --- sets up the necessary structures to allow efficient
108  /// nearest-neighbour finding on the std::vector<EtaPhi> of input points
109  //virtual DynamicNearestNeighbours(const std::vector<EtaPhi> &,
110  // const bool & verbose = false ) = 0;
111 
112  /// Returns the index of the nearest neighbour of point labelled
113  /// by ii (assumes ii is valid)
114  virtual int NearestNeighbourIndex(const int & ii) const = 0;
115 
116  /// Returns the distance to the nearest neighbour of point labelled
117  /// by index ii (assumes ii is valid)
118  virtual double NearestNeighbourDistance(const int & ii) const = 0;
119 
120  /// Returns true iff the given index corresponds to a point that
121  /// exists in the DNN structure (meaning that it has been added, and
122  /// not removed in the meantime)
123  virtual bool Valid(const int & index) const = 0;
124 
125  /// remove the points labelled by the std::vector indices_to_remove, and
126  /// add the points specified by the std::vector points_to_add
127  /// (corresponding indices will be calculated automatically); the
128  /// idea behind this routine is that the points to be added will
129  /// somehow be close to the one or other of the points being removed
130  /// and this can be used by the implementation to provide hints for
131  /// inserting the new points in whatever structure it is using. In a
132  /// kt-algorithm the points being added will be a result of a
133  /// combination of the points to be removed -- hence the proximity
134  /// is (more or less) guaranteed.
135  virtual void RemoveAndAddPoints(const std::vector<int> & indices_to_remove,
136  const std::vector<EtaPhi> & points_to_add,
137  std::vector<int> & indices_added,
138  std::vector<int> & indices_of_updated_neighbours) = 0;
139 
140 
141  /// Remove the point labelled by index and return the list of
142  /// points whose nearest neighbours have changed in the process
143  inline void RemovePoint (const int & index,
144  std::vector<int> & indices_of_updated_neighbours) {
145  std::vector<int> indices_added;
146  std::vector<EtaPhi> points_to_add;
147  std::vector<int> indices_to_remove(1);
148  indices_to_remove[0] = index;
149  RemoveAndAddPoints(indices_to_remove, points_to_add, indices_added,
150  indices_of_updated_neighbours
151  );};
152 
153 
154  /// Removes the two points labelled by index1, index2 and adds in the
155  /// a point with coordinates newpoint; it returns an index for the new
156  /// point (index 3) and a std::vector of indices of neighbours whose
157  /// nearest neighbour has changed (the list includes index3, i.e. the new
158  /// point).
159  inline void RemoveCombinedAddCombination(
160  const int & index1, const int & index2,
161  const EtaPhi & newpoint,
162  int & index3,
163  std::vector<int> & indices_of_updated_neighbours) {
164  std::vector<int> indices_added(1);
165  std::vector<EtaPhi> points_to_add(1);
166  std::vector<int> indices_to_remove(2);
167  indices_to_remove[0] = index1;
168  indices_to_remove[1] = index2;
169  points_to_add[0] = newpoint;
170  RemoveAndAddPoints(indices_to_remove, points_to_add, indices_added,
171  indices_of_updated_neighbours
172  );
173  index3 = indices_added[0];
174  };
175 
176  /// destructor -- here it is now implemented
177  virtual ~DynamicNearestNeighbours () {}
178 };
179 
180 
181 FASTJET_END_NAMESPACE
182 
183 #endif // __FASTJET_DYNAMICNEARESTNEIGHBOURS_HH__
Shortcut for dealing with eta-phi coordinates.
void sanitize()
put things into the desired range.