/* $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 */