/*******************************************************************************
+
+  LEDA 3.5
+
+  node_pq.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_NODE_PQ_H
#define LEDA_NODE_PQ_H

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


//------------------------------------------------------------------------------
// node priority queues
//
// S. Naeher (1995)
//------------------------------------------------------------------------------

#include <LEDA/graph.h>
#include <LEDA/impl/bin_heap.h>

#define PRIO_IMPL bin_heap
#define PRIO_ITEM bin_heap_item


/*{\Manpage {node_pq} {P} {Node Priority Queues}}*/

template <class P>

class node_pq : private PRIO_IMPL
{

/*{\Mdefinition
An instance $Q$ of the parameterized data type |\Mname| is a partial
function from the nodes of a graph $G$ to a linearly ordered type $P$
of priorities. The priority of a node is sometimes called the information
of the node. For every graph $G$ only one |\Mname| may be used and every node
of $G$ may be contained in the queue at most once (cf. section 
\ref{Priority Queues} for general priority queues). }*/

node_map<PRIO_ITEM> ITEM;


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

int  cmp(GenPtr x, GenPtr y) const { return LEDA_COMPARE(P,x,y); }

void print_key(GenPtr x)     const { LEDA_PRINT(P,x,cout); }
void print_inf(GenPtr x)     const { cout << index(node(x));  }
void clear_key(GenPtr& x)    const { LEDA_CLEAR(P,x); }
void copy_key(GenPtr& x)     const { LEDA_COPY(P,x);  }

public:

/*{\Mcreation Q }*/
 
node_pq(const graph& G) : ITEM(G,nil) {}
/*{\Mcreate creates an instance $Q$ ot type |\Mname| for the nodes of graph $G$
    with $dom(Q)=\emptyset$.}*/

~node_pq() { clear(); }


/*{\Moperations 1.3 4.7}*/

void insert(node v, const P& x)
{ ITEM[v] = PRIO_IMPL::insert(leda_cast(x),v);}
/*{\Mop          adds the node $v$ with priority $x$ to
          	 |\Mvar|.\\ \precond $v\not\in dom(Q)$.}*/

P prio(node v) const
{ return LEDA_ACCESS(P,PRIO_IMPL::key(ITEM[v])); }
/*{\Mop         returns the priority of node $v$.}*/



bool member(node v) const {return ITEM[v] != nil;};
/*{\Mop         returns true if $v$ in |\Mvar|, false otherwise.}*/

void decrease_p(node v, const P& x)
{ PRIO_IMPL::decrease_key(ITEM[v],leda_cast(x)); }
/*{\Mop          makes $x$ the new priority of node $v$.\\
        	 \precond $x \le Q$.prio$(v)$.}*/

node find_min() const
{ return (node)PRIO_IMPL::inf(PRIO_IMPL::find_min());   }
/*{\Mop          returns a node with minimal priority 
                 (nil if |\Mvar| is empty).}*/

void del(node v) 
{ PRIO_IMPL::del_item(ITEM[v]); ITEM[v] = nil; }
/*{\Mop          removes the node $v$ from |\Mvar|. }*/

node del_min()   
{ node v = find_min(); PRIO_IMPL::del_min(); ITEM[v] = nil;  return v; }
/*{\Mop          removes a node with minimal priority from |\Mvar| 
                 and returns it (nil if |\Mvar| is empty).}*/

void clear()     { PRIO_IMPL::clear(); }
/*{\Mop          makes $Q$ the empty node priority queue.}*/

int size()   const { return PRIO_IMPL::size(); }
/*{\Mop          returns $dom(Q)$. }*/

int empty()  const { return PRIO_IMPL::empty(); }
/*{\Mop          returns true if |\Mvar| is the empty node
		 priority queue, false otherwise.}*/

P inf(node v) const
{ return LEDA_ACCESS(P,PRIO_IMPL::key(ITEM[v])); }
/*{\Mop         returns the priority of node $v$.}*/

void decrease_inf(node v, const P& x)
{ PRIO_IMPL::decrease_key(ITEM[v],leda_cast(x)); }
/*{\Xop (for backward compatibility) makes $x$ the new priority of node $v$.\\
        	 \precond $p \le Q$.prio$(v)$.}*/


};

/*{\Mimplementation
Node priority queues are implemented by fibonacci heaps and node arrays.
Operations insert, del\_node, del\_min take time $O(\log n)$, find\_min, 
decrease\_inf, empty take time $O(1)$ and clear takes time $O(m)$, where 
$m$ is the size of $Q$. The space requirement is $O(n)$, where $n$ is the 
number of nodes of $G$.}*/


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

#endif
