OpenTTD Source  20241120-master-g6d3adc6169
nodelist.hpp
Go to the documentation of this file.
1 /*
2  * This file is part of OpenTTD.
3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
6  */
7 
10 #ifndef NODELIST_HPP
11 #define NODELIST_HPP
12 
13 #include "../../misc/hashtable.hpp"
14 #include "../../misc/binaryheap.hpp"
15 
20 template <class Titem, int Thash_bits_open, int Thash_bits_closed>
21 class NodeList {
22 public:
23  using Item = Titem;
24  using Key = typename Titem::Key;
25 
26 protected:
27  std::deque<Titem> items;
31  Titem *new_node;
32 
33 public:
35  NodeList() : open_queue(2048)
36  {
37  this->new_node = nullptr;
38  }
39 
41  inline int OpenCount()
42  {
43  return this->open_nodes.Count();
44  }
45 
47  inline int ClosedCount()
48  {
49  return this->closed_nodes.Count();
50  }
51 
53  inline int TotalCount()
54  {
55  return this->items.Length();
56  }
57 
59  inline Titem &CreateNewNode()
60  {
61  if (this->new_node == nullptr) this->new_node = &this->items.emplace_back();
62  return *this->new_node;
63  }
64 
66  inline void FoundBestNode(Titem &item)
67  {
68  /* for now it is enough to invalidate m_new_node if it is our given node */
69  if (&item == this->new_node) {
70  this->new_node = nullptr;
71  }
72  /* TODO: do we need to store best nodes found in some extra list/array? Probably not now. */
73  }
74 
76  inline void InsertOpenNode(Titem &item)
77  {
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;
83  }
84  }
85 
87  inline Titem *GetBestOpenNode()
88  {
89  if (!this->open_queue.IsEmpty()) {
90  return this->open_queue.Begin();
91  }
92  return nullptr;
93  }
94 
96  inline Titem *PopBestOpenNode()
97  {
98  if (!this->open_queue.IsEmpty()) {
99  Titem *item = this->open_queue.Shift();
100  this->open_nodes.Pop(*item);
101  return item;
102  }
103  return nullptr;
104  }
105 
107  inline Titem *FindOpenNode(const Key &key)
108  {
109  return this->open_nodes.Find(key);
110  }
111 
113  inline Titem &PopOpenNode(const Key &key)
114  {
115  Titem &item = this->open_nodes.Pop(key);
116  size_t index = this->open_queue.FindIndex(item);
117  this->open_queue.Remove(index);
118  return item;
119  }
120 
122  inline void InsertClosedNode(Titem &item)
123  {
124  assert(this->open_nodes.Find(item.GetKey()) == nullptr);
125  this->closed_nodes.Push(item);
126  }
127 
129  inline Titem *FindClosedNode(const Key &key)
130  {
131  return this->closed_nodes.Find(key);
132  }
133 
135  inline Titem &ItemAt(int index)
136  {
137  return this->items[index];
138  }
139 
141  template <class D>
142  void Dump(D &dmp) const
143  {
144  dmp.WriteStructT("data", &this->items);
145  }
146 };
147 
148 #endif /* NODELIST_HPP */
void Remove(size_t index)
Remove item at given index from the priority queue.
Definition: binaryheap.hpp:233
T * Begin()
Get the smallest item in the binary tree.
Definition: binaryheap.hpp:172
void Include(T *new_item)
Insert new item into the priority queue, maintaining heap order.
Definition: binaryheap.hpp:195
size_t FindIndex(const T &item) const
Search for an item in the priority queue.
Definition: binaryheap.hpp:263
bool IsEmpty() const
Test if the priority queue is empty.
Definition: binaryheap.hpp:162
T * Shift()
Remove and return the smallest (and also first) item from the priority queue.
Definition: binaryheap.hpp:210
const Titem * Find(const Tkey &key) const
const item search
Definition: hashtable.hpp:180
void Push(Titem &new_item)
add one item - copy it from the given item
Definition: hashtable.hpp:238
int Count() const
item count
Definition: hashtable.hpp:167
Titem & Pop(const Tkey &key)
non-const item search & removal
Definition: hashtable.hpp:210
Hash table based node list multi-container class.
Definition: nodelist.hpp:21
HashTable< Titem, Thash_bits_open > open_nodes
Hash table of pointers to open nodes.
Definition: nodelist.hpp:28
CBinaryHeapT< Titem > open_queue
Priority queue of pointers to open nodes.
Definition: nodelist.hpp:30
Titem * PopBestOpenNode()
remove and return the best open node
Definition: nodelist.hpp:96
void Dump(D &dmp) const
Helper for creating output of this array.
Definition: nodelist.hpp:142
NodeList()
default constructor
Definition: nodelist.hpp:35
void InsertClosedNode(Titem &item)
close node
Definition: nodelist.hpp:122
Titem * FindClosedNode(const Key &key)
return the closed node specified by a key or nullptr if not found
Definition: nodelist.hpp:129
Titem * FindOpenNode(const Key &key)
return the open node specified by a key or nullptr if not found
Definition: nodelist.hpp:107
Titem & CreateNewNode()
allocate new data item from items
Definition: nodelist.hpp:59
int TotalCount()
return the total number of nodes.
Definition: nodelist.hpp:53
void InsertOpenNode(Titem &item)
insert given item as open node (into m_open and m_open_queue)
Definition: nodelist.hpp:76
int OpenCount()
return number of open nodes
Definition: nodelist.hpp:41
std::deque< Titem > items
Storage of the nodes.
Definition: nodelist.hpp:27
int ClosedCount()
return number of closed nodes
Definition: nodelist.hpp:47
Titem & ItemAt(int index)
Get a particular item.
Definition: nodelist.hpp:135
Titem * GetBestOpenNode()
return the best open node
Definition: nodelist.hpp:87
Titem & PopOpenNode(const Key &key)
remove and return the open node specified by a key
Definition: nodelist.hpp:113
void FoundBestNode(Titem &item)
Notify the nodelist that we don't want to discard the given node.
Definition: nodelist.hpp:66
Titem * new_node
New node under construction.
Definition: nodelist.hpp:31
HashTable< Titem, Thash_bits_closed > closed_nodes
Hash table of pointers to closed nodes.
Definition: nodelist.hpp:29