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