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 CHashTableT<Titem_, Thash_bits_open_  > COpenList;   
  typedef CHashTableT<Titem_, Thash_bits_closed_> CClosedList; 
  typedef CBinaryHeapT<Titem_> CPriorityQueue;                 
 
protected:
  CItemArray      m_arr;        
  COpenList       m_open;       
  CClosedList     m_closed;     
  CPriorityQueue  m_open_queue; 
  Titem          *m_new_node;   
 
public:
  CNodeList_HashTableT() : m_open_queue(2048)
  {
    m_new_node = nullptr;
  }
 
  ~CNodeList_HashTableT()
  {
  }
 
  inline int OpenCount()
  {
    return m_open.Count();
  }
 
  inline int ClosedCount()
  {
    return m_closed.Count();
  }
 
  inline Titem_ *CreateNewNode()
  {
    if (m_new_node == nullptr) m_new_node = &m_arr.emplace_back();
    return m_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 == m_new_node) {
      m_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(m_closed.Find(item.GetKey()) == nullptr);
    m_open.Push(item);
    m_open_queue.Include(&item);
    if (&item == m_new_node) {
      m_new_node = nullptr;
    }
  }
 
  inline Titem_ *GetBestOpenNode()
  {
    if (!m_open_queue.IsEmpty()) {
      return m_open_queue.Begin();
    }
    return nullptr;
  }
 
  inline Titem_ *PopBestOpenNode()
  {
    if (!m_open_queue.IsEmpty()) {
      Titem_ *item = m_open_queue.Shift();
      m_open.Pop(*item);
      return item;
    }
    return nullptr;
  }
 
  inline Titem_ *FindOpenNode(const Key &key)
  {
    Titem_ *item = m_open.Find(key);
    return item;
  }
 
  inline Titem_ &PopOpenNode(const Key &key)
  {
    Titem_ &item = m_open.Pop(key);
    size_t idxPop = m_open_queue.FindIndex(item);
    m_open_queue.Remove(idxPop);
    return item;
  }
 
  inline void InsertClosedNode(Titem_ &item)
  {
    assert(m_open.Find(item.GetKey()) == nullptr);
    m_closed.Push(item);
  }
 
  inline Titem_ *FindClosedNode(const Key &key)
  {
    Titem_ *item = m_closed.Find(key);
    return item;
  }
 
  inline int TotalCount()
  {
    return m_arr.Length();
  }
 
  inline Titem_ &ItemAt(int idx)
  {
    return m_arr[idx];
  }
 
  template <class D> void Dump(D &dmp) const
  {
    dmp.WriteStructT("m_arr", &m_arr);
  }
};
 
#endif /* NODELIST_HPP */