/*******************************************************************************++  LEDA 3.5+++  m_heap.h+++  Copyright (c) 1995, 1996, 1997  by  LEDA Software GmbH+  Postfach 151101, 66041 Saarbruecken, Germany+  All rights reserved.+ *******************************************************************************/#ifndef LEDA_M_HEAP_H#define LEDA_M_HEAP_H//------------------------------------------------------------------------------// m_heap : monotonic heaps //// a) the sequence of minimum keys (over time) is monotonic (non-decreasing)// b) the difference of minimum and maximum key is bounded by a constant M//// Implementation: cyclic array of lists//// Stefan Naeher  (1991)//------------------------------------------------------------------------------#include <LEDA/basic.h>#include <LEDA/list.h>typedef list_item m_heap_item;class __exportC m_heap {    int start;    int offset;    int M;    int count;    list<GenPtr> L;    list_item*   T;virtual void copy_inf(GenPtr&)  const {}virtual void clear_inf(GenPtr&) const {}virtual void print_inf(GenPtr x) const { cout << x; }public:typedef m_heap_item item;m_heap_item insert(GenPtr,GenPtr);m_heap_item find_min() const;m_heap_item first_item() const;m_heap_item next_item(m_heap_item) const;GenPtr       del_min();void change_key(m_heap_item,GenPtr);void decrease_key(m_heap_item it,GenPtr x) { change_key(it,x); }void change_inf(m_heap_item it, GenPtr x)  { copy_inf(x); L[it] = x; };void del_item(m_heap_item);void clear();GenPtr inf(m_heap_item it) const { return L.inf(it); }GenPtr key(m_heap_item) const{ error_handler(1,"m_heap::key not implemented");  return 0;  }int    size()   const     { return count; }int    empty()  const     { return count==0; }void   print() const; m_heap(int M=1024);          m_heap(int,int) { error_handler(1,"illegal constuctor"); }virtual ~m_heap() { delete T; }// still to do: copy operations m_heap& operator=(const m_heap&) { return *this; } m_heap(const m_heap&) {}};#endif