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__ |
---|