Each element is a pair of key and value (k, v). Key is supposed to be an index with type index_t. Value is usually something to be sorted, e.g., priority. IndexDenseHeap use a heap to sort values by comparing value. It also can modify value by key and resort the values. More...

#include <utilities/IndexHeap.hpp>

Collaboration diagram for AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >:

Public Types
using	kv_pair = std::pair<key_type, value_type>

Public Member Functions
	IndexDenseHeap ()
	Default constructor.

constexpr size_t	min_size ()
	Gets the minimum physical size of the heap array.

size_t	heap_size () const
	Gets the current number of elements stored in the heap.

void	reserve (size_t s)
	Reserves memory to minimize reallocation overhead.

bool	empty () const
	Checks whether the heap contains no elements.

template<bool AllowUpdate = true>
void	push (key_type key, const value_type &value)
	push a (key, value) pair into heap.

const kv_pair &	top () const
	get the (key, value) pair on the top of heap.

void	pop ()
	pop the (key, value) pair on the top of heap.

bool	exist (key_type key) const
	Check if a key exists.

void	update (key_type key, const value_type &value)
	update a value specified by key.

void	remove (size_t key)
	remove a pair of key and value specified by key.

Public Attributes
const key_type	InvalidIndex = static_cast<key_type>(-1)

Protected Member Functions
constexpr size_t	empty_pos () const
	Sentinel value representing empty/invalid position.

constexpr size_t	first_pos () const
	Index of the first element.

size_t	last_pos () const
	Index of the last element in the heap.

index_t	leftc (index_t i) const
	get Index of the left child of node at index i

index_t	rightc (index_t i) const
	get Index of the right child of node at index i

index_t	parent (index_t i) const
	get Index of the parent of node at index i

bool	compare (index_t i0, index_t i1) const
	Compare two kv_pair by value in heap indexed by i0 and i1.

void	up_move (index_t idx)
	move element in heap[idx] up.

void	down_move (index_t idx)
	move element in heap[idx] down.

Protected Attributes
std::vector< key_type >	m_pos_in_heap
	map key to position in heap

std::vector< kv_pair >	m_heap
	sort (key, value).

Detailed Description

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>
class AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >

Each element is a pair of key and value (k, v). Key is supposed to be an index with type index_t. Value is usually something to be sorted, e.g., priority. IndexDenseHeap use a heap to sort values by comparing value. It also can modify value by key and resort the values.

Note: We suppose that key is densely distributed, otherwise use unordered_map to implement m_pos_in_heap.

Member Function Documentation

◆ compare()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

bool AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::compare	(	index_t	i0 ,
		index_t	i1 ) const

inline protected

Compare two kv_pair by value in heap indexed by i0 and i1.

Parameters

i0	first index for compare
i1	second index for compare

Returns: true if element i0 has higher priority than i1 false otherwise

◆ down_move()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

void AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::down_move ( index_t idx )

inline protected

move element in heap[idx] down.

Parameters

idx	the position in heap.

◆ empty()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

bool AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::empty ( ) const

inline

Checks whether the heap contains no elements.

Returns: true if the heap is empty, false otherwise

◆ empty_pos()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

size_t AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::empty_pos ( ) const

inline constexpr protected

Sentinel value representing empty/invalid position.

Returns: 0 indicating an empty or invalid position

◆ exist()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

bool AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::exist ( key_type key ) const

inline

Check if a key exists.

Parameters

key	the key to query

Returns: true if key exists,false otherwise

◆ first_pos()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

size_t AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::first_pos ( ) const

inline constexpr protected

Index of the first element.

Returns: 1 the starting index of valid heap elements

◆ heap_size()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

size_t AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::heap_size ( ) const

inline

Gets the current number of elements stored in the heap.

Returns: the count of valid primitives in the heap

◆ last_pos()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

size_t AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::last_pos ( ) const

inline protected

Index of the last element in the heap.

Returns: the last valid heap position

◆ leftc()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

index_t AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::leftc ( index_t i ) const

inline protected

get Index of the left child of node at index i

Parameters

i	input index

Returns: Index of the left child of node at index i

◆ min_size()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

size_t AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::min_size ( )

inline constexpr

Gets the minimum physical size of the heap array.

Returns: the starting offset of the heap (typically 1)

◆ parent()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

index_t AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::parent ( index_t i ) const

inline protected

get Index of the parent of node at index i

Parameters

i	input index

Returns: Index of the parent of node at index i

◆ push()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

template<bool AllowUpdate = true>

void AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::push	(	key_type	key ,
		const value_type &	value )

inline

push a (key, value) pair into heap.

Parameters

key	the key for pair
value	the value for pair

◆ remove()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

void AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::remove ( size_t key )

inline

remove a pair of key and value specified by key.

Parameters

specified key

◆ reserve()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

void AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::reserve ( size_t s )

inline

Reserves memory to minimize reallocation overhead.

Parameters

s	the expected total number of elements

◆ rightc()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

index_t AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::rightc ( index_t i ) const

inline protected

get Index of the right child of node at index i

Parameters

i	input index

Returns: Index of the right child of node at index i

◆ top()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

const kv_pair & AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::top ( ) const

inline

get the (key, value) pair on the top of heap.

Returns: the (key, value) pair on the top of heap.

◆ up_move()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

void AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::up_move ( index_t idx )

inline protected

move element in heap[idx] up.

Parameters

idx	the position in heap.

◆ update()

template<typename value_type, typename key_type = index_t, typename comparator = std::less<value_type>>

void AMCAX::Meshing::IndexDenseHeap< value_type, key_type, comparator >::update	(	key_type	key ,
		const value_type &	value )

inline

update a value specified by key.

Parameters

key	specified key
value	the new value.

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

utilities/IndexHeap.hpp

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Member Function Documentation

◆ compare()

◆ down_move()

◆ empty()

◆ empty_pos()

◆ exist()

◆ first_pos()

◆ heap_size()

◆ last_pos()

◆ leftc()

◆ min_size()

◆ parent()

◆ push()

◆ remove()

◆ reserve()

◆ rightc()

◆ top()

◆ up_move()

◆ update()