OpenTTD Source  1.11.0-beta2
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/array.hpp"
14 #include "../../misc/hashtable.hpp"
15 #include "../../misc/binaryheap.hpp"
16 
22 template <class Titem_, int Thash_bits_open_, int Thash_bits_closed_>
24 public:
25  typedef Titem_ Titem;
26  typedef typename Titem_::Key Key;
31 
32 protected:
38 
39 public:
42  {
43  m_new_node = nullptr;
44  }
45 
48  {
49  }
50 
52  inline int OpenCount()
53  {
54  return m_open.Count();
55  }
56 
58  inline int ClosedCount()
59  {
60  return m_closed.Count();
61  }
62 
64  inline Titem_ *CreateNewNode()
65  {
66  if (m_new_node == nullptr) m_new_node = m_arr.AppendC();
67  return m_new_node;
68  }
69 
71  inline void FoundBestNode(Titem_ &item)
72  {
73  /* for now it is enough to invalidate m_new_node if it is our given node */
74  if (&item == m_new_node) {
75  m_new_node = nullptr;
76  }
77  /* TODO: do we need to store best nodes found in some extra list/array? Probably not now. */
78  }
79 
81  inline void InsertOpenNode(Titem_ &item)
82  {
83  assert(m_closed.Find(item.GetKey()) == nullptr);
84  m_open.Push(item);
85  m_open_queue.Include(&item);
86  if (&item == m_new_node) {
87  m_new_node = nullptr;
88  }
89  }
90 
92  inline Titem_ *GetBestOpenNode()
93  {
94  if (!m_open_queue.IsEmpty()) {
95  return m_open_queue.Begin();
96  }
97  return nullptr;
98  }
99 
101  inline Titem_ *PopBestOpenNode()
102  {
103  if (!m_open_queue.IsEmpty()) {
104  Titem_ *item = m_open_queue.Shift();
105  m_open.Pop(*item);
106  return item;
107  }
108  return nullptr;
109  }
110 
112  inline Titem_ *FindOpenNode(const Key &key)
113  {
114  Titem_ *item = m_open.Find(key);
115  return item;
116  }
117 
119  inline Titem_& PopOpenNode(const Key &key)
120  {
121  Titem_ &item = m_open.Pop(key);
122  uint idxPop = m_open_queue.FindIndex(item);
123  m_open_queue.Remove(idxPop);
124  return item;
125  }
126 
128  inline void InsertClosedNode(Titem_ &item)
129  {
130  assert(m_open.Find(item.GetKey()) == nullptr);
131  m_closed.Push(item);
132  }
133 
135  inline Titem_ *FindClosedNode(const Key &key)
136  {
137  Titem_ *item = m_closed.Find(key);
138  return item;
139  }
140 
142  inline int TotalCount()
143  {
144  return m_arr.Length();
145  }
146 
148  inline Titem_& ItemAt(int idx)
149  {
150  return m_arr[idx];
151  }
152 
154  template <class D> void Dump(D &dmp) const
155  {
156  dmp.WriteStructT("m_arr", &m_arr);
157  }
158 };
159 
160 #endif /* NODELIST_HPP */
CNodeList_HashTableT::GetBestOpenNode
Titem_ * GetBestOpenNode()
return the best open node
Definition: nodelist.hpp:92
CBinaryHeapT::Shift
T * Shift()
Remove and return the smallest (and also first) item from the priority queue.
Definition: binaryheap.hpp:232
CNodeList_HashTableT::CItemArray
SmallArray< Titem_, 65536, 256 > CItemArray
Type that we will use as item container.
Definition: nodelist.hpp:27
CNodeList_HashTableT::m_arr
CItemArray m_arr
Here we store full item data (Titem_).
Definition: nodelist.hpp:33
CNodeList_HashTableT::PopOpenNode
Titem_ & PopOpenNode(const Key &key)
remove and return the open node specified by a key
Definition: nodelist.hpp:119
CHashTableT::Pop
Titem_ & Pop(const Tkey &key)
non-const item search & removal
Definition: hashtable.hpp:219
CNodeList_HashTableT::OpenCount
int OpenCount()
return number of open nodes
Definition: nodelist.hpp:52
SmallArray::Length
uint Length() const
Return actual number of items.
Definition: array.hpp:54
CBinaryHeapT::IsEmpty
bool IsEmpty() const
Test if the priority queue is empty.
Definition: binaryheap.hpp:168
CNodeList_HashTableT::Dump
void Dump(D &dmp) const
Helper for creating output of this array.
Definition: nodelist.hpp:154
CNodeList_HashTableT::FindClosedNode
Titem_ * FindClosedNode(const Key &key)
return the closed node specified by a key or nullptr if not found
Definition: nodelist.hpp:135
CNodeList_HashTableT::COpenList
CHashTableT< Titem_, Thash_bits_open_ > COpenList
How pointers to open nodes will be stored.
Definition: nodelist.hpp:28
CHashTableT::Find
const Titem_ * Find(const Tkey &key) const
const item search
Definition: hashtable.hpp:189
CNodeList_HashTableT::m_closed
CClosedList m_closed
Hash table of pointers to closed item data.
Definition: nodelist.hpp:35
CNodeList_HashTableT::ClosedCount
int ClosedCount()
return number of closed nodes
Definition: nodelist.hpp:58
CNodeList_HashTableT::m_new_node
Titem * m_new_node
New open node under construction.
Definition: nodelist.hpp:37
CNodeList_HashTableT::m_open_queue
CPriorityQueue m_open_queue
Priority queue of pointers to open item data.
Definition: nodelist.hpp:36
CBinaryHeapT< Titem_ >
CNodeList_HashTableT::FoundBestNode
void FoundBestNode(Titem_ &item)
Notify the nodelist that we don't want to discard the given node.
Definition: nodelist.hpp:71
CNodeList_HashTableT
Hash table based node list multi-container class.
Definition: nodelist.hpp:23
CHashTableT::Count
int Count() const
item count
Definition: hashtable.hpp:177
CNodeList_HashTableT::ItemAt
Titem_ & ItemAt(int idx)
Get a particular item.
Definition: nodelist.hpp:148
CNodeList_HashTableT::Key
Titem_::Key Key
Make Titem_::Key a property of this class.
Definition: nodelist.hpp:26
SmallArray::AppendC
T * AppendC()
allocate and construct new item
Definition: array.hpp:80
CNodeList_HashTableT::InsertClosedNode
void InsertClosedNode(Titem_ &item)
close node
Definition: nodelist.hpp:128
SmallArray< Titem_, 65536, 256 >
CNodeList_HashTableT::FindOpenNode
Titem_ * FindOpenNode(const Key &key)
return the open node specified by a key or nullptr if not found
Definition: nodelist.hpp:112
CNodeList_HashTableT::PopBestOpenNode
Titem_ * PopBestOpenNode()
remove and return the best open node
Definition: nodelist.hpp:101
CBinaryHeapT::FindIndex
uint FindIndex(const T &item) const
Search for an item in the priority queue.
Definition: binaryheap.hpp:282
CNodeList_HashTableT::InsertOpenNode
void InsertOpenNode(Titem_ &item)
insert given item as open node (into m_open and m_open_queue)
Definition: nodelist.hpp:81
CNodeList_HashTableT::~CNodeList_HashTableT
~CNodeList_HashTableT()
destructor
Definition: nodelist.hpp:47
CNodeList_HashTableT::TotalCount
int TotalCount()
The number of items.
Definition: nodelist.hpp:142
CNodeList_HashTableT::m_open
COpenList m_open
Hash table of pointers to open item data.
Definition: nodelist.hpp:34
CBinaryHeapT::Include
void Include(T *new_item)
Insert new item into the priority queue, maintaining heap order.
Definition: binaryheap.hpp:211
CNodeList_HashTableT::CClosedList
CHashTableT< Titem_, Thash_bits_closed_ > CClosedList
How pointers to closed nodes will be stored.
Definition: nodelist.hpp:29
CBinaryHeapT::Remove
void Remove(uint index)
Remove item at given index from the priority queue.
Definition: binaryheap.hpp:254
CNodeList_HashTableT::Titem
Titem_ Titem
Make #Titem_ visible from outside of class.
Definition: nodelist.hpp:25
CNodeList_HashTableT::CPriorityQueue
CBinaryHeapT< Titem_ > CPriorityQueue
How the priority queue will be managed.
Definition: nodelist.hpp:30
CBinaryHeapT::Begin
T * Begin()
Get the smallest item in the binary tree.
Definition: binaryheap.hpp:188
CNodeList_HashTableT::CreateNewNode
Titem_ * CreateNewNode()
allocate new data item from m_arr
Definition: nodelist.hpp:64
CHashTableT::Push
void Push(Titem_ &new_item)
add one item - copy it from the given item
Definition: hashtable.hpp:247
CHashTableT< Titem_, Thash_bits_open_ >
CNodeList_HashTableT::CNodeList_HashTableT
CNodeList_HashTableT()
default constructor
Definition: nodelist.hpp:41