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/hashtable.hpp"
  14 #include "../../misc/binaryheap.hpp"
  15
  16 /**
  17  * Hash table based node list multi-container class.
  18  *  Implements open list, closed list and priority queue for A-star
  19  *  path finder.
  20  */
  21 template <class Titem_, int Thash_bits_open_, int Thash_bits_closed_>
  22 class CNodeList_HashTableT {
  23 public:
  24         typedef Titem_ Titem;                                        ///< Make #Titem_ visible from outside of class.
  25         typedef typename Titem_::Key Key;                            ///< Make Titem_::Key a property of this class.
  26         using CItemArray = std::deque<Titem_>;                       ///< Type that we will use as item container.
  27         typedef CHashTableT<Titem_, Thash_bits_open_  > COpenList;   ///< How pointers to open nodes will be stored.
  28         typedef CHashTableT<Titem_, Thash_bits_closed_> CClosedList; ///< How pointers to closed nodes will be stored.
  29         typedef CBinaryHeapT<Titem_> CPriorityQueue;                 ///< How the priority queue will be managed.
  30
  31 protected:
  32         CItemArray      m_arr;        ///< Here we store full item data (Titem_).
  33         COpenList       m_open;       ///< Hash table of pointers to open item data.
  34         CClosedList     m_closed;     ///< Hash table of pointers to closed item data.
  35         CPriorityQueue  m_open_queue; ///< Priority queue of pointers to open item data.
  36         Titem          *m_new_node;   ///< New open node under construction.
  37
  38 public:
  39         /** default constructor */
  40         CNodeList_HashTableT() : m_open_queue(2048)
  41         {
  42                 m_new_node = nullptr;
  43         }
  44
  45         /** destructor */
  46         ~CNodeList_HashTableT()
  47         {
  48         }
  49
  50         /** return number of open nodes */
  51         inline int OpenCount()
  52         {
  53                 return m_open.Count();
  54         }
  55
  56         /** return number of closed nodes */
  57         inline int ClosedCount()
  58         {
  59                 return m_closed.Count();
  60         }
  61
  62         /** allocate new data item from m_arr */
  63         inline Titem_ *CreateNewNode()
  64         {
  65                 if (m_new_node == nullptr) m_new_node = &m_arr.emplace_back();
  66                 return m_new_node;
  67         }
  68
  69         /** Notify the nodelist that we don't want to discard the given node. */
  70         inline void FoundBestNode(Titem_ &item)
  71         {
  72                 /* for now it is enough to invalidate m_new_node if it is our given node */
  73                 if (&item == m_new_node) {
  74                         m_new_node = nullptr;
  75                 }
  76                 /* TODO: do we need to store best nodes found in some extra list/array? Probably not now. */
  77         }
  78
  79         /** insert given item as open node (into m_open and m_open_queue) */
  80         inline void InsertOpenNode(Titem_ &item)
  81         {
  82                 assert(m_closed.Find(item.GetKey()) == nullptr);
  83                 m_open.Push(item);
  84                 m_open_queue.Include(&item);
  85                 if (&item == m_new_node) {
  86                         m_new_node = nullptr;
  87                 }
  88         }
  89
  90         /** return the best open node */
  91         inline Titem_ *GetBestOpenNode()
  92         {
  93                 if (!m_open_queue.IsEmpty()) {
  94                         return m_open_queue.Begin();
  95                 }
  96                 return nullptr;
  97         }
  98
  99         /** remove and return the best open node */
 100         inline Titem_ *PopBestOpenNode()
 101         {
 102                 if (!m_open_queue.IsEmpty()) {
 103                         Titem_ *item = m_open_queue.Shift();
 104                         m_open.Pop(*item);
 105                         return item;
 106                 }
 107                 return nullptr;
 108         }
 109
 110         /** return the open node specified by a key or nullptr if not found */
 111         inline Titem_ *FindOpenNode(const Key &key)
 112         {
 113                 Titem_ *item = m_open.Find(key);
 114                 return item;
 115         }
 116
 117         /** remove and return the open node specified by a key */
 118         inline Titem_ &PopOpenNode(const Key &key)
 119         {
 120                 Titem_ &item = m_open.Pop(key);
 121                 size_t idxPop = m_open_queue.FindIndex(item);
 122                 m_open_queue.Remove(idxPop);
 123                 return item;
 124         }
 125
 126         /** close node */
 127         inline void InsertClosedNode(Titem_ &item)
 128         {
 129                 assert(m_open.Find(item.GetKey()) == nullptr);
 130                 m_closed.Push(item);
 131         }
 132
 133         /** return the closed node specified by a key or nullptr if not found */
 134         inline Titem_ *FindClosedNode(const Key &key)
 135         {
 136                 Titem_ *item = m_closed.Find(key);
 137                 return item;
 138         }
 139
 140         /** The number of items. */
 141         inline int TotalCount()
 142         {
 143                 return m_arr.Length();
 144         }
 145
 146         /** Get a particular item. */
 147         inline Titem_ &ItemAt(int idx)
 148         {
 149                 return m_arr[idx];
 150         }
 151
 152         /** Helper for creating output of this array. */
 153         template <class D> void Dump(D &dmp) const
 154         {
 155                 dmp.WriteStructT("m_arr", &m_arr);
 156         }
 157 };
 158
 159 #endif /* NODELIST_HPP */