hudson::BucketPQ< Item > Class Template Reference

#include <BucketPQ.h>

Inheritance diagram for hudson::BucketPQ< Item >:

List of all members.

Public Member Functions
	BucketPQ ()
bool	empty () const
void	push (int key, const Item &item)
Item &	top ()
const Item &	top () const
void	pop ()

---

Detailed Description

template<class Item>
class hudson::BucketPQ< Item >

We represent an "infinite" (32-bit limited) number of buckets. Each bucket is a stack. Only a few are actually represented, of course: we represent a contiguous set of buckets, numbered base_ through base_ + nbuckets_. Bucket numbers may be negative.

All runtimes except filter() are O(1) amortized, assuming that insertions only insert items with key O(1) away from the last key popped. We achieve this using a finger.

API:

• push(k, i): Insert item i in bucket k.
• empty(): Return whether there are any items.
• min(): Return a reference to top of the smallest-numbered stack.
• pop(): Pop said element.
• filter(pred): Keep every item where 'pred' is true, remove all the others.

---

Constructor & Destructor Documentation

template<class Item> hudson::BucketPQ< Item >::BucketPQ (   )  [inline]

---

Member Function Documentation

template<class Item> bool hudson::BucketPQ< Item >::empty (   )  const [inline]

template<class Item> void hudson::BucketPQ< Item >::pop (   )  [inline]

template<class Item> void hudson::BucketPQ< Item >::push (  int  key, const Item &  item )  [inline]

template<class Item> const Item& hudson::BucketPQ< Item >::top (   )  const [inline]

template<class Item> Item& hudson::BucketPQ< Item >::top (   )  [inline]

---

The documentation for this class was generated from the following file:

• utilities/BucketPQ.h

---