nodelist.hpp

Go to the documentation of this file.

/*
 * This file is part of OpenTTD.
 * 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.
 * 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.
 * 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/>.
 */
 
#ifndef NODELIST_HPP
#define NODELIST_HPP
 
#include "../../misc/hashtable.hpp"
#include "../../misc/binaryheap.hpp"
 
template <class Titem_, int Thash_bits_open_, int Thash_bits_closed_>
class CNodeList_HashTableT {
public:
  typedef Titem_ Titem;                                        
  typedef typename Titem_::Key Key;                            
  using CItemArray = std::deque<Titem_>;                       
  typedef HashTable<Titem_, Thash_bits_open_  > COpenList;     
  typedef HashTable<Titem_, Thash_bits_closed_> CClosedList;   
  typedef CBinaryHeapT<Titem_> CPriorityQueue;                 
 
protected:
  CItemArray items; 
  COpenList open_nodes; 
  CClosedList closed_nodes; 
  CPriorityQueue open_queue; 
  Titem *new_node; 
 
public:
  CNodeList_HashTableT() : open_queue(2048)
  {
    this->new_node = nullptr;
  }
 
  ~CNodeList_HashTableT()
  {
  }
 
  inline int OpenCount()
  {
    return this->open_nodes.Count();
  }
 
  inline int ClosedCount()
  {
    return this->closed_nodes.Count();
  }
 
  inline Titem_ *CreateNewNode()
  {
    if (this->new_node == nullptr) this->new_node = &this->items.emplace_back();
    return this->new_node;
  }
 
  inline void FoundBestNode(Titem_ &item)
  {
    /* for now it is enough to invalidate m_new_node if it is our given node */
    if (&item == this->new_node) {
      this->new_node = nullptr;
    }
    /* TODO: do we need to store best nodes found in some extra list/array? Probably not now. */
  }
 
  inline void InsertOpenNode(Titem_ &item)
  {
    assert(this->closed_nodes.Find(item.GetKey()) == nullptr);
    this->open_nodes.Push(item);
    this->open_queue.Include(&item);
    if (&item == this->new_node) {
      this->new_node = nullptr;
    }
  }
 
  inline Titem_ *GetBestOpenNode()
  {
    if (!this->open_queue.IsEmpty()) {
      return this->open_queue.Begin();
    }
    return nullptr;
  }
 
  inline Titem_ *PopBestOpenNode()
  {
    if (!this->open_queue.IsEmpty()) {
      Titem_ *item = this->open_queue.Shift();
      this->open_nodes.Pop(*item);
      return item;
    }
    return nullptr;
  }
 
  inline Titem_ *FindOpenNode(const Key &key)
  {
    Titem_ *item = this->open_nodes.Find(key);
    return item;
  }
 
  inline Titem_ &PopOpenNode(const Key &key)
  {
    Titem_ &item = this->open_nodes.Pop(key);
    size_t idxPop = this->open_queue.FindIndex(item);
    this->open_queue.Remove(idxPop);
    return item;
  }
 
  inline void InsertClosedNode(Titem_ &item)
  {
    assert(this->open_nodes.Find(item.GetKey()) == nullptr);
    this->closed_nodes.Push(item);
  }
 
  inline Titem_ *FindClosedNode(const Key &key)
  {
    Titem_ *item = this->closed_nodes.Find(key);
    return item;
  }
 
  inline int TotalCount()
  {
    return this->items.Length();
  }
 
  inline Titem_ &ItemAt(int idx)
  {
    return this->items[idx];
  }
 
  template <class D> void Dump(D &dmp) const
  {
    dmp.WriteStructT("data", &this->items);
  }
};
 
#endif /* NODELIST_HPP */