summaryrefslogtreecommitdiff
path: root/src/yapf/nodelist.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/yapf/nodelist.hpp')
-rw-r--r--src/yapf/nodelist.hpp130
1 files changed, 130 insertions, 0 deletions
diff --git a/src/yapf/nodelist.hpp b/src/yapf/nodelist.hpp
new file mode 100644
index 000000000..f51afbfd4
--- /dev/null
+++ b/src/yapf/nodelist.hpp
@@ -0,0 +1,130 @@
+/* $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 */