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 <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
 */

 
#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 NodeList {
public:
  using Item = Titem;
  using Key = typename Titem::Key;
 
protected:
  std::deque<Titem> items; 
  HashTable<Titem, Thash_bits_open> open_nodes; 
  HashTable<Titem, Thash_bits_closed> closed_nodes; 
  CBinaryHeapT<Titem> open_queue; 
  Titem *new_node; 
 
public:
  NodeList() : open_queue(2048)
  {
    this->new_node = nullptr;
  }

  inline int OpenCount()
  {
    return this->open_nodes.Count();
  }

  inline int ClosedCount()
  {
    return this->closed_nodes.Count();
  }

  inline int TotalCount()
  {
    return this->items.Length();
  }

  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 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)
  {
    return this->open_nodes.Find(key);
  }

  inline Titem &PopOpenNode(const Key &key)
  {
    Titem &item = this->open_nodes.Pop(key);
    size_t index = this->open_queue.FindIndex(item);
    this->open_queue.Remove(index);
    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)
  {
    return this->closed_nodes.Find(key);
  }

  inline Titem &ItemAt(int index)
  {
    return this->items[index];
  }

  template <class D>
  void Dump(D &dmp) const
  {
    dmp.WriteStructT("data", &this->items);
  }
};
 
#endif /* NODELIST_HPP */