37 #ifndef REPLACEMENT_HEAPBLOCK_H    38 #define REPLACEMENT_HEAPBLOCK_H    46 #define RBHEAP_DEBUG if(0)    62     return s << 
"[" << p.
value << 
"]";
    80 template<
class T,
class Compare> 
    94   void heapify(
size_t i);
   110   void deleteRun(
size_t i);
   130         s << 
"ReplacementheapBlock " << 
this << 
": " << size << 
" runs";
   134         for(
size_t i=0; i<size; i++) {
   135       s << endl << 
"  <-  i=" << i<< 
": " <<  mergeHeap[i].
run;
   137       mergeHeap[i].
run->name(&runname);
   138       runlen = mergeHeap[i].
run->stream_len();
   139       s << 
", " << runname << 
", len=" << runlen; 
   154 template<
class T,
class Compare>
   160   arity = runList->length();
   166   for (
unsigned int i=0; i< arity; i++) {
   169     runList->dequeue(&str);
   178 template<
class T,
class Compare>
   182     cerr << 
"warning: ~ReplacementHeapBlock: heap not empty!\n";
   185   for(
size_t i=0; i<size; i++) {
   186     if (mergeHeap[i].
run) 
   187       delete mergeHeap[i].run;
   197 template<
class T,
class Compare>
   204     cerr << 
"ReplacementHeapBlockBlock::addRun size =" << size << 
",arity=" << arity 
   205          << 
" full, cannot add another run.\n";
   211   mergeHeap[size].run = 
r;
   217     cerr << 
"ReplacementHeapBlock::addRun added run " << strname 
   218          << 
" (rheap size=" << size << 
")" << endl;
   234 template<
class T,
class Compare>
   238   assert(i >= 0 && i < size && mergeHeap[i].
run);
   242       cerr << 
"ReplacementHeapBlock::deleteRun  deleting run " << i << 
", "   243            << mergeHeap[i].run << endl;
   249   delete mergeHeap[i].run;
   252     mergeHeap[i].value = mergeHeap[size-1].value;
   253     mergeHeap[i].run = mergeHeap[size-1].run;
   265 template<
class T,
class Compare>
   280     err = mergeHeap[i].run->seek(0);   
   282        cerr << 
"ReplacementHeapBlock::Init(): cannot seek run " << i << 
"\n";
   287      err = mergeHeap[i].run->read_item(&elt); 
   293          cerr << 
"ReplacementHeapBlock::Init(): cannot read run " << i << 
"\n";
   299        mergeHeap[i].value = *elt;
   311 template<
class T,
class Compare>
   314   size_t min_index = i;
   315   size_t lc = rheap_lchild(i);
   316   size_t rc = rheap_rchild(i);
   319   assert(i >= 0 && i < size);
   321       (cmpobj.compare(mergeHeap[lc].value, mergeHeap[min_index].value) == -1)) {
   325       (cmpobj.compare(mergeHeap[rc].
value, mergeHeap[min_index].value) == -1)) {
   329   if (min_index != i) {
   332     mergeHeap[min_index] = mergeHeap[i];
   343 template<
class T,
class Compare>
   348     for (
int i = rheap_parent(size-1); i>=0; i--) {
   358 template<
class T,
class Compare>
   365   min = mergeHeap[0].value;
   370   err = mergeHeap[0].run->read_item(&elt); 
   374       RBHEAP_DEBUG cerr << 
"rheap extract_min: run " << mergeHeap[0].run 
   375                        << 
" empty. deleting\n ";
   378       cerr << 
"ReplacementHeapBlock::extract_min: cannot read\n";
   384     mergeHeap[0].value = *elt;
   388   if (size > 0) heapify(0);
 
AMI_err name(char **stream_name)
 
SYMBOL * err(FILE *fp, SYMBOL *s, char *msg)
 
#define assert(condition)
 
ostream & print(ostream &s) const
 
ReplacementHeapBlock(queue< MEM_STREAM< T > *> *runList)
 
friend ostream & operator<<(ostream &s, const BlockHeapElement &p)
 
void addRun(MEM_STREAM< T > *run)