]>
Commit | Line | Data |
---|---|---|
370be031 | 1 | //STARTHEADER |
2 | // $Id: DynamicNearestNeighbours.hh 293 2006-08-17 19:38:38Z salam $ | |
3 | // | |
4 | // Copyright (c) 2005-2006, Matteo Cacciari and Gavin Salam | |
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, write to the Free Software | |
26 | // Foundation, Inc.: | |
27 | // 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
28 | //---------------------------------------------------------------------- | |
29 | //ENDHEADER | |
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 | ||
42 | namespace fastjet { // defined in fastjet/internal/base.hh | |
43 | ||
44 | /// Shortcut for dealing with eta-phi coordinates. | |
45 | //typedef std::pair<double,double> EtaPhi; | |
46 | ||
47 | /// use a class instead of a pair so that phi can be sanitized | |
48 | /// and put into proper range on initialization. | |
49 | class EtaPhi { | |
50 | public: | |
51 | double first, second; | |
52 | EtaPhi() {} | |
53 | EtaPhi(double a, double b) {first = a; second = b;} | |
54 | /// put things into the desired range. | |
55 | void sanitize() { | |
56 | if (second < 0) second += twopi; | |
57 | if (second >= twopi) second -= twopi; | |
58 | } | |
59 | ||
60 | }; | |
61 | ||
62 | /// class corresponding to errors that will be thrown by Dynamic | |
63 | /// Nearest Neighbours code | |
64 | class DnnError { | |
65 | public: | |
66 | // constructors | |
67 | DnnError() {;}; | |
68 | DnnError(const std::string & message) { | |
69 | _message = message; std::cerr << message << std::endl;}; | |
70 | ||
71 | std::string message() const {return _message;}; | |
72 | ||
73 | private: | |
74 | std::string _message; | |
75 | }; | |
76 | ||
77 | ||
78 | /// | |
79 | /// Abstract base class for quick location of nearest neighbours in a set of | |
80 | /// points, with facilities for adding and removing points from the | |
81 | /// set after initialisation. Derived classes will be | |
82 | /// named according to the convention DnnSomeName (e.g. DnnPlane). | |
83 | /// | |
84 | /// The main purpose of this abstract base class is to define the | |
85 | /// general interface of a whole set of classes that deal with | |
86 | /// nearest-neighbour location on different 2-d geometries and with | |
87 | /// various underlying data structures and algorithms. | |
88 | /// | |
89 | class DynamicNearestNeighbours { | |
90 | ||
91 | public: | |
92 | /// Dummy initialiser --- does nothing! | |
93 | //virtual DynamicNearestNeighbours() {}; | |
94 | ||
95 | /// Initialiser --- sets up the necessary structures to allow efficient | |
96 | /// nearest-neighbour finding on the std::vector<EtaPhi> of input points | |
97 | //virtual DynamicNearestNeighbours(const std::vector<EtaPhi> &, | |
98 | // const bool & verbose = false ) = 0; | |
99 | ||
100 | /// Returns the index of the nearest neighbour of point labelled | |
101 | /// by ii (assumes ii is valid) | |
102 | virtual int NearestNeighbourIndex(const int & ii) const = 0; | |
103 | ||
104 | /// Returns the distance to the nearest neighbour of point labelled | |
105 | /// by index ii (assumes ii is valid) | |
106 | virtual double NearestNeighbourDistance(const int & ii) const = 0; | |
107 | ||
108 | /// Returns true iff the given index corresponds to a point that | |
109 | /// exists in the DNN structure (meaning that it has been added, and | |
110 | /// not removed in the meantime) | |
111 | virtual bool Valid(const int & index) const = 0; | |
112 | ||
113 | /// remove the points labelled by the std::vector indices_to_remove, and | |
114 | /// add the points specified by the std::vector points_to_add | |
115 | /// (corresponding indices will be calculated automatically); the | |
116 | /// idea behind this routine is that the points to be added will | |
117 | /// somehow be close to the one or other of the points being removed | |
118 | /// and this can be used by the implementation to provide hints for | |
119 | /// inserting the new points in whatever structure it is using. In a | |
120 | /// kt-algorithm the points being added will be a result of a | |
121 | /// combination of the points to be removed -- hence the proximity | |
122 | /// is (more or less) guaranteed. | |
123 | virtual void RemoveAndAddPoints(const std::vector<int> & indices_to_remove, | |
124 | const std::vector<EtaPhi> & points_to_add, | |
125 | std::vector<int> & indices_added, | |
126 | std::vector<int> & indices_of_updated_neighbours) = 0; | |
127 | ||
128 | ||
129 | /// Remove the point labelled by index and return the list of | |
130 | /// points whose nearest neighbours have changed in the process | |
131 | inline void RemovePoint (const int & index, | |
132 | std::vector<int> & indices_of_updated_neighbours) { | |
133 | std::vector<int> indices_added; | |
134 | std::vector<EtaPhi> points_to_add; | |
135 | std::vector<int> indices_to_remove(1); | |
136 | indices_to_remove[0] = index; | |
137 | RemoveAndAddPoints(indices_to_remove, points_to_add, indices_added, | |
138 | indices_of_updated_neighbours | |
139 | );}; | |
140 | ||
141 | ||
142 | /// Removes the two points labelled by index1, index2 and adds in the | |
143 | /// a point with coordinates newpoint; it returns an index for the new | |
144 | /// point (index 3) and a std::vector of indices of neighbours whose | |
145 | /// nearest neighbour has changed (the list includes index3, i.e. the new | |
146 | /// point). | |
147 | inline void RemoveCombinedAddCombination( | |
148 | const int & index1, const int & index2, | |
149 | const EtaPhi & newpoint, | |
150 | int & index3, | |
151 | std::vector<int> & indices_of_updated_neighbours) { | |
152 | std::vector<int> indices_added(1); | |
153 | std::vector<EtaPhi> points_to_add(1); | |
154 | std::vector<int> indices_to_remove(2); | |
155 | indices_to_remove[0] = index1; | |
156 | indices_to_remove[1] = index2; | |
157 | points_to_add[0] = newpoint; | |
158 | RemoveAndAddPoints(indices_to_remove, points_to_add, indices_added, | |
159 | indices_of_updated_neighbours | |
160 | ); | |
161 | index3 = indices_added[0]; | |
162 | }; | |
163 | ||
164 | /// destructor -- here it is now implemented | |
165 | virtual ~DynamicNearestNeighbours () {} | |
166 | }; | |
167 | ||
168 | ||
169 | } // fastjet namespace | |
170 | ||
171 | #endif // __FASTJET_DYNAMICNEARESTNEIGHBOURS_HH__ |