/*******************************************************************************
+
+  LEDA 3.5
+
+  b_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_BPRIO_H
#define LEDA_BPRIO_H

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

//------------------------------------------------------------------------------
// b_priority_queues: bounded priority queues implemented by b_heaps 
//------------------------------------------------------------------------------

#include <LEDA/impl/b_heap.h>

/*{\Manpage {b_priority_queue} {K} {Bounded Priority Queues}}*/

typedef b_heap_item b_pq_item;

template<class K> 

class b_priority_queue : public b_heap 
{

/*{\Mdefinition 
An instance $Q$ of the parameterized data type |\Mname| is a
priority\_queue (cf. section \ref{Priority Queues}) whose information type is a
fixed interval $[a..b]$ of integers.}*/

public:

/*{\Mcreation Q}*/

b_priority_queue(int a, int b): b_heap(a,b)  {}

/*{\Mcreate creates an instance |\Mvar| of type |\Mname| with information type 
            $[a..b]$ and initializes it with the empty priority queue. }*/


virtual ~b_priority_queue()  { }


/*{\Moperations 2 5.5 }*/

/*{\Mtext See section \ref{Priority Queues}.}*/

b_pq_item insert(const K& k, int info)
                           { return b_heap::insert(info,leda_cast(k)); }

void decrease_inf(b_pq_item it,int newinf)
                           { b_heap::decrease_key(it,newinf); }

void del_item(b_pq_item x) { b_heap::delete_item(x); }

int      inf(b_pq_item x)  { return b_heap::key(x); }

K key(b_pq_item x)  { return LEDA_ACCESS(K,b_heap::inf(x)); }

K del_min()               { return LEDA_ACCESS(K,b_heap::del_min()); }

b_pq_item find_min()       { return b_heap::find_min(); }

void clear()               { b_heap::clear(); }

int empty()                { return (find_min()==0) ? true : false; }

};

 
/*{\Mimplementation
Bounded priority queues are implemented by arrays of linear lists.
Operations insert, find\_min, del\_item, decrease\_inf, key, inf,
and empty take time $O(1)$, del\_min (=  del\_item for the minimal
element) takes time $O(d)$, where $d$ is the distance of the minimal
element to the next bigger element in the queue (= $O(b-a)$ in the
worst case). clear takes time $O(b-a+n)$ and the space requirement is
$O(b-a+n)$, where $n$ is the current size of the queue.}*/


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

#endif

