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__ |
---|