home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / basic / _b_heap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  3.0 KB  |  121 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _b_heap.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/b_heap.h>
  17.  
  18. b_heap::b_heap(int a, int b) : T(a,b)
  19. { if (b<a) error_handler(1,"constructor: illegal size\n");
  20.   low = a;
  21.   high = b;
  22.   min = high+1;
  23.   max = low-1;
  24.   int i;
  25.   for(i=a;i<=b;i++) T[i] = new list(b_heap_item);
  26. }
  27.  
  28. void b_heap::clear()
  29. { int i;
  30.   for (i=low;i<=high;i++) T[i]->clear();
  31.   min = high+1;
  32.   max = low-1;
  33. } 
  34.  
  35. b_heap_item b_heap::insert(int key, ent info) 
  36. { if (key<low || key>high) 
  37.   error_handler(1,string("insert: illegal key %d\n",key));
  38.   if (key<min) min = key;
  39.   if (key>max) max = key;
  40.   b_heap_item it = new  b_heap_node(key,info);
  41.   it->loc = T[key]->append(it); 
  42.   return it;
  43. }
  44.  
  45. b_heap_item b_heap::find_min()
  46. { if (min>high) return 0;
  47.   return T[min]->head();
  48. }
  49.  
  50. b_heap_item b_heap::find_max()
  51. { if (max<low) return 0;
  52.   return T[max]->head();
  53. }
  54.  
  55. ent b_heap::del_min()
  56. { if (min>high) 
  57.        error_handler(1,"b_heap del_min: heap is empty");
  58.   b_heap_item p = T[min]->pop();
  59.   ent res = p->info;
  60.   delete p;
  61.   while ((min <= high) && (T[min]->empty())) min++;
  62.   if (min>high) max = low-1;
  63.   return res;
  64. }
  65.  
  66. ent b_heap::del_max()
  67. { if (max<0) error_handler(1,"b_heap del_max: heap is empty");
  68.   b_heap_item p = T[max]->pop();
  69.   ent res = p->info;
  70.   delete p;
  71.   while ((max>=low) && (T[max]->empty())) max--;
  72.   if (max<low) min = high+1;
  73.   return res;
  74. }
  75.  
  76. b_heap_item b_heap::decrease_key(b_heap_item it, int k)
  77. { if (it==0) error_handler(1,"decrease_key: item = nil\n");
  78.   if (k<low || k>high) error_handler(1,"decrease_key: illegal key\n");
  79.   if (it->loc==0) error_handler(1,"decrease_key: item not found\n");
  80.   T[it->key]->del(it->loc);
  81.   while ((max >= low) && (T[max]->empty())) max--;
  82.   it->key = k;
  83.   it->loc = T[k]->append(it); 
  84.   if (k<min) min = k;
  85.   return it;
  86. }
  87.  
  88. b_heap_item b_heap::increase_key(b_heap_item it, int k)
  89. { if (it==0) error_handler(1,"increase_key: item = nil\n");
  90.   if (k<low || k>high) error_handler(1,"increase_key:illegal key\n");
  91.   if (it->loc==0) error_handler(1,"increase_key: item not found\n");
  92.   T[it->key]->del(it->loc);
  93.   while ((min <= high) && (T[min]->empty())) min++;
  94.   it->key = k;
  95.   it->loc = T[k]->append(it); 
  96.   if (k>max) max = k;
  97.   return it;
  98. }
  99.  
  100.  
  101. void b_heap::delete_item(b_heap_item it) 
  102. { if (it==0) error_handler(1,"delete_item: item = nil\n");
  103.   if (it->loc==0) error_handler(1,"delete_item: item not found\n");
  104.   T[it->key]->del(it->loc); 
  105.   while ((min <= high) && (T[min]->empty())) min++;
  106.   while ((max >= low) && (T[max]->empty())) max--;
  107.   delete it;
  108. }
  109.  
  110. /* TEST */
  111.  
  112. void b_heap::print()
  113. { int i;
  114.   for (i=low;i<=high;i++) { cout << i << ": ";
  115.                             T[i]->print();
  116.                             cout << "\n";
  117.                            }
  118. }
  119.  
  120.  
  121.