FastJet  3.2.0
MinHeap.cc
1 //FJSTARTHEADER
2 // $Id: MinHeap.cc 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 #include "fastjet/internal/MinHeap.hh"
32 #include<iostream>
33 #include<cmath>
34 #include<limits>
35 
36 FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh
37 
38 using 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
47 void 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 //----------------------------------------------------------------------
79 void 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 
128 FASTJET_END_NAMESPACE
129