/*******************************************************************************
+
+  LEDA 3.5
+
+  _p_queue.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_P_QUEUE_H
#define _LEDA_P_QUEUE_H

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

#include <LEDA/p_queue.h>

//------------------------------------------------------------------------------
//
// Priority queues with implementation parameter:
//
//   _p_queue<priotype,inftype,prio_impl> 
//
//------------------------------------------------------------------------------


/*{\Manpage {_p_queue} {P,I,impl} {Priority Queues with Implementation Parameter} }*/

/*{\Mdefinition
An instance of type |\Mname| is a priority queue implemented by data type $impl$.
$impl$ must be one of the priority queue implementations listed in
section \ref{Implementations Priority Queues} or a user defined data structure
fulfilling the specification given in section \ref{User Implementations
Priority Queues}. Note that the priority type $P$ must linearly ordered.
}*/


template <class P, class I, class impl> 

#if defined(__NO_TEMPLATE_ARG_BASE__)
class _p_queue : public p_queue<P,I>
{ impl* dummy; 
  public: _p_queue(int=0) {}
 };
#else

class _p_queue : private impl, public p_queue<P,I>
{


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

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

public:

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

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

P del_min() 
{ pq_item it = find_min();
  P x = prio(it);
  del_item(it);
  return x; 
 }

P prio(pq_item x) const 
{ return LEDA_ACCESS(P,impl::key(impl::item(x)));}

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

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

void decrease_p(pq_item x, const P& k)
{ impl::decrease_key(impl::item(x),leda_cast(k));}

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

int  size() const { return impl::size(); }
bool empty() const { return impl::size()==0; }
void clear() { impl::clear(); }

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))); }

_p_queue<P,I,impl>& operator=(const _p_queue<P,I,impl>& Q)
{ impl::operator=(Q); return *this; }

 _p_queue() {}
 _p_queue(int n) : impl(n) {}
 _p_queue(int n, int n2) : impl(n, n2) {}
 _p_queue(const _p_queue<P,I,impl>& Q) : impl(Q) {}
~_p_queue() { impl::clear(); }

};

#endif


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