home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / incl / prio_m.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  5.9 KB  |  178 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  PRIO_M.h
  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.  
  17.  
  18. #ifndef PRIO_H
  19. #define PRIO_H
  20.  
  21.  
  22. #include <LEDA/f_heap.h>
  23.  
  24.  
  25. typedef f_heap_item pq_item;
  26.  
  27. #define prio(ktype,itype) name3(itype,ktype,prio)
  28.  
  29.  
  30. #define priodeclare2(ktype,itype)\
  31. \
  32. class prio(ktype,itype)  : public f_heap\
  33. {\
  34.   int  cmp(ent& x, ent& y) const { return compare(*(itype*)&x,*(itype*)&y); }\
  35.   void print_key(ent& x)   const { Print(*(itype*)&x); }\
  36.   void print_inf(ent& x)   const { Print(*(ktype*)&x); }\
  37.   void clear_key(ent& x)   const { Clear(*(itype*)&x); }\
  38.   void clear_inf(ent& x)   const { Clear(*(ktype*)&x); }\
  39.   void copy_key(ent& x)    const { Copy(*(itype*)&x); }\
  40.   void copy_inf(ent& x)    const { Copy(*(ktype*)&x); }\
  41. \
  42. public:\
  43. \
  44. virtual pq_item insert(ktype k,itype i) { return f_heap::insert(Ent(i),Ent(k));}\
  45. virtual pq_item find_min()        const { return f_heap::find_min();}\
  46. virtual ktype   del_min()   { ktype x = key(find_min()); f_heap::del_min(); return x; }\
  47. virtual ktype key(pq_item x)      const { return ktype(f_heap::inf(x)); }\
  48. virtual itype inf(pq_item x)      const { return itype(f_heap::key(x)); }\
  49. virtual void change_key(pq_item x, ktype k) { f_heap::change_inf(x,Ent(k)); }\
  50. virtual void decrease_inf(pq_item x,itype i){ f_heap::decrease_key(x,Ent(i)); }\
  51. virtual void del_item(pq_item x)            { f_heap::del_item(x); }\
  52. \
  53. virtual bool empty() const { return f_heap::empty(); }\
  54. virtual int  size()  const { return f_heap::size(); }\
  55. \
  56. virtual pq_item first_item()          const { return f_heap::first_item(); }\
  57. virtual pq_item next_item(pq_item it) const { return f_heap::next_item(it); }\
  58. \
  59. virtual prio(ktype,itype)& operator=(const prio(ktype,itype)& Q) { return (prio(ktype,itype)&)f_heap::operator=((f_heap&)Q); }\
  60. \
  61.  prio(ktype,itype)()  {}\
  62.  prio(ktype,itype)(const prio(ktype,itype)& Q) : f_heap((f_heap&)Q)  {}\
  63. ~prio(ktype,itype)()  { f_heap::clear(); }\
  64. };
  65.  
  66. #define forall_pq_items(i,Q) for(i = (Q).first_item(); i; i=(Q).next_item(i))
  67.  
  68.  
  69.  
  70. #define PRIO_ITEM(T) name2(T,_item)
  71.  
  72. #define PRIO(ktype,itype,impl) name4(itype,ktype,impl,PRIO)
  73.  
  74.  
  75. #define PRIOdeclare3(ktype,itype,impl)\
  76. \
  77. class PRIO(ktype,itype,impl) : public prio(ktype,itype), public impl\
  78. {\
  79. int  cmp(ent& x, ent& y) const { int b =  compare(*(itype*)x,*(itype*)y);\
  80.                                  return (b==0) ? int(x)-int(y) : b;}\
  81. \
  82. void print_key(ent& x)   const { Print(*(itype*)x);  }\
  83. void print_inf(ent& x)   const { Print(*(ktype*)&x); }\
  84. void clear_key(ent&)     const {}\
  85. void clear_inf(ent& x)   const { Clear(*(ktype*)&x); }\
  86. void copy_key(ent&)      const {}\
  87. void copy_inf(ent& x)    const { Copy(*(ktype*)&x); }\
  88. \
  89. public:\
  90. \
  91. pq_item insert(ktype k,itype i) { itype* p=new itype; *p=i; Copy(*p);\
  92.                                   return pq_item(impl::insert(Ent(p),Ent(k)));}\
  93. \
  94. pq_item find_min()   const { return pq_item(impl::find_min());}\
  95. \
  96. ktype del_min()            { pq_item it = find_min(); ktype x = key(it);\
  97.                              del_item(it); return x; }\
  98. \
  99. ktype key(pq_item x) const { return ktype(impl::inf(PRIO_ITEM(impl)(x))); }\
  100. itype inf(pq_item x) const { return *(itype*)impl::key(PRIO_ITEM(impl)(x));}\
  101. \
  102. void  change_key(pq_item x, ktype k)\
  103.                            { impl::change_inf(PRIO_ITEM(impl)(x),Ent(k)); }\
  104. \
  105. void  decrease_inf(pq_item x,itype i)\
  106.                            { itype* p=new itype; *p=i; Copy(*p);\
  107.                              impl::decrease_key(PRIO_ITEM(impl)(x),Ent(p));}\
  108. \
  109. void  del_item(pq_item x)  { delete (itype*)impl::key(PRIO_ITEM(impl)(x));\
  110.                              impl::del_item(PRIO_ITEM(impl)(x)); }\
  111. \
  112. bool  empty() const        { return impl::empty(); }\
  113. int   size()  const        { return impl::size(); }\
  114. \
  115. pq_item first_item()          const { return pq_item(impl::first_item()); }\
  116. pq_item next_item(pq_item it) const { return pq_item(impl::next_item(PRIO_ITEM(impl)(it))); }\
  117. \
  118. prio(ktype,itype)& operator=(const prio(ktype,itype)& Q)\
  119. {  return (PRIO(ktype,itype,impl)&)impl::operator=(*(impl*)&Q); }\
  120. \
  121. PRIO(ktype,itype,impl)(const PRIO(ktype,itype,impl)& Q):impl((impl&)Q)  {}\
  122. \
  123. PRIO(ktype,itype,impl)()  {}\
  124. \
  125. ~PRIO(ktype,itype,impl)()  { impl::clear(); }\
  126. };
  127.  
  128.  
  129.  
  130. //------------------------------------------------------------------------------
  131. // Bounded Priority Queues
  132. //------------------------------------------------------------------------------
  133.  
  134.  
  135. #define B_PRIO_ITEM(T) name2(T,_item)
  136.  
  137. #define B_PRIO(ktype,impl) name3(ktype,impl,B_PRIO)
  138.  
  139.  
  140. #define B_PRIOdeclare2(ktype,impl)\
  141. \
  142. class B_PRIO(ktype,impl) : public prio(ktype,int), public impl\
  143. {\
  144. int  cmp(ent& x, ent& y) const { return int(x) - int(y); }\
  145. void print_inf(ent& x)   const { Print(int(x)); }\
  146. void print_key(ent& x)   const { Print(*(ktype*)&x);}\
  147. void clear_key(ent& x)   const { Clear(*(ktype*)&x);}\
  148. void copy_key(ent& x)    const { Copy(*(ktype*)&x); }\
  149. \
  150. public:\
  151. \
  152. pq_item insert(ktype k,int i) { return pq_item(impl::insert(Ent(k),i));}\
  153. \
  154. pq_item find_min()   const { return pq_item(impl::find_min());}\
  155. \
  156. ktype del_min()            { return ktype(impl::del_min()); }\
  157. \
  158. ktype key(pq_item x) const { return ktype(impl::key(B_PRIO_ITEM(impl)(x))); }\
  159. int   inf(pq_item x) const { return impl::inf(B_PRIO_ITEM(impl)(x));}\
  160. \
  161. void  change_key(pq_item x, ktype k)\
  162.                            { impl::change_key(B_PRIO_ITEM(impl)(x),Ent(k)); }\
  163. \
  164. void  decrease_inf(pq_item x, int i)\
  165.                            { impl::decrease_inf(B_PRIO_ITEM(impl)(x),i);}\
  166. \
  167. void  del_item(pq_item x)  { impl::del_item(B_PRIO_ITEM(impl)(x)); }\
  168. \
  169. bool  empty() const        { return impl::empty(); }\
  170. int   size()  const        { return impl::size(); }\
  171. \
  172.  B_PRIO(ktype,impl)(int N) : impl(N) {}\
  173. ~B_PRIO(ktype,impl)()                { impl::clear(); }\
  174. };
  175.  
  176.  
  177. #endif
  178.