]>
Commit | Line | Data |
---|---|---|
370be031 | 1 | //STARTHEADER |
2 | // $Id: MinHeap.hh 293 2006-08-17 19:38:38Z salam $ | |
3 | // | |
4 | // Copyright (c) 2005-2006, Matteo Cacciari and Gavin Salam | |
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, write to the Free Software | |
26 | // Foundation, Inc.: | |
27 | // 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
28 | //---------------------------------------------------------------------- | |
29 | //ENDHEADER | |
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 | namespace fastjet { // defined in fastjet/internal/base.hh | |
41 | ||
42 | //====================================================================== | |
43 | /// A class which provides a "heap"-like structure that allows | |
44 | /// access to a the minimal value of a dynamically changing set of numbers | |
45 | class MinHeap { | |
46 | public: | |
47 | /// construct a MinHeap from the vector of values, allowing future | |
48 | /// expansion to a maximum size max_size; | |
49 | MinHeap (const std::vector<double> & values, unsigned int max_size) : | |
50 | _heap(max_size) {_initialise(values);}; | |
51 | ||
52 | /// constructor in which the the maximum size is the size of the values array | |
53 | MinHeap (const std::vector<double> & values) : | |
54 | _heap(values.size()) {_initialise(values);}; | |
55 | ||
56 | /// return the location of the minimal value on the heap | |
57 | inline unsigned int minloc() const { | |
58 | return (_heap[0].minloc) - &(_heap[0]);}; | |
59 | ||
60 | /// return the minimal value on the heap | |
61 | inline double minval() const {return _heap[0].minloc->value;}; | |
62 | ||
63 | inline double operator[](int i) const {return _heap[i].value;}; | |
64 | ||
65 | /// remove the value at the specified location (i.e. replace it with | |
66 | /// the largest possible value). | |
67 | void remove(unsigned int loc) { | |
68 | update(loc,std::numeric_limits<double>::max());}; | |
69 | ||
70 | /// update the value at the specified location | |
71 | void update(unsigned int, double); | |
72 | ||
73 | private: | |
74 | ||
75 | struct ValueLoc{ | |
76 | double value; | |
77 | ValueLoc * minloc; | |
78 | }; | |
79 | ||
80 | std::vector<ValueLoc> _heap; | |
81 | ||
82 | void _initialise(const std::vector<double> & values); | |
83 | ||
84 | ||
85 | }; | |
86 | ||
87 | ||
88 | } // fastjet namespace | |
89 | ||
90 | #endif // __FASTJET_MINHEAP__HH__ |