Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members

MinHeap.hh

Go to the documentation of this file.
00001 //STARTHEADER
00002 // $Id: MinHeap.hh 293 2006-08-17 19:38:38Z salam $
00003 //
00004 // Copyright (c) 2005-2006, Matteo Cacciari and Gavin Salam
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, write to the Free Software
00026 //  Foundation, Inc.:
00027 //      59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00028 //----------------------------------------------------------------------
00029 //ENDHEADER
00030 
00031 #ifndef __FASTJET_MINHEAP__HH__
00032 #define __FASTJET_MINHEAP__HH__
00033 
00034 #include<vector>
00035 #include<cassert>
00036 #include<memory>
00037 #include<limits>
00038 #include "fastjet/internal/base.hh"
00039 
00040 FASTJET_BEGIN_NAMESPACE      // defined in fastjet/internal/base.hh
00041 
00042 //======================================================================
00045 class MinHeap {
00046 public:
00049   MinHeap (const std::vector<double> & values, unsigned int max_size) :
00050     _heap(max_size) {_initialise(values);};
00051 
00053   MinHeap (const std::vector<double> & values) :
00054     _heap(values.size()) {_initialise(values);};
00055   
00057   inline unsigned int minloc() const {
00058     return (_heap[0].minloc) - &(_heap[0]);};
00059   
00061   inline double       minval() const {return _heap[0].minloc->value;};
00062 
00063   inline double operator[](int i) const {return _heap[i].value;};
00064 
00067   void remove(unsigned int loc) {
00068     update(loc,std::numeric_limits<double>::max());};
00069 
00071   void update(unsigned int, double);
00072 
00073 private:
00074 
00075   struct ValueLoc{
00076     double value;
00077     ValueLoc * minloc;
00078   };
00079       
00080   std::vector<ValueLoc> _heap;
00081 
00082   void _initialise(const std::vector<double> & values);
00083 
00084 
00085 };
00086 
00087 
00088 FASTJET_END_NAMESPACE
00089 
00090 #endif // __FASTJET_MINHEAP__HH__

Generated on Mon Apr 2 20:57:48 2007 for fastjet by  doxygen 1.4.2