[11] | 1 | //STARTHEADER
|
---|
| 2 | // $Id: DynamicNearestNeighbours.hh,v 1.1 2008-11-06 14:32:09 ovyn Exp $
|
---|
| 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 "Utilities/Fastjet/include/fastjet/internal/numconsts.hh"
|
---|
| 41 |
|
---|
| 42 | FASTJET_BEGIN_NAMESPACE // 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_END_NAMESPACE
|
---|
| 170 |
|
---|
| 171 | #endif // __FASTJET_DYNAMICNEARESTNEIGHBOURS_HH__
|
---|