/*******************************************************************************
+
+  LEDA 3.5
+
+  _prio.h
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#ifndef _LEDA_PRIO_H 
#define _LEDA_PRIO_H 


#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350007
#include <LEDA/REDEFINE_NAMES.h>
#endif
#include <LEDA/prio.h>

//------------------------------------------------------------------------------
//
// Priority queues with implementation parameter:
//
//   _priority_queue<keytype,inftype,prio_impl> 
//
//------------------------------------------------------------------------------


template <class ktype, class I, class impl> 

#if defined(__NO_TEMPLATE_ARG_BASE__)
class _priority_queue : public priority_queue<ktype,I> 
{ impl* dummy; 
  public: _priority_queue(int=0) {}
 };
#else

class _priority_queue : private impl, public priority_queue<ktype,I>
{


int key_type_id() const { return LEDA_TYPE_ID(I); }

int  cmp(GenPtr x, GenPtr y) const { return LEDA_COMPARE(I,x,y); }
void clear_key(GenPtr& x) const { LEDA_CLEAR(I,x); }
void clear_inf(GenPtr& x) const { LEDA_CLEAR(ktype,x); }
void copy_key(GenPtr& x)  const { LEDA_COPY(I,x); }
void copy_inf(GenPtr& x)  const { LEDA_COPY(ktype,x); }
void print_key(GenPtr x)  const { LEDA_PRINT(I,x,cout); }
void print_inf(GenPtr x)  const { LEDA_PRINT(ktype,x,cout); }

public:

pq_item insert(const ktype& k, const I& i) 
{ return pq_item(impl::insert(leda_cast(i),leda_cast(k)));}

pq_item find_min() const { return pq_item(impl::find_min());}

ktype del_min() 
{ pq_item it = find_min();
  ktype x = key(it);
  del_item(it);
  return x; 
 }

ktype key(pq_item x) const 
{ return LEDA_ACCESS(ktype,impl::inf(impl::item(x)));}

I inf(pq_item x) const 
{ return LEDA_ACCESS(I,impl::key(impl::item(x)));}

void change_key(pq_item x, const ktype& k) 
{ impl::change_inf(impl::item(x),leda_cast(k)); }

void decrease_inf(pq_item x, const I& i)
{ impl::decrease_key(impl::item(x),leda_cast(i));}

void del_item(pq_item x)        
{ impl::del_item(impl::item(x)); }

int  size()  const { return impl::size(); }
bool empty() const { return (size()==0) ? true : false; }

pq_item first_item() const { return pq_item(impl::first_item()); }
pq_item next_item(pq_item it) const 
{ return pq_item(impl::next_item(impl::item(it))); }

_priority_queue<ktype,I,impl>& operator=(const _priority_queue<ktype,I,impl>& Q)
{ return (_priority_queue<ktype,I,impl>&)impl::operator=(Q); }

 _priority_queue() {}
 _priority_queue(int n) : impl(n) {}
 _priority_queue(const _priority_queue<ktype,I,impl>& Q) : impl(Q) {}
~_priority_queue() { impl::clear(); }

};

#endif


#if LEDA_ROOT_INCL_ID == 350007
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif
#endif
