Hash table based node list multi-container class. More...

#include <nodelist.hpp>

Public Types
using	Item = Titem
using	Key = typename Titem::Key

Public Member Functions
	NodeList ()
	default constructor
int	OpenCount ()
	Get open node count.
int	ClosedCount ()
	Get closed node count.
int	TotalCount ()
	Get the total node count.
Titem &	CreateNewNode ()
	Allocate new data item from items.
void	FoundBestNode (Titem &item)
	Notify the nodelist that we don't want to discard the given node.
void	InsertOpenNode (Titem &item)
	Insert given item as open node (into open_nodes and open_queue).
Titem *	GetBestOpenNode ()
	Get the open node at the begin of the open queue.
Titem *	PopBestOpenNode ()
	Remove and return the best open node.
Titem *	FindOpenNode (const Key &key)
	Find an open node by key.
Titem &	PopOpenNode (const Key &key)
	Find and remove an open node by key.
void	InsertClosedNode (Titem &item)
	Insert the given item into the closed nodes set.
Titem *	FindClosedNode (const Key &key)
	Find a closed node by its key.
Titem &	ItemAt (int index)
	Get a particular item.
template<class D>
void	Dump (D &dmp) const
	Helper for creating output of this array.

Protected Attributes
std::deque< Titem >	items
	Storage of the nodes.
HashTable< Titem, Thash_bits_open >	open_nodes
	Hash table of pointers to open nodes.
HashTable< Titem, Thash_bits_closed >	closed_nodes
	Hash table of pointers to closed nodes.
CBinaryHeapT< Titem >	open_queue
	Priority queue of pointers to open nodes.
Titem *	new_node
	New node under construction.

Detailed Description

template<class Titem, int Thash_bits_open, int Thash_bits_closed>
class NodeList< Titem, Thash_bits_open, Thash_bits_closed >

Hash table based node list multi-container class.

Implements open list, closed list and priority queue for A-star pathfinder.

Definition at line 21 of file nodelist.hpp.

Member Typedef Documentation

◆ Item

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

using NodeList< Titem, Thash_bits_open, Thash_bits_closed >::Item = Titem

Definition at line 23 of file nodelist.hpp.

◆ Key

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

using NodeList< Titem, Thash_bits_open, Thash_bits_closed >::Key = typename Titem::Key

Definition at line 24 of file nodelist.hpp.

Constructor & Destructor Documentation

◆ NodeList()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

NodeList< Titem, Thash_bits_open, Thash_bits_closed >::NodeList ( )

inline

default constructor

Definition at line 35 of file nodelist.hpp.

Member Function Documentation

◆ ClosedCount()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

int NodeList< Titem, Thash_bits_open, Thash_bits_closed >::ClosedCount ( )

inline

Get closed node count.

Returns: Number of closed nodes.

Definition at line 53 of file nodelist.hpp.

Referenced by CYapfBaseT< Types >::FindPath().

◆ CreateNewNode()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

Titem & NodeList< Titem, Thash_bits_open, Thash_bits_closed >::CreateNewNode ( )

inline

Allocate new data item from items.

Returns: The allocated node.

Definition at line 71 of file nodelist.hpp.

Referenced by CYapfBaseT< Types >::CreateNewNode().

◆ Dump()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

template<class D>

void NodeList< Titem, Thash_bits_open, Thash_bits_closed >::Dump ( D & dmp ) const

inline

Helper for creating output of this array.

Parameters

dmp	The data to dump.

Definition at line 188 of file nodelist.hpp.

◆ FindClosedNode()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

Titem * NodeList< Titem, Thash_bits_open, Thash_bits_closed >::FindClosedNode ( const Key & key )

inline

Find a closed node by its key.

Parameters

key	The key to look for.

Returns: The closed node specified by a key or nullptr if not found.

Definition at line 168 of file nodelist.hpp.

Referenced by CYapfBaseT< Types >::AddNewNode().

◆ FindOpenNode()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

Titem * NodeList< Titem, Thash_bits_open, Thash_bits_closed >::FindOpenNode ( const Key & key )

inline

Find an open node by key.

Parameters

key	The key to look for.

Returns: The open node specified by a key or nullptr if not found.

Definition at line 135 of file nodelist.hpp.

Referenced by CYapfBaseT< Types >::AddNewNode(), and CYapfBaseT< Types >::AddStartupNode().

◆ FoundBestNode()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

void NodeList< Titem, Thash_bits_open, Thash_bits_closed >::FoundBestNode ( Titem & item )

