fastjet::MinHeap Class Reference

A class which provides a "heap"-like structure that allows access to a the minimal value of a dynamically changing set of numbers. More...

#include <MinHeap.hh>

List of all members.

Public Member Functions

 MinHeap (const std::vector< double > &values, unsigned int max_size)
 construct a MinHeap from the vector of values, allowing future expansion to a maximum size max_size;
 MinHeap (const std::vector< double > &values)
 constructor in which the the maximum size is the size of the values array
unsigned int minloc () const
 return the location of the minimal value on the heap
double minval () const
 return the minimal value on the heap
double operator[] (int i) const
void remove (unsigned int loc)
 remove the value at the specified location (i.e.
void update (unsigned int, double)
 update the value at the specified location

Private Member Functions

void _initialise (const std::vector< double > &values)
 construct the MinHeap; structure will be as follows:

Private Attributes

std::vector< ValueLoc_heap

Classes

struct  ValueLoc


Detailed Description

A class which provides a "heap"-like structure that allows access to a the minimal value of a dynamically changing set of numbers.

Definition at line 45 of file MinHeap.hh.


Constructor & Destructor Documentation

fastjet::MinHeap::MinHeap ( const std::vector< double > &  values,
unsigned int  max_size 
) [inline]

construct a MinHeap from the vector of values, allowing future expansion to a maximum size max_size;

Definition at line 49 of file MinHeap.hh.

00049                                                                     :
00050     _heap(max_size) {_initialise(values);};

fastjet::MinHeap::MinHeap ( const std::vector< double > &  values  )  [inline]

constructor in which the the maximum size is the size of the values array

Definition at line 53 of file MinHeap.hh.

00053                                              :
00054     _heap(values.size()) {_initialise(values);};
  


Member Function Documentation

unsigned int fastjet::MinHeap::minloc (  )  const [inline]

return the location of the minimal value on the heap

Definition at line 57 of file MinHeap.hh.

Referenced by fastjet::ClusterSequence::_minheap_faster_tiled_N2_cluster(), and update().

00057                                      {
00058     return (_heap[0].minloc) - &(_heap[0]);};

double fastjet::MinHeap::minval (  )  const [inline]

return the minimal value on the heap

Definition at line 61 of file MinHeap.hh.

Referenced by fastjet::ClusterSequence::_minheap_faster_tiled_N2_cluster().

00061 {return _heap[0].minloc->value;};

double fastjet::MinHeap::operator[] ( int  i  )  const [inline]

Definition at line 63 of file MinHeap.hh.

00063 {return _heap[i].value;};

void fastjet::MinHeap::remove ( unsigned int  loc  )  [inline]

remove the value at the specified location (i.e.

replace it with the largest possible value).

Definition at line 67 of file MinHeap.hh.

Referenced by fastjet::ClusterSequence::_minheap_faster_tiled_N2_cluster().

00067                                 {
00068     update(loc,std::numeric_limits<double>::max());};

void fastjet::MinHeap::update ( unsigned  int,
double   
)

update the value at the specified location

Definition at line 79 of file MinHeap.cc.

References _heap, fastjet::MinHeap::ValueLoc::minloc, minloc(), and fastjet::MinHeap::ValueLoc::value.

00079                                                        {
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 }

void fastjet::MinHeap::_initialise ( const std::vector< double > &  values  )  [private]

construct the MinHeap; structure will be as follows:

_heap[0].minloc points to globally smallest entry _heap[1].minloc points to smallest entry in one half of heap _heap[2].minloc points to smallest entry in other half of heap

. for _heap[i], the "parent" is to be found at (i-1)/2

Definition at line 47 of file MinHeap.cc.

References _heap, fastjet::MinHeap::ValueLoc::minloc, and fastjet::MinHeap::ValueLoc::value.

00047                                                          {
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 }


Member Data Documentation

std::vector<ValueLoc> fastjet::MinHeap::_heap [private]

Definition at line 80 of file MinHeap.hh.

Referenced by _initialise(), and update().


The documentation for this class was generated from the following files:
Generated on Tue Dec 18 17:05:55 2007 for fastjet by  doxygen 1.5.2