diff options
Diffstat (limited to 'src/yapf/nodelist.hpp')
-rw-r--r-- | src/yapf/nodelist.hpp | 130 |
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 */ |