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 pathfinder.
  19  */
  20 template <class Titem, int Thash_bits_open, int Thash_bits_closed>
  21 class NodeList {
  22 public:
  23         using Item = Titem;
  24         using Key = typename Titem::Key;
  25
  26 protected:
  27         std::deque<Titem> items; ///< Storage of the nodes.
  28         HashTable<Titem, Thash_bits_open> open_nodes; ///< Hash table of pointers to open nodes.
  29         HashTable<Titem, Thash_bits_closed> closed_nodes; ///< Hash table of pointers to closed nodes.
  30         CBinaryHeapT<Titem> open_queue; ///< Priority queue of pointers to open nodes.
  31         Titem *new_node; ///< New node under construction.
  32
  33 public:
  34         /** default constructor */
  35         NodeList() : open_queue(2048)
  36         {
  37                 this->new_node = nullptr;
  38         }
  39
  40         /** return number of open nodes */
  41         inline int OpenCount()
  42         {
  43                 return this->open_nodes.Count();
  44         }
  45
  46         /** return number of closed nodes */
  47         inline int ClosedCount()
  48         {
  49                 return this->closed_nodes.Count();
  50         }
  51
  52         /** return the total number of nodes. */
  53         inline int TotalCount()
  54         {
  55                 return this->items.Length();
  56         }
  57
  58         /** allocate new data item from items */
  59         inline Titem &CreateNewNode()
  60         {
  61                 if (this->new_node == nullptr) this->new_node = &this->items.emplace_back();
  62                 return *this->new_node;
  63         }
  64
  65         /** Notify the nodelist that we don't want to discard the given node. */
  66         inline void FoundBestNode(Titem &item)
  67         {
  68                 /* for now it is enough to invalidate new_node if it is our given node */
  69                 if (&item == this->new_node) {
  70                         this->new_node = nullptr;
  71                 }
  72                 /* TODO: do we need to store best nodes found in some extra list/array? Probably not now. */
  73         }
  74
  75         /** insert given item as open node (into open_nodes and open_queue) */
  76         inline void InsertOpenNode(Titem &item)
  77         {
  78                 assert(this->closed_nodes.Find(item.GetKey()) == nullptr);
  79                 this->open_nodes.Push(item);
  80                 this->open_queue.Include(&item);
  81                 if (&item == this->new_node) {
  82                         this->new_node = nullptr;
  83                 }
  84         }
  85
  86         /** return the best open node */
  87         inline Titem *GetBestOpenNode()
  88         {
  89                 if (!this->open_queue.IsEmpty()) {
  90                         return this->open_queue.Begin();
  91                 }
  92                 return nullptr;
  93         }
  94
  95         /** remove and return the best open node */
  96         inline Titem *PopBestOpenNode()
  97         {
  98                 if (!this->open_queue.IsEmpty()) {
  99                         Titem *item = this->open_queue.Shift();
 100                         this->open_nodes.Pop(*item);
 101                         return item;
 102                 }
 103                 return nullptr;
 104         }
 105
 106         /** return the open node specified by a key or nullptr if not found */
 107         inline Titem *FindOpenNode(const Key &key)
 108         {
 109                 return this->open_nodes.Find(key);
 110         }
 111
 112         /** remove and return the open node specified by a key */
 113         inline Titem &PopOpenNode(const Key &key)
 114         {
 115                 Titem &item = this->open_nodes.Pop(key);
 116                 size_t index = this->open_queue.FindIndex(item);
 117                 this->open_queue.Remove(index);
 118                 return item;
 119         }
 120
 121         /** close node */
 122         inline void InsertClosedNode(Titem &item)
 123         {
 124                 assert(this->open_nodes.Find(item.GetKey()) == nullptr);
 125                 this->closed_nodes.Push(item);
 126         }
 127
 128         /** return the closed node specified by a key or nullptr if not found */
 129         inline Titem *FindClosedNode(const Key &key)
 130         {
 131                 return this->closed_nodes.Find(key);
 132         }
 133
 134         /** Get a particular item. */
 135         inline Titem &ItemAt(int index)
 136         {
 137                 return this->items[index];
 138         }
 139
 140         /** Helper for creating output of this array. */
 141         template <class D>
 142         void Dump(D &dmp) const
 143         {
 144                 dmp.WriteStructT("data", &this->items);
 145         }
 146 };
 147
 148 #endif /* NODELIST_HPP */