Fork me on GitHub

source: git/external/fastjet/MinHeap.cc@ 6049672

Timing
Last change on this file since 6049672 was b7b836a, checked in by Pavel Demin <pavel-demin@…>, 6 years ago

update FastJet library to 3.3.1 and FastJet Contrib library to 1.036

  • Property mode set to 100644
File size: 4.5 KB
Line 
1//FJSTARTHEADER
2// $Id: MinHeap.cc 4354 2018-04-22 07:12:37Z salam $
3//
4// Copyright (c) 2005-2018, 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#include "fastjet/internal/MinHeap.hh"
32#include<iostream>
33#include<cmath>
34#include<limits>
35
36FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh
37
38using namespace std;
39
40//----------------------------------------------------------------------
41/// construct the MinHeap; structure will be as follows:
42/// . _heap[0].minloc points to globally smallest entry
43/// _heap[1].minloc points to smallest entry in one half of heap
44/// _heap[2].minloc points to smallest entry in other half of heap
45///
46/// . for _heap[i], the "parent" is to be found at (i-1)/2
47void MinHeap::initialise(const std::vector<double> & values){
48
49 // fill the high-range of the heap with the largest possible value
50 // (minloc of each entry is itself)
51 for (unsigned i = values.size(); i < _heap.size(); i++) {
52 _heap[i].value = std::numeric_limits<double>::max();
53 _heap[i].minloc = &(_heap[i]);
54 }
55
56 // fill the rest of the heap with the actual values
57 // (minloc of each entry is itself)
58 for (unsigned i = 0; i < values.size(); i++) {
59 _heap[i].value = values[i];
60 _heap[i].minloc = &(_heap[i]);
61 }
62
63 // now adjust the minlocs so that everything is OK...
64 for (unsigned i = _heap.size()-1; i > 0; i--) {
65 ValueLoc * parent = &(_heap[(i-1)/2]);
66 ValueLoc * here = &(_heap[i]);
67 if (here->minloc->value < parent->minloc->value) {
68 parent->minloc = here->minloc;
69 }
70 }
71 //cout << minloc() << " "<<sqrt(minval())<<endl;
72 //cout << sqrt(_heap[47].value)<<endl;
73 //cout << sqrt(_heap[48].value)<<endl;
74 //cout << sqrt(_heap[25].value)<<endl;
75}
76
77
78//----------------------------------------------------------------------
79void MinHeap::update(unsigned int loc, double new_value) {
80
81
82 assert(loc < _heap.size());
83 ValueLoc * start = &(_heap[loc]);
84
85 // if the minloc is somewhere below us and our value is no smaller
86 // than the previous value, we can't possibly change the minloc
87 if (start->minloc != start && !(new_value < start->minloc->value)) {
88 start->value = new_value;
89 //std::cout << " had easy exit\n";
90 return;
91 }
92
93 // update the value and put a temporary location
94 start->value = new_value;
95 start->minloc = start;
96 // warn that a change has been made at this place
97 bool change_made = true;
98 // to make sure we don't go off edge...
99 ValueLoc * heap_end = (&(_heap[0])) + _heap.size();
100
101 // now work our way up the heap
102 while(change_made) {
103 ValueLoc * here = &(_heap[loc]);
104 change_made = false;
105
106 // if we were pointing to start, then we must re-initialise things
107 if (here->minloc == start) {
108 here->minloc = here; change_made = true;
109 }
110
111 // now compare current location to children (at 2*loc+1, 2*loc+2)
112 ValueLoc * child = &(_heap[2*loc+1]);
113 if (child < heap_end && child->minloc->value < here->minloc->value ) {
114 here->minloc = child->minloc;
115 change_made = true;}
116 child++;
117 if (child < heap_end && child->minloc->value < here->minloc->value ) {
118 here->minloc = child->minloc;
119 change_made = true;}
120
121 // then we move up (loc ->(loc-1)/2) if there's anywhere to go
122 if (loc == 0) {break;}
123 loc = (loc-1)/2;
124 }
125
126}
127
128FASTJET_END_NAMESPACE
129
Note: See TracBrowser for help on using the repository browser.