inline

Notify the nodelist that we don't want to discard the given node.

Parameters

item	The new best node.

Definition at line 81 of file nodelist.hpp.

◆ GetBestOpenNode()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

Titem * NodeList< Titem, Thash_bits_open, Thash_bits_closed >::GetBestOpenNode ( )

inline

Get the open node at the begin of the open queue.

Returns: The best open node, or nullptr when there isn't any.

Definition at line 108 of file nodelist.hpp.

Referenced by CYapfBaseT< Types >::FindPath().

◆ InsertClosedNode()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

void NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertClosedNode ( Titem & item )

inline

Insert the given item into the closed nodes set.

Parameters

item	The item to add.

Definition at line 157 of file nodelist.hpp.

Referenced by CYapfBaseT< Types >::FindPath().

◆ InsertOpenNode()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

void NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertOpenNode ( Titem & item )

inline

Insert given item as open node (into open_nodes and open_queue).

Parameters

item	The node to add.

Definition at line 94 of file nodelist.hpp.

Referenced by CYapfBaseT< Types >::AddNewNode(), and CYapfBaseT< Types >::AddStartupNode().

◆ ItemAt()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

Titem & NodeList< Titem, Thash_bits_open, Thash_bits_closed >::ItemAt ( int index )

inline

Get a particular item.

Parameters

index The index of the item.

Returns: The item.

Definition at line 178 of file nodelist.hpp.

◆ OpenCount()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

int NodeList< Titem, Thash_bits_open, Thash_bits_closed >::OpenCount ( )

inline

Get open node count.

Returns: Number of open nodes.

Definition at line 44 of file nodelist.hpp.

Referenced by CYapfBaseT< Types >::FindPath().

◆ PopBestOpenNode()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

Titem * NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopBestOpenNode ( )

inline

Remove and return the best open node.

Returns: The best open node, or nullptr when there isn't any.

Definition at line 120 of file nodelist.hpp.

◆ PopOpenNode()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

Titem & NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopOpenNode ( const Key & key )

inline

Find and remove an open node by key.

Parameters

key	The key to look for.

Returns: The open node specified by a key.

Definition at line 145 of file nodelist.hpp.

Referenced by CYapfBaseT< Types >::AddNewNode(), and CYapfBaseT< Types >::FindPath().

◆ TotalCount()

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

int NodeList< Titem, Thash_bits_open, Thash_bits_closed >::TotalCount ( )

inline

Get the total node count.

Returns: The total number of nodes.

Definition at line 62 of file nodelist.hpp.

Field Documentation

◆ closed_nodes

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

HashTable<Titem, Thash_bits_closed> NodeList< Titem, Thash_bits_open, Thash_bits_closed >::closed_nodes

protected

Hash table of pointers to closed nodes.

Definition at line 29 of file nodelist.hpp.

◆ items

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

std::deque<Titem> NodeList< Titem, Thash_bits_open, Thash_bits_closed >::items

protected

Storage of the nodes.

Definition at line 27 of file nodelist.hpp.

◆ new_node

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

Titem* NodeList< Titem, Thash_bits_open, Thash_bits_closed >::new_node

protected

New node under construction.

Definition at line 31 of file nodelist.hpp.

◆ open_nodes

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

HashTable<Titem, Thash_bits_open> NodeList< Titem, Thash_bits_open, Thash_bits_closed >::open_nodes

protected

Hash table of pointers to open nodes.

Definition at line 28 of file nodelist.hpp.

◆ open_queue

template<class Titem, int Thash_bits_open, int Thash_bits_closed>

CBinaryHeapT<Titem> NodeList< Titem, Thash_bits_open, Thash_bits_closed >::open_queue

protected

Priority queue of pointers to open nodes.

Definition at line 30 of file nodelist.hpp.

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

src/pathfinder/yapf/nodelist.hpp

Public Types

Public Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ Item

◆ Key

Constructor & Destructor Documentation

◆ NodeList()

Member Function Documentation

◆ ClosedCount()

◆ CreateNewNode()

◆ Dump()

◆ FindClosedNode()

◆ FindOpenNode()

◆ FoundBestNode()

◆ GetBestOpenNode()

◆ InsertClosedNode()

◆ InsertOpenNode()

◆ ItemAt()

◆ OpenCount()

◆ PopBestOpenNode()

◆ PopOpenNode()

◆ TotalCount()

Field Documentation

◆ closed_nodes

◆ items

◆ new_node

◆ open_nodes

◆ open_queue