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