13#include "../../misc/hashtable.hpp"
14#include "../../misc/binaryheap.hpp"
20template <
class Titem,
int Thash_bits_open,
int Thash_bits_closed>
24 using Key =
typename Titem::Key;
37 this->new_node =
nullptr;
43 return this->open_nodes.
Count();
49 return this->closed_nodes.
Count();
55 return this->items.Length();
61 if (this->new_node ==
nullptr) this->new_node = &this->items.emplace_back();
69 if (&item == this->new_node) {
70 this->new_node =
nullptr;
78 assert(this->closed_nodes.
Find(item.GetKey()) ==
nullptr);
79 this->open_nodes.
Push(item);
80 this->open_queue.
Include(&item);
81 if (&item == this->new_node) {
82 this->new_node =
nullptr;
89 if (!this->open_queue.
IsEmpty()) {
90 return this->open_queue.
Begin();
98 if (!this->open_queue.
IsEmpty()) {
99 Titem *item = this->open_queue.
Shift();
100 this->open_nodes.
Pop(*item);
109 return this->open_nodes.
Find(key);
115 Titem &item = this->open_nodes.
Pop(key);
116 size_t index = this->open_queue.
FindIndex(item);
117 this->open_queue.
Remove(index);
124 assert(this->open_nodes.
Find(item.GetKey()) ==
nullptr);
125 this->closed_nodes.
Push(item);
131 return this->closed_nodes.
Find(key);
137 return this->items[index];
144 dmp.WriteStructT(
"data", &this->items);
Binary Heap as C++ template.
void Remove(size_t index)
Remove item at given index from the priority queue.
void Include(T *new_item)
Insert new item into the priority queue, maintaining heap order.
size_t FindIndex(const T &item) const
Search for an item in the priority queue.
T * Shift()
Remove and return the smallest (and also first) item from the priority queue.
bool IsEmpty() const
Test if the priority queue is empty.
T * Begin()
Get the smallest item in the binary tree.
class HashTable<Titem, HASH_BITS> - simple hash table of pointers allocated elsewhere.
void Push(Titem &new_item)
add one item - copy it from the given item
const Titem * Find(const Tkey &key) const
const item search
int Count() const
item count
Titem & Pop(const Tkey &key)
non-const item search & removal
Hash table based node list multi-container class.
HashTable< Titem, Thash_bits_open > open_nodes
Hash table of pointers to open nodes.
CBinaryHeapT< Titem > open_queue
Priority queue of pointers to open nodes.
void Dump(D &dmp) const
Helper for creating output of this array.
NodeList()
default constructor
void InsertClosedNode(Titem &item)
close node
Titem * FindClosedNode(const Key &key)
return the closed node specified by a key or nullptr if not found
int TotalCount()
return the total number of nodes.
void InsertOpenNode(Titem &item)
insert given item as open node (into m_open and m_open_queue)
int OpenCount()
return number of open nodes
Titem * PopBestOpenNode()
remove and return the best open node
std::deque< Titem > items
Storage of the nodes.
int ClosedCount()
return number of closed nodes
Titem & CreateNewNode()
allocate new data item from items
Titem * GetBestOpenNode()
return the best open node
Titem & ItemAt(int index)
Get a particular item.
Titem & PopOpenNode(const Key &key)
remove and return the open node specified by a key
void FoundBestNode(Titem &item)
Notify the nodelist that we don't want to discard the given node.
Titem * new_node
New node under construction.
HashTable< Titem, Thash_bits_closed > closed_nodes
Hash table of pointers to closed nodes.
Titem * FindOpenNode(const Key &key)
return the open node specified by a key or nullptr if not found