Files
@ r10188:9ef551fc3371
Branch filter:
Location: cpp/openttd-patchpack/source/src/yapf/nodelist.hpp
r10188:9ef551fc3371
4.0 KiB
text/x-c++hdr
(svn r14401) -Fix (r11724): Don't check articulated parts or rear multihead parts for callback 1D when moving a chain of wagons.
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 | /* $Id$ */
/** @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 CArrayT<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(204800)
{
m_new_node = NULL;
}
/** destructor */
~CNodeList_HashTableT()
{
}
/** return number of open nodes */
FORCEINLINE int OpenCount() {return m_open.Count();}
/** return number of closed nodes */
FORCEINLINE int ClosedCount() {return m_closed.Count();}
/** allocate new data item from m_arr */
FORCEINLINE Titem_* CreateNewNode()
{
if (m_new_node == NULL) m_new_node = &m_arr.Add();
return m_new_node;
}
/** notify the nodelist, that we don't want to discard the given node */
FORCEINLINE 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) */
FORCEINLINE void InsertOpenNode(Titem_& item)
{
assert(m_closed.Find(item.GetKey()) == NULL);
m_open.Push(item);
// TODO: check if m_open_queue is not full
assert(!m_open_queue.IsFull());
m_open_queue.Push(item);
if (&item == m_new_node)
m_new_node = NULL;
}
/** return the best open node */
FORCEINLINE Titem_* GetBestOpenNode()
{
if (!m_open_queue.IsEmpty()) {
Titem_& item = m_open_queue.GetHead();
return &item;
}
return NULL;
}
/** remove and return the best open node */
FORCEINLINE Titem_* PopBestOpenNode()
{
if (!m_open_queue.IsEmpty()) {
Titem_& item = m_open_queue.PopHead();
m_open.Pop(item);
return &item;
}
return NULL;
}
/** return the open node specified by a key or NULL if not found */
FORCEINLINE Titem_* FindOpenNode(const Key& key)
{
Titem_* item = m_open.Find(key);
return item;
}
/** remove and return the open node specified by a key */
FORCEINLINE Titem_& PopOpenNode(const Key& key)
{
Titem_& item = m_open.Pop(key);
int idxPop = m_open_queue.FindLinear(item);
m_open_queue.RemoveByIdx(idxPop);
return item;
}
/** close node */
FORCEINLINE 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 */
FORCEINLINE Titem_* FindClosedNode(const Key& key)
{
Titem_* item = m_closed.Find(key);
return item;
}
FORCEINLINE int TotalCount() {return m_arr.Size();}
FORCEINLINE Titem_& ItemAt(int idx) {return m_arr[idx];}
template <class D> void Dump(D &dmp) const
{
dmp.WriteStructT("m_arr", &m_arr);
}
};
#endif /* NODELIST_HPP */
|