FastJet  3.0.3
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
MinHeap.hh
1 //STARTHEADER
2 // $Id: MinHeap.hh 2577 2011-09-13 15:11:38Z salam $
3 //
4 // Copyright (c) 2005-2011, Matteo Cacciari, Gavin P. Salam and Gregory Soyez
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, see <http://www.gnu.org/licenses/>.
26 //----------------------------------------------------------------------
27 //ENDHEADER
28 
29 #ifndef __FASTJET_MINHEAP__HH__
30 #define __FASTJET_MINHEAP__HH__
31 
32 #include<vector>
33 #include<cassert>
34 #include<memory>
35 #include<limits>
36 #include "fastjet/internal/base.hh"
37 
38 FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh
39 
40 //======================================================================
41 /// \if internal_doc
42 /// @ingroup internal
43 /// \class MinHeap
44 /// A class which provides a "heap"-like structure that allows
45 /// access to a the minimal value of a dynamically changing set of numbers
46 /// \endif
47 class MinHeap {
48 public:
49  /// construct a MinHeap from the vector of values, allowing future
50  /// expansion to a maximum size max_size;
51  MinHeap (const std::vector<double> & values, unsigned int max_size) :
52  _heap(max_size) {_initialise(values);};
53 
54  /// constructor in which the the maximum size is the size of the values array
55  MinHeap (const std::vector<double> & values) :
56  _heap(values.size()) {_initialise(values);};
57 
58  /// return the location of the minimal value on the heap
59  inline unsigned int minloc() const {
60  return (_heap[0].minloc) - &(_heap[0]);};
61 
62  /// return the minimal value on the heap
63  inline double minval() const {return _heap[0].minloc->value;};
64 
65  inline double operator[](int i) const {return _heap[i].value;};
66 
67  /// remove the value at the specified location (i.e. replace it with
68  /// the largest possible value).
69  void remove(unsigned int loc) {
70  update(loc,std::numeric_limits<double>::max());};
71 
72  /// update the value at the specified location
73  void update(unsigned int, double);
74 
75 private:
76 
77  struct ValueLoc{
78  double value;
79  ValueLoc * minloc;
80  };
81 
82  std::vector<ValueLoc> _heap;
83 
84  void _initialise(const std::vector<double> & values);
85 
86 
87 };
88 
89 
90 FASTJET_END_NAMESPACE
91 
92 #endif // __FASTJET_MINHEAP__HH__