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 ()
	return number of open nodes

int	ClosedCount ()
	return number of closed nodes

int	TotalCount ()
	return the total number of nodes.

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 ()
	return the best open node

Titem *	PopBestOpenNode ()
	remove and return the best open node

Titem *	FindOpenNode (const Key &key)
	return the open node specified by a key or nullptr if not found

Titem &	PopOpenNode (const Key &key)
	remove and return the open node specified by a key

void	InsertClosedNode (Titem &item)
	close node

Titem *	FindClosedNode (const Key &key)
	return the closed node specified by a key or nullptr if not found

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

return number of closed nodes

Definition at line 47 of file nodelist.hpp.

References HashTable< Titem, Thash_bits_ >::Count().

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

◆ 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

Definition at line 59 of file nodelist.hpp.

References NodeList< Titem, Thash_bits_open, Thash_bits_closed >::new_node.

Referenced by CYapfBaseT< Types >::CreateNewNode(), and AyStar::OpenListAdd().

◆ 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.

Definition at line 142 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

return the closed node specified by a key or nullptr if not found

Definition at line 129 of file nodelist.hpp.

References HashTable< Titem, Thash_bits_ >::Find().

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

◆ 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

return the open node specified by a key or nullptr if not found

Definition at line 107 of file nodelist.hpp.

References HashTable< Titem, Thash_bits_ >::Find().

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

◆ 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.

Definition at line 66 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

return the best open node

Definition at line 87 of file nodelist.hpp.

References CBinaryHeapT< T >::Begin(), and CBinaryHeapT< T >::IsEmpty().

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

close node

Definition at line 122 of file nodelist.hpp.

References HashTable< Titem, Thash_bits_ >::Find(), and HashTable< Titem, Thash_bits_ >::Push().

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

◆ 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)

Definition at line 76 of file nodelist.hpp.

References HashTable< Titem, Thash_bits_ >::Find(), CBinaryHeapT< T >::Include(), and HashTable< Titem, Thash_bits_ >::Push().

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

◆ 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.

Definition at line 135 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

return number of open nodes

Definition at line 41 of file nodelist.hpp.

References HashTable< Titem, Thash_bits_ >::Count().

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

Definition at line 96 of file nodelist.hpp.

References CBinaryHeapT< T >::IsEmpty(), HashTable< Titem, Thash_bits_ >::Pop(), and CBinaryHeapT< T >::Shift().

Referenced by AyStar::Loop().

◆ 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

remove and return the open node specified by a key

Definition at line 113 of file nodelist.hpp.

References CBinaryHeapT< T >::FindIndex(), HashTable< Titem, Thash_bits_ >::Pop(), and CBinaryHeapT< T >::Remove().

Referenced by CYapfBaseT< Types >::AddNewNode(), AyStar::CheckTile(), 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

return the total number of nodes.

Definition at line 53 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.

Referenced by NodeList< Titem, Thash_bits_open, Thash_bits_closed >::CreateNewNode().

◆ 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