An indirect priority queue that supports random access modification of priority. More...

#include <teca_priority_queue.h>

Public Member Functions
bool	empty ()

void	push (const key_t &key)
	add a value into the queue More...

void	clear ()
	free all resources and reset the queue to an empty state More...

void	modified (const key_t &key)

key_t	pop ()

key_t	peak ()

void	to_stream (std::ostream &os, bool priorities=true)

Static Public Member Functions
static p_teca_priority_queue< key_t, lookup_t, comp_t, key_map_t >	New (lookup_t &lookup, unsigned long init_size=256, unsigned long block_size=256)

Protected Member Functions
	teca_priority_queue (const teca_priority_queue< key_t, lookup_t > &)=delete

void	operator= (const teca_priority_queue< key_t, lookup_t > &)=delete

template<typename u = key_map_t>
	teca_priority_queue (lookup_t lookup, unsigned long init_size, unsigned long block_size, typename std::enable_if< std::is_same< std::vector< unsigned long >, u >::value >::type *=0)

template<typename u = key_map_t>
	teca_priority_queue (lookup_t lookup, unsigned long init_size, unsigned long block_size, typename std::enable_if< std::is_same< std::map< key_t, unsigned long >, u >::value >::type *=0)

template<typename u = key_map_t>
void	grow (unsigned long n, typename std::enable_if< std::is_same< std::vector< unsigned long >, u >::value >::type *=0)

template<typename u = key_map_t>
void	grow (unsigned long n, typename std::enable_if< std::is_same< std::map< key_t, unsigned long >, u >::value >::type *=0)

void	up_heapify (unsigned long id)

void	down_heapify (unsigned long id)

void	swap (unsigned long i, unsigned long j)

unsigned long	left_child (unsigned long a_id)

unsigned long	right_child (unsigned long a_id)

unsigned long	parent (unsigned long a_id)

Detailed Description

template<typename key_t, typename lookup_t, typename comp_t, typename key_map_t>
class teca_priority_queue< key_t, lookup_t, comp_t, key_map_t >

An indirect priority queue that supports random access modification of priority.

an indirect priority queue that supports random access modification of priority the queue works with user provided keys and lookup functor that converts keys to priorities.

template parameters:

name	description
key_t	type of the user provided keys
lookup_t	callable that implements: priority_t operator()(key_t key)
comp_t	callable that implements the predicate: bool(key_t, key_t),
	used to enforce heap order. (std::less<key_t>)
key_map_t	type of container used to track the position in the heap
	of the keys. The default, a vector, is only valid for
	interger ordinals from 0 to N. Use mapped_key_t<key_t>
	for all other cases. (contiguous_key_t)

typical usage:

construct a container of objects to prioritize, and initialize a lookup object that given a key returns the priority of the coresponding object. create an instance of the priority_queue and push the key values. as keys are pushed heap ording is imposed, this is why objects need to be in place before pushing keys. when an object's priority has been changed one must call modified passing the key of the object. the location of each object is tracked and the queue will reprioritize itself after modification.

recomendation:

to obtain high performance, it's best to avoid using std::function for lookup operations. Instead, write a small functor so that the compiler can inline lookup calls.

don't forget to change key_map_t to mapped_key_t<key_t> if keys are not integer ordinals 0 to N.

Member Function Documentation

◆ clear()

template<typename key_t , typename lookup_t , typename comp_t , typename key_map_t >

void teca_priority_queue< key_t, lookup_t, comp_t, key_map_t >::clear

free all resources and reset the queue to an empty state

◆ push()

template<typename key_t , typename lookup_t , typename comp_t , typename key_map_t >

void teca_priority_queue< key_t, lookup_t, comp_t, key_map_t >::push ( const key_t & key )

add a value into the queue

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

develop/data/teca_priority_queue.h

Public Member Functions

Static Public Member Functions

Protected Member Functions