/*******************************************************************************
+
+  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_PRIORITY_QUEUE_H
#define LEDA_PRIORITY_QUEUE_H

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


#include <LEDA/impl/f_heap.h>

typedef f_heap_item pq_item;

/*{\Manpage {p_queue} {P,I} {Priority Queues}}*/

template<class P, class I> 

class p_queue: private f_heap
{


/*{\Mdefinition
An instance $Q$ of the parameterized data type |\Mname| is a collection of items
(type $pq\_item$). Every item contains a priority from a linearly ordered type 
$P$ and an information from an arbitrary type $I$. $P$ is called the priority 
type of $Q$ and $I$ is called the information type of $Q$. The number of items 
in $Q$ is called the size of $Q$. If $Q$ has size zero it is called the empty 
priority queue. We use $\<p,i\>$ to denote a $pq\_item$\ with priority $p$ and
information $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:

typedef pq_item item;
typedef P prio_type;
typedef I inf_type;

/*{\Mcreation Q }*/

p_queue()  {}
/*{\Mcreate 
creates an instance |\Mvar| of type |\Mname| and initializes it with the
empty priority queue. }*/

 p_queue(const p_queue<P,I>& Q):f_heap(Q) {}
~p_queue()  { f_heap::clear(); }

p_queue<P,I>& operator=(const p_queue<P,I>& Q) 
{ return (p_queue<P,I>&)f_heap::operator=(Q); }


/*{\Moperations 2 5}*/

virtual P prio(pq_item it) const 
{ return LEDA_ACCESS(P,f_heap::key(it)); }
/*{\Mop     returns the priority of item $it$.\\
            \precond $it$ is an item in |\Mvar|.}*/

virtual I inf(pq_item it) const 
{ return LEDA_ACCESS(I,f_heap::inf(it)); }
/*{\Mop     returns the information of item $it$.\\
	    \precond $it$ is an item in |\Mvar|.}*/

virtual pq_item insert(const P& x, const I& i) 
                         { return f_heap::insert(leda_cast(x),leda_cast(i)); }
/*{\Mop     adds a new item $\<x,i\>$ to |\Mvar| and returns it.}*/


virtual pq_item find_min() const { return f_heap::find_min();}
/*{\Mop     returns an item with minimal priority 
	    (nil if |\Mvar| is empty).}*/


virtual P   del_min() 
{ P x = prio(find_min()); f_heap::del_min(); return x; }
/*{\Mop    removes the item $it$ = |\Mvar|.find\_min() from |\Mvar| 
	   and returns the priority of it.\\
           \precond |\Mvar| is not empty.}*/

virtual void del_item(pq_item it) { f_heap::del_item(it); }
/*{\Mop    removes the item $it$ from |\Mvar|.\\
	   \precond $it$ is an item in |\Mvar|.}*/

virtual void change_inf(pq_item it, const I& i) 
{ f_heap::change_inf(it,leda_cast(i)); }
/*{\Mop    makes $i$ the new information of item $it$.\\
	   \precond $it$ is an item in |\Mvar|.}*/

virtual void decrease_p(pq_item it, const P& x)
{ f_heap::decrease_key(it,leda_cast(x)); }
/*{\Mopl    makes $x$ the new priority of item $it$.\\
	    \precond $it$ is an item in |\Mvar| and $x$
	    is not larger then $prio(it)$.}*/


virtual int  size()    const { return f_heap::size(); }
/*{\Mop     returns the size of |\Mvar|.}*/

virtual bool empty()   const { return (size()==0) ? true : false; }
/*{\Mop     returns true, if |\Mvar| is empty, false otherwise.}*/

void clear() {f_heap::clear();}
/*{\Mop     makes |\Mvar| the empty priority queue. }*/


virtual pq_item first_item() const { return f_heap::first_item(); }
virtual pq_item next_item(pq_item it) const { return f_heap::next_item(it); }

};


/*{\Mimplementation
Priority queues are implemented by Fibonacci heaps \cite{FT87}. Operations
insert, del\_item, del\_min take time $O(\log n)$, find\_min, decrease\_p, 
prio, inf, empty take time $O(1)$ and clear takes time $O(n)$, where $n$ is the 
size of |\Mvar|. The space requirement is $O(n)$.}*/


/*{\Mexample
Dijkstra's Algorithm (cf. section \ref{Graph and network algorithms})}*/


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

#endif
