gwnavruntime/querysystem/workingmemcontainers/workingmembinaryheap.h Source File

workingmembinaryheap.h
Go to the documentation of this file.
1 /*
2 * Copyright 2015 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 #ifndef Navigation_WorkingMemBinaryHeap_H
9 #define Navigation_WorkingMemBinaryHeap_H
10 
14 
15 namespace Kaim
16 {
17 
18 typedef KyUInt16 IndexInBinHeap;
19 static const IndexInBinHeap IndexInBinHeap_UnSet = KyUInt16MAXVAL;
20 static const IndexInBinHeap IndexInBinHeap_Removed = IndexInBinHeap_UnSet - 1;
21 
22 template <typename T>
23 class WorkingMemBinaryHeapIndexTracker_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 template <class Item, typename Comparator = DefaultLess<Item>, typename BinaryHeapIndexTracker = WorkingMemBinaryHeapIndexTracker_None<Item> >
32 class WorkingMemBinaryHeap
33 {
34 public:
35  WorkingMemBinaryHeap();
36  WorkingMemBinaryHeap(WorkingMemory* workingMemory);
37 
38  void Init(WorkingMemory* workingMemory);
39 
40  KY_INLINE bool IsInitialized() const;
41  KY_INLINE KyUInt32 GetCount() const;
42  KY_INLINE KyUInt32 GetCapacity() const;
43 
44  KY_INLINE bool IsEmpty() const;
45  KY_INLINE bool IsFull();
46 
47  KY_INLINE void Clear();
48 
49  /* Retrieves the first sorted element in the container.
50  \pre IsEmpty() == false */
51  KY_INLINE void GetFirst(Item& item) const;
52 
53  /* Retrieves the first sorted element in the container.
54  \pre IsEmpty() == false */
55  KY_INLINE const Item& GetFirst() const;
56 
57  /* Add a element in the container. */
58  void Insert(const Item& item);
59 
60  /* Removes and retrieves the first sorted element in the container.
61  \pre IsEmpty() == false
62  \post IsSorted() == true */
63  void ExtractFirst(Item& item);
64 
65  /* Updates the referenced element and sort the container.
66  \pre index < GetCount()
67  \post IsSorted() == true */
68  void UpdateAt(KyUInt32 index);
69 
70  Comparator& GetComparator() { return m_comparator; }
71 
72  void ReleaseWorkingMemoryBuffer() { m_heap.ReleaseWorkingMemoryBuffer(); }
73 
74 private:
75  KY_INLINE KyUInt32 GetParentIndex(KyUInt32 index) { return (index - 1) >> 1; }
76  KY_INLINE KyUInt32 GetLeftChildIndex(KyUInt32 index) { return (index << 1) + 1; }
77  KY_INLINE KyUInt32 GetRigthChildIndex(KyUInt32 index) { return (index << 1) + 2; }
78 
79  /* Moves an element towards the first element until it is sorted.*/
80  void PercolateUp(KyUInt32 HoleIndex);
81 
82  /* Moves an element towards the last element until it is sorted.*/
83  void PercolateDown(KyUInt32 HoleIndex, KyUInt32 currentCount);
84 
85 private:
86  WorkingMemArray<Item> m_heap;
87 public:
88  Comparator m_comparator;
89  BinaryHeapIndexTracker m_binayHeapTracker;
90 };
91 
92 }
93 
95 
96 
97 #endif
98 
Definition: gamekitcrowddispersion.h:20
#define KyUInt16MAXVAL
The maximum value that can be stored in the KyUInt16 variable type.
Definition: types.h:230
unsigned short KyUInt16
Type used internally to represent an unsigned 16-bit integer.
Definition: types.h:40
unsigned int KyUInt32
Type used internally to represent an unsigned 32-bit integer.
Definition: types.h:36