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