#include <id_set_queue.h>

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

bool	contains (unsigned id) const
	Checks whether an ID is in the queue.

bool	empty () const
	Checks whether the queue contains any element.

unsigned	id_count () const

	IDSetMinQueue ()

	IDSetMinQueue (unsigned n)
	The queue may contain IDs from 0 to n-1.

unsigned	peek () const

unsigned	pop ()

void	push (unsigned id)

Static Private Member Functions
static unsigned	is_larger_child (unsigned x)
	True if other_child(x) < x. Only works if x != root.

static unsigned	is_smaller_child (unsigned x)
	True if other_child(x) > x. Only works if x != root.

static unsigned	larger_child (unsigned x)
	Returns the node y such that parent(y) == x and y > other_child(y).

static unsigned	other_child (unsigned x)
	Maps a node onto its sibling. Only works if x != root.

static unsigned	parent (unsigned x)
	Maps a node onto its parent. Only works if x != root.

static unsigned	smaller_child (unsigned x)
	Returns the node y such that parent(y) == x and y < other_child(y).

static unsigned	smallest_two_power_no_smaller_than (unsigned x)

Private Attributes
std::vector< bool >	data

unsigned	max_number_of_ids

unsigned	min_id

unsigned	offset

Static Private Attributes
static const unsigned	root = 1

Detailed Description

This is min queue that can only contain IDs from a given range. IDs are compared by their value. Ids in the queue cannot be duplicated.

Definition at line 14 of file id_set_queue.h.

Constructor & Destructor Documentation

◆ IDSetMinQueue() [1/2]

RoutingKit::IDSetMinQueue::IDSetMinQueue ( )

inline

Definition at line 108 of file id_set_queue.h.

◆ IDSetMinQueue() [2/2]

RoutingKit::IDSetMinQueue::IDSetMinQueue ( unsigned n )

inlineexplicit

The queue may contain IDs from 0 to n-1.

Definition at line 111 of file id_set_queue.h.

Member Function Documentation

◆ clear()

void RoutingKit::IDSetMinQueue::clear ( )

inline

Removes all elements from the queue.

Definition at line 218 of file id_set_queue.h.

References empty(), and pop().

Referenced by RoutingKit::CustomizableContractionHierarchyPartialCustomization::reset(), and RoutingKit::CustomizableContractionHierarchyPartialCustomization::reset().

Here is the caller graph for this function:

◆ contains()

bool RoutingKit::IDSetMinQueue::contains ( unsigned id ) const

inline

Checks whether an ID is in the queue.

Definition at line 153 of file id_set_queue.h.

References data, id_count(), and offset.

◆ empty()

bool RoutingKit::IDSetMinQueue::empty ( ) const

inline

Checks whether the queue contains any element.

Definition at line 159 of file id_set_queue.h.

References RoutingKit::invalid_id, and min_id.

Referenced by clear(), RoutingKit::CustomizableContractionHierarchyPartialCustomization::customize(), and pop().

Here is the caller graph for this function:

◆ id_count()

unsigned RoutingKit::IDSetMinQueue::id_count ( ) const

inline

Definition at line 118 of file id_set_queue.h.

References max_number_of_ids.

Referenced by contains(), push(), and RoutingKit::CustomizableContractionHierarchyPartialCustomization::reset().

Here is the caller graph for this function:

◆ is_larger_child()

static unsigned RoutingKit::IDSetMinQueue::is_larger_child ( unsigned x )

inlinestaticprivate

True if other_child(x) < x. Only works if x != root.

Definition at line 79 of file id_set_queue.h.

Referenced by is_smaller_child().

Here is the caller graph for this function:

◆ is_smaller_child()

static unsigned RoutingKit::IDSetMinQueue::is_smaller_child ( unsigned x )

inlinestaticprivate

True if other_child(x) > x. Only works if x != root.

Definition at line 84 of file id_set_queue.h.

References is_larger_child().

Referenced by pop().

Here is the caller graph for this function:

◆ larger_child()

static unsigned RoutingKit::IDSetMinQueue::larger_child ( unsigned x )

