FastJet  3.1.0-beta.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
MinHeap.hh
1 //FJSTARTHEADER
2 // $Id: MinHeap.hh 3433 2014-07-23 08:17:03Z salam $
3 //
4 // Copyright (c) 2005-2014, 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. They are described in the original FastJet paper,
16 // hep-ph/0512210 and in the manual, arXiv:1111.6097. If you use
17 // FastJet as part of work towards a scientific publication, please
18 // quote the version you use and include a citation to the manual and
19 // optionally also to hep-ph/0512210.
20 //
21 // FastJet is distributed in the hope that it will be useful,
22 // but WITHOUT ANY WARRANTY; without even the implied warranty of
23 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 // GNU General Public License for more details.
25 //
26 // You should have received a copy of the GNU General Public License
27 // along with FastJet. If not, see <http://www.gnu.org/licenses/>.
28 //----------------------------------------------------------------------
29 //FJENDHEADER
30 
31 #ifndef __FASTJET_MINHEAP__HH__
32 #define __FASTJET_MINHEAP__HH__
33 
34 #include<vector>
35 #include<cassert>
36 #include<memory>
37 #include<limits>
38 #include "fastjet/internal/base.hh"
39 
40 FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh
41 
42 //======================================================================
43 /// \if internal_doc
44 /// @ingroup internal
45 /// \class MinHeap
46 /// A class which provides a "heap"-like structure that allows
47 /// access to a the minimal value of a dynamically changing set of numbers
48 /// \endif
49 class MinHeap {
50 public:
51  /// construct a MinHeap from the vector of values, allowing future
52  /// expansion to a maximum size max_size;
53  MinHeap (const std::vector<double> & values, unsigned int max_size) :
54  _heap(max_size) {initialise(values);}
55 
56  /// do the minimal setup for a MinHeap that can reach max_size;
57  /// initialisation must be performed later with the actual values.
58  MinHeap (unsigned int max_size) : _heap(max_size) {}
59 
60  /// constructor in which the the maximum size is the size of the values array
61  MinHeap (const std::vector<double> & values) :
62  _heap(values.size()) {initialise(values);}
63 
64  /// initialise the heap with the supplied values. Should only be called if
65  /// the constructor did not supply values.
66  void initialise(const std::vector<double> & values);
67 
68  /// return the location of the minimal value on the heap
69  inline unsigned int minloc() const {
70  return (_heap[0].minloc) - &(_heap[0]);}
71 
72  /// return the minimal value on the heap
73  inline double minval() const {return _heap[0].minloc->value;}
74 
75  inline double operator[](int i) const {return _heap[i].value;}
76 
77  /// remove the value at the specified location (i.e. replace it with
78  /// the largest possible value).
79  void remove(unsigned int loc) {
80  update(loc,std::numeric_limits<double>::max());};
81 
82  /// update the value at the specified location
83  void update(unsigned int, double);
84 
85 private:
86 
87  struct ValueLoc{
88  double value;
89  ValueLoc * minloc;
90  };
91 
92  std::vector<ValueLoc> _heap;
93 
94 
95 
96 };
97 
98 
99 FASTJET_END_NAMESPACE
100 
101 #endif // __FASTJET_MINHEAP__HH__