F´ Flight Software - C/C++ Documentation  devel
A framework for building embedded system applications to NASA flight quality standards.
MaxHeap.hpp
Go to the documentation of this file.
1 // ======================================================================
2 // \title MaxHeap.hpp
3 // \author dinkel
4 // \brief An implementation of a stable max heap data structure
5 //
6 // \copyright
7 // Copyright 2009-2015, by the California Institute of Technology.
8 // ALL RIGHTS RESERVED. United States Government Sponsorship
9 // acknowledged.
10 //
11 // ======================================================================
12 
13 #ifndef UTILS_TYPES_MAX_HEAP_HPP
14 #define UTILS_TYPES_MAX_HEAP_HPP
15 
16 #include <FpConfig.hpp>
17 
18 namespace Types {
19 
28 class MaxHeap {
29  public:
34  MaxHeap();
39  ~MaxHeap();
47  bool create(FwSizeType capacity);
57  bool push(FwQueuePriorityType value, FwSizeType id);
67  bool pop(FwQueuePriorityType& value, FwSizeType& id);
73  bool isFull();
79  bool isEmpty();
85  FwSizeType getSize() const;
86 
87  private:
88  // Private functions:
89  // Ensure the heap meets the heap property:
90  void heapify();
91  // Swap two elements on the heap:
92  void swap(FwSizeType a, FwSizeType b);
93  // Return the max between two elements on the heap:
95 
96  // The data structure for a node on the heap:
97  struct Node {
98  FwQueuePriorityType value; // the priority of the node
99  FwSizeType order; // order in which node was pushed
100  FwSizeType id; // unique id for this node
101  };
102 
103  // Private members:
104  Node* m_heap; // the heap itself
105  FwSizeType m_size; // the current size of the heap
106  FwSizeType m_order; // the current count of heap pushes
107  FwSizeType m_capacity; // the maximum capacity of the heap
108 };
109 
110 } // namespace Types
111 
112 #endif // UTILS_TYPES_MAX_HEAP_HPP
PlatformSizeType FwSizeType
Definition: FpConfig.h:35
PlatformQueuePriorityType FwQueuePriorityType
Definition: FpConfig.h:55
C++-compatible configuration header for fprime configuration.
A stable max heap data structure.
Definition: MaxHeap.hpp:28
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