OdinAI
 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>
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
int Pop()
Definition: PriorityQueue.h:60
void ChangePriority(int index)
Definition: PriorityQueue.h:71
bool Empty() const
Definition: PriorityQueue.h:36
void Insert(int index)
Definition: PriorityQueue.h:44
Definition: PriorityQueue.h:24