FastJet 3.0.2
|
00001 //STARTHEADER 00002 // $Id: DynamicNearestNeighbours.hh 2687 2011-11-14 11:17:51Z soyez $ 00003 // 00004 // Copyright (c) 2005-2011, Matteo Cacciari, Gavin P. Salam and Gregory Soyez 00005 // 00006 //---------------------------------------------------------------------- 00007 // This file is part of FastJet. 00008 // 00009 // FastJet is free software; you can redistribute it and/or modify 00010 // it under the terms of the GNU General Public License as published by 00011 // the Free Software Foundation; either version 2 of the License, or 00012 // (at your option) any later version. 00013 // 00014 // The algorithms that underlie FastJet have required considerable 00015 // development and are described in hep-ph/0512210. If you use 00016 // FastJet as part of work towards a scientific publication, please 00017 // include a citation to the FastJet paper. 00018 // 00019 // FastJet is distributed in the hope that it will be useful, 00020 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00021 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00022 // GNU General Public License for more details. 00023 // 00024 // You should have received a copy of the GNU General Public License 00025 // along with FastJet. If not, see <http://www.gnu.org/licenses/>. 00026 //---------------------------------------------------------------------- 00027 //ENDHEADER 00028 00029 00030 #ifndef __FASTJET_DYNAMICNEARESTNEIGHBOURS_HH__ 00031 #define __FASTJET_DYNAMICNEARESTNEIGHBOURS_HH__ 00032 00033 #include<vector> 00034 #include<string> 00035 #include<iostream> 00036 #include<sstream> 00037 #include<cassert> 00038 #include "fastjet/internal/numconsts.hh" 00039 00040 FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh 00041 00042 /// Shortcut for dealing with eta-phi coordinates. 00043 //typedef std::pair<double,double> EtaPhi; 00044 00045 /// \if internal_doc 00046 /// @ingroup internal 00047 /// \class EtaPhi 00048 /// use a class instead of a pair so that phi can be sanitized 00049 /// and put into proper range on initialization. 00050 /// \endif 00051 class EtaPhi { 00052 public: 00053 double first, second; 00054 EtaPhi() {} 00055 EtaPhi(double a, double b) {first = a; second = b;} 00056 /// put things into the desired range. 00057 void sanitize() { 00058 if (second < 0) second += twopi; 00059 if (second >= twopi) second -= twopi; 00060 } 00061 00062 }; 00063 00064 /// \if internal_doc 00065 /// @ingroup internal 00066 /// \class DnnError 00067 /// class corresponding to errors that will be thrown by Dynamic 00068 /// Nearest Neighbours code 00069 /// \endif 00070 class DnnError { 00071 public: 00072 // constructors 00073 DnnError() {;}; 00074 DnnError(const std::string & message_in) { 00075 _message = message_in; std::cerr << message_in << std::endl;}; 00076 00077 std::string message() const {return _message;}; 00078 00079 private: 00080 std::string _message; 00081 }; 00082 00083 00084 /// \if internal_doc 00085 /// @ingroup internal 00086 /// \class DynamicNearestNeighbours 00087 /// Abstract base class for quick location of nearest neighbours in a set of 00088 /// points. 00089 /// 00090 /// Abstract base class for quick location of nearest neighbours in a set of 00091 /// points, with facilities for adding and removing points from the 00092 /// set after initialisation. Derived classes will be 00093 /// named according to the convention DnnSomeName (e.g. DnnPlane). 00094 /// 00095 /// The main purpose of this abstract base class is to define the 00096 /// general interface of a whole set of classes that deal with 00097 /// nearest-neighbour location on different 2-d geometries and with 00098 /// various underlying data structures and algorithms. 00099 /// 00100 /// \endif 00101 class DynamicNearestNeighbours { 00102 00103 public: 00104 /// Dummy initialiser --- does nothing! 00105 //virtual DynamicNearestNeighbours() {}; 00106 00107 /// Initialiser --- sets up the necessary structures to allow efficient 00108 /// nearest-neighbour finding on the std::vector<EtaPhi> of input points 00109 //virtual DynamicNearestNeighbours(const std::vector<EtaPhi> &, 00110 // const bool & verbose = false ) = 0; 00111 00112 /// Returns the index of the nearest neighbour of point labelled 00113 /// by ii (assumes ii is valid) 00114 virtual int NearestNeighbourIndex(const int & ii) const = 0; 00115 00116 /// Returns the distance to the nearest neighbour of point labelled 00117 /// by index ii (assumes ii is valid) 00118 virtual double NearestNeighbourDistance(const int & ii) const = 0; 00119 00120 /// Returns true iff the given index corresponds to a point that 00121 /// exists in the DNN structure (meaning that it has been added, and 00122 /// not removed in the meantime) 00123 virtual bool Valid(const int & index) const = 0; 00124 00125 /// remove the points labelled by the std::vector indices_to_remove, and 00126 /// add the points specified by the std::vector points_to_add 00127 /// (corresponding indices will be calculated automatically); the 00128 /// idea behind this routine is that the points to be added will 00129 /// somehow be close to the one or other of the points being removed 00130 /// and this can be used by the implementation to provide hints for 00131 /// inserting the new points in whatever structure it is using. In a 00132 /// kt-algorithm the points being added will be a result of a 00133 /// combination of the points to be removed -- hence the proximity 00134 /// is (more or less) guaranteed. 00135 virtual void RemoveAndAddPoints(const std::vector<int> & indices_to_remove, 00136 const std::vector<EtaPhi> & points_to_add, 00137 std::vector<int> & indices_added, 00138 std::vector<int> & indices_of_updated_neighbours) = 0; 00139 00140 00141 /// Remove the point labelled by index and return the list of 00142 /// points whose nearest neighbours have changed in the process 00143 inline void RemovePoint (const int & index, 00144 std::vector<int> & indices_of_updated_neighbours) { 00145 std::vector<int> indices_added; 00146 std::vector<EtaPhi> points_to_add; 00147 std::vector<int> indices_to_remove(1); 00148 indices_to_remove[0] = index; 00149 RemoveAndAddPoints(indices_to_remove, points_to_add, indices_added, 00150 indices_of_updated_neighbours 00151 );}; 00152 00153 00154 /// Removes the two points labelled by index1, index2 and adds in the 00155 /// a point with coordinates newpoint; it returns an index for the new 00156 /// point (index 3) and a std::vector of indices of neighbours whose 00157 /// nearest neighbour has changed (the list includes index3, i.e. the new 00158 /// point). 00159 inline void RemoveCombinedAddCombination( 00160 const int & index1, const int & index2, 00161 const EtaPhi & newpoint, 00162 int & index3, 00163 std::vector<int> & indices_of_updated_neighbours) { 00164 std::vector<int> indices_added(1); 00165 std::vector<EtaPhi> points_to_add(1); 00166 std::vector<int> indices_to_remove(2); 00167 indices_to_remove[0] = index1; 00168 indices_to_remove[1] = index2; 00169 points_to_add[0] = newpoint; 00170 RemoveAndAddPoints(indices_to_remove, points_to_add, indices_added, 00171 indices_of_updated_neighbours 00172 ); 00173 index3 = indices_added[0]; 00174 }; 00175 00176 /// destructor -- here it is now implemented 00177 virtual ~DynamicNearestNeighbours () {} 00178 }; 00179 00180 00181 FASTJET_END_NAMESPACE 00182 00183 #endif // __FASTJET_DYNAMICNEARESTNEIGHBOURS_HH__