utility::heap Class Reference

#include <heap.hh>

Inheritance diagram for utility::heap:

Public Member Functions
	heap (int max_items)
	Create a heap with this number of items. More...
	~heap () override
void	heap_insert (int val, float coval, bool &err)
	Inserts a value into the heap that is sorted by coval. The err status will be set to true if the heap is already at capacity; this function w not increase the size of the heap. More...
void	heap_extract (int &val, float &coval, bool &err)
	Extracts the val,coval pair with the lowest coval from the heap. This modifies the heap, and the returned values are put into the arguments val and coval. More...
void	heap_replace (int val, float coval)
	replace the lowest value (equivalent to heap_extract; heap_insert but faster) If you call heap_insert with a full heap (ie last = maxsize) then heap_replace gets called instead. More...
void	reset_coval (int val, float coval)
float	heap_head () const
	returns the smallest covalue stored in the heap. More...
int	head_item () const
	returns the item with the smallest covalue More...
float	coval (int index) const
	Return the colvaue for a particular position in the heap. More...
int	val (int index) const
	Return the item index for a particular position in the heap. More...
float	coval_for_val (int val) const
	Return the colvaue for a particular item; O(N) More...
int	size () const
	Return the size of the heap. More...
int	capacity () const
	Return the capacity of the heap. More...
Public Member Functions inherited from utility::VirtualBase
	VirtualBase ()=default
	Default constructor. More...
virtual	~VirtualBase ()=default
	The virtual destructor is one of the main reasons for the VirtualBase class. More...
	VirtualBase (VirtualBase const &)=default
	VirtualBase (VirtualBase &&)=default
VirtualBase &	operator= (VirtualBase const &)=default
VirtualBase &	operator= (VirtualBase &&)=default

Private Member Functions
void	heap_init (int max_items)
	sets up an empty heap and stores the dimensioned size More...
void	heap_down (int index_in)
void	heap_up (int index_in)
int	heap_size () const
int	heap_capacity () const
int &	heap_size ()
int &	heap_capacity ()
void	decrease_coval (int index, float coval)
void	increase_coval (int index, float coval)
int	index_for_val (int val) const

Private Attributes
utility::vector0< int >	heap_
utility::vector0< float >	coheap_

Constructor & Destructor Documentation

heap()

utility::heap::heap

(

int

max_items

)

Create a heap with this number of items.

References coheap_, heap_, and heap_init().

~heap()

utility::heap::~heap ( )

overridedefault

Member Function Documentation

capacity()

int utility::heap::capacity

(

)

const

Return the capacity of the heap.

References heap_.

coval()

float utility::heap::coval

(

int

index

)

const

Return the colvaue for a particular position in the heap.

References coheap_.

Referenced by decrease_coval(), heap_extract(), heap_insert(), heap_replace(), increase_coval(), and reset_coval().

coval_for_val()

float utility::heap::coval_for_val

(

int

val

)

const

Return the colvaue for a particular item; O(N)

Return the colvaue for a particular item.

References coheap_, index_for_val(), and val().

decrease_coval()

void utility::heap::decrease_coval ( int  index, float  coval  )

private

References coheap_, coval(), and heap_up().

Referenced by reset_coval().

head_item()

int utility::heap::head_item

(

)

const

returns the item with the smallest covalue

References heap_.

heap_capacity() [1/2]

int & utility::heap::heap_capacity ( )

private

References heap_.

heap_capacity() [2/2]

int utility::heap::heap_capacity ( ) const

private

References heap_.

Referenced by heap_init(), and heap_insert().

heap_down()

void utility::heap::heap_down ( int  index_in )

private

References coheap_, heap_, and heap_size().

Referenced by heap_extract(), heap_replace(), and increase_coval().

heap_extract()

void utility::heap::heap_extract	(	int &	val,
		float &	coval,
		bool &	err
	)

Extracts the val,coval pair with the lowest coval from the heap. This modifies the heap, and the returned values are put into the arguments val and coval.

modifes heap and last_val return val and err.

References coheap_, coval(), heap_, heap_down(), heap_size(), and val().

heap_head()

float utility::heap::heap_head

(

)

const

returns the smallest covalue stored in the heap.

References coheap_.

heap_init()

void utility::heap::heap_init ( int  max_items )

private

sets up an empty heap and stores the dimensioned size

References heap_capacity(), and heap_size().

Referenced by heap().

heap_insert()

void utility::heap::heap_insert	(	int	val,
		float	coval,
		bool &	err
	)

Inserts a value into the heap that is sorted by coval. The err status will be set to true if the heap is already at capacity; this function w not increase the size of the heap.

modifies heap and last_dummy, inserts val, returns err requires heap_max to be previously set via heap_init

References coheap_, coval(), heap_, heap_capacity(), heap_replace(), heap_size(), heap_up(), and val().

heap_replace()

void utility::heap::heap_replace	(	int	val,
		float	coval
	)

replace the lowest value (equivalent to heap_extract; heap_insert but faster) If you call heap_insert with a full heap (ie last = maxsize) then heap_replace gets called instead.

References coheap_, coval(), heap_, heap_down(), and val().

Referenced by heap_insert().

heap_size() [1/2]

int & utility::heap::heap_size ( )

private

References heap_.

heap_size() [2/2]

int utility::heap::heap_size ( ) const

private

References heap_.

Referenced by heap_down(), heap_extract(), heap_init(), heap_insert(), and index_for_val().

heap_up()

void utility::heap::heap_up ( int  index_in )

private

References coheap_, heap_, test.T850_SubClassing::pv, and value.

Referenced by decrease_coval(), and heap_insert().

increase_coval()

void utility::heap::increase_coval ( int  index, float  coval  )

private

References coheap_, coval(), and heap_down().

Referenced by reset_coval().

index_for_val()

int utility::heap::index_for_val ( int  val ) const

private

References heap_, heap_size(), create_a3b_hbs::ii, and val().

Referenced by coval_for_val(), and reset_coval().

reset_coval()

void utility::heap::reset_coval	(	int	val,
		float	coval
	)

References coheap_, coval(), decrease_coval(), increase_coval(), index_for_val(), and val().

size()

int utility::heap::size

(

)

const

Return the size of the heap.

References heap_.

val()

int utility::heap::val

(

int

index

)

const

Return the item index for a particular position in the heap.

References heap_.

Referenced by coval_for_val(), heap_extract(), heap_insert(), heap_replace(), index_for_val(), and reset_coval().

Member Data Documentation

coheap_

utility::vector0< float > utility::heap::coheap_

private

Referenced by coval(), coval_for_val(), decrease_coval(), heap(), heap_down(), heap_extract(), heap_head(), heap_insert(), heap_replace(), heap_up(), increase_coval(), and reset_coval().

heap_

utility::vector0< int > utility::heap::heap_

private

Referenced by capacity(), head_item(), heap(), heap_capacity(), heap_down(), heap_extract(), heap_insert(), heap_replace(), heap_size(), heap_up(), index_for_val(), size(), and val().

---

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

• src/utility/heap.hh
• src/utility/heap.cc