1

/* $Id$ */

     2

     3

/** @file nodelist.hpp */

     4

     5

#ifndef  NODELIST_HPP

     6

#define  NODELIST_HPP

     7

     8

#include "../misc/array.hpp"

     9

#include "../misc/hashtable.hpp"

    10

#include "../misc/binaryheap.hpp"

    11

    12

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

    13

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

    14

 *  path finder. */

    15

template <class Titem_, int Thash_bits_open_, int Thash_bits_closed_>

    16

class CNodeList_HashTableT {

    17

public:

    18

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

    19

	typedef Titem_ Titem;

    20

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

    21

	typedef typename Titem_::Key Key;

    22

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

    23

	typedef CArrayT<Titem_, 65536, 256> CItemArray;

    24

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

    25

	typedef CHashTableT<Titem_, Thash_bits_open_  > COpenList;

    26

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

    27

	typedef CHashTableT<Titem_, Thash_bits_closed_> CClosedList;

    28

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

    29

	typedef CBinaryHeapT<Titem_> CPriorityQueue;

    30

    31

protected:

    32

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

    33

	CItemArray            m_arr;

    34

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

    35

	COpenList             m_open;

    36

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

    37

	CClosedList           m_closed;

    38

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

    39

	CPriorityQueue        m_open_queue;

    40

	/** new open node under construction */

    41

	Titem                *m_new_node;

    42

public:

    43

	/** default constructor */

    44

	CNodeList_HashTableT()

    45

		: m_open_queue(204800)

    46

	{

    47

		m_new_node = NULL;

    48

	}

    49

	/** destructor */

    50

	~CNodeList_HashTableT()

    51

	{

    52

	}

    53

	/** return number of open nodes */

    54

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

    55

	/** return number of closed nodes */

    56

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

    57

	/** allocate new data item from m_arr */

    58

	FORCEINLINE Titem_* CreateNewNode()

    59

	{

    60

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

    61

		return m_new_node;

    62

	}

    63

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

    64

	FORCEINLINE void FoundBestNode(Titem_& item)

    65

	{

    66

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

    67

		if (&item == m_new_node)

    68

			m_new_node = NULL;

    69

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

    70

	}

    71

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

    72

	FORCEINLINE void InsertOpenNode(Titem_& item)

    73

	{

    74

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

    75

		m_open.Push(item);

    76

		// TODO: check if m_open_queue is not full

    77

		assert(!m_open_queue.IsFull());

    78

		m_open_queue.Push(item);

    79

		if (&item == m_new_node)

    80

			m_new_node = NULL;

    81

	}

    82

	/** return the best open node */

    83

	FORCEINLINE Titem_* GetBestOpenNode()

    84

	{

    85

		if (!m_open_queue.IsEmpty()) {

    86

			Titem_& item = m_open_queue.GetHead();

    87

			return &item;

    88

		}

    89

		return NULL;

    90

	}

    91

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

    92

	FORCEINLINE Titem_* PopBestOpenNode()

    93

	{

    94

		if (!m_open_queue.IsEmpty()) {

    95

			Titem_& item = m_open_queue.PopHead();

    96

			m_open.Pop(item);

    97

			return &item;

    98

		}

    99

		return NULL;

   100

	}

   101

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

   102

	FORCEINLINE Titem_* FindOpenNode(const Key& key)

   103

	{

   104

		Titem_* item = m_open.Find(key);

   105

		return item;

   106

	}

   107

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

   108

	FORCEINLINE Titem_& PopOpenNode(const Key& key)

   109

	{

   110

		Titem_& item = m_open.Pop(key);

   111

		int idxPop = m_open_queue.FindLinear(item);

   112

		m_open_queue.RemoveByIdx(idxPop);

   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

	template <class D> void Dump(D &dmp) const

   132

	{

   133

		dmp.WriteStructT("m_arr", &m_arr);

   134

	}

   135

};

   136

   137

#endif /* NODELIST_HPP */