F´ Flight Software - C/C++ Documentation  devel
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 <FpConfig.hpp>
19 #include <Fw/Logger/Logger.hpp>
20 #include "Fw/Types/Assert.hpp"
21 
22 #include <cstdio>
23 #include <new>
24 
25 // Macros for traversing the heap:
26 #define LCHILD(x) (2 * x + 1)
27 #define RCHILD(x) (2 * x + 2)
28 #define PARENT(x) ((x - 1) / 2)
29 
30 namespace Types {
31 
33  // Initialize the heap:
34  this->m_capacity = 0;
35  this->m_heap = nullptr;
36  this->m_size = 0;
37  this->m_order = 0;
38 }
39 
41  delete[] this->m_heap;
42  this->m_heap = nullptr;
43 }
44 
45 bool MaxHeap::create(FwSizeType capacity) {
46  FW_ASSERT(this->m_heap == nullptr);
47  // Loop bounds will overflow if capacity set to the max allowable value
48  FW_ASSERT(capacity < std::numeric_limits<FwSizeType>::max());
49  this->m_heap = new (std::nothrow) Node[capacity];
50  if (nullptr == this->m_heap) {
51  return false;
52  }
53  this->m_capacity = capacity;
54  return true;
55 }
56 
58  // If the queue is full, return false:
59  if (this->isFull()) {
60  return false;
61  }
62 
63  // Heap indexes:
64  FwSizeType parent;
65  FwSizeType index = this->m_size;
66 
67  // Max loop bounds for bit flip protection:
68  const FwSizeType maxIter = this->m_size + 1;
69  FW_ASSERT(maxIter != 0);
70  // Start at the bottom of the heap and work our ways
71  // upwards until we find a parent that has a value
72  // greater than ours.
73  FwSizeType i = 0;
74  for (i = 0; (i < maxIter) && (index != 0); i++) {
75  // Get the parent index:
76  parent = PARENT(index);
77  // The parent index should ALWAYS be less than the
78  // current index. Let's verify that.
79  FW_ASSERT(parent < index, static_cast<FwAssertArgType>(parent), static_cast<FwAssertArgType>(index));
80  // If the current value is less than the parent,
81  // then the current index is in the correct place,
82  // so break out of the loop:
83  if (value <= this->m_heap[parent].value) {
84  break;
85  }
86  // Swap the parent and child:
87  this->m_heap[index] = this->m_heap[parent];
88  index = parent;
89  }
90 
91  // Check for programming errors or bit flips:
92  FW_ASSERT(i < maxIter, static_cast<FwAssertArgType>(i), static_cast<FwAssertArgType>(maxIter));
93  FW_ASSERT(index <= this->m_size, static_cast<FwAssertArgType>(index));
94 
95  // Set the values of the new element:
96  this->m_heap[index].value = value;
97  this->m_heap[index].order = m_order;
98  this->m_heap[index].id = id;
99 
100  ++this->m_size;
101  ++this->m_order;
102  return true;
103 }
104 
106  // If there is nothing in the heap then
107  // return false:
108  if (this->isEmpty()) {
109  return false;
110  }
111 
112  // Set the return values to the top (max) of
113  // the heap:
114  value = this->m_heap[0].value;
115  id = this->m_heap[0].id;
116 
117  // Now place the last element on the heap in
118  // the root position, and resize the heap.
119  // This will put the smallest value in the
120  // heap on the top, violating the heap property.
121  FwSizeType index = this->m_size - 1;
122  // Fw::Logger::log("Putting on top: i: %u v: %d\n", index, this->m_heap[index].value);
123  this->m_heap[0] = this->m_heap[index];
124  --this->m_size;
125 
126  // Now that the heap property is violated, we
127  // need to reorganize the heap to restore it's
128  // heapy-ness.
129  this->heapify();
130  return true;
131 }
132 
133 // Is the heap full:
135  return (this->m_size == this->m_capacity);
136 }
137 
138 // Is the heap empty:
140  return (this->m_size == 0);
141 }
142 
143 // Get the current size of the heap:
145  return this->m_size;
146 }
147 
148 // A non-recursive heapify method.
149 // Note: This method had an additional property, such that
150 // items pushed of the same priority will be popped in FIFO
151 // order.
152 void MaxHeap::heapify() {
153  FwSizeType index = 0;
154  FwSizeType left;
155  FwSizeType right;
156  FwSizeType largest;
157 
158  // Max loop bounds for bit flip protection:
159  const FwSizeType maxIter = this->m_size + 1;
160  FwSizeType i = 0;
161 
162  for (i = 0; (i < maxIter) && (index <= this->m_size); i++) {
163  // Get the children indexes for this node:
164  left = LCHILD(index);
165  right = RCHILD(index);
166  FW_ASSERT(left > index, static_cast<FwAssertArgType>(left), static_cast<FwAssertArgType>(index));
167  FW_ASSERT(right > left, static_cast<FwAssertArgType>(right), static_cast<FwAssertArgType>(left));
168 
169  // If the left node is bigger than the heap
170  // size, we have reached the end of the heap
171  // so we can stop:
172  if (left >= this->m_size) {
173  break;
174  }
175 
176  // Initialize the largest node to the current
177  // node:
178  largest = index;
179 
180  // Which one is larger, the current node or
181  // the left node?:
182  largest = this->max(left, largest);
183 
184  // Make sure the right node exists before checking it:
185  if (right < this->m_size) {
186  // Which one is larger, the current largest
187  // node or the right node?
188  largest = this->max(right, largest);
189  }
190 
191  // If the largest node is the current node
192  // then we are done heapifying:
193  if (largest == index) {
194  break;
195  }
196 
197  // Swap the largest node with the current node:
198  this->swap(index, largest);
199 
200  // Set the new index to whichever child was larger:
201  index = largest;
202  }
203 
204  // Check for programming errors or bit flips:
205  FW_ASSERT(i < maxIter, static_cast<FwAssertArgType>(i), static_cast<FwAssertArgType>(maxIter));
206  FW_ASSERT(index <= this->m_size, static_cast<FwAssertArgType>(index));
207 }
208 
209 // Return the maximum priority index between two nodes. If their
210 // priorities are equal, return the oldest to keep the heap stable
211 FwSizeType MaxHeap::max(FwSizeType a, FwSizeType b) {
212  static_assert(not std::numeric_limits<FwSizeType>::is_signed, "FwSizeType must be unsigned");
213  FW_ASSERT(a < this->m_size, static_cast<FwAssertArgType>(a), static_cast<FwAssertArgType>(this->m_size));
214  FW_ASSERT(b < this->m_size, static_cast<FwAssertArgType>(b), static_cast<FwAssertArgType>(this->m_size));
215 
216  // Extract the priorities:
217  FwQueuePriorityType aValue = this->m_heap[a].value;
218  FwQueuePriorityType bValue = this->m_heap[b].value;
219 
220  // If the priorities are equal, the "larger" one will be
221  // the "older" one as determined by order pushed on to the
222  // heap. Using this secondary ordering technique makes the
223  // heap stable (ie. FIFO for equal priority elements).
224  // Note: We check this first, because it is the most common
225  // case. Let's save as many ticks as we can...
226  if (aValue == bValue) {
227  FwSizeType aAge = this->m_order - this->m_heap[a].order;
228  FwSizeType bAge = this->m_order - this->m_heap[b].order;
229  if (aAge > bAge) {
230  return a;
231  }
232  return b;
233  }
234 
235  // Which priority is larger?:
236  if (aValue > bValue) {
237  return a;
238  }
239  // B is larger:
240  return b;
241 }
242 
243 // Swap two nodes in the heap:
244 void MaxHeap::swap(FwSizeType a, FwSizeType b) {
245  FW_ASSERT(a < this->m_size, static_cast<FwAssertArgType>(a), static_cast<FwAssertArgType>(this->m_size));
246  FW_ASSERT(b < this->m_size, static_cast<FwAssertArgType>(b), static_cast<FwAssertArgType>(this->m_size));
247  Node temp = this->m_heap[a];
248  this->m_heap[a] = this->m_heap[b];
249  this->m_heap[b] = temp;
250 }
251 
252 } // namespace Types
#define FW_ASSERT(...)
Definition: Assert.hpp:14
PlatformAssertArgType FwAssertArgType
Definition: FpConfig.h:39
PlatformSizeType FwSizeType
Definition: FpConfig.h:35
PlatformQueuePriorityType FwQueuePriorityType
Definition: FpConfig.h:55
C++-compatible configuration header for fprime configuration.
#define LCHILD(x)
Definition: MaxHeap.cpp:26
#define PARENT(x)
Definition: MaxHeap.cpp:28
#define RCHILD(x)
Definition: MaxHeap.cpp:27
MaxHeap()
MaxHeap constructor.
Definition: MaxHeap.cpp:32
FwSizeType getSize() const
Get the current number of elements on the heap.
Definition: MaxHeap.cpp:144
bool isFull()
Is the heap full?
Definition: MaxHeap.cpp:134
~MaxHeap()
MaxHeap deconstructor.
Definition: MaxHeap.cpp:40
bool isEmpty()
Is the heap empty?
Definition: MaxHeap.cpp:139
bool pop(FwQueuePriorityType &value, FwSizeType &id)
Pop an item from the heap.
Definition: MaxHeap.cpp:105
bool create(FwSizeType capacity)
MaxHeap creation.
Definition: MaxHeap.cpp:45
bool push(FwQueuePriorityType value, FwSizeType id)
Push an item onto the heap.
Definition: MaxHeap.cpp:57