Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
m_heap.h
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 2k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

m_heap.h：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  m_heap.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #ifndef LEDA_M_HEAP_H
  14. #define LEDA_M_HEAP_H
  16. //------------------------------------------------------------------------------
  17. // m_heap : monotonic heaps 
  18. //
  19. // a) the sequence of minimum keys (over time) is monotonic (non-decreasing)
  20. // b) the difference of minimum and maximum key is bounded by a constant M
  21. //
  22. // Implementation: cyclic array of lists
  23. //
  24. // Stefan Naeher  (1991)
  25. //------------------------------------------------------------------------------
  28. #include <LEDA/basic.h>
  29. #include <LEDA/list.h>
  32. typedef list_item m_heap_item;
  34. class m_heap {
  36.     int start;
  37.     int offset;
  38.     int M;
  39.     int count;
  40.     list<GenPtr> L;
  42.     list_item*   T;
  44. virtual void copy_inf(GenPtr&)  const {}
  45. virtual void clear_inf(GenPtr&) const {}
  46. virtual void print_inf(GenPtr x) const { cout << x; }
  48. protected:
  50. m_heap_item item(void* p) const { return (m_heap_item)p; }
  52. public:
  54. m_heap_item insert(GenPtr,GenPtr);
  55. m_heap_item find_min() const;
  56. m_heap_item first_item() const;
  57. m_heap_item next_item(m_heap_item) const;
  59. GenPtr       del_min();
  61. void change_key(m_heap_item,GenPtr);
  62. void decrease_key(m_heap_item it,GenPtr x) { change_key(it,x); }
  63. void change_inf(m_heap_item it, GenPtr x)  { copy_inf(x); L[it] = x; };
  64. void del_item(m_heap_item);
  65. void clear();
  67. GenPtr inf(m_heap_item it) const { return L.inf(it); }
  69. GenPtr key(m_heap_item) const
  70. { error_handler(1,"m_heap::key not implemented");
  71.   return 0; 
  72.  }
  74. int    size()   const     { return count; }
  75. int    empty()  const     { return count==0; }
  77. void   print() const;
  79.  m_heap(int M=1024);         
  80.  m_heap(int,int) { error_handler(1,"illegal constuctor"); }
  82. virtual ~m_heap() { delete T; }
  85. // still to do: copy operations
  87.  m_heap& operator=(const m_heap&) { return *this; }
  88.  m_heap(const m_heap&) {}
  90. };
  92. #endif