MinHeap.cc

Go to the documentation of this file.
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 

Generated on Tue Dec 18 17:05:03 2007 for fastjet by  doxygen 1.5.2