summaryrefslogtreecommitdiff
path: root/yapf/nodelist.hpp
diff options
context:
space:
mode:
authorrubidium <rubidium@openttd.org>2007-01-02 19:19:48 +0000
committerrubidium <rubidium@openttd.org>2007-01-02 19:19:48 +0000
commit66bbf336c6af7353ef0aeed58002c46543b30635 (patch)
treead4a63860df2626b22f77e7dac712e958bea54cb /yapf/nodelist.hpp
parentccc0a3f4dbf58c005b22341ac8874252924690cd (diff)
downloadopenttd-66bbf336c6af7353ef0aeed58002c46543b30635.tar.xz
(svn r7759) -Merge: makefile rewrite. This merge features:
- A proper ./configure, so everything needs to be configured only once, not for every make. - Usage of makedepend when available. This greatly reduces the time needed for generating the dependencies. - A generator for all project files. There is a single file with sources, which is used to generate Makefiles and the project files for MSVC. - Proper support for OSX universal binaries. - Object files for non-MSVC compiles are also placed in separate directories, making is faster to switch between debug and release compiles and it does not touch the directory with the source files. - Functionality to make a bundle of all needed files for for example a nightly or distribution of a binary with all needed GRFs and language files. Note: as this merge moves almost all files, it is recommended to make a backup of your working copy before updating your working copy.
Diffstat (limited to 'yapf/nodelist.hpp')
-rw-r--r--yapf/nodelist.hpp130
1 files changed, 0 insertions, 130 deletions
diff --git a/yapf/nodelist.hpp b/yapf/nodelist.hpp
deleted file mode 100644
index f51afbfd4..000000000
--- a/yapf/nodelist.hpp
+++ /dev/null
@@ -1,130 +0,0 @@
-/* $Id$ */
-
-#ifndef NODELIST_HPP
-#define NODELIST_HPP
-
-#include "array.hpp"
-#include "hashtable.hpp"
-#include "binaryheap.hpp"
-
-/** Hash table based node list multi-container class.
- * Implements open list, closed list and priority queue for A-star
- * path finder. */
-template <class Titem_, int Thash_bits_open_, int Thash_bits_closed_>
-class CNodeList_HashTableT {
-public:
- /** make Titem_ visible from outside of class */
- typedef Titem_ Titem;
- /** make Titem_::Key a property of HashTable */
- typedef typename Titem_::Key Key;
- /** type that we will use as item container */
- typedef CArrayT<Titem_, 65536, 256> CItemArray;
- /** how pointers to open nodes will be stored */
- typedef CHashTableT<Titem_, Thash_bits_open_ > COpenList;
- /** how pointers to closed nodes will be stored */
- typedef CHashTableT<Titem_, Thash_bits_closed_> CClosedList;
- /** how the priority queue will be managed */
- typedef CBinaryHeapT<Titem_> CPriorityQueue;
-
-protected:
- /** here we store full item data (Titem_) */
- CItemArray m_arr;
- /** hash table of pointers to open item data */
- COpenList m_open;
- /** hash table of pointers to closed item data */
- CClosedList m_closed;
- /** priority queue of pointers to open item data */
- CPriorityQueue m_open_queue;
- /** new open node under construction */
- Titem *m_new_node;
-public:
- /** default constructor */
- CNodeList_HashTableT()
- : m_open_queue(204800)
- {
- m_new_node = NULL;
- }
- /** destructor */
- ~CNodeList_HashTableT()
- {
- }
- /** return number of open nodes */
- FORCEINLINE int OpenCount() {return m_open.Count();}
- /** return number of closed nodes */
- FORCEINLINE int ClosedCount() {return m_closed.Count();}
- /** allocate new data item from m_arr */
- FORCEINLINE Titem_* CreateNewNode()
- {
- if (m_new_node == NULL) m_new_node = &m_arr.Add();
- return m_new_node;
- }
- /** notify the nodelist, that we don't want to discard the given node */
- FORCEINLINE 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 = NULL;
- // TODO: do we need to store best nodes found in some extra list/array? Probably not now.
- }
- /** insert given item as open node (into m_open and m_open_queue) */
- FORCEINLINE void InsertOpenNode(Titem_& item)
- {
- assert(m_closed.Find(item.GetKey()) == NULL);
- m_open.Push(item);
- // TODO: check if m_open_queue is not full
- assert(!m_open_queue.IsFull());
- m_open_queue.Push(item);
- if (&item == m_new_node)
- m_new_node = NULL;
- }
- /** return the best open node */
- FORCEINLINE Titem_* GetBestOpenNode()
- {
- if (!m_open_queue.IsEmpty()) {
- Titem_& item = m_open_queue.GetHead();
- return &item;
- }
- return NULL;
- }
- /** remove and return the best open node */
- FORCEINLINE Titem_* PopBestOpenNode()
- {
- if (!m_open_queue.IsEmpty()) {
- Titem_& item = m_open_queue.PopHead();
- m_open.Pop(item);
- return &item;
- }
- return NULL;
- }
- /** return the open node specified by a key or NULL if not found */
- FORCEINLINE Titem_* FindOpenNode(const Key& key)
- {
- Titem_* item = m_open.Find(key);
- return item;
- }
- /** remove and return the open node specified by a key */
- FORCEINLINE Titem_& PopOpenNode(const Key& key)
- {
- Titem_& item = m_open.Pop(key);
- int idxPop = m_open_queue.FindLinear(item);
- m_open_queue.RemoveByIdx(idxPop);
- return item;
- }
- /** close node */
- FORCEINLINE void InsertClosedNode(Titem_& item)
- {
- assert(m_open.Find(item.GetKey()) == NULL);
- m_closed.Push(item);
- }
- /** return the closed node specified by a key or NULL if not found */
- FORCEINLINE Titem_* FindClosedNode(const Key& key)
- {
- Titem_* item = m_closed.Find(key);
- return item;
- }
-
- FORCEINLINE int TotalCount() {return m_arr.Size();}
- FORCEINLINE Titem_& ItemAt(int idx) {return m_arr[idx];}
-};
-
-#endif /* NODELIST_HPP */