gwnavruntime/containers/binaryheap.h Source File

binaryheap.h
Go to the documentation of this file.
1 /*
2 * Copyright 2016 Autodesk, Inc. All rights reserved.
3 * Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
4 * or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
5 */
6 
7 
8 #pragma once
9 
10 #include "gwnavruntime/base/memory.h"
11 #include "gwnavruntime/kernel/SF_Alg.h"
12 #include "gwnavruntime/basesystem/logger.h"
13 #include "gwnavruntime/math/fastmath.h"
14 #include "gwnavruntime/containers/kyarray.h"
15 
16 namespace Kaim
17 {
18 
19 static const KyUInt32 BinaryHeapInvalidReference = KyUInt32MAXVAL;
20 
21 /* Class for BinaryHeap to ignore index tracking. */
22 template <typename T>
23 class BinaryHeapIndexTracker_None
24 {
25 public:
26  static void OnAdd(T& /*value*/, KyUInt32 /*indexInBinaryHeap*/) {}
27  static void OnRemove(T& /*value*/) {}
28  static void OnSwap(T& /*lhs*/, T& /*rhs*/) {}
29 };
30 
31 /* Class for BinaryHeap to update index in binaryHeap assuming index is T::m_indexInBinaryHeap. */
32 template <typename T>
33 class BinaryHeapIndexTracker_IndexInBinaryHeap
34 {
35 public:
36  // Called after the element has been added.
37  static KY_INLINE void OnAdd(T& value, KyUInt32 indexInBinaryHeap) { value.m_indexInBinaryHeap = indexInBinaryHeap; }
38  // Called before the element has been removed.
39  static KY_INLINE void OnRemove(T& value) { value.m_indexInBinaryHeap = BinaryHeapInvalidReference; }
40  // Called after the elements has been swapped.
41  static KY_INLINE void OnSwap(T& lhs, T& rhs) { Alg::Swap(lhs.m_indexInBinaryHeap, rhs.m_indexInBinaryHeap); }
42 };
43 
44 /* Class for BinaryHeap to update index in binaryHeap assuming index is T::m_indexInBinaryHeap.
45  Specialisation for pointer.
46 */
47 template <typename T>
48 class BinaryHeapIndexTracker_IndexInBinaryHeap<T*>
49 {
50 public:
51  // Called after the element has been added.
52  static KY_INLINE void OnAdd(T*& value, KyUInt32 indexInBinaryHeap) { value->m_indexInBinaryHeap = indexInBinaryHeap; }
53  // Called before the element has been removed.
54  static KY_INLINE void OnRemove(T*& value) { value->m_indexInBinaryHeap = BinaryHeapInvalidReference; }
55  // Called after the elements has been swapped.
56  static KY_INLINE void OnSwap(T*& lhs, T*& rhs) { Alg::Swap(lhs->m_indexInBinaryHeap, rhs->m_indexInBinaryHeap); }
57 };
58 
59 /*
60  BinaryHeap is a class in which the first element is always the element with the "best" cost (according to Comparator)
61  BinaryHeapIndexTracker is a class which is used to keep a track of index in BinaryHeap to allow removal or update or internal element.
62  (@see BinaryHeapIndexTracker_IndexInBinaryHeap as example of BinaryHeapIndexTracker).
63 */
64 template <class T, typename ArrayType = KyArray<T>, typename Comparator = DefaultLess<T>, typename BinaryHeapIndexTracker = BinaryHeapIndexTracker_None<T> >
65 class BinaryHeap
66 {
67  KY_DEFINE_NEW_DELETE_OPERATORS(Stat_Default_Mem)
68 public:
69 
70  typedef typename ArrayType::Iterator Iterator;
71  typedef typename ArrayType::ConstIterator ConstIterator;
72 
73 public:
74  /* Retrieves the first sorted element in the container.
75  \pre IsEmpty() == false */
76  KY_INLINE void GetFirst(T& item) const;
77 
78  /* Retrieves the first sorted element in the container.
79  \pre IsEmpty() == false */
80  KY_INLINE const T& GetFirst() const { return *Begin(); }
81 
82  /* Add a element in the container.
83  \post IsSorted() == true */
84  void Insert(const T& item);
85 
86  /* Removes the first sorted element in the container.
87  \pre IsEmpty() == false
88  \post IsSorted() == true */
89  void ExtractFirst();
90 
91  /* Removes and retrieves the first sorted element in the container.
92  \pre IsEmpty() == false
93  \post IsSorted() == true */
94  void ExtractFirst(T& item);
95 
96  KY_INLINE void Clear() { m_heap.Clear(); }
97  KY_INLINE void Reserve(KyUInt32 size) { return m_heap.Reserve(size); }
98 
99  KY_INLINE KyUInt32 GetCount() const { return (KyUInt32)m_heap.GetSize();}
100  KY_INLINE KyUInt32 GetCapacity() const { return (KyUInt32)m_heap.GetCapacity();}
101  KY_INLINE bool IsEmpty() const { return GetCount() == 0; }
102 
103  bool IsSorted() const;
104 
105  /* Retrieves the referenced element in the container.
106  \pre index < GetCount() */
107  void At(KyUInt32 index, T& item);
108 
109  KY_INLINE const T& operator[](KyUInt32 index) const { return m_heap[index]; }
110  KY_INLINE T& operator[](KyUInt32 index) { return m_heap[index]; }
111 
112  /* Updates the referenced element and sort the container.
113  \pre index < GetCount()
114  \post IsSorted() == true */
115  void UpdateAt(KyUInt32 index);
116 
117  /* Removes the referenced element in the container.
118  \pre index < GetCount()
119  \post IsSorted() == true */
120  void RemoveAt(KyUInt32 index);
121 
122  /* Removes the element pointed by the iterator in the container.
123  \post IsSorted() == true
124  \returns An iterator pointing to the following element in the container.*/
125  Iterator Erase(Iterator it);
126 
127  /* Returns an iterator that points to the first element in the container. */
128  KY_INLINE ConstIterator Begin() const { return m_heap.Begin(); }
129  KY_INLINE Iterator Begin() { return m_heap.Begin(); }
130 
131  /* Returns an iterator that points after the last element in the container. */
132  KY_INLINE ConstIterator End() const { return m_heap.End(); }
133  KY_INLINE Iterator End() { return m_heap.End(); }
134 
135  Comparator& GetComparator() { return m_comparator; }
136  ArrayType& GetHeap() { return m_heap; }
137 private:
138  KY_INLINE ConstIterator GetLast() const { return ConstIterator(&m_heap, (GetCount() - 1)); }
139  KY_INLINE Iterator GetLast() { return Iterator(&m_heap, (GetCount() - 1)); }
140 
141  KY_INLINE ConstIterator GetParent(ConstIterator it) const {return Begin() + ((GetIndex(it) - 1) >> 1);}
142  KY_INLINE Iterator GetParent(Iterator it) {return Begin() + ((GetIndex(it) - 1) >> 1);}
143 
144  /* Returns an iterator that points to the left child element in the container */
145  KY_INLINE ConstIterator GetLeft(ConstIterator it) const {return Begin() + 1 + (GetIndex(it) << 1);}
146  KY_INLINE Iterator GetLeft(Iterator it) {return Begin() + 1 + (GetIndex(it) << 1);}
147 
148  /* Returns an iterator that points to the right child element in the container */
149  KY_INLINE ConstIterator GetRight(ConstIterator it) const {return Begin() + 2 + (GetIndex(it) << 1);}
150  KY_INLINE Iterator GetRight(Iterator it) {return Begin() + 2 + (GetIndex(it) << 1);}
151 
152  KY_INLINE KyUInt32 GetIndex(ConstIterator it) const { return KyUInt32(it.GetIndex()); }
153  KY_INLINE KyUInt32 GetIndex(Iterator it) const { return KyUInt32(it.GetIndex()); }
154 
155  /* Moves an element towards the first element until it is sorted.*/
156  void PercolateUp(Iterator hole);
157 
158  /* Moves an element towards the last element until it is sorted.*/
159  void PercolateDown(Iterator hole);
160 
161 private:
162  ArrayType m_heap;
163  Comparator m_comparator;
164 };
165 
166 } // namespace Kaim
167 
168 #include "gwnavruntime/containers/binaryheap.inl"
169 
KyUInt32
std::uint32_t KyUInt32
uint32_t
Definition: types.h:29
KY_DEFINE_NEW_DELETE_OPERATORS
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:132
Kaim
The Autodesk Navigation namespace.
Definition: gamekitcrowddispersion.cpp:17
KyUInt32MAXVAL
#define KyUInt32MAXVAL
KyUInt32 max value
Definition: types.h:68
SF_Alg.h
Please send us your comment about this page