A queue that remembers every object inserted, and prevents the addition of nodes that have already been inserted even if they've been popped. More...

#include <unique_queue.h>

Collaboration diagram for HF::GraphGenerator::UniqueQueue:

Public Member Functions
bool	push (const HF::SpatialStructures::Node &p)
	Add a node to the queue if it has never previously been in the queue. More...

HF::SpatialStructures::Node	pop ()
	Remove the topmost node from the queue and return it. More...

int	size () const
	Determine how many nodes are currently in the queue. More...

HF::SpatialStructures::Node	popFromDict ()
	Retrieve the topmost node from the queue, but "forget" about it to allow it to enter again in the future. More...

bool	hasNode (const HF::SpatialStructures::Node &p) const
	Check to see if the node has ever been in the queue. More...

bool	forcePush (const HF::SpatialStructures::Node &p)
	Forcibly push a node onto the queue without checking it. Saves a hash function, but risks breaking the invariant. More...

bool	empty () const
	Tell if the queue is empty. More...

void	clearQueue ()
	Clear every node from the queue without forgetting them. More...

std::vector< SpatialStructures::Node >	popMany (int max=-1)
	Pop a set amount of nodes from the queue, and return them as a vector. More...

template<typename arr_type >
bool	PushAny (const arr_type &node)
	Call push with any type of object. More...

Private Attributes
std::queue< HF::SpatialStructures::Node >	node_queue
	The underlying queue. More...

robin_hood::unordered_map< HF::SpatialStructures::Node, int >	hashmap
	Hashmap to keep track of nodes that have entered the queue. More...

Detailed Description

A queue that remembers every object inserted, and prevents the addition of nodes that have already been inserted even if they've been popped.

Invariant: All unique nodes can only enter the queue once. After they've been popped, future attempts to push them will fail.

Remarks: This class was designed specificlaly to manage the GraphGenerator's todo list with as few hashmap calls as possible.

Todo:: This could be a useful standalone templated class.

Definition at line 29 of file unique_queue.h.

Member Function Documentation

◆ clearQueue()

void HF::GraphGenerator::UniqueQueue::clearQueue ( )

Clear every node from the queue without forgetting them.

Definition at line 57 of file unique_queue.cpp.

References node_queue.

◆ empty()

bool HF::GraphGenerator::UniqueQueue::empty ( ) const

Tell if the queue is empty.

Returns: False if there is atleast one node in the queue. True otherwise.

Definition at line 55 of file unique_queue.cpp.

References size().

Referenced by HF::GraphGenerator::GraphGenerator::CrawlGeom(), and HF::GraphGenerator::GraphGenerator::CrawlGeomParallel().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ forcePush()

bool HF::GraphGenerator::UniqueQueue::forcePush ( const HF::SpatialStructures::Node & p )

Forcibly push a node onto the queue without checking it. Saves a hash function, but risks breaking the invariant.

Parameters

p	Node to add to the end of the queue.

Returns: Always true since it cannot fail.

Definition at line 47 of file unique_queue.cpp.

References node_queue.

◆ hasNode()

bool HF::GraphGenerator::UniqueQueue::hasNode ( const HF::SpatialStructures::Node & p ) const

Check to see if the node has ever been in the queue.

Parameters

p	Node to check.

Returns: True if the node has existed in the queue.

Definition at line 43 of file unique_queue.cpp.

◆ pop()

HF::SpatialStructures::Node HF::GraphGenerator::UniqueQueue::pop ( )

Remove the topmost node from the queue and return it.

Returns: The node at the top of the queue.

See also: popFromDict for removing the topmost node and allowing it to enter again in the future.

Definition at line 25 of file unique_queue.cpp.

References node_queue.

Referenced by HF::GraphGenerator::GraphGenerator::CrawlGeom(), and popMany().

Here is the caller graph for this function:

◆ popFromDict()

HF::SpatialStructures::Node HF::GraphGenerator::UniqueQueue::popFromDict ( )

Retrieve the topmost node from the queue, but "forget" about it to allow it to enter again in the future.

Returns: Topmost node in the queue.

This sets the node's value to 0 in the hashmap, making it behave exactly like a node that has never been seen by the queue.

Definition at line 34 of file unique_queue.cpp.

References node_queue.

◆ popMany()

std::vector< SpatialStructures::Node > HF::GraphGenerator::UniqueQueue::popMany ( int max = -1 )

Pop a set amount of nodes from the queue, and return them as a vector.

Parameters

max	Stop after popping this amount of nodes.

Use this to quickly pop several nodes without having to make a function call for each.

Todo:: Opetion to pop every node by setting max to -1.

Definition at line 64 of file unique_queue.cpp.

References node_queue, pop(), and size().

Referenced by HF::GraphGenerator::GraphGenerator::CrawlGeomParallel().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ push()

bool HF::GraphGenerator::UniqueQueue::push ( const HF::SpatialStructures::Node & p )

Add a node to the queue if it has never previously been in the queue.

Parameters

p	Node to add to the queue.

Returns: False if the node wasn't added, true if it was

If the node has a value of 1 in hashmap, then the node is ignored. If the node doesn't already exist in the hashmap, the call to hashmap[p] will automatically create an entry with a value of 0, indicating that the node hasn't been seen before.

Definition at line 11 of file unique_queue.cpp.

References node_queue.

Referenced by HF::GraphGenerator::GraphGenerator::CrawlGeomParallel(), and PushAny().

Here is the caller graph for this function:

◆ PushAny()

template<typename arr_type >

bool HF::GraphGenerator::UniqueQueue::PushAny ( const arr_type & node )

inline

Call push with any type of object.

Parameters

p	Node to add to the queue.

Returns: False if the node wasn't added, true if it was.

If the node has a value of 1 in hashmap, then the node is ignored. If the node doesn't already exist in the hashmap, the call to hashmap[p] will automatically create an entry with a value of 0, indicating that the node hasn't been seen before.

Definition at line 118 of file unique_queue.h.

References push().

Referenced by HF::GraphGenerator::GraphGenerator::CrawlGeom(), and HF::GraphGenerator::GraphGenerator::IMPL_BuildNetwork().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ size()

int HF::GraphGenerator::UniqueQueue::size ( ) const

Determine how many nodes are currently in the queue.

Returns: The number of nodes in the queue

Definition at line 32 of file unique_queue.cpp.

References node_queue.

Referenced by HF::GraphGenerator::GraphGenerator::CrawlGeomParallel(), empty(), and popMany().

Here is the caller graph for this function:

Member Data Documentation

◆ hashmap

robin_hood::unordered_map<HF::SpatialStructures::Node, int> HF::GraphGenerator::UniqueQueue::hashmap

private

Hashmap to keep track of nodes that have entered the queue.

Values of 0 indicate that a node has never been pushed before. Values of 1 indicate that a node has already been in the hashmap previously.

Definition at line 38 of file unique_queue.h.

◆ node_queue

std::queue<HF::SpatialStructures::Node> HF::GraphGenerator::UniqueQueue::node_queue

private

The underlying queue.

Definition at line 31 of file unique_queue.h.

Referenced by clearQueue(), forcePush(), pop(), popFromDict(), popMany(), push(), and size().

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

Cpp/analysismethods/src/unique_queue.h
Cpp/analysismethods/src/unique_queue.cpp

Public Member Functions

Private Attributes

Detailed Description

Member Function Documentation

◆ clearQueue()

◆ empty()

◆ forcePush()

◆ hasNode()

◆ pop()

◆ popFromDict()

◆ popMany()

◆ push()

◆ PushAny()

◆ size()

Member Data Documentation

◆ hashmap

◆ node_queue