FastJet 3.0.2
MinHeap.cc
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 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends