src/pathfinder/yapf/nodelist.hpp

   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
   8 /** @file nodelist.hpp List of nodes used for the A-star pathfinder. */
   9
  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
  17 /**
  18  * Hash table based node list multi-container class.
  19  *  Implements open list, closed list and priority queue for A-star
  20  *  path finder.
  21  */
  22 template <class Titem_, int Thash_bits_open_, int Thash_bits_closed_>
  23 class CNodeList_HashTableT {
  24 public:
  25         typedef Titem_ Titem;                                        ///< Make #Titem_ visible from outside of class.
  26         typedef typename Titem_::Key Key;                            ///< Make Titem_::Key a property of this class.
  27         typedef SmallArray<Titem_, 65536, 256> CItemArray;           ///< Type that we will use as item container.
  28         typedef CHashTableT<Titem_, Thash_bits_open_  > COpenList;   ///< How pointers to open nodes will be stored.
  29         typedef CHashTableT<Titem_, Thash_bits_closed_> CClosedList; ///< How pointers to closed nodes will be stored.
  30         typedef CBinaryHeapT<Titem_> CPriorityQueue;                 ///< How the priority queue will be managed.
  31
  32 protected:
  33         CItemArray      m_arr;        ///< Here we store full item data (Titem_).
  34         COpenList       m_open;       ///< Hash table of pointers to open item data.
  35         CClosedList     m_closed;     ///< Hash table of pointers to closed item data.
  36         CPriorityQueue  m_open_queue; ///< Priority queue of pointers to open item data.
  37         Titem          *m_new_node;   ///< New open node under construction.
  38
  39 public:
  40         /** default constructor */
  41         CNodeList_HashTableT() : m_open_queue(2048)
  42         {
  43                 m_new_node = nullptr;
  44         }
  45
  46         /** destructor */
  47         ~CNodeList_HashTableT()
  48         {
  49         }
  50
  51         /** return number of open nodes */
  52         inline int OpenCount()
  53         {
  54                 return m_open.Count();
  55         }
  56
  57         /** return number of closed nodes */
  58         inline int ClosedCount()
  59         {
  60                 return m_closed.Count();
  61         }
  62
  63         /** allocate new data item from m_arr */
  64         inline Titem_ *CreateNewNode()
  65         {
  66                 if (m_new_node == nullptr) m_new_node = m_arr.AppendC();
  67                 return m_new_node;
  68         }
  69
  70         /** Notify the nodelist that we don't want to discard the given node. */
  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
  80         /** insert given item as open node (into m_open and m_open_queue) */
  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
  91         /** return the best open node */
  92         inline Titem_ *GetBestOpenNode()
  93         {
  94                 if (!m_open_queue.IsEmpty()) {
  95                         return m_open_queue.Begin();
  96                 }
  97                 return nullptr;
  98         }
  99
 100         /** remove and return the best open node */
 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
 111         /** return the open node specified by a key or nullptr if not found */
 112         inline Titem_ *FindOpenNode(const Key &key)
 113         {
 114                 Titem_ *item = m_open.Find(key);
 115                 return item;
 116         }
 117
 118         /** remove and return the open node specified by a key */
 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
 127         /** close node */
 128         inline void InsertClosedNode(Titem_ &item)
 129         {
 130                 assert(m_open.Find(item.GetKey()) == nullptr);
 131                 m_closed.Push(item);
 132         }
 133
 134         /** return the closed node specified by a key or nullptr if not found */
 135         inline Titem_ *FindClosedNode(const Key &key)
 136         {
 137                 Titem_ *item = m_closed.Find(key);
 138                 return item;
 139         }
 140
 141         /** The number of items. */
 142         inline int TotalCount()
 143         {
 144                 return m_arr.Length();
 145         }
 146
 147         /** Get a particular item. */
 148         inline Titem_& ItemAt(int idx)
 149         {
 150                 return m_arr[idx];
 151         }
 152
 153         /** Helper for creating output of this array. */
 154         template <class D> void Dump(D &dmp) const
 155         {
 156                 dmp.WriteStructT("m_arr", &m_arr);
 157         }
 158 };
 159
 160 #endif /* NODELIST_HPP */