FastJet 3.0.2
|
00001 //STARTHEADER 00002 // $Id: MinHeap.hh 2577 2011-09-13 15:11:38Z salam $ 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 #ifndef __FASTJET_MINHEAP__HH__ 00030 #define __FASTJET_MINHEAP__HH__ 00031 00032 #include<vector> 00033 #include<cassert> 00034 #include<memory> 00035 #include<limits> 00036 #include "fastjet/internal/base.hh" 00037 00038 FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh 00039 00040 //====================================================================== 00041 /// \if internal_doc 00042 /// @ingroup internal 00043 /// \class MinHeap 00044 /// A class which provides a "heap"-like structure that allows 00045 /// access to a the minimal value of a dynamically changing set of numbers 00046 /// \endif 00047 class MinHeap { 00048 public: 00049 /// construct a MinHeap from the vector of values, allowing future 00050 /// expansion to a maximum size max_size; 00051 MinHeap (const std::vector<double> & values, unsigned int max_size) : 00052 _heap(max_size) {_initialise(values);}; 00053 00054 /// constructor in which the the maximum size is the size of the values array 00055 MinHeap (const std::vector<double> & values) : 00056 _heap(values.size()) {_initialise(values);}; 00057 00058 /// return the location of the minimal value on the heap 00059 inline unsigned int minloc() const { 00060 return (_heap[0].minloc) - &(_heap[0]);}; 00061 00062 /// return the minimal value on the heap 00063 inline double minval() const {return _heap[0].minloc->value;}; 00064 00065 inline double operator[](int i) const {return _heap[i].value;}; 00066 00067 /// remove the value at the specified location (i.e. replace it with 00068 /// the largest possible value). 00069 void remove(unsigned int loc) { 00070 update(loc,std::numeric_limits<double>::max());}; 00071 00072 /// update the value at the specified location 00073 void update(unsigned int, double); 00074 00075 private: 00076 00077 struct ValueLoc{ 00078 double value; 00079 ValueLoc * minloc; 00080 }; 00081 00082 std::vector<ValueLoc> _heap; 00083 00084 void _initialise(const std::vector<double> & values); 00085 00086 00087 }; 00088 00089 00090 FASTJET_END_NAMESPACE 00091 00092 #endif // __FASTJET_MINHEAP__HH__