inlinestaticprivate

Returns the node y such that parent(y) == x and y > other_child(y).

Definition at line 94 of file id_set_queue.h.

◆ other_child()

static unsigned RoutingKit::IDSetMinQueue::other_child ( unsigned x )

inlinestaticprivate

Maps a node onto its sibling. Only works if x != root.

Definition at line 74 of file id_set_queue.h.

Referenced by pop().

Here is the caller graph for this function:

◆ parent()

static unsigned RoutingKit::IDSetMinQueue::parent ( unsigned x )

inlinestaticprivate

Maps a node onto its parent. Only works if x != root.

Definition at line 69 of file id_set_queue.h.

Referenced by pop(), and push().

Here is the caller graph for this function:

◆ peek()

unsigned RoutingKit::IDSetMinQueue::peek ( ) const

inline

Returns the smallest ID in the queue without removing it. Returns invalid_id if the queue is empty.

Definition at line 165 of file id_set_queue.h.

References min_id.

◆ pop()

unsigned RoutingKit::IDSetMinQueue::pop ( )

inline

Returns the smallest ID in the queue and removes it. Returns invalid_id if the queue is empty.

Definition at line 171 of file id_set_queue.h.

References data, empty(), RoutingKit::invalid_id, is_smaller_child(), min_id, offset, other_child(), parent(), root, and smaller_child().

Referenced by clear(), and RoutingKit::CustomizableContractionHierarchyPartialCustomization::customize().

Here is the caller graph for this function:

◆ push()

void RoutingKit::IDSetMinQueue::push ( unsigned id )

inline

Adds an ID to the queue. If the ID is already in the queue, then nothing happens.

Definition at line 124 of file id_set_queue.h.

References data, id_count(), RoutingKit::invalid_id, min_id, RoutingKit::min_to(), offset, parent(), and root.

Referenced by RoutingKit::CustomizableContractionHierarchyPartialCustomization::customize(), and RoutingKit::CustomizableContractionHierarchyPartialCustomization::update_arc().

Here is the caller graph for this function:

◆ smaller_child()

static unsigned RoutingKit::IDSetMinQueue::smaller_child ( unsigned x )

inlinestaticprivate

Returns the node y such that parent(y) == x and y < other_child(y).

Definition at line 89 of file id_set_queue.h.

Referenced by pop().

Here is the caller graph for this function:

◆ smallest_two_power_no_smaller_than()

static unsigned RoutingKit::IDSetMinQueue::smallest_two_power_no_smaller_than ( unsigned x )

inlinestaticprivate

Definition at line 98 of file id_set_queue.h.

Field Documentation

◆ data

std::vector<bool> RoutingKit::IDSetMinQueue::data

private

Definition at line 228 of file id_set_queue.h.

Referenced by contains(), pop(), and push().

◆ max_number_of_ids

unsigned RoutingKit::IDSetMinQueue::max_number_of_ids

private

Definition at line 225 of file id_set_queue.h.

Referenced by id_count().

◆ min_id

unsigned RoutingKit::IDSetMinQueue::min_id

private

Definition at line 226 of file id_set_queue.h.

Referenced by empty(), peek(), pop(), and push().

◆ offset

unsigned RoutingKit::IDSetMinQueue::offset

private

Definition at line 227 of file id_set_queue.h.

Referenced by contains(), pop(), and push().

◆ root

const unsigned RoutingKit::IDSetMinQueue::root = 1

staticprivate

Definition at line 66 of file id_set_queue.h.

Referenced by pop(), and push().

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

id_set_queue.h

Public Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ IDSetMinQueue() [1/2]

◆ IDSetMinQueue() [2/2]

Member Function Documentation

◆ clear()

◆ contains()

◆ empty()

◆ id_count()

◆ is_larger_child()

◆ is_smaller_child()

◆ larger_child()

◆ other_child()

◆ parent()

◆ peek()

◆ pop()

◆ push()

◆ smaller_child()

◆ smallest_two_power_no_smaller_than()

Field Documentation

◆ data

◆ max_number_of_ids

◆ min_id

◆ offset

◆ root