Files
@ r19164:fb28ade150af
Branch filter:
Location: cpp/openttd-patchpack/source/src/pathfinder/yapf/nodelist.hpp
r19164:fb28ade150af
4.5 KiB
text/x-c++hdr
(svn r24052) -Fix (r23883) [FS#5107]: Imported GRF sounds were inserted into the wrong slots.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 | /* $Id$ */
/*
* This file is part of OpenTTD.
* 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.
* 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.
* 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/>.
*/
/** @file nodelist.hpp List of nodes used for the A-star pathfinder. */
#ifndef NODELIST_HPP
#define NODELIST_HPP
#include "../../misc/array.hpp"
#include "../../misc/hashtable.hpp"
#include "../../misc/binaryheap.hpp"
/**
* Hash table based node list multi-container class.
* Implements open list, closed list and priority queue for A-star
* path finder.
*/
template <class Titem_, int Thash_bits_open_, int Thash_bits_closed_>
class CNodeList_HashTableT {
public:
/** make Titem_ visible from outside of class */
typedef Titem_ Titem;
/** make Titem_::Key a property of HashTable */
typedef typename Titem_::Key Key;
/** type that we will use as item container */
typedef SmallArray<Titem_, 65536, 256> CItemArray;
/** how pointers to open nodes will be stored */
typedef CHashTableT<Titem_, Thash_bits_open_ > COpenList;
/** how pointers to closed nodes will be stored */
typedef CHashTableT<Titem_, Thash_bits_closed_> CClosedList;
/** how the priority queue will be managed */
typedef CBinaryHeapT<Titem_> CPriorityQueue;
protected:
/** here we store full item data (Titem_) */
CItemArray m_arr;
/** hash table of pointers to open item data */
COpenList m_open;
/** hash table of pointers to closed item data */
CClosedList m_closed;
/** priority queue of pointers to open item data */
CPriorityQueue m_open_queue;
/** new open node under construction */
Titem *m_new_node;
public:
/** default constructor */
CNodeList_HashTableT()
: m_open_queue(2048)
{
m_new_node = NULL;
}
/** destructor */
~CNodeList_HashTableT()
{
}
/** return number of open nodes */
inline int OpenCount()
{
return m_open.Count();
}
/** return number of closed nodes */
inline int ClosedCount()
{
return m_closed.Count();
}
/** allocate new data item from m_arr */
inline Titem_ *CreateNewNode()
{
if (m_new_node == NULL) m_new_node = m_arr.AppendC();
return m_new_node;
}
/** Notify the nodelist that we don't want to discard the given node. */
inline void FoundBestNode(Titem_& item)
{
/* for now it is enough to invalidate m_new_node if it is our given node */
if (&item == m_new_node) {
m_new_node = NULL;
}
/* TODO: do we need to store best nodes found in some extra list/array? Probably not now. */
}
/** insert given item as open node (into m_open and m_open_queue) */
inline void InsertOpenNode(Titem_& item)
{
assert(m_closed.Find(item.GetKey()) == NULL);
m_open.Push(item);
m_open_queue.Include(&item);
if (&item == m_new_node) {
m_new_node = NULL;
}
}
/** return the best open node */
inline Titem_ *GetBestOpenNode()
{
if (!m_open_queue.IsEmpty()) {
return m_open_queue.Begin();
}
return NULL;
}
/** remove and return the best open node */
inline Titem_ *PopBestOpenNode()
{
if (!m_open_queue.IsEmpty()) {
Titem_ *item = m_open_queue.Shift();
m_open.Pop(*item);
return item;
}
return NULL;
}
/** return the open node specified by a key or NULL if not found */
inline Titem_ *FindOpenNode(const Key& key)
{
Titem_ *item = m_open.Find(key);
return item;
}
/** remove and return the open node specified by a key */
inline Titem_& PopOpenNode(const Key& key)
{
Titem_& item = m_open.Pop(key);
uint idxPop = m_open_queue.FindIndex(item);
m_open_queue.Remove(idxPop);
return item;
}
/** close node */
inline void InsertClosedNode(Titem_& item)
{
assert(m_open.Find(item.GetKey()) == NULL);
m_closed.Push(item);
}
/** return the closed node specified by a key or NULL if not found */
inline Titem_ *FindClosedNode(const Key& key)
{
Titem_ *item = m_closed.Find(key);
return item;
}
/** The number of items. */
inline int TotalCount() {return m_arr.Length();}
/** Get a particular item. */
inline Titem_& ItemAt(int idx) {return m_arr[idx];}
/** Helper for creating output of this array. */
template <class D> void Dump(D &dmp) const
{
dmp.WriteStructT("m_arr", &m_arr);
}
};
#endif /* NODELIST_HPP */
|