JETAN/fastjet/fastjet/internal/DynamicNearestNeighbours.hh

   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__