Embedded Template Library 1.0
Loading...
Searching...
No Matches
priority_queue.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2015 John Wellbelove, rlindeman
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_PRIORITY_QUEUE_INCLUDED
32#define ETL_PRIORITY_QUEUE_INCLUDED
33
34#include "platform.h"
35#include "algorithm.h"
36#include "utility.h"
37#include "functional.h"
38#include "iterator.h"
39#include "vector.h"
40#include "type_traits.h"
41#include "parameter_type.h"
42#include "error_handler.h"
43#include "exception.h"
44
45#include <stddef.h>
46
47//*****************************************************************************
52//*****************************************************************************
53
54namespace etl
55{
56 //***************************************************************************
59 //***************************************************************************
69
70 //***************************************************************************
73 //***************************************************************************
75 {
76 public:
77
79 : priority_queue_exception(ETL_ERROR_TEXT("priority_queue:full", ETL_PRIORITY_QUEUE_FILE_ID"A"), file_name_, line_number_)
80 {
81 }
82 };
83
84 //***************************************************************************
87 //***************************************************************************
89 {
90 public:
91
93 : priority_queue_exception(ETL_ERROR_TEXT("priority_queue:iterator", ETL_PRIORITY_QUEUE_FILE_ID"B"), file_name_, line_number_)
94 {
95 }
96 };
97
98 //***************************************************************************
113 //***************************************************************************
114 template <typename T, typename TContainer, typename TCompare = etl::less<T> >
116 {
117 public:
118
119 typedef T value_type;
122 typedef T& reference;
123 typedef const T& const_reference;
124#if ETL_USING_CPP11
125 typedef T&& rvalue_reference;
126#endif
127 typedef typename TContainer::size_type size_type;
128 typedef typename etl::iterator_traits<typename TContainer::iterator>::difference_type difference_type;
129
130 //*************************************************************************
133 //*************************************************************************
135 {
136 return container.front();
137 }
138
139 //*************************************************************************
142 //*************************************************************************
144 {
145 return container.front();
146 }
147
148 //*************************************************************************
153 //*************************************************************************
155 {
157
158 // Put element at end
159 container.push_back(value);
160 // Make elements in container into heap
161 etl::push_heap(container.begin(), container.end(), compare);
162 }
163
164#if ETL_USING_CPP11
165 //*************************************************************************
170 //*************************************************************************
171 void push(rvalue_reference value)
172 {
174
175 // Put element at end
176 container.push_back(etl::move(value));
177 // Make elements in container into heap
178 etl::push_heap(container.begin(), container.end(), compare);
179 }
180#endif
181
182#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT && !defined(ETL_PRIORITY_QUEUE_FORCE_CPP03_IMPLEMENTATION)
183 //*************************************************************************
188 //*************************************************************************
189 template <typename ... Args>
190 void emplace(Args && ... args)
191 {
193
194 // Put element at end
195 container.emplace_back(etl::forward<Args>(args)...);
196 // Make elements in container into heap
197 etl::push_heap(container.begin(), container.end(), compare);
198 }
199#else
200 //*************************************************************************
205 //*************************************************************************
206 void emplace()
207 {
209
210 // Put element at end
211 container.emplace_back();
212 // Make elements in container into heap
213 etl::push_heap(container.begin(), container.end(), compare);
214 }
215
216 //*************************************************************************
221 //*************************************************************************
222 template <typename T1>
223 void emplace(const T1& value1)
224 {
226
227 // Put element at end
228 container.emplace_back(value1);
229 // Make elements in container into heap
230 etl::push_heap(container.begin(), container.end(), compare);
231 }
232
233 //*************************************************************************
238 //*************************************************************************
239 template <typename T1, typename T2>
240 void emplace(const T1& value1, const T2& value2)
241 {
243
244 // Put element at end
245 container.emplace_back(value1, value2);
246 // Make elements in container into heap
247 etl::push_heap(container.begin(), container.end(), compare);
248 }
249
250 //*************************************************************************
255 //*************************************************************************
256 template <typename T1, typename T2, typename T3>
257 void emplace(const T1& value1, const T2& value2, const T3& value3)
258 {
260
261 // Put element at end
262 container.emplace_back(value1, value2, value3);
263 // Make elements in container into heap
264 etl::push_heap(container.begin(), container.end(), compare);
265 }
266
267 //*************************************************************************
272 //*************************************************************************
273 template <typename T1, typename T2, typename T3, typename T4>
274 void emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
275 {
277
278 // Put element at end
279 container.emplace_back(value1, value2, value3, value4);
280 // Make elements in container into heap
281 etl::push_heap(container.begin(), container.end(), compare);
282 }
283#endif
284
285 //*************************************************************************
293 //*************************************************************************
294 template <typename TIterator>
295 void assign(TIterator first, TIterator last)
296 {
297#if ETL_IS_DEBUG_BUILD
298 difference_type d = etl::distance(first, last);
299 ETL_ASSERT(d >= 0, ETL_ERROR(etl::priority_queue_iterator));
300 ETL_ASSERT(static_cast<size_t>(d) <= max_size(), ETL_ERROR(etl::priority_queue_full));
301#endif
302
303 clear();
304 container.assign(first, last);
305 etl::make_heap(container.begin(), container.end(), compare);
306 }
307
308 //*************************************************************************
311 //*************************************************************************
312 void pop()
313 {
314 // Move largest element to end
315 etl::pop_heap(container.begin(), container.end(), compare);
316 // Actually remove largest element at end
317 container.pop_back();
318 }
319
320 //*************************************************************************
323 //*************************************************************************
325 {
326 destination = ETL_MOVE(top());
327 pop();
328 }
329
330 //*************************************************************************
332 //*************************************************************************
334 {
335 return container.size();
336 }
337
338 //*************************************************************************
340 //*************************************************************************
342 {
343 return container.max_size();
344 }
345
346 //*************************************************************************
349 //*************************************************************************
350 bool empty() const
351 {
352 return container.empty();
353 }
354
355 //*************************************************************************
358 //*************************************************************************
359 bool full() const
360 {
361 return container.size() == container.max_size();
362 }
363
364 //*************************************************************************
367 //*************************************************************************
369 {
370 return container.max_size() - container.size();
371 }
372
373 //*************************************************************************
375 //*************************************************************************
376 void clear()
377 {
378 container.clear();
379 }
380
381 //*************************************************************************
383 //*************************************************************************
385 {
386 if (&rhs != this)
387 {
388 clone(rhs);
389 }
390
391 return *this;
392 }
393
394#if ETL_USING_CPP11
395 //*************************************************************************
397 //*************************************************************************
399 {
400 if (&rhs != this)
401 {
402 clear();
403 move(etl::move(rhs));
404 }
405
406 return *this;
407 }
408#endif
409
410 protected:
411
412 //*************************************************************************
414 //*************************************************************************
416 {
417 assign(other.container.cbegin(), other.container.cend());
418 }
419
420#if ETL_USING_CPP11
421 //*************************************************************************
423 //*************************************************************************
424 void move(ipriority_queue&& other)
425 {
426 while (!other.empty())
427 {
428 push(etl::move(other.top()));
429 other.pop();
430 }
431 }
432#endif
433
434 //*************************************************************************
436 //*************************************************************************
438 {
439 }
440
441 private:
442
443 // Disable copy construction.
445
447 TContainer container;
448
450 };
451
452 //***************************************************************************
458 //***************************************************************************
459 template <typename T, const size_t SIZE, typename TContainer = etl::vector<T, SIZE>, typename TCompare = etl::less<typename TContainer::value_type> >
460 class priority_queue : public etl::ipriority_queue<T, TContainer, TCompare>
461 {
462 public:
463
464 typedef typename TContainer::size_type size_type;
466
467 static ETL_CONSTANT size_type MAX_SIZE = size_type(SIZE);
468
469 //*************************************************************************
471 //*************************************************************************
476
477 //*************************************************************************
479 //*************************************************************************
485
486#if ETL_USING_CPP11
487 //*************************************************************************
489 //*************************************************************************
492 {
494 }
495#endif
496
497 //*************************************************************************
502 //*************************************************************************
503 template <typename TIterator>
509
510 //*************************************************************************
512 //*************************************************************************
517
518 //*************************************************************************
520 //*************************************************************************
522 {
523 if (&rhs != this)
524 {
526 }
527
528 return *this;
529 }
530
531#if ETL_USING_CPP11
532 //*************************************************************************
534 //*************************************************************************
536 {
537 if (&rhs != this)
538 {
541 }
542
543 return *this;
544 }
545#endif
546 };
547
548 template <typename T, const size_t SIZE, typename TContainer, typename TCompare>
549 ETL_CONSTANT typename priority_queue<T, SIZE, TContainer, TCompare>::size_type priority_queue<T, SIZE, TContainer, TCompare>::MAX_SIZE;
550}
551
552#endif
Definition priority_queue.h:461
~priority_queue()
Destructor.
Definition priority_queue.h:513
priority_queue(const priority_queue &rhs)
Copy constructor.
Definition priority_queue.h:480
priority_queue & operator=(const priority_queue &rhs)
Assignment operator.
Definition priority_queue.h:521
priority_queue()
Default constructor.
Definition priority_queue.h:472
priority_queue(TIterator first, TIterator last)
Definition priority_queue.h:504
#define ETL_ASSERT(b, e)
Definition error_handler.h:356
Definition exception.h:47
bool full() const
Definition priority_queue.h:359
void pop_into(reference destination)
Definition priority_queue.h:324
bool empty() const
Definition priority_queue.h:350
size_type max_size() const
Returns the maximum number of items that can be queued.
Definition priority_queue.h:341
void assign(TIterator first, TIterator last)
Definition priority_queue.h:295
void emplace(const T1 &value1, const T2 &value2, const T3 &value3)
Definition priority_queue.h:257
void push(const_reference value)
Definition priority_queue.h:154
T & reference
A reference to the type used in the queue.
Definition priority_queue.h:122
void emplace(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Definition priority_queue.h:274
ipriority_queue & operator=(const ipriority_queue &rhs)
Assignment operator.
Definition priority_queue.h:384
TCompare compare_type
The comparison type.
Definition priority_queue.h:121
reference top()
Definition priority_queue.h:134
const T & const_reference
A const reference to the type used in the queue.
Definition priority_queue.h:123
T value_type
The type stored in the queue.
Definition priority_queue.h:119
size_type size() const
Returns the current number of items in the priority queue.
Definition priority_queue.h:333
void clone(const ipriority_queue &other)
Make this a clone of the supplied priority queue.
Definition priority_queue.h:415
const_reference top() const
Definition priority_queue.h:143
void clear()
Clears the queue to the empty state.
Definition priority_queue.h:376
void pop()
Definition priority_queue.h:312
void emplace(const T1 &value1)
Definition priority_queue.h:223
size_type available() const
Definition priority_queue.h:368
void emplace()
Definition priority_queue.h:206
TContainer::size_type size_type
The type used for determining the size of the queue.
Definition priority_queue.h:127
TContainer container_type
The container type used for priority queue.
Definition priority_queue.h:120
ipriority_queue()
The constructor that is called from derived classes.
Definition priority_queue.h:437
void emplace(const T1 &value1, const T2 &value2)
Definition priority_queue.h:240
This is the base for all priority queues that contain a particular type.
Definition priority_queue.h:116
Definition priority_queue.h:61
Definition priority_queue.h:75
Definition priority_queue.h:89
bitset_ext
Definition absolute.h:38
Definition compare.h:51
pair holds two objects of arbitrary type
Definition utility.h:164