fastjet/internal/MinHeap.hh

0001 //FJSTARTHEADER
0002 // $Id$
0003 //
0004 // Copyright (c) 2005-2021, Matteo Cacciari, Gavin P. Salam and Gregory Soyez
0005 //
0006 //----------------------------------------------------------------------
0007 // This file is part of FastJet.
0008 //
0009 //  FastJet is free software; you can redistribute it and/or modify
0010 //  it under the terms of the GNU General Public License as published by
0011 //  the Free Software Foundation; either version 2 of the License, or
0012 //  (at your option) any later version.
0013 //
0014 //  The algorithms that underlie FastJet have required considerable
0015 //  development. They are described in the original FastJet paper,
0016 //  hep-ph/0512210 and in the manual, arXiv:1111.6097. If you use
0017 //  FastJet as part of work towards a scientific publication, please
0018 //  quote the version you use and include a citation to the manual and
0019 //  optionally also to hep-ph/0512210.
0020 //
0021 //  FastJet is distributed in the hope that it will be useful,
0022 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
0023 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0024 //  GNU General Public License for more details.
0025 //
0026 //  You should have received a copy of the GNU General Public License
0027 //  along with FastJet. If not, see <http://www.gnu.org/licenses/>.
0028 //----------------------------------------------------------------------
0029 //FJENDHEADER
0030
0031 #ifndef __FASTJET_MINHEAP__HH__
0032 #define __FASTJET_MINHEAP__HH__
0033
0034 #include<vector>
0035 #include<cassert>
0036 #include<memory>
0037 #include<limits>
0038 #include "fastjet/internal/base.hh"
0039
0040 FASTJET_BEGIN_NAMESPACE      // defined in fastjet/internal/base.hh
0041
0042 //======================================================================
0043 /// \if internal_doc
0044 /// @ingroup internal
0045 /// \class MinHeap
0046 /// A class which provides a "heap"-like structure that allows
0047 /// access to a the minimal value of a dynamically changing set of numbers
0048 /// \endif
0049 class MinHeap {
0050 public:
0051   /// construct a MinHeap from the vector of values, allowing future
0052   /// expansion to a maximum size max_size;
0053   MinHeap (const std::vector<double> & values, unsigned int max_size) :
0054     _heap(max_size) {initialise(values);}
0055
0056   /// do the minimal setup for a MinHeap that can reach max_size;
0057   /// initialisation must be performed later with the actual values.
0058   MinHeap (unsigned int max_size) : _heap(max_size) {}
0059
0060   /// constructor in which the the maximum size is the size of the values array
0061   MinHeap (const std::vector<double> & values) :
0062     _heap(values.size()) {initialise(values);}
0063
0064   /// initialise the heap with the supplied values. Should only be called if
0065   /// the constructor did not supply values.
0066   void initialise(const std::vector<double> & values);
0067
0068   /// return the location of the minimal value on the heap
0069   inline unsigned int minloc() const {
0070     return (_heap[0].minloc) - &(_heap[0]);}
0071
0072   /// return the minimal value on the heap
0073   inline double       minval() const {return _heap[0].minloc->value;}
0074
0075   inline double operator[](int i) const {return _heap[i].value;}
0076
0077   /// remove the value at the specified location (i.e. replace it with
0078   /// the largest possible value).
0079   void remove(unsigned int loc) {
0080     update(loc,std::numeric_limits<double>::max());};
0081
0082   /// update the value at the specified location
0083   void update(unsigned int, double);
0084
0085 private:
0086
0087   struct ValueLoc{
0088     double value;
0089     ValueLoc * minloc;
0090   };
0091
0092   std::vector<ValueLoc> _heap;
0093
0094
0095
0096 };
0097
0098
0099 FASTJET_END_NAMESPACE
0100
0101 #endif // __FASTJET_MINHEAP__HH__