Detailed Description

template<typename KeyType, unsigned Arity = 2, class Compare = std::less<KeyType>>
class tlx::DAryAddressableIntHeap< KeyType, Arity, Compare >

This class implements an addressable integer priority queue, precisely a d-ary heap.

Keys must be unique unsigned integers. The addressable heap holds an array indexed by the keys, hence it requires a multiple of the highest integer key as space!

Template Parameters

KeyType	Has to be an unsigned integer type.
Arity	A positive integer.
Compare	Function object.

Definition at line 41 of file d_ary_addressable_int_heap.hpp.

#include <d_ary_addressable_int_heap.hpp>

Public Types
using	compare_type = Compare

using	key_type = KeyType

Public Member Functions
	DAryAddressableIntHeap (compare_type cmp=compare_type())
	Allocates an empty heap. More...

	DAryAddressableIntHeap (const DAryAddressableIntHeap &)=default
	Copy. More...

	DAryAddressableIntHeap (DAryAddressableIntHeap &&)=default
	Move. More...

template<class InputIterator >
void	build_heap (InputIterator first, InputIterator last)
	Builds a heap from a container. More...

void	build_heap (const std::vector< key_type > &keys)
	Builds a heap from the vector `keys`. Items of `keys` are copied. More...

void	build_heap (std::vector< key_type > &&keys)
	Builds a heap from the vector `keys`. Items of `keys` are moved. More...

size_t	capacity () const noexcept
	Returns the capacity of the heap. More...

void	clear ()
	Empties the heap. More...

bool	contains (key_type key) const
	Returns true if the key `key` is in the heap, false otherwise. More...

bool	empty () const noexcept
	Returns true if the heap has no items, false otherwise. More...

key_type	extract_top ()
	Removes and returns the top item. More...

DAryAddressableIntHeap &	operator= (const DAryAddressableIntHeap &)=default

DAryAddressableIntHeap &	operator= (DAryAddressableIntHeap &&)=default

void	pop ()
	Removes the top item. More...

void	push (const key_type &new_key)
	Inserts a new item. More...

void	push (key_type &&new_key)
	Inserts a new item. More...

void	remove (key_type key)
	Removes the item with key `key`. More...

void	reserve (size_t new_size)
	Allocates space for `new_size` items. More...

bool	sanity_check ()

size_t	size () const noexcept
	Returns the number of items in the heap. More...

const key_type &	top () const noexcept
	Returns the top item. More...

void	update (key_type key)
	Updates the priority queue after the priority associated to the item with key `key` has been changed; if the key `key` is not present in the priority queue, it will be added. More...

void	update_all ()
	Rebuilds the heap. More...

Static Public Attributes
static constexpr size_t	arity = Arity

Static Protected Member Functions
static constexpr key_type	not_present ()
	Marks a key that is not in the heap. More...

Protected Attributes
compare_type	cmp_
	Compare function. More...

std::vector< key_type >	handles_
	Positions of the keys in the heap vector. More...

std::vector< key_type >	heap_
	Cells in the heap. More...

Private Member Functions
void	heapify ()
	Reorganize heap_ into a heap. More...

size_t	left (size_t k) const
	Returns the position of the left child of the node at position `k`. More...

size_t	parent (size_t k) const
	Returns the position of the parent of the node at position `k`. More...

void	sift_down (size_t k)

void	sift_up (size_t k)

Member Typedef Documentation

◆ compare_type

using compare_type = Compare

Definition at line 50 of file d_ary_addressable_int_heap.hpp.

◆ key_type

using key_type = KeyType

Definition at line 49 of file d_ary_addressable_int_heap.hpp.

Constructor & Destructor Documentation

◆ DAryAddressableIntHeap() [1/3]

DAryAddressableIntHeap ( compare_type cmp = compare_type() )

inlineexplicit

Allocates an empty heap.

Definition at line 71 of file d_ary_addressable_int_heap.hpp.

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::reserve().

◆ DAryAddressableIntHeap() [2/3]

DAryAddressableIntHeap ( const DAryAddressableIntHeap< KeyType, Arity, Compare > & )

default

Copy.

◆ DAryAddressableIntHeap() [3/3]

DAryAddressableIntHeap ( DAryAddressableIntHeap< KeyType, Arity, Compare > && )

default

Move.

Member Function Documentation

◆ build_heap() [1/3]

void build_heap	(	InputIterator	first,
		InputIterator	last
	)

inline

Builds a heap from a container.

Definition at line 207 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::heapify().

