00001 //STARTHEADER 00002 // $Id: MinHeap.cc 293 2006-08-17 19:38:38Z salam $ 00003 // 00004 // Copyright (c) 2005-2006, Matteo Cacciari and Gavin Salam 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, write to the Free Software 00026 // Foundation, Inc.: 00027 // 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 00028 //---------------------------------------------------------------------- 00029 //ENDHEADER 00030 00031 #include "fastjet/internal/MinHeap.hh" 00032 #include<iostream> 00033 #include<cmath> 00034 #include<limits> 00035 00036 FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh 00037 00038 using namespace std; 00039 00040 //---------------------------------------------------------------------- 00047 void MinHeap::_initialise(const std::vector<double> & values){ 00048 00049 // fill the high-range of the heap with the largest possible value 00050 // (minloc of each entry is itself) 00051 for (unsigned i = values.size(); i < _heap.size(); i++) { 00052 _heap[i].value = std::numeric_limits<double>::max(); 00053 _heap[i].minloc = &(_heap[i]); 00054 } 00055 00056 // fill the rest of the heap with the actual values 00057 // (minloc of each entry is itself) 00058 for (unsigned i = 0; i < values.size(); i++) { 00059 _heap[i].value = values[i]; 00060 _heap[i].minloc = &(_heap[i]); 00061 } 00062 00063 // now adjust the minlocs so that everything is OK... 00064 for (unsigned i = _heap.size()-1; i > 0; i--) { 00065 ValueLoc * parent = &(_heap[(i-1)/2]); 00066 ValueLoc * here = &(_heap[i]); 00067 if (here->minloc->value < parent->minloc->value) { 00068 parent->minloc = here->minloc; 00069 } 00070 } 00071 //cout << minloc() << " "<<sqrt(minval())<<endl; 00072 //cout << sqrt(_heap[47].value)<<endl; 00073 //cout << sqrt(_heap[48].value)<<endl; 00074 //cout << sqrt(_heap[25].value)<<endl; 00075 } 00076 00077 00078 //---------------------------------------------------------------------- 00079 void MinHeap::update(unsigned int loc, double new_value) { 00080 00081 00082 assert(loc < _heap.size()); 00083 ValueLoc * start = &(_heap[loc]); 00084 00085 // if the minloc is somewhere below us and our value is no smaller 00086 // than the previous value, we can't possibly change the minloc 00087 if (start->minloc != start && !(new_value < start->minloc->value)) { 00088 start->value = new_value; 00089 //std::cout << " had easy exit\n"; 00090 return; 00091 } 00092 00093 // update the value and put a temporary location 00094 start->value = new_value; 00095 start->minloc = start; 00096 // warn that a change has been made at this place 00097 bool change_made = true; 00098 // to make sure we don't go off edge... 00099 ValueLoc * heap_end = (&(_heap[0])) + _heap.size(); 00100 00101 // now work our way up the heap 00102 while(change_made) { 00103 ValueLoc * here = &(_heap[loc]); 00104 change_made = false; 00105 00106 // if we were pointing to start, then we must re-initialise things 00107 if (here->minloc == start) { 00108 here->minloc = here; change_made = true; 00109 } 00110 00111 // now compare current location to children (at 2*loc+1, 2*loc+2) 00112 ValueLoc * child = &(_heap[2*loc+1]); 00113 if (child < heap_end && child->minloc->value < here->minloc->value ) { 00114 here->minloc = child->minloc; 00115 change_made = true;} 00116 child++; 00117 if (child < heap_end && child->minloc->value < here->minloc->value ) { 00118 here->minloc = child->minloc; 00119 change_made = true;} 00120 00121 // then we move up (loc ->(loc-1)/2) if there's anywhere to go 00122 if (loc == 0) {break;} 00123 loc = (loc-1)/2; 00124 } 00125 00126 } 00127 00128 FASTJET_END_NAMESPACE 00129