KUDr@3900: /* $Id$ */
KUDr@3900: 
KUDr@3900: #ifndef  NODELIST_HPP
KUDr@3900: #define  NODELIST_HPP
KUDr@3900: 
KUDr@3900: #include "array.hpp"
KUDr@3900: #include "hashtable.hpp"
KUDr@3900: #include "binaryheap.hpp"
KUDr@3900: 
KUDr@3900: /** Hash table based node list multi-container class.
rubidium@4549:  *  Implements open list, closed list and priority queue for A-star
rubidium@4549:  *  path finder. */
KUDr@3900: template <class Titem_, int Thash_bits_open_, int Thash_bits_closed_>
KUDr@3900: class CNodeList_HashTableT {
KUDr@3900: public:
KUDr@3900: 	/** make Titem_ visible from outside of class */
KUDr@3900: 	typedef Titem_ Titem;
KUDr@3900: 	/** make Titem_::Key a property of HashTable */
KUDr@3900: 	typedef typename Titem_::Key Key;
KUDr@3900: 	/** type that we will use as item container */
KUDr@3900: 	typedef CArrayT<Titem_, 65536, 256> CItemArray;
KUDr@3900: 	/** how pointers to open nodes will be stored */
KUDr@3900: 	typedef CHashTableT<Titem_, Thash_bits_open_  > COpenList;
KUDr@3900: 	/** how pointers to closed nodes will be stored */
KUDr@3900: 	typedef CHashTableT<Titem_, Thash_bits_closed_> CClosedList;
KUDr@3900: 	/** how the priority queue will be managed */
KUDr@3900: 	typedef CBinaryHeapT<Titem_> CPriorityQueue;
KUDr@3900: 
KUDr@3900: protected:
KUDr@3900: 	/** here we store full item data (Titem_) */
KUDr@3900: 	CItemArray            m_arr;
KUDr@3900: 	/** hash table of pointers to open item data */
KUDr@3900: 	COpenList             m_open;
KUDr@3900: 	/** hash table of pointers to closed item data */
KUDr@3900: 	CClosedList           m_closed;
KUDr@3900: 	/** priority queue of pointers to open item data */
KUDr@3900: 	CPriorityQueue        m_open_queue;
KUDr@3900: 	/** new open node under construction */
KUDr@3900: 	Titem                *m_new_node;
KUDr@3900: public:
KUDr@3900: 	/** default constructor */
KUDr@3900: 	CNodeList_HashTableT()
KUDr@3900: 		: m_open_queue(204800)
KUDr@3900: 	{
KUDr@3900: 		m_new_node = NULL;
KUDr@3900: 	}
KUDr@3900: 	/** destructor */
KUDr@3900: 	~CNodeList_HashTableT()
KUDr@3900: 	{
KUDr@3900: 	}
KUDr@3900: 	/** return number of open nodes */
KUDr@3900: 	FORCEINLINE int OpenCount() {return m_open.Count();}
KUDr@3900: 	/** return number of closed nodes */
KUDr@3900: 	FORCEINLINE int ClosedCount() {return m_closed.Count();}
KUDr@3900: 	/** allocate new data item from m_arr */
KUDr@3900: 	FORCEINLINE Titem_* CreateNewNode()
KUDr@3900: 	{
KUDr@3900: 		if (m_new_node == NULL) m_new_node = &m_arr.Add();
KUDr@3900: 		return m_new_node;
KUDr@3900: 	}
KUDr@3900: 	/** notify the nodelist, that we don't want to discard the given node */
KUDr@3900: 	FORCEINLINE void FoundBestNode(Titem_& item)
KUDr@3900: 	{
KUDr@3900: 		// for now it is enough to invalidate m_new_node if it is our given node
KUDr@3900: 		if (&item == m_new_node)
KUDr@3900: 			m_new_node = NULL;
KUDr@3900: 		// TODO: do we need to store best nodes found in some extra list/array? Probably not now.
KUDr@3900: 	}
KUDr@3900: 	/** insert given item as open node (into m_open and m_open_queue) */
KUDr@3900: 	FORCEINLINE void InsertOpenNode(Titem_& item)
KUDr@3900: 	{
KUDr@5083: 		assert(m_closed.Find(item.GetKey()) == NULL);
KUDr@3900: 		m_open.Push(item);
KUDr@3900: 		// TODO: check if m_open_queue is not full
KUDr@3900: 		assert(!m_open_queue.IsFull());
KUDr@3900: 		m_open_queue.Push(item);
KUDr@3900: 		if (&item == m_new_node)
KUDr@3900: 			m_new_node = NULL;
KUDr@3900: 	}
KUDr@3900: 	/** return the best open node */
KUDr@5083: 	FORCEINLINE Titem_* GetBestOpenNode()
KUDr@3900: 	{
KUDr@3900: 		if (!m_open_queue.IsEmpty()) {
KUDr@3900: 			Titem_& item = m_open_queue.GetHead();
KUDr@5083: 			return &item;
KUDr@3900: 		}
KUDr@5083: 		return NULL;
KUDr@3900: 	}
KUDr@3900: 	/** remove and return the best open node */
KUDr@5083: 	FORCEINLINE Titem_* PopBestOpenNode()
KUDr@3900: 	{
KUDr@3900: 		if (!m_open_queue.IsEmpty()) {
KUDr@3900: 			Titem_& item = m_open_queue.PopHead();
KUDr@3900: 			m_open.Pop(item);
KUDr@5083: 			return &item;
KUDr@3900: 		}
KUDr@5083: 		return NULL;
KUDr@3900: 	}
KUDr@3900: 	/** return the open node specified by a key or NULL if not found */
KUDr@5083: 	FORCEINLINE Titem_* FindOpenNode(const Key& key)
KUDr@3900: 	{
KUDr@5083: 		Titem_* item = m_open.Find(key);
KUDr@3900: 		return item;
KUDr@3900: 	}
KUDr@3900: 	/** remove and return the open node specified by a key */
KUDr@3900: 	FORCEINLINE Titem_& PopOpenNode(const Key& key)
KUDr@3900: 	{
KUDr@3900: 		Titem_& item = m_open.Pop(key);
KUDr@5083: 		int idxPop = m_open_queue.FindLinear(item);
KUDr@5083: 		m_open_queue.RemoveByIdx(idxPop);
KUDr@3900: 		return item;
KUDr@3900: 	}
KUDr@3900: 	/** close node */
KUDr@3900: 	FORCEINLINE void InsertClosedNode(Titem_& item)
KUDr@3900: 	{
KUDr@5083: 		assert(m_open.Find(item.GetKey()) == NULL);
KUDr@3900: 		m_closed.Push(item);
KUDr@3900: 	}
KUDr@3900: 	/** return the closed node specified by a key or NULL if not found */
KUDr@5083: 	FORCEINLINE Titem_* FindClosedNode(const Key& key)
KUDr@3900: 	{
KUDr@5083: 		Titem_* item = m_closed.Find(key);
KUDr@3900: 		return item;
KUDr@3900: 	}
KUDr@3900: 
KUDr@3900: 	FORCEINLINE int TotalCount() {return m_arr.Size();}
KUDr@3900: 	FORCEINLINE Titem_& ItemAt(int idx) {return m_arr[idx];}
KUDr@3900: };
KUDr@3900: 
KUDr@3900: #endif /* NODELIST_HPP */