#include <MinHeap.hh>
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 |
Definition at line 45 of file MinHeap.hh.
| 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);};
| 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().
| 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] |
| 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 }
std::vector<ValueLoc> fastjet::MinHeap::_heap [private] |
1.5.2