Sarah Marsh / Mbed OS EddystoneBeacon

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

source/EventQueue/PriorityQueue.h@0:1c7da5f83647, 2016-11-29 (annotated)

Committer:
sarahmarshy
Date:
Tue Nov 29 06:29:10 2016 +0000
Revision:
0:1c7da5f83647
Initial commit

Who changed what in which revision?

UserRevisionLine numberNew contents of line
sarahmarshy 0:1c7da5f83647 1 /*
sarahmarshy 0:1c7da5f83647 2 * Copyright (c) 2016, ARM Limited, All Rights Reserved
sarahmarshy 0:1c7da5f83647 3 * SPDX-License-Identifier: Apache-2.0
sarahmarshy 0:1c7da5f83647 4 *
sarahmarshy 0:1c7da5f83647 5 * Licensed under the Apache License, Version 2.0 (the "License"); you may
sarahmarshy 0:1c7da5f83647 6 * not use this file except in compliance with the License.
sarahmarshy 0:1c7da5f83647 7 * You may obtain a copy of the License at
sarahmarshy 0:1c7da5f83647 8 *
sarahmarshy 0:1c7da5f83647 9 * http://www.apache.org/licenses/LICENSE-2.0
sarahmarshy 0:1c7da5f83647 10 *
sarahmarshy 0:1c7da5f83647 11 * Unless required by applicable law or agreed to in writing, software
sarahmarshy 0:1c7da5f83647 12 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
sarahmarshy 0:1c7da5f83647 13 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
sarahmarshy 0:1c7da5f83647 14 * See the License for the specific language governing permissions and
sarahmarshy 0:1c7da5f83647 15 * limitations under the License.
sarahmarshy 0:1c7da5f83647 16 */
sarahmarshy 0:1c7da5f83647 17 #ifndef EVENTQUEUE_STACKPRIORITYQUEUE_H_
sarahmarshy 0:1c7da5f83647 18 #define EVENTQUEUE_STACKPRIORITYQUEUE_H_
sarahmarshy 0:1c7da5f83647 19
sarahmarshy 0:1c7da5f83647 20 #include <cstddef>
sarahmarshy 0:1c7da5f83647 21 #include "AlignedStorage.h"
sarahmarshy 0:1c7da5f83647 22
sarahmarshy 0:1c7da5f83647 23 namespace eq {
sarahmarshy 0:1c7da5f83647 24
sarahmarshy 0:1c7da5f83647 25 /**
sarahmarshy 0:1c7da5f83647 26 * Priority queue of Ts.
sarahmarshy 0:1c7da5f83647 27 * Ts are ordered from the smaller to the bigger ( < ).
sarahmarshy 0:1c7da5f83647 28 * Elements in the queue are mutable (this is a design choice).
sarahmarshy 0:1c7da5f83647 29 * After a mutation the function update should be called to ensure that the
sarahmarshy 0:1c7da5f83647 30 * queue is still properly sorted.
sarahmarshy 0:1c7da5f83647 31 * @tparam T type of elements in this queue
sarahmarshy 0:1c7da5f83647 32 * @param capacity Number of elements that this queue can contain
sarahmarshy 0:1c7da5f83647 33 */
sarahmarshy 0:1c7da5f83647 34 template<typename T, std::size_t Capacity>
sarahmarshy 0:1c7da5f83647 35 class PriorityQueue {
sarahmarshy 0:1c7da5f83647 36
sarahmarshy 0:1c7da5f83647 37 public:
sarahmarshy 0:1c7da5f83647 38 /**
sarahmarshy 0:1c7da5f83647 39 * Type of the nodes in this queue.
sarahmarshy 0:1c7da5f83647 40 */
sarahmarshy 0:1c7da5f83647 41 struct Node {
sarahmarshy 0:1c7da5f83647 42 AlignedStorage<T> storage; /// storage for the T
sarahmarshy 0:1c7da5f83647 43 Node* next; /// pointer to the next node
sarahmarshy 0:1c7da5f83647 44 };
sarahmarshy 0:1c7da5f83647 45
sarahmarshy 0:1c7da5f83647 46 /**
sarahmarshy 0:1c7da5f83647 47 * Iterator for elements of the queue.
sarahmarshy 0:1c7da5f83647 48 */
sarahmarshy 0:1c7da5f83647 49 class Iterator {
sarahmarshy 0:1c7da5f83647 50 friend PriorityQueue;
sarahmarshy 0:1c7da5f83647 51
sarahmarshy 0:1c7da5f83647 52 /// Construct an iterator from a Node.
sarahmarshy 0:1c7da5f83647 53 /// This constructor is private and can only be invoked from the PriorityQueue.
sarahmarshy 0:1c7da5f83647 54 Iterator(Node* current) :
sarahmarshy 0:1c7da5f83647 55 _current(current) {
sarahmarshy 0:1c7da5f83647 56 }
sarahmarshy 0:1c7da5f83647 57
sarahmarshy 0:1c7da5f83647 58 public:
sarahmarshy 0:1c7da5f83647 59
sarahmarshy 0:1c7da5f83647 60 /// Indirection operator.
sarahmarshy 0:1c7da5f83647 61 /// return a reference to the inner T
sarahmarshy 0:1c7da5f83647 62 T& operator*() {
sarahmarshy 0:1c7da5f83647 63 return _current->storage.get();
sarahmarshy 0:1c7da5f83647 64 }
sarahmarshy 0:1c7da5f83647 65
sarahmarshy 0:1c7da5f83647 66 /// Const version of indirection operator.
sarahmarshy 0:1c7da5f83647 67 /// return a reference to the inner T
sarahmarshy 0:1c7da5f83647 68 const T& operator*() const {
sarahmarshy 0:1c7da5f83647 69 return _current->storage.get();
sarahmarshy 0:1c7da5f83647 70 }
sarahmarshy 0:1c7da5f83647 71
sarahmarshy 0:1c7da5f83647 72 /// dereference operator.
sarahmarshy 0:1c7da5f83647 73 /// Will invoke the operation on the inner T
sarahmarshy 0:1c7da5f83647 74 T* operator->() {
sarahmarshy 0:1c7da5f83647 75 return &(_current->storage.get());
sarahmarshy 0:1c7da5f83647 76 }
sarahmarshy 0:1c7da5f83647 77
sarahmarshy 0:1c7da5f83647 78 /// const dereference operator.
sarahmarshy 0:1c7da5f83647 79 /// Will invoke the operation on the inner T
sarahmarshy 0:1c7da5f83647 80 const T* operator->() const {
sarahmarshy 0:1c7da5f83647 81 return &(_current->storage.get());
sarahmarshy 0:1c7da5f83647 82 }
sarahmarshy 0:1c7da5f83647 83
sarahmarshy 0:1c7da5f83647 84 /// pre incrementation to the next T in the list
sarahmarshy 0:1c7da5f83647 85 Iterator& operator++() {
sarahmarshy 0:1c7da5f83647 86 _current = _current->next;
sarahmarshy 0:1c7da5f83647 87 return *this;
sarahmarshy 0:1c7da5f83647 88 }
sarahmarshy 0:1c7da5f83647 89
sarahmarshy 0:1c7da5f83647 90 /// post incrementation to the next T in the list
sarahmarshy 0:1c7da5f83647 91 Iterator operator++(int) {
sarahmarshy 0:1c7da5f83647 92 Iterator tmp(*this);
sarahmarshy 0:1c7da5f83647 93 _current = _current->next;
sarahmarshy 0:1c7da5f83647 94 return tmp;
sarahmarshy 0:1c7da5f83647 95 }
sarahmarshy 0:1c7da5f83647 96
sarahmarshy 0:1c7da5f83647 97 /// Equality operator
sarahmarshy 0:1c7da5f83647 98 friend bool operator==(const Iterator& lhs, const Iterator& rhs) {
sarahmarshy 0:1c7da5f83647 99 return lhs._current == rhs._current;
sarahmarshy 0:1c7da5f83647 100 }
sarahmarshy 0:1c7da5f83647 101
sarahmarshy 0:1c7da5f83647 102 /// Unequality operator
sarahmarshy 0:1c7da5f83647 103 friend bool operator!=(const Iterator& lhs, const Iterator& rhs) {
sarahmarshy 0:1c7da5f83647 104 return !(lhs == rhs);
sarahmarshy 0:1c7da5f83647 105 }
sarahmarshy 0:1c7da5f83647 106
sarahmarshy 0:1c7da5f83647 107 /// return the internal node.
sarahmarshy 0:1c7da5f83647 108 Node* get_node() {
sarahmarshy 0:1c7da5f83647 109 return _current;
sarahmarshy 0:1c7da5f83647 110 }
sarahmarshy 0:1c7da5f83647 111
sarahmarshy 0:1c7da5f83647 112 private:
sarahmarshy 0:1c7da5f83647 113 Node* _current;
sarahmarshy 0:1c7da5f83647 114 };
sarahmarshy 0:1c7da5f83647 115
sarahmarshy 0:1c7da5f83647 116 typedef Iterator iterator;
sarahmarshy 0:1c7da5f83647 117
sarahmarshy 0:1c7da5f83647 118 /// Construct an empty priority queue.
sarahmarshy 0:1c7da5f83647 119 PriorityQueue() : nodes(), free_nodes(NULL), head(NULL), used_nodes_count(0) {
sarahmarshy 0:1c7da5f83647 120 initialize();
sarahmarshy 0:1c7da5f83647 121 }
sarahmarshy 0:1c7da5f83647 122
sarahmarshy 0:1c7da5f83647 123 /// Copy construct a priority queue.
sarahmarshy 0:1c7da5f83647 124 /// The queue will have the same content has other.
sarahmarshy 0:1c7da5f83647 125 PriorityQueue(const PriorityQueue& other) :
sarahmarshy 0:1c7da5f83647 126 nodes(), free_nodes(NULL), head(NULL), used_nodes_count(0) {
sarahmarshy 0:1c7da5f83647 127 initialize();
sarahmarshy 0:1c7da5f83647 128 copy(other);
sarahmarshy 0:1c7da5f83647 129 }
sarahmarshy 0:1c7da5f83647 130
sarahmarshy 0:1c7da5f83647 131 /// destroy a priority queue.
sarahmarshy 0:1c7da5f83647 132 ~PriorityQueue() {
sarahmarshy 0:1c7da5f83647 133 clear();
sarahmarshy 0:1c7da5f83647 134 }
sarahmarshy 0:1c7da5f83647 135
sarahmarshy 0:1c7da5f83647 136 /// Copy assignemnent from another priority queue.
sarahmarshy 0:1c7da5f83647 137 /// The content of the queue will be destroyed then the content from
sarahmarshy 0:1c7da5f83647 138 /// other will be copied.
sarahmarshy 0:1c7da5f83647 139 PriorityQueue& operator=(const PriorityQueue& other) {
sarahmarshy 0:1c7da5f83647 140 if (&other == this) {
sarahmarshy 0:1c7da5f83647 141 return *this;
sarahmarshy 0:1c7da5f83647 142 }
sarahmarshy 0:1c7da5f83647 143 copy(other);
sarahmarshy 0:1c7da5f83647 144 return *this;
sarahmarshy 0:1c7da5f83647 145 }
sarahmarshy 0:1c7da5f83647 146
sarahmarshy 0:1c7da5f83647 147 /// Push a new element to the queue.
sarahmarshy 0:1c7da5f83647 148 /// It will be added before the first element p in the queue where
sarahmarshy 0:1c7da5f83647 149 /// element < p == true.
sarahmarshy 0:1c7da5f83647 150 /// @return An iterator to the inserted element.
sarahmarshy 0:1c7da5f83647 151 iterator push(const T& element) {
sarahmarshy 0:1c7da5f83647 152 if (full()) {
sarahmarshy 0:1c7da5f83647 153 return NULL;
sarahmarshy 0:1c7da5f83647 154 }
sarahmarshy 0:1c7da5f83647 155
sarahmarshy 0:1c7da5f83647 156 // get a free node
sarahmarshy 0:1c7da5f83647 157 Node* new_node = free_nodes;
sarahmarshy 0:1c7da5f83647 158 free_nodes = free_nodes->next;
sarahmarshy 0:1c7da5f83647 159 new_node->next = NULL;
sarahmarshy 0:1c7da5f83647 160
sarahmarshy 0:1c7da5f83647 161 ++used_nodes_count;
sarahmarshy 0:1c7da5f83647 162
sarahmarshy 0:1c7da5f83647 163 // copy content
sarahmarshy 0:1c7da5f83647 164 new (new_node->storage.get_storage()) T(element);
sarahmarshy 0:1c7da5f83647 165
sarahmarshy 0:1c7da5f83647 166 // if there is no node in the queue, just link the head
sarahmarshy 0:1c7da5f83647 167 // to the new node and return
sarahmarshy 0:1c7da5f83647 168 if (head == NULL) {
sarahmarshy 0:1c7da5f83647 169 head = new_node;
sarahmarshy 0:1c7da5f83647 170 return new_node;
sarahmarshy 0:1c7da5f83647 171 }
sarahmarshy 0:1c7da5f83647 172
sarahmarshy 0:1c7da5f83647 173 // if the new node has an higher priority than the node in head
sarahmarshy 0:1c7da5f83647 174 // just link it as the head
sarahmarshy 0:1c7da5f83647 175 if (element < head->storage.get()) {
sarahmarshy 0:1c7da5f83647 176 new_node->next = head;
sarahmarshy 0:1c7da5f83647 177 head = new_node;
sarahmarshy 0:1c7da5f83647 178 return new_node;
sarahmarshy 0:1c7da5f83647 179 }
sarahmarshy 0:1c7da5f83647 180
sarahmarshy 0:1c7da5f83647 181 // insert the node after head
sarahmarshy 0:1c7da5f83647 182 insert_after(head, new_node);
sarahmarshy 0:1c7da5f83647 183
sarahmarshy 0:1c7da5f83647 184 return new_node;
sarahmarshy 0:1c7da5f83647 185 }
sarahmarshy 0:1c7da5f83647 186
sarahmarshy 0:1c7da5f83647 187 /// pop the head of the queue.
sarahmarshy 0:1c7da5f83647 188 bool pop() {
sarahmarshy 0:1c7da5f83647 189 if (!head) {
sarahmarshy 0:1c7da5f83647 190 return false;
sarahmarshy 0:1c7da5f83647 191 }
sarahmarshy 0:1c7da5f83647 192
sarahmarshy 0:1c7da5f83647 193 Node* target = head;
sarahmarshy 0:1c7da5f83647 194 target->storage.get().~T();
sarahmarshy 0:1c7da5f83647 195 head = target->next;
sarahmarshy 0:1c7da5f83647 196 target->next = free_nodes;
sarahmarshy 0:1c7da5f83647 197 free_nodes = target;
sarahmarshy 0:1c7da5f83647 198 --used_nodes_count;
sarahmarshy 0:1c7da5f83647 199 return true;
sarahmarshy 0:1c7da5f83647 200 }
sarahmarshy 0:1c7da5f83647 201
sarahmarshy 0:1c7da5f83647 202 /// If the content of an element is updated is updated after the insertion
sarahmarshy 0:1c7da5f83647 203 /// then, the list can be in an unordered state.
sarahmarshy 0:1c7da5f83647 204 /// This function help; it update the position of an iterator in the list.
sarahmarshy 0:1c7da5f83647 205 void update(iterator it) {
sarahmarshy 0:1c7da5f83647 206 Node* target = it.get_node();
sarahmarshy 0:1c7da5f83647 207 Node* hint = head;
sarahmarshy 0:1c7da5f83647 208
sarahmarshy 0:1c7da5f83647 209 if (target == NULL) {
sarahmarshy 0:1c7da5f83647 210 return;
sarahmarshy 0:1c7da5f83647 211 }
sarahmarshy 0:1c7da5f83647 212
sarahmarshy 0:1c7da5f83647 213 // remove the node from the list
sarahmarshy 0:1c7da5f83647 214 if (target == head) {
sarahmarshy 0:1c7da5f83647 215 // if it is the only node in the list, just return
sarahmarshy 0:1c7da5f83647 216 // it is not needed to update its position
sarahmarshy 0:1c7da5f83647 217 if (target->next == NULL) {
sarahmarshy 0:1c7da5f83647 218 return;
sarahmarshy 0:1c7da5f83647 219 }
sarahmarshy 0:1c7da5f83647 220
sarahmarshy 0:1c7da5f83647 221 // if the order is already correct, just return
sarahmarshy 0:1c7da5f83647 222 if (target->storage.get() < target->next->storage.get()) {
sarahmarshy 0:1c7da5f83647 223 return;
sarahmarshy 0:1c7da5f83647 224 }
sarahmarshy 0:1c7da5f83647 225
sarahmarshy 0:1c7da5f83647 226 // otherwise remove the node from the list
sarahmarshy 0:1c7da5f83647 227 // and update the hint
sarahmarshy 0:1c7da5f83647 228 head = target->next;
sarahmarshy 0:1c7da5f83647 229 hint = head;
sarahmarshy 0:1c7da5f83647 230 } else {
sarahmarshy 0:1c7da5f83647 231 bool node_found = false;
sarahmarshy 0:1c7da5f83647 232 for (Node* current = head; current != NULL; current = current->next) {
sarahmarshy 0:1c7da5f83647 233 if (current->next == target) {
sarahmarshy 0:1c7da5f83647 234 // check if it is needed to move the node
sarahmarshy 0:1c7da5f83647 235 if (current->storage.get() < target->storage.get()) {
sarahmarshy 0:1c7da5f83647 236 if (target->next == NULL) {
sarahmarshy 0:1c7da5f83647 237 return;
sarahmarshy 0:1c7da5f83647 238 }
sarahmarshy 0:1c7da5f83647 239
sarahmarshy 0:1c7da5f83647 240 if (target->storage.get() < target->next->storage.get()) {
sarahmarshy 0:1c7da5f83647 241 return;
sarahmarshy 0:1c7da5f83647 242 }
sarahmarshy 0:1c7da5f83647 243
sarahmarshy 0:1c7da5f83647 244 // there is no need to iterate again the whole list
sarahmarshy 0:1c7da5f83647 245 // just mark the hint has the current node
sarahmarshy 0:1c7da5f83647 246 hint = current;
sarahmarshy 0:1c7da5f83647 247 }
sarahmarshy 0:1c7da5f83647 248
sarahmarshy 0:1c7da5f83647 249 // remove the node from the list and break out of the loop
sarahmarshy 0:1c7da5f83647 250 current->next = target->next;
sarahmarshy 0:1c7da5f83647 251 node_found = true;
sarahmarshy 0:1c7da5f83647 252 break;
sarahmarshy 0:1c7da5f83647 253 }
sarahmarshy 0:1c7da5f83647 254 }
sarahmarshy 0:1c7da5f83647 255
sarahmarshy 0:1c7da5f83647 256 // the node in parameter doesn't belong to this queue
sarahmarshy 0:1c7da5f83647 257 if (!node_found) {
sarahmarshy 0:1c7da5f83647 258 return;
sarahmarshy 0:1c7da5f83647 259 }
sarahmarshy 0:1c7da5f83647 260 }
sarahmarshy 0:1c7da5f83647 261
sarahmarshy 0:1c7da5f83647 262 // insert the node after hint
sarahmarshy 0:1c7da5f83647 263 insert_after(hint, target);
sarahmarshy 0:1c7da5f83647 264 }
sarahmarshy 0:1c7da5f83647 265
sarahmarshy 0:1c7da5f83647 266 /// return an iterator to the begining of the queue.
sarahmarshy 0:1c7da5f83647 267 iterator begin() {
sarahmarshy 0:1c7da5f83647 268 return head;
sarahmarshy 0:1c7da5f83647 269 }
sarahmarshy 0:1c7da5f83647 270
sarahmarshy 0:1c7da5f83647 271 /// return an iterator to the end of the queue.
sarahmarshy 0:1c7da5f83647 272 /// @note can't be dereferenced
sarahmarshy 0:1c7da5f83647 273 iterator end() {
sarahmarshy 0:1c7da5f83647 274 return NULL;
sarahmarshy 0:1c7da5f83647 275 }
sarahmarshy 0:1c7da5f83647 276
sarahmarshy 0:1c7da5f83647 277 /// erase an iterator from the list
sarahmarshy 0:1c7da5f83647 278 bool erase(iterator it) {
sarahmarshy 0:1c7da5f83647 279 return erase(it.get_node());
sarahmarshy 0:1c7da5f83647 280 }
sarahmarshy 0:1c7da5f83647 281
sarahmarshy 0:1c7da5f83647 282 /// erase a node from the list
sarahmarshy 0:1c7da5f83647 283 bool erase(Node* n) {
sarahmarshy 0:1c7da5f83647 284 if (n == NULL) {
sarahmarshy 0:1c7da5f83647 285 return false;
sarahmarshy 0:1c7da5f83647 286 }
sarahmarshy 0:1c7da5f83647 287
sarahmarshy 0:1c7da5f83647 288 if (head == n) {
sarahmarshy 0:1c7da5f83647 289 return pop();
sarahmarshy 0:1c7da5f83647 290 }
sarahmarshy 0:1c7da5f83647 291
sarahmarshy 0:1c7da5f83647 292 Node* current = head;
sarahmarshy 0:1c7da5f83647 293 while (current->next) {
sarahmarshy 0:1c7da5f83647 294 if (current->next == n) {
sarahmarshy 0:1c7da5f83647 295 current->next = n->next;
sarahmarshy 0:1c7da5f83647 296 n->storage.get().~T();
sarahmarshy 0:1c7da5f83647 297 n->next = free_nodes;
sarahmarshy 0:1c7da5f83647 298 free_nodes = n;
sarahmarshy 0:1c7da5f83647 299 --used_nodes_count;
sarahmarshy 0:1c7da5f83647 300 return true;
sarahmarshy 0:1c7da5f83647 301 }
sarahmarshy 0:1c7da5f83647 302 current = current->next;
sarahmarshy 0:1c7da5f83647 303 }
sarahmarshy 0:1c7da5f83647 304 return false;
sarahmarshy 0:1c7da5f83647 305 }
sarahmarshy 0:1c7da5f83647 306
sarahmarshy 0:1c7da5f83647 307 /**
sarahmarshy 0:1c7da5f83647 308 * Indicate if the queue is empty or not.
sarahmarshy 0:1c7da5f83647 309 * @return true if the queue is empty and false otherwise.
sarahmarshy 0:1c7da5f83647 310 * @invariant the queue remains untouched.
sarahmarshy 0:1c7da5f83647 311 */
sarahmarshy 0:1c7da5f83647 312 bool empty() const {
sarahmarshy 0:1c7da5f83647 313 return head == NULL;
sarahmarshy 0:1c7da5f83647 314 }
sarahmarshy 0:1c7da5f83647 315
sarahmarshy 0:1c7da5f83647 316 /**
sarahmarshy 0:1c7da5f83647 317 * Indicate if the true is full or not.
sarahmarshy 0:1c7da5f83647 318 * @return true if the queue is full and false otherwise.
sarahmarshy 0:1c7da5f83647 319 * @invariant the queue remains untouched.
sarahmarshy 0:1c7da5f83647 320 */
sarahmarshy 0:1c7da5f83647 321 bool full() const {
sarahmarshy 0:1c7da5f83647 322 return free_nodes == NULL;
sarahmarshy 0:1c7da5f83647 323 }
sarahmarshy 0:1c7da5f83647 324
sarahmarshy 0:1c7da5f83647 325 /**
sarahmarshy 0:1c7da5f83647 326 * Indicate the number of elements in the queue.
sarahmarshy 0:1c7da5f83647 327 * @return the number of elements currently held by the queue.
sarahmarshy 0:1c7da5f83647 328 * @invariant the queue remains untouched.
sarahmarshy 0:1c7da5f83647 329 */
sarahmarshy 0:1c7da5f83647 330 std::size_t size() const {
sarahmarshy 0:1c7da5f83647 331 return used_nodes_count;
sarahmarshy 0:1c7da5f83647 332 }
sarahmarshy 0:1c7da5f83647 333
sarahmarshy 0:1c7da5f83647 334 /**
sarahmarshy 0:1c7da5f83647 335 * Expose the capacity of the queue in terms of number of elements the
sarahmarshy 0:1c7da5f83647 336 * queue can hold.
sarahmarshy 0:1c7da5f83647 337 * @return the capacity of the queue.
sarahmarshy 0:1c7da5f83647 338 * @invariant this function should always return Capacity.
sarahmarshy 0:1c7da5f83647 339 */
sarahmarshy 0:1c7da5f83647 340 std::size_t capacity() const {
sarahmarshy 0:1c7da5f83647 341 return Capacity;
sarahmarshy 0:1c7da5f83647 342 }
sarahmarshy 0:1c7da5f83647 343
sarahmarshy 0:1c7da5f83647 344 /**
sarahmarshy 0:1c7da5f83647 345 * Clear the queue from all its elements.
sarahmarshy 0:1c7da5f83647 346 */
sarahmarshy 0:1c7da5f83647 347 void clear() {
sarahmarshy 0:1c7da5f83647 348 while (head) {
sarahmarshy 0:1c7da5f83647 349 head->storage.get().~T();
sarahmarshy 0:1c7da5f83647 350 Node* tmp = head;
sarahmarshy 0:1c7da5f83647 351 head = head->next;
sarahmarshy 0:1c7da5f83647 352 tmp->next = free_nodes;
sarahmarshy 0:1c7da5f83647 353 free_nodes = tmp;
sarahmarshy 0:1c7da5f83647 354 }
sarahmarshy 0:1c7da5f83647 355 used_nodes_count = 0;
sarahmarshy 0:1c7da5f83647 356 }
sarahmarshy 0:1c7da5f83647 357
sarahmarshy 0:1c7da5f83647 358 private:
sarahmarshy 0:1c7da5f83647 359 void initialize() {
sarahmarshy 0:1c7da5f83647 360 /// link all the nodes together
sarahmarshy 0:1c7da5f83647 361 for (std::size_t i = 0; i < (Capacity - 1); ++i) {
sarahmarshy 0:1c7da5f83647 362 nodes[i].next = &nodes[i + 1];
sarahmarshy 0:1c7da5f83647 363 }
sarahmarshy 0:1c7da5f83647 364 /// the last node does not have a next node
sarahmarshy 0:1c7da5f83647 365 nodes[Capacity - 1].next = NULL;
sarahmarshy 0:1c7da5f83647 366 /// set all the nodes as free
sarahmarshy 0:1c7da5f83647 367 free_nodes = nodes;
sarahmarshy 0:1c7da5f83647 368 }
sarahmarshy 0:1c7da5f83647 369
sarahmarshy 0:1c7da5f83647 370 void copy(const PriorityQueue& other) {
sarahmarshy 0:1c7da5f83647 371 if (empty() == false) {
sarahmarshy 0:1c7da5f83647 372 clear();
sarahmarshy 0:1c7da5f83647 373 }
sarahmarshy 0:1c7da5f83647 374
sarahmarshy 0:1c7da5f83647 375 Node *to_copy = other.head;
sarahmarshy 0:1c7da5f83647 376 Node *previous = NULL;
sarahmarshy 0:1c7da5f83647 377 while (to_copy) {
sarahmarshy 0:1c7da5f83647 378 // pick a free node
sarahmarshy 0:1c7da5f83647 379 Node* new_node = free_nodes;
sarahmarshy 0:1c7da5f83647 380 free_nodes = free_nodes->next;
sarahmarshy 0:1c7da5f83647 381 new_node->next = NULL;
sarahmarshy 0:1c7da5f83647 382
sarahmarshy 0:1c7da5f83647 383 // copy content
sarahmarshy 0:1c7da5f83647 384 new (new_node->storage.get_storage()) T(to_copy->storage.get());
sarahmarshy 0:1c7da5f83647 385
sarahmarshy 0:1c7da5f83647 386 // link into the queue or update head then update previous pointer
sarahmarshy 0:1c7da5f83647 387 if (previous) {
sarahmarshy 0:1c7da5f83647 388 previous->next = new_node;
sarahmarshy 0:1c7da5f83647 389 } else {
sarahmarshy 0:1c7da5f83647 390 head = new_node;
sarahmarshy 0:1c7da5f83647 391 }
sarahmarshy 0:1c7da5f83647 392 previous = new_node;
sarahmarshy 0:1c7da5f83647 393
sarahmarshy 0:1c7da5f83647 394 // update the node to copy
sarahmarshy 0:1c7da5f83647 395 to_copy = to_copy->next;
sarahmarshy 0:1c7da5f83647 396 }
sarahmarshy 0:1c7da5f83647 397 used_nodes_count = other.used_nodes_count;
sarahmarshy 0:1c7da5f83647 398 }
sarahmarshy 0:1c7da5f83647 399
sarahmarshy 0:1c7da5f83647 400 void insert_after(Node* prev, Node* to_insert) {
sarahmarshy 0:1c7da5f83647 401 for (; prev != NULL; prev = prev->next) {
sarahmarshy 0:1c7da5f83647 402 if (prev->next == NULL || to_insert->storage.get() < prev->next->storage.get()) {
sarahmarshy 0:1c7da5f83647 403 to_insert->next = prev->next;
sarahmarshy 0:1c7da5f83647 404 prev->next = to_insert;
sarahmarshy 0:1c7da5f83647 405 break;
sarahmarshy 0:1c7da5f83647 406 }
sarahmarshy 0:1c7da5f83647 407 }
sarahmarshy 0:1c7da5f83647 408 }
sarahmarshy 0:1c7da5f83647 409
sarahmarshy 0:1c7da5f83647 410 Node nodes[Capacity]; //< Nodes of the queue
sarahmarshy 0:1c7da5f83647 411 Node *free_nodes; //< entry point for the list of free nodes
sarahmarshy 0:1c7da5f83647 412 Node *head; //< head of the queue
sarahmarshy 0:1c7da5f83647 413 std::size_t used_nodes_count; // number of nodes used
sarahmarshy 0:1c7da5f83647 414 };
sarahmarshy 0:1c7da5f83647 415
sarahmarshy 0:1c7da5f83647 416 } // namespace eq
sarahmarshy 0:1c7da5f83647 417
sarahmarshy 0:1c7da5f83647 418 #endif /* EVENTQUEUE_STACKPRIORITYQUEUE_H_ */