src/pathfinder/yapf/nodelist.hpp

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