FastJet 3.0.2
|
00001 //STARTHEADER 00002 // $Id: MinHeap.cc 2577 2011-09-13 15:11:38Z salam $ 00003 // 00004 // Copyright (c) 2005-2011, Matteo Cacciari, Gavin P. Salam and Gregory Soyez 00005 // 00006 //---------------------------------------------------------------------- 00007 // This file is part of FastJet. 00008 // 00009 // FastJet is free software; you can redistribute it and/or modify 00010 // it under the terms of the GNU General Public License as published by 00011 // the Free Software Foundation; either version 2 of the License, or 00012 // (at your option) any later version. 00013 // 00014 // The algorithms that underlie FastJet have required considerable 00015 // development and are described in hep-ph/0512210. If you use 00016 // FastJet as part of work towards a scientific publication, please 00017 // include a citation to the FastJet paper. 00018 // 00019 // FastJet is distributed in the hope that it will be useful, 00020 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00021 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00022 // GNU General Public License for more details. 00023 // 00024 // You should have received a copy of the GNU General Public License 00025 // along with FastJet. If not, see <http://www.gnu.org/licenses/>. 00026 //---------------------------------------------------------------------- 00027 //ENDHEADER 00028 00029 #include "fastjet/internal/MinHeap.hh" 00030 #include<iostream> 00031 #include<cmath> 00032 #include<limits> 00033 00034 FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh 00035 00036 using namespace std; 00037 00038 //---------------------------------------------------------------------- 00039 /// construct the MinHeap; structure will be as follows: 00040 /// . _heap[0].minloc points to globally smallest entry 00041 /// _heap[1].minloc points to smallest entry in one half of heap 00042 /// _heap[2].minloc points to smallest entry in other half of heap 00043 /// 00044 /// . for _heap[i], the "parent" is to be found at (i-1)/2 00045 void MinHeap::_initialise(const std::vector<double> & values){ 00046 00047 // fill the high-range of the heap with the largest possible value 00048 // (minloc of each entry is itself) 00049 for (unsigned i = values.size(); i < _heap.size(); i++) { 00050 _heap[i].value = std::numeric_limits<double>::max(); 00051 _heap[i].minloc = &(_heap[i]); 00052 } 00053 00054 // fill the rest of the heap with the actual values 00055 // (minloc of each entry is itself) 00056 for (unsigned i = 0; i < values.size(); i++) { 00057 _heap[i].value = values[i]; 00058 _heap[i].minloc = &(_heap[i]); 00059 } 00060 00061 // now adjust the minlocs so that everything is OK... 00062 for (unsigned i = _heap.size()-1; i > 0; i--) { 00063 ValueLoc * parent = &(_heap[(i-1)/2]); 00064 ValueLoc * here = &(_heap[i]); 00065 if (here->minloc->value < parent->minloc->value) { 00066 parent->minloc = here->minloc; 00067 } 00068 } 00069 //cout << minloc() << " "<<sqrt(minval())<<endl; 00070 //cout << sqrt(_heap[47].value)<<endl; 00071 //cout << sqrt(_heap[48].value)<<endl; 00072 //cout << sqrt(_heap[25].value)<<endl; 00073 } 00074 00075 00076 //---------------------------------------------------------------------- 00077 void MinHeap::update(unsigned int loc, double new_value) { 00078 00079 00080 assert(loc < _heap.size()); 00081 ValueLoc * start = &(_heap[loc]); 00082 00083 // if the minloc is somewhere below us and our value is no smaller 00084 // than the previous value, we can't possibly change the minloc 00085 if (start->minloc != start && !(new_value < start->minloc->value)) { 00086 start->value = new_value; 00087 //std::cout << " had easy exit\n"; 00088 return; 00089 } 00090 00091 // update the value and put a temporary location 00092 start->value = new_value; 00093 start->minloc = start; 00094 // warn that a change has been made at this place 00095 bool change_made = true; 00096 // to make sure we don't go off edge... 00097 ValueLoc * heap_end = (&(_heap[0])) + _heap.size(); 00098 00099 // now work our way up the heap 00100 while(change_made) { 00101 ValueLoc * here = &(_heap[loc]); 00102 change_made = false; 00103 00104 // if we were pointing to start, then we must re-initialise things 00105 if (here->minloc == start) { 00106 here->minloc = here; change_made = true; 00107 } 00108 00109 // now compare current location to children (at 2*loc+1, 2*loc+2) 00110 ValueLoc * child = &(_heap[2*loc+1]); 00111 if (child < heap_end && child->minloc->value < here->minloc->value ) { 00112 here->minloc = child->minloc; 00113 change_made = true;} 00114 child++; 00115 if (child < heap_end && child->minloc->value < here->minloc->value ) { 00116 here->minloc = child->minloc; 00117 change_made = true;} 00118 00119 // then we move up (loc ->(loc-1)/2) if there's anywhere to go 00120 if (loc == 0) {break;} 00121 loc = (loc-1)/2; 00122 } 00123 00124 } 00125 00126 FASTJET_END_NAMESPACE 00127