1

/* $Id$ */

     2

     3

#ifndef  NODELIST_HPP

     4

#define  NODELIST_HPP

     5

     6

#include "array.hpp"

     7

#include "hashtable.hpp"

     8

#include "binaryheap.hpp"

     9

    10

/** Hash table based node list multi-container class.

    11

 *  Implements open list, closed list and priority queue for A-star

    12

 *  path finder. */

    13

template <class Titem_, int Thash_bits_open_, int Thash_bits_closed_>

    14

class CNodeList_HashTableT {

    15

public:

    16

	/** make Titem_ visible from outside of class */

    17

	typedef Titem_ Titem;

    18

	/** make Titem_::Key a property of HashTable */

    19

	typedef typename Titem_::Key Key;

    20

	/** type that we will use as item container */

    21

	typedef CArrayT<Titem_, 65536, 256> CItemArray;

    22

	/** how pointers to open nodes will be stored */

    23

	typedef CHashTableT<Titem_, Thash_bits_open_  > COpenList;

    24

	/** how pointers to closed nodes will be stored */

    25

	typedef CHashTableT<Titem_, Thash_bits_closed_> CClosedList;

    26

	/** how the priority queue will be managed */

    27

	typedef CBinaryHeapT<Titem_> CPriorityQueue;

    28

    29

protected:

    30

	/** here we store full item data (Titem_) */

    31

	CItemArray            m_arr;

    32

	/** hash table of pointers to open item data */

    33

	COpenList             m_open;

    34

	/** hash table of pointers to closed item data */

    35

	CClosedList           m_closed;

    36

	/** priority queue of pointers to open item data */

    37

	CPriorityQueue        m_open_queue;

    38

	/** new open node under construction */

    39

	Titem                *m_new_node;

    40

public:

    41

	/** default constructor */

    42

	CNodeList_HashTableT()

    43

		: m_open_queue(204800)

    44

	{

    45

		m_new_node = NULL;

    46

	}

    47

	/** destructor */

    48

	~CNodeList_HashTableT()

    49

	{

    50

	}

    51

	/** return number of open nodes */

    52

	FORCEINLINE int OpenCount() {return m_open.Count();}

    53

	/** return number of closed nodes */

    54

	FORCEINLINE int ClosedCount() {return m_closed.Count();}

    55

	/** allocate new data item from m_arr */

    56

	FORCEINLINE Titem_* CreateNewNode()

    57

	{

    58

		if (m_new_node == NULL) m_new_node = &m_arr.Add();

    59

		return m_new_node;

    60

	}

    61

	/** notify the nodelist, that we don't want to discard the given node */

    62

	FORCEINLINE void FoundBestNode(Titem_& item)

    63

	{

    64

		// for now it is enough to invalidate m_new_node if it is our given node

    65

		if (&item == m_new_node)

    66

			m_new_node = NULL;

    67

		// TODO: do we need to store best nodes found in some extra list/array? Probably not now.

    68

	}

    69

	/** insert given item as open node (into m_open and m_open_queue) */

    70

	FORCEINLINE void InsertOpenNode(Titem_& item)

    71

	{

    72

		assert(&m_closed.Find(item.GetKey()) == NULL);

    73

		m_open.Push(item);

    74

		// TODO: check if m_open_queue is not full

    75

		assert(!m_open_queue.IsFull());

    76

		m_open_queue.Push(item);

    77

		if (&item == m_new_node)

    78

			m_new_node = NULL;

    79

	}

    80

	/** return the best open node */

    81

	FORCEINLINE Titem_& GetBestOpenNode()

    82

	{

    83

		if (!m_open_queue.IsEmpty()) {

    84

			Titem_& item = m_open_queue.GetHead();

    85

			return item;

    86

		}

    87

		return *(Titem_*)NULL;

    88

	}

    89

	/** remove and return the best open node */

    90

	FORCEINLINE Titem_& PopBestOpenNode()

    91

	{

    92

		if (!m_open_queue.IsEmpty()) {

    93

			Titem_& item = m_open_queue.PopHead();

    94

			m_open.Pop(item);

    95

			return item;

    96

		}

    97

		return *(Titem_*)NULL;

    98

	}

    99

	/** return the open node specified by a key or NULL if not found */

   100

	FORCEINLINE Titem_& FindOpenNode(const Key& key)

   101

	{

   102

		Titem_& item = m_open.Find(key);

   103

		return item;

   104

	}

   105

	/** remove and return the open node specified by a key */

   106

	FORCEINLINE Titem_& PopOpenNode(const Key& key)

   107

	{

   108

		Titem_& item = m_open.Pop(key);

   109

		if (&item != NULL) {

   110

			int idxPop = m_open_queue.FindLinear(item);

   111

			m_open_queue.RemoveByIdx(idxPop);

   112

		}

   113

		return item;

   114

	}

   115

	/** close node */

   116

	FORCEINLINE void InsertClosedNode(Titem_& item)

   117

	{

   118

		assert(&m_open.Find(item.GetKey()) == NULL);

   119

		m_closed.Push(item);

   120

	}

   121

	/** return the closed node specified by a key or NULL if not found */

   122

	FORCEINLINE Titem_& FindClosedNode(const Key& key)

   123

	{

   124

		Titem_& item = m_closed.Find(key);

   125

		return item;

   126

	}

   127

   128

	FORCEINLINE int TotalCount() {return m_arr.Size();}

   129

	FORCEINLINE Titem_& ItemAt(int idx) {return m_arr[idx];}

   130

};

   131

   132

#endif /* NODELIST_HPP */