F´ Flight Software - C/C++ Documentation  NASA-v2.0.0
A framework for building embedded system applications to NASA flight quality standards.
MaxHeap.cpp
Go to the documentation of this file.
1 // ======================================================================
2 // \title MaxHeap.cpp
3 // \author dinkel
4 // \brief An implementation of a stable max heap data structure. Items
5 // popped off the heap are guaranteed to be in order of decreasing
6 // "value" (max removed first). Items of equal "value" will be
7 // popped off in FIFO order. The performance of both push and pop
8 // is O(log(n)).
9 //
10 // \copyright
11 // Copyright 2009-2015, by the California Institute of Technology.
12 // ALL RIGHTS RESERVED. United States Government Sponsorship
13 // acknowledged.
14 //
15 // ======================================================================
16 
18 #include "Fw/Types/BasicTypes.hpp"
19 #include "Fw/Types/Assert.hpp"
20 #include <stdio.h>
21 #include <Fw/Logger/Logger.hpp>
22 
23 // Macros for traversing the heap:
24 #define LCHILD(x) (2 * x + 1)
25 #define RCHILD(x) (2 * x + 2)
26 #define PARENT(x) ((x - 1) / 2)
27 
28 namespace Os {
29 
31  // Initialize the heap:
32  this->capacity = 0;
33  this->heap = NULL;
34  this->size = 0;
35  this->order = 0;
36  }
37 
39  delete [] this->heap;
40  this->heap = NULL;
41  }
42 
44  {
45  // The heap has already been created.. so delete
46  // it and try again.
47  if( NULL != this->heap ) {
48  delete [] this->heap;
49  this->heap = NULL;
50  }
51 
52  this->heap = new Node[capacity];
53  if( NULL == this->heap ) {
54  return false;
55  }
56  this->capacity = capacity;
57  return true;
58  }
59 
61  // If the queue is full, return false:
62  if(this->isFull()) {
63  return false;
64  }
65 
66  // Heap indexes:
67  NATIVE_UINT_TYPE parent;
68  NATIVE_UINT_TYPE index = this->size;
69 
70  // Max loop bounds for bit flip protection:
71  NATIVE_UINT_TYPE maxIter = this->size+1;
72  NATIVE_UINT_TYPE maxCount = 0;
73 
74  // Start at the bottom of the heap and work our ways
75  // upwards until we find a parent that has a value
76  // greater than ours.
77  while(index && maxCount < maxIter) {
78  // Get the parent index:
79  parent = PARENT(index);
80  // The parent index should ALWAYS be less than the
81  // current index. Let's verify that.
82  FW_ASSERT(parent < index, parent, index);
83  // If the current value is less than the parent,
84  // then the current index is in the correct place,
85  // so break out of the loop:
86  if(value <= this->heap[parent].value) {
87  break;
88  }
89  // Swap the parent and child:
90  this->heap[index] = this->heap[parent];
91  index = parent;
92  ++maxCount;
93  }
94 
95  // Check for programming errors or bit flips:
96  FW_ASSERT(maxCount < maxIter, maxCount, maxIter);
97  FW_ASSERT(index <= this->size, index);
98 
99  // Set the values of the new element:
100  this->heap[index].value = value;
101  this->heap[index].order = order;
102  this->heap[index].id = id;
103 
104  ++this->size;
105  ++this->order;
106  return true;
107  }
108 
110  // If there is nothing in the heap then
111  // return false:
112  if(this->isEmpty()) {
113  return false;
114  }
115 
116  // Set the return values to the top (max) of
117  // the heap:
118  value = this->heap[0].value;
119  id = this->heap[0].id;
120 
121  // Now place the last element on the heap in
122  // the root position, and resize the heap.
123  // This will put the smallest value in the
124  // heap on the top, violating the heap property.
125  NATIVE_UINT_TYPE index = this->size-1;
126  // Fw::Logger::logMsg("Putting on top: i: %u v: %d\n", index, this->heap[index].value);
127  this->heap[0]= this->heap[index];
128  --this->size;
129 
130  // Now that the heap property is violated, we
131  // need to reorganize the heap to restore it's
132  // heapy-ness.
133  this->heapify();
134  return true;
135  }
136 
137  // Is the heap full:
139  return (this->size == this->capacity);
140  }
141 
142  // Is the heap empty:
144  return (this->size == 0);
145  }
146 
147  // Get the current size of the heap:
149  return this->size;
150  }
151 
152  // A non-recursive heapify method.
153  // Note: This method had an additional property, such that
154  // items pushed of the same priority will be popped in FIFO
155  // order.
156  void MaxHeap::heapify() {
157  NATIVE_UINT_TYPE index = 0;
158  NATIVE_UINT_TYPE left;
159  NATIVE_UINT_TYPE right;
160  NATIVE_UINT_TYPE largest;
161 
162  // Max loop bounds for bit flip protection:
163  NATIVE_UINT_TYPE maxIter = this->size+1;
164  NATIVE_UINT_TYPE maxCount = 0;
165 
166  while(index <= this->size && maxCount < maxIter) {
167  // Get the children indexes for this node:
168  left = LCHILD(index);
169  right = RCHILD(index);
170  FW_ASSERT(left > index, left, index);
171  FW_ASSERT(right > left, right, left);
172 
173  // If the left node is bigger than the heap
174  // size, we have reached the end of the heap
175  // so we can stop:
176  if (left >= this->size) {
177  break;
178  }
179 
180  // Initialize the largest node to the current
181  // node:
182  largest = index;
183 
184  // Which one is larger, the current node or
185  // the left node?:
186  largest = this->max(left, largest);
187 
188  // Make sure the right node exists before checking it:
189  if (right < this->size) {
190  // Which one is larger, the current largest
191  // node or the right node?
192  largest = this->max(right, largest);
193  }
194 
195  // If the largest node is the current node
196  // then we are done heapifying:
197  if (largest == index)
198  {
199  break;
200  }
201 
202  // Swap the largest node with the current node:
203  // Fw::Logger::logMsg("Swapping: i: %u v: %d with i: %u v: %d\n",
204  // index, this->heap[index].value,
205  // largest, this->heap[largest].value);
206  this->swap(index, largest);
207 
208  // Set the new index to whichever child was larger:
209  index = largest;
210  }
211 
212  // Check for programming errors or bit flips:
213  FW_ASSERT(maxCount < maxIter, maxCount, maxIter);
214  FW_ASSERT(index <= this->size, index);
215  }
216 
217  // Return the maximum priority index between two nodes. If their
218  // priorities are equal, return the oldest to keep the heap stable
220  FW_ASSERT(a < this->size, a, this->size);
221  FW_ASSERT(b < this->size, b, this->size);
222 
223  // Extract the priorities:
224  NATIVE_INT_TYPE aValue = this->heap[a].value;
225  NATIVE_INT_TYPE bValue = this->heap[b].value;
226 
227  // If the priorities are equal, the "larger" one will be
228  // the "older" one as determined by order pushed on to the
229  // heap. Using this secondary ordering technique makes the
230  // heap stable (ie. FIFO for equal priority elements).
231  // Note: We check this first, because it is the most common
232  // case. Let's save as many ticks as we can...
233  if(aValue == bValue) {
234  NATIVE_UINT_TYPE aAge = this->order - this->heap[a].order;
235  NATIVE_UINT_TYPE bAge = this->order - this->heap[b].order;
236  if(aAge > bAge) {
237  return a;
238  }
239  return b;
240  }
241 
242  // Which priority is larger?:
243  if( aValue > bValue ) {
244  return a;
245  }
246  // B is larger:
247  return b;
248  }
249 
250  // Swap two nodes in the heap:
251  void MaxHeap::swap(NATIVE_UINT_TYPE a, NATIVE_UINT_TYPE b) {
252  FW_ASSERT(a < this->size, a, this->size);
253  FW_ASSERT(b < this->size, b, this->size);
254  Node temp = this->heap[a];
255  this->heap[a] = this->heap[b];
256  this->heap[b] = temp;
257  }
258 
259  // Print heap, for debugging purposes only:
260  void MaxHeap::print() {
261  NATIVE_UINT_TYPE index = 0;
262  NATIVE_UINT_TYPE left;
263  NATIVE_UINT_TYPE right;
264  Fw::Logger::logMsg("Printing Heap of Size: %d\n", this->size);
265  while(index < this->size) {
266  left = LCHILD(index);
267  right = RCHILD(index);
268 
269  if( left >= size && index == 0) {
270  Fw::Logger::logMsg("i: %u v: %d d: %u -> (NULL, NULL)\n",
271  index, this->heap[index].value, this->heap[index].id);
272  }
273  else if( right >= size && left < size ) {
274  Fw::Logger::logMsg("i: %u v: %d d: %u -> (i: %u v: %d d: %u, NULL)\n",
275  index, this->heap[index].value, this->heap[index].id,
276  left, this->heap[left].value, this->heap[left].id);
277  }
278  else if( right < size && left < size ) {
279  Fw::Logger::logMsg("i: %u v: %d d: %u -> (i: %u v: %d d: %u, i: %u v: %d d: %u)\n",
280  index, this->heap[index].value, this->heap[index].id,
281  left, this->heap[left].value,this->heap[left].id,
282  right, this->heap[right].value, this->heap[right].id);
283  }
284 
285  ++index;
286  }
287  }
288 }
Os
Definition: File.cpp:7
Os::MaxHeap::push
bool push(NATIVE_INT_TYPE value, NATIVE_UINT_TYPE id)
Push an item onto the heap.
Definition: MaxHeap.cpp:60
Os::MaxHeap::create
bool create(NATIVE_UINT_TYPE capacity)
MaxHeap creation.
Definition: MaxHeap.cpp:43
Os::MaxHeap::isEmpty
bool isEmpty()
Is the heap empty?
Definition: MaxHeap.cpp:143
Os::MaxHeap::getSize
NATIVE_UINT_TYPE getSize()
Get the current number of elements on the heap.
Definition: MaxHeap.cpp:148
Assert.hpp
LCHILD
#define LCHILD(x)
Definition: MaxHeap.cpp:24
Os::MaxHeap::~MaxHeap
~MaxHeap()
MaxHeap deconstructor.
Definition: MaxHeap.cpp:38
PARENT
#define PARENT(x)
Definition: MaxHeap.cpp:26
NATIVE_UINT_TYPE
unsigned int NATIVE_UINT_TYPE
native unsigned integer type declaration
Definition: BasicTypes.hpp:30
Os::MaxHeap::print
void print()
Print the contents of the heap to stdout.
Definition: MaxHeap.cpp:260
FW_ASSERT
#define FW_ASSERT(...)
Definition: Assert.hpp:9
Os::MaxHeap::isFull
bool isFull()
Is the heap full?
Definition: MaxHeap.cpp:138
Fw::Logger::logMsg
static void logMsg(const char *fmt, POINTER_CAST a0=0, POINTER_CAST a1=0, POINTER_CAST a2=0, POINTER_CAST a3=0, POINTER_CAST a4=0, POINTER_CAST a5=0, POINTER_CAST a6=0, POINTER_CAST a7=0, POINTER_CAST a8=0, POINTER_CAST a9=0)
Definition: Logger.cpp:18
MaxHeap.hpp
BasicTypes.hpp
Declares ISF basic types.
NATIVE_INT_TYPE
int NATIVE_INT_TYPE
native integer type declaration
Definition: BasicTypes.hpp:29
RCHILD
#define RCHILD(x)
Definition: MaxHeap.cpp:25
NULL
#define NULL
NULL.
Definition: BasicTypes.hpp:100
Logger.hpp
Os::MaxHeap::pop
bool pop(NATIVE_INT_TYPE &value, NATIVE_UINT_TYPE &id)
Pop an item from the heap.
Definition: MaxHeap.cpp:109
Os::MaxHeap::MaxHeap
MaxHeap()
MaxHeap constructor.
Definition: MaxHeap.cpp:30