priority_queue< T > Class Template Reference

priority queue for items More...

#include <mst.h>

List of all members.

Public Member Functions
	priority_queue (byte_allocator &all, size_t N, const _vector< T > &pred, size_t dim=3)
	constructor
bool	empty () const
	checks if queue is empty
size_t	size () const
	size of queue
void	insert (size_t v)
	inserts item
size_t	getmin ()
	gets min element
void	lower (size_t v)
	puts item at the lower position
Private Member Functions
void	exchange (size_t i, size_t j)
	interchanges items at positions i, j
void	fixUp (size_t i)
	moves up
void	fixDown (size_t k, size_t N)
	moves down
Private Attributes
size_t	_dim
	dimension
size_t	_Num
	queue size
priority_queue_vec_t	_pq
	queue vector
priority_queue_vec_t	_qp
	reverse queue vector
const _vector< T > &	_pred
	predicate

---

Detailed Description

template<class T>
class priority_queue< T >

priority queue for items

Definition at line 44 of file mst.h.

---

Constructor & Destructor Documentation

template<class T>

BEGIN_TERIMBER_NAMESPACE priority_queue< T >::priority_queue	(	byte_allocator &	all,
		size_t	N,
		const _vector< T > &	pred,
		size_t	dim = 3
	)			[inline]

constructor

Parameters:

all	external allocator
N	queue size
pred	predicate
dim	dimension

Definition at line 39 of file mst.hpp.

References priority_queue< T >::_pq, priority_queue< T >::_qp, and _vector< T, A >::resize().

---

Member Function Documentation

template<class T>

bool priority_queue< T >::empty

(

)

const [inline]

checks if queue is empty

Definition at line 49 of file mst.hpp.

References priority_queue< T >::_Num.

Referenced by mst< T, N >::pfs().

template<class T>

size_t priority_queue< T >::size

(

)

const [inline]

size of queue

Definition at line 57 of file mst.hpp.

References priority_queue< T >::_Num.

template<class T>

void priority_queue< T >::insert

(

size_t

v

)

[inline]

inserts item

Parameters:

v

item

Definition at line 65 of file mst.hpp.

References priority_queue< T >::_Num, priority_queue< T >::_pq, priority_queue< T >::_qp, and priority_queue< T >::fixUp().

Referenced by mst< T, N >::pfs().

template<class T>

size_t priority_queue< T >::getmin

(

)

[inline]

gets min element

Definition at line 75 of file mst.hpp.

References priority_queue< T >::_Num, priority_queue< T >::_pq, priority_queue< T >::exchange(), and priority_queue< T >::fixDown().

Referenced by mst< T, N >::pfs().

template<class T>

void priority_queue< T >::lower

(

size_t

v

)

[inline]

puts item at the lower position

Parameters:

v

item

Definition at line 85 of file mst.hpp.

References priority_queue< T >::_qp, and priority_queue< T >::fixUp().

Referenced by mst< T, N >::pfs().

template<class T>

void priority_queue< T >::exchange	(	size_t	i,
		size_t	j
	)			[inline, private]

interchanges items at positions i, j

Parameters:

i	first index
j	second index

Definition at line 93 of file mst.hpp.

References priority_queue< T >::_pq, and priority_queue< T >::_qp.

Referenced by priority_queue< T >::fixDown(), priority_queue< T >::fixUp(), and priority_queue< T >::getmin().

template<class T>

void priority_queue< T >::fixUp

(

size_t

i

)

[inline, private]

moves up

Parameters:

i

index

Definition at line 106 of file mst.hpp.

References priority_queue< T >::_dim, priority_queue< T >::_pq, priority_queue< T >::_pred, and priority_queue< T >::exchange().

Referenced by priority_queue< T >::insert(), and priority_queue< T >::lower().

template<class T>

void priority_queue< T >::fixDown	(	size_t	k,
		size_t	N
	)			[inline, private]

moves down

Parameters:

k	index
N	size

Definition at line 119 of file mst.hpp.

References priority_queue< T >::_dim, priority_queue< T >::_pq, priority_queue< T >::_pred, and priority_queue< T >::exchange().

Referenced by priority_queue< T >::getmin().

---

Member Data Documentation

template<class T>

size_t priority_queue< T >::_dim [private]

dimension

Definition at line 97 of file mst.h.

Referenced by priority_queue< T >::fixDown(), and priority_queue< T >::fixUp().

template<class T>

size_t priority_queue< T >::_Num [private]

queue size

Definition at line 98 of file mst.h.

Referenced by priority_queue< T >::empty(), priority_queue< T >::getmin(), priority_queue< T >::insert(), and priority_queue< T >::size().

template<class T>

priority_queue_vec_t priority_queue< T >::_pq [private]

queue vector

Definition at line 99 of file mst.h.

Referenced by priority_queue< T >::exchange(), priority_queue< T >::fixDown(), priority_queue< T >::fixUp(), priority_queue< T >::getmin(), priority_queue< T >::insert(), and priority_queue< T >::priority_queue().

template<class T>

priority_queue_vec_t priority_queue< T >::_qp [private]

reverse queue vector

Definition at line 100 of file mst.h.

Referenced by priority_queue< T >::exchange(), priority_queue< T >::insert(), priority_queue< T >::lower(), and priority_queue< T >::priority_queue().

template<class T>

const _vector< T >& priority_queue< T >::_pred [private]

predicate

Definition at line 101 of file mst.h.

Referenced by priority_queue< T >::fixDown(), and priority_queue< T >::fixUp().

---

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

• mst.h
• mst.hpp