#include <heap.hh>

Inheritance diagram for utility::heap:

Public Member Functions
	heap (int max_items)
	Create a heap with this number of items. More...

virtual	~heap ()

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::pointer::ReferenceCount
	ReferenceCount ()
	Default constructor. More...

virtual	~ReferenceCount ()

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_

Additional Inherited Members
Public Types inherited from utility::pointer::ReferenceCount
typedef platform::Size	Size

typedef platform::Size	size_type

Constructor & Destructor Documentation

utility::heap::heap ( int max_items )

Create a heap with this number of items.

References coheap_, heap_, and heap_init().

utility::heap::~heap ( )

virtualdefault

Member Function Documentation

int utility::heap::capacity ( ) const

Return the capacity of the heap.

References heap_.

float utility::heap::coval ( int index ) const

Return the colvaue for a particular position in the heap.

References coheap_, and ObjexxFCL::index().

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

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_, ObjexxFCL::index(), and index_for_val().

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

private

References coheap_, coval(), heap_up(), and ObjexxFCL::index().

Referenced by reset_coval().

int utility::heap::head_item ( ) const

returns the item with the smallest covalue

References heap_.

int utility::heap::heap_capacity ( ) const

private

References heap_.

Referenced by heap_init(), and heap_insert().

int & utility::heap::heap_capacity ( )

private

References heap_.

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

private

References coheap_, heap_, and heap_size().

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

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_, heap_, heap_down(), and heap_size().

float utility::heap::heap_head ( ) const

returns the smallest covalue stored in the heap.

References coheap_.

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().

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().

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().

int utility::heap::heap_size ( ) const

private

References heap_.

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

int & utility::heap::heap_size ( )

private

References heap_.

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

private

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