FastJet 3.0.2
DynamicNearestNeighbours.hh
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__
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends