OdinAI

- Main Page
- Namespaces
- Classes
- Files
- Examples

- File List

All Classes Namespaces Functions Variables
PriorityQueue.h
1 /*******************************************************************************
2 * ________ .___.__ _____ .___
3 * \_____ \ __| _/|__| ____ / _ \ | |
4 * / | \ / __ | | |/ \ / /_\ \| |
5 * / | \/ /_/ | | | | \/ | \ |
6 * \_______ /\____ | |__|___| /\____|__ /___|
7 * \/ \/ \/ \/
8 *
9 * Copyright (c) Emil Sandstø 2012
10 *******************************************************************************/
11 #ifndef ODINAI_PRIORITY_QUEUE_H_
12 #define ODINAI_PRIORITY_QUEUE_H_
13
14 #include <vector>
15 #include "DebugUtil.h"
16
17 namespace OdinAI
18 {
23 template<class T>
24 class IndexedPriorityQLow
25 {
26 public:
27 IndexedPriorityQLow(std::vector<T> &keys, int maxSize) : m_keys(keys),
28 m_maxSize(maxSize),
29 m_size(0),
30 m_heap(maxSize+1),
31 m_heapHandler(maxSize+1) {}
32
36 bool Empty() const
37 {
38 return m_size == 0;
39 }
40
44 void Insert(int index)
45 {
46 Assert(m_size + 1 <= m_maxSize &&
47 "PriorityQueue::Insert() not enough memory!");
48
49 ++m_size;
50
51 m_heap[m_size] = index;
52 m_heapHandler[index] = m_size;
53
54 ReorderUpwards(m_size);
55 }
56
60 int Pop()
61 {
62 Swap(1, m_size);
63 ReorderDownwards(1, m_size - 1);
64
65 return m_heap[m_size--];
66 }
67
71 void ChangePriority(int index)
72 {
73 ReorderUpwards(m_heapHandler[index]);
74 }
75 private:
76 std::vector<T> &m_keys;
77 std::vector<int> m_heap;
78 std::vector<int> m_heapHandler;
79
80 int m_size;
81 int m_maxSize;
82
86 void Swap(int a, int b)
87 {
88 int tmp = m_heap[a];
89 m_heap[a] = m_heap[b];
90 m_heap[b] = tmp;
91
92 m_heapHandler[m_heap[a]] = a;
93 m_heapHandler[m_heap[b]] = b;
94 }
95
96 void ReorderUpwards(int n)
97 {
98 int halfN = 0;
99 //Use bitshift to do n / 2 as fast as possible.
100 while(n > 1 && m_keys[m_heap[(halfN = n >> 1)]] > m_keys[m_heap[n]])
101 {
102 Swap(halfN, n);
103
104 n = halfN;
105 }
106 }
107
108 void ReorderDownwards(int n, int heapSize)
109 {
110 //Use bitshift to do n * 2 as fast as possible.
111 int doubleN = 0;
112 while((doubleN = n << 1) <= heapSize)
113 {
114 if(doubleN < heapSize && m_keys[m_heap[doubleN]] > m_keys[m_heap[doubleN+1]])
115 {
116 ++doubleN;
117 }
118
119 if(m_keys[m_heap[n]] > m_keys[m_heap[doubleN]])
120 {
121 Swap(doubleN, n);
122
123 n = doubleN;
124 }
125 else
126 {
127 return;
128 }
129 }
130 }
131 };
132 }
133
134 #endif
OdinAI::IndexedPriorityQLow::Pop
int Pop()
Definition: PriorityQueue.h:60
OdinAI::IndexedPriorityQLow::ChangePriority
void ChangePriority(int index)
Definition: PriorityQueue.h:71
OdinAI::IndexedPriorityQLow::Empty
bool Empty() const
Definition: PriorityQueue.h:36
OdinAI::IndexedPriorityQLow::Insert
void Insert(int index)
Definition: PriorityQueue.h:44
OdinAI::IndexedPriorityQLow
Definition: PriorityQueue.h:24