◆ build_heap() [2/3]

void build_heap ( const std::vector< key_type > & keys )

inline

Builds a heap from the vector keys. Items of keys are copied.

Definition at line 213 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::heapify().

◆ build_heap() [3/3]

void build_heap ( std::vector< key_type > && keys )

inline

Builds a heap from the vector keys. Items of keys are moved.

Definition at line 220 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::empty(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::heapify().

◆ capacity()

size_t capacity ( ) const

inlinenoexcept

Returns the capacity of the heap.

Definition at line 100 of file d_ary_addressable_int_heap.hpp.

◆ clear()

void clear ( )

inline

Empties the heap.

Definition at line 91 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::not_present().

◆ contains()

bool contains ( key_type key ) const

inline

Returns true if the key key is in the heap, false otherwise.

Definition at line 201 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::not_present().

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::remove().

◆ empty()

bool empty ( ) const

inlinenoexcept

Returns true if the heap has no items, false otherwise.

Definition at line 103 of file d_ary_addressable_int_heap.hpp.

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::build_heap(), DAryAddressableIntHeap< KeyType, Arity, Compare >::sanity_check(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::top().

◆ extract_top()

key_type extract_top ( )

inline

Removes and returns the top item.

Definition at line 168 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::pop(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::top().

◆ heapify()

void heapify ( )

inlineprivate

Reorganize heap_ into a heap.

Definition at line 319 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::cmp_, DAryAddressableIntHeap< KeyType, Arity, Compare >::left(), max(), DAryAddressableIntHeap< KeyType, Arity, Compare >::not_present(), and gen_data::value.

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::build_heap(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::update_all().

◆ left()

size_t left ( size_t k ) const

inlineprivate

Returns the position of the left child of the node at position k.

Definition at line 266 of file d_ary_addressable_int_heap.hpp.

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::heapify(), DAryAddressableIntHeap< KeyType, Arity, Compare >::sanity_check(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::sift_down().

◆ not_present()

static constexpr key_type not_present ( )

inlinestaticprotected

Marks a key that is not in the heap.

Definition at line 65 of file d_ary_addressable_int_heap.hpp.

◆ operator=() [1/2]

DAryAddressableIntHeap& operator= ( const DAryAddressableIntHeap< KeyType, Arity, Compare > & )

default

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::reserve().

◆ operator=() [2/2]

DAryAddressableIntHeap& operator= ( DAryAddressableIntHeap< KeyType, Arity, Compare > && )

default

◆ parent()

size_t parent ( size_t k ) const

inlineprivate

Returns the position of the parent of the node at position k.

Definition at line 269 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::arity.

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::remove(), DAryAddressableIntHeap< KeyType, Arity, Compare >::sift_up(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::update().

◆ pop()

void pop ( )

inline

Removes the top item.

Definition at line 165 of file d_ary_addressable_int_heap.hpp.

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::extract_top().

◆ push() [1/2]

void push ( const key_type & new_key )

inline

Inserts a new item.

Definition at line 106 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::not_present(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::sift_up().

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::update().

◆ push() [2/2]

void push ( key_type && new_key )

inline

Inserts a new item.

Definition at line 123 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::not_present(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::sift_up().

◆ remove()

void remove ( key_type key )

inline

Removes the item with key key.

Definition at line 140 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::cmp_, DAryAddressableIntHeap< KeyType, Arity, Compare >::contains(), DAryAddressableIntHeap< KeyType, Arity, Compare >::not_present(), DAryAddressableIntHeap< KeyType, Arity, Compare >::parent(), DAryAddressableIntHeap< KeyType, Arity, Compare >::sift_down(), DAryAddressableIntHeap< KeyType, Arity, Compare >::sift_up(), DAryAddressableIntHeap< KeyType, Arity, Compare >::size(), and tlx::swap().

◆ reserve()

void reserve ( size_t new_size )

inline

Allocates space for new_size items.

Definition at line 75 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::DAryAddressableIntHeap(), DAryAddressableIntHeap< KeyType, Arity, Compare >::not_present(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::operator=().

◆ sanity_check()

bool sanity_check ( )

inline

For debugging: runs a BFS from the root node and verifies that the heap property is respected.

Definition at line 229 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::cmp_, DAryAddressableIntHeap< KeyType, Arity, Compare >::empty(), DAryAddressableIntHeap< KeyType, Arity, Compare >::left(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::not_present().

◆ sift_down()

void sift_down ( size_t k )

inlineprivate

Pushes the item at position k down until either it becomes a leaf or all its children have higher priority

Definition at line 287 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::arity, DAryAddressableIntHeap< KeyType, Arity, Compare >::cmp_, DAryAddressableIntHeap< KeyType, Arity, Compare >::left(), min(), and gen_data::value.

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::remove(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::update().

◆ sift_up()

void sift_up ( size_t k )

inlineprivate

Pushes the node at position k up until either it becomes the root or its parent has lower or equal priority.

Definition at line 273 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::cmp_, DAryAddressableIntHeap< KeyType, Arity, Compare >::parent(), and gen_data::value.

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::push(), DAryAddressableIntHeap< KeyType, Arity, Compare >::remove(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::update().

◆ size()

size_t size ( ) const

inlinenoexcept

Returns the number of items in the heap.

Definition at line 97 of file d_ary_addressable_int_heap.hpp.

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::remove().

◆ top()

const key_type& top ( ) const

inlinenoexcept

Returns the top item.

Definition at line 159 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::empty().

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::extract_top().

◆ update()

void update ( key_type key )

inline

Updates the priority queue after the priority associated to the item with key key has been changed; if the key key is not present in the priority queue, it will be added.

Note: if not called after a priority is changed, the behavior of the data structure is undefined.

Definition at line 187 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::cmp_, DAryAddressableIntHeap< KeyType, Arity, Compare >::not_present(), DAryAddressableIntHeap< KeyType, Arity, Compare >::parent(), DAryAddressableIntHeap< KeyType, Arity, Compare >::push(), DAryAddressableIntHeap< KeyType, Arity, Compare >::sift_down(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::sift_up().

◆ update_all()

void update_all ( )

inline

Rebuilds the heap.

Definition at line 175 of file d_ary_addressable_int_heap.hpp.

References DAryAddressableIntHeap< KeyType, Arity, Compare >::heapify().

Member Data Documentation

◆ arity

constexpr size_t arity = Arity

static

Definition at line 52 of file d_ary_addressable_int_heap.hpp.

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::parent(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::sift_down().

◆ cmp_

compare_type cmp_

protected

Compare function.

Definition at line 62 of file d_ary_addressable_int_heap.hpp.

Referenced by DAryAddressableIntHeap< KeyType, Arity, Compare >::heapify(), DAryAddressableIntHeap< KeyType, Arity, Compare >::remove(), DAryAddressableIntHeap< KeyType, Arity, Compare >::sanity_check(), DAryAddressableIntHeap< KeyType, Arity, Compare >::sift_down(), DAryAddressableIntHeap< KeyType, Arity, Compare >::sift_up(), and DAryAddressableIntHeap< KeyType, Arity, Compare >::update().

◆ handles_

std::vector<key_type> handles_

protected

Positions of the keys in the heap vector.

Definition at line 59 of file d_ary_addressable_int_heap.hpp.

◆ heap_

std::vector<key_type> heap_

protected

Cells in the heap.

Definition at line 56 of file d_ary_addressable_int_heap.hpp.

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

extlib/tlx/tlx/container/d_ary_addressable_int_heap.hpp

Detailed Description

template<typename KeyType, unsigned Arity = 2, class Compare = std::less<KeyType>> class tlx::DAryAddressableIntHeap< KeyType, Arity, Compare >

Public Types

Public Member Functions

Static Public Attributes

Static Protected Member Functions

Protected Attributes

Private Member Functions

Member Typedef Documentation

◆ compare_type

◆ key_type

Constructor & Destructor Documentation

◆ DAryAddressableIntHeap() [1/3]

◆ DAryAddressableIntHeap() [2/3]

◆ DAryAddressableIntHeap() [3/3]

Member Function Documentation

◆ build_heap() [1/3]

◆ build_heap() [2/3]

◆ build_heap() [3/3]

◆ capacity()

◆ clear()

◆ contains()

◆ empty()

◆ extract_top()

◆ heapify()

◆ left()

◆ not_present()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ parent()

◆ pop()

◆ push() [1/2]

◆ push() [2/2]

◆ remove()

◆ reserve()

◆ sanity_check()

◆ sift_down()

◆ sift_up()

◆ size()

◆ top()

◆ update()

◆ update_all()

Member Data Documentation

◆ arity

◆ cmp_

◆ handles_

◆ heap_

template<typename KeyType, unsigned Arity = 2, class Compare = std::less<KeyType>>
class tlx::DAryAddressableIntHeap< KeyType, Arity, Compare >