Fork me on GitHub

source: svn/trunk/external/fastjet/internal/MinHeap.hh@ 1204

Last change on this file since 1204 was 859, checked in by Pavel Demin, 12 years ago

update fastjet to version 3.0.3

File size: 3.0 KB
Line 
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
38FASTJET_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
47class MinHeap {
48public:
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
75private:
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
90FASTJET_END_NAMESPACE
91
92#endif // __FASTJET_MINHEAP__HH__
Note: See TracBrowser for help on using the repository browser.