#include <id_queue.h>

Public Member Functions
void	clear ()
	Removes all elements from the queue.

bool	contains_id (unsigned id)
	Checks whether an element is in the queue.

bool	decrease_key (IDKeyPair p)

bool	empty () const
	Returns whether the queue is empty. Equivalent to checking whether size() returns 0.

unsigned	get_key (unsigned id) const

unsigned	id_count () const
	Returns the id_count value passed to the constructor.

bool	increase_key (IDKeyPair p)

	MinIDQueue ()

	MinIDQueue (unsigned id_count)

IDKeyPair	peek () const
	Returns the smallest element key pair without removing it from the queue.

IDKeyPair	pop ()
	Returns the smallest element key pair and removes it form the queue.

void	push (IDKeyPair p)

unsigned	size () const
	Returns the number of elements in the queue.

Private Member Functions
void	move_down_in_tree (unsigned pos)

void	move_up_in_tree (unsigned pos)

Private Attributes
std::vector< IDKeyPair >	heap

unsigned	heap_size

std::vector< unsigned >	id_pos

Static Private Attributes
static const unsigned	tree_arity = 4

Friends
void	swap (MinIDQueue &l, MinIDQueue &r)

Detailed Description

A priority queue where the elements are IDs from 0 to id_count-1 where id_count is a number that is set in the constructor. The elements are sorted by integer keys.

Definition at line 18 of file id_queue.h.

Constructor & Destructor Documentation

◆ MinIDQueue() [1/2]

RoutingKit::MinIDQueue::MinIDQueue ( )

inline

Definition at line 22 of file id_queue.h.

◆ MinIDQueue() [2/2]

RoutingKit::MinIDQueue::MinIDQueue ( unsigned id_count )

inlineexplicit

Definition at line 24 of file id_queue.h.

Member Function Documentation

◆ clear()

void RoutingKit::MinIDQueue::clear ( )

inline

Removes all elements from the queue.

Definition at line 51 of file id_queue.h.

References heap, heap_size, id_pos, and RoutingKit::invalid_id.

Referenced by RoutingKit::ContractionHierarchyQuery::reset(), RoutingKit::ContractionHierarchyQuery::reset_source(), and RoutingKit::ContractionHierarchyQuery::reset_target().

Here is the caller graph for this function:

◆ contains_id()

bool RoutingKit::MinIDQueue::contains_id ( unsigned id )

inline

Checks whether an element is in the queue.

Definition at line 45 of file id_queue.h.

References id_count(), id_pos, and RoutingKit::invalid_id.

Referenced by RoutingKit::ContractionHierarchyQuery::add_source(), RoutingKit::ContractionHierarchyQuery::add_target(), decrease_key(), increase_key(), and push().

Here is the caller graph for this function:

◆ decrease_key()

bool RoutingKit::MinIDQueue::decrease_key ( IDKeyPair p )

inline

Updates the key of an element if the new key is smaller than the old key. Does nothing if the new key is larger. Undefined if the element is not part of the queue.

Definition at line 107 of file id_queue.h.

References contains_id(), heap, RoutingKit::IDKeyPair::id, id_count(), id_pos, RoutingKit::IDKeyPair::key, and move_up_in_tree().

Referenced by RoutingKit::ContractionHierarchyQuery::add_source(), and RoutingKit::ContractionHierarchyQuery::add_target().

Here is the caller graph for this function:

◆ empty()

bool RoutingKit::MinIDQueue::empty ( ) const

inline

Returns whether the queue is empty. Equivalent to checking whether size() returns 0.

Definition at line 30 of file id_queue.h.

References heap_size.

Referenced by peek(), pop(), RoutingKit::ContractionHierarchyQuery::run(), RoutingKit::ContractionHierarchyQuery::run_to_pinned_sources(), and RoutingKit::ContractionHierarchyQuery::run_to_pinned_targets().

Here is the caller graph for this function:

◆ get_key()

unsigned RoutingKit::MinIDQueue::get_key ( unsigned id ) const

inline

Returns the current key of an element. Undefined if the element is not part of the queue.

Definition at line 66 of file id_queue.h.

References heap, id_count(), id_pos, and RoutingKit::invalid_id.

◆ id_count()

unsigned RoutingKit::MinIDQueue::id_count ( ) const

inline

Returns the id_count value passed to the constructor.

Definition at line 40 of file id_queue.h.

References id_pos.

Referenced by contains_id(), decrease_key(), get_key(), increase_key(), and push().

Here is the caller graph for this function:

◆ increase_key()

bool RoutingKit::MinIDQueue::increase_key ( IDKeyPair p )

inline

Updates the key of an element if the new key is larger than the old key. Does nothing if the new key is smaller. Undefined if the element is not part of the queue.

Definition at line 125 of file id_queue.h.

References contains_id(), heap, RoutingKit::IDKeyPair::id, id_count(), id_pos, RoutingKit::IDKeyPair::key, and move_down_in_tree().

◆ move_down_in_tree()

void RoutingKit::MinIDQueue::move_down_in_tree ( unsigned pos )

inlineprivate

Definition at line 152 of file id_queue.h.

References heap, heap_size, id_pos, std::swap(), and tree_arity.

Referenced by increase_key(), and pop().

Here is the caller graph for this function:

◆ move_up_in_tree()

void RoutingKit::MinIDQueue::move_up_in_tree ( unsigned pos )

inlineprivate

Definition at line 141 of file id_queue.h.

References heap, id_pos, std::swap(), and tree_arity.

Referenced by decrease_key(), and push().

Here is the caller graph for this function:

◆ peek()

IDKeyPair RoutingKit::MinIDQueue::peek ( ) const

inline

Returns the smallest element key pair without removing it from the queue.

Definition at line 73 of file id_queue.h.

References empty(), and heap.

Referenced by RoutingKit::ContractionHierarchyQuery::run().

Here is the caller graph for this function:

◆ pop()

IDKeyPair RoutingKit::MinIDQueue::pop ( )

inline

Returns the smallest element key pair and removes it form the queue.

Definition at line 79 of file id_queue.h.

References empty(), heap, heap_size, id_pos, RoutingKit::invalid_id, move_down_in_tree(), and std::swap().

◆ push()

void RoutingKit::MinIDQueue::push ( IDKeyPair p )

inline

Inserts a element key pair. Undefined if the element is part of the queue.

Definition at line 93 of file id_queue.h.

References contains_id(), heap, heap_size, RoutingKit::IDKeyPair::id, id_count(), id_pos, and move_up_in_tree().

Referenced by RoutingKit::ContractionHierarchyQuery::add_source(), and RoutingKit::ContractionHierarchyQuery::add_target().

Here is the caller graph for this function:

◆ size()

unsigned RoutingKit::MinIDQueue::size ( ) const

inline

Returns the number of elements in the queue.

Definition at line 35 of file id_queue.h.

References heap_size.

Friends And Related Symbol Documentation

◆ swap

void swap	(	MinIDQueue &	l,
		MinIDQueue &	r
	)

friend

Definition at line 57 of file id_queue.h.

Field Documentation

◆ heap

std::vector<IDKeyPair> RoutingKit::MinIDQueue::heap

private

Definition at line 174 of file id_queue.h.

Referenced by clear(), decrease_key(), get_key(), increase_key(), move_down_in_tree(), move_up_in_tree(), peek(), pop(), and push().

◆ heap_size

unsigned RoutingKit::MinIDQueue::heap_size

private

Definition at line 176 of file id_queue.h.

Referenced by clear(), empty(), move_down_in_tree(), pop(), push(), and size().

◆ id_pos

std::vector<unsigned> RoutingKit::MinIDQueue::id_pos

private

Definition at line 173 of file id_queue.h.

Referenced by clear(), contains_id(), decrease_key(), get_key(), id_count(), increase_key(), move_down_in_tree(), move_up_in_tree(), pop(), and push().

◆ tree_arity

const unsigned RoutingKit::MinIDQueue::tree_arity = 4

staticprivate

Definition at line 20 of file id_queue.h.

Referenced by move_down_in_tree(), and move_up_in_tree().

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

id_queue.h

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ MinIDQueue() [1/2]

◆ MinIDQueue() [2/2]

Member Function Documentation

◆ clear()

◆ contains_id()

◆ decrease_key()

◆ empty()

◆ get_key()

◆ id_count()

◆ increase_key()

◆ move_down_in_tree()

◆ move_up_in_tree()

◆ peek()

◆ pop()

◆ push()

◆ size()

Friends And Related Symbol Documentation

◆ swap

Field Documentation

◆ heap

◆ heap_size

◆ id_pos

◆ tree_arity