Embedded Template Library 1.0
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 //***************************************************************************
61 {
62 public:
63
64 priority_queue_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
65 : exception(reason_, file_name_, line_number_)
66 {
67 }
68 };
69
70 //***************************************************************************
73 //***************************************************************************
75 {
76 public:
77
78 priority_queue_full(string_type file_name_, numeric_type line_number_)
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
92 priority_queue_iterator(string_type file_name_, numeric_type line_number_)
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;
120 typedef TContainer container_type;
121 typedef TCompare compare_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 template <typename T1>
207 void emplace(const T1& value1)
208 {
210
211 // Put element at end
212 container.emplace_back(value1);
213 // Make elements in container into heap
214 etl::push_heap(container.begin(), container.end(), compare);
215 }
216
217 //*************************************************************************
222 //*************************************************************************
223 template <typename T1, typename T2>
224 void emplace(const T1& value1, const T2& value2)
225 {
227
228 // Put element at end
229 container.emplace_back(value1, value2);
230 // Make elements in container into heap
231 etl::push_heap(container.begin(), container.end(), compare);
232 }
233
234 //*************************************************************************
239 //*************************************************************************
240 template <typename T1, typename T2, typename T3>
241 void emplace(const T1& value1, const T2& value2, const T3& value3)
242 {
244
245 // Put element at end
246 container.emplace_back(value1, value2, value3);
247 // Make elements in container into heap
248 etl::push_heap(container.begin(), container.end(), compare);
249 }
250
251 //*************************************************************************
256 //*************************************************************************
257 template <typename T1, typename T2, typename T3, typename T4>
258 void emplace(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
259 {
261
262 // Put element at end
263 container.emplace_back(value1, value2, value3, value4);
264 // Make elements in container into heap
265 etl::push_heap(container.begin(), container.end(), compare);
266 }
267#endif
268
269 //*************************************************************************
277 //*************************************************************************
278 template <typename TIterator>
279 void assign(TIterator first, TIterator last)
280 {
281#if ETL_IS_DEBUG_BUILD
282 difference_type d = etl::distance(first, last);
283 ETL_ASSERT(d >= 0, ETL_ERROR(etl::priority_queue_iterator));
284 ETL_ASSERT(static_cast<size_t>(d) <= max_size(), ETL_ERROR(etl::priority_queue_full));
285#endif
286
287 clear();
288 container.assign(first, last);
289 etl::make_heap(container.begin(), container.end(), compare);
290 }
291
292 //*************************************************************************
295 //*************************************************************************
296 void pop()
297 {
298 // Move largest element to end
299 etl::pop_heap(container.begin(), container.end(), compare);
300 // Actually remove largest element at end
301 container.pop_back();
302 }
303
304 //*************************************************************************
307 //*************************************************************************
308 void pop_into(reference destination)
309 {
310 destination = ETL_MOVE(top());
311 pop();
312 }
313
314 //*************************************************************************
316 //*************************************************************************
318 {
319 return container.size();
320 }
321
322 //*************************************************************************
324 //*************************************************************************
326 {
327 return container.max_size();
328 }
329
330 //*************************************************************************
333 //*************************************************************************
334 bool empty() const
335 {
336 return container.empty();
337 }
338
339 //*************************************************************************
342 //*************************************************************************
343 bool full() const
344 {
345 return container.size() == container.max_size();
346 }
347
348 //*************************************************************************
351 //*************************************************************************
353 {
354 return container.max_size() - container.size();
355 }
356
357 //*************************************************************************
359 //*************************************************************************
360 void clear()
361 {
362 container.clear();
363 }
364
365 //*************************************************************************
367 //*************************************************************************
369 {
370 if (&rhs != this)
371 {
372 clone(rhs);
373 }
374
375 return *this;
376 }
377
378#if ETL_USING_CPP11
379 //*************************************************************************
381 //*************************************************************************
383 {
384 if (&rhs != this)
385 {
386 move(etl::move(rhs));
387 }
388
389 return *this;
390 }
391#endif
392
393 protected:
394
395 //*************************************************************************
397 //*************************************************************************
398 void clone(const ipriority_queue& other)
399 {
400 assign(other.container.cbegin(), other.container.cend());
401 }
402
403#if ETL_USING_CPP11
404 //*************************************************************************
406 //*************************************************************************
407 void move(ipriority_queue&& other)
408 {
409 while (!other.empty())
410 {
411 push(etl::move(other.top()));
412 other.pop();
413 }
414 }
415#endif
416
417 //*************************************************************************
419 //*************************************************************************
421 {
422 }
423
424 private:
425
426 // Disable copy construction.
428
430 TContainer container;
431
432 TCompare compare;
433 };
434
435 //***************************************************************************
441 //***************************************************************************
442 template <typename T, const size_t SIZE, typename TContainer = etl::vector<T, SIZE>, typename TCompare = etl::less<typename TContainer::value_type> >
443 class priority_queue : public etl::ipriority_queue<T, TContainer, TCompare>
444 {
445 public:
446
447 typedef typename TContainer::size_type size_type;
448 typedef TContainer container_type;
449
450 static ETL_CONSTANT size_type MAX_SIZE = size_type(SIZE);
451
452 //*************************************************************************
454 //*************************************************************************
456 : etl::ipriority_queue<T, TContainer, TCompare>()
457 {
458 }
459
460 //*************************************************************************
462 //*************************************************************************
464 : etl::ipriority_queue<T, TContainer, TCompare>()
465 {
467 }
468
469#if ETL_USING_CPP11
470 //*************************************************************************
472 //*************************************************************************
474 : etl::ipriority_queue<T, TContainer, TCompare>()
475 {
477 }
478#endif
479
480 //*************************************************************************
485 //*************************************************************************
486 template <typename TIterator>
487 priority_queue(TIterator first, TIterator last)
488 : etl::ipriority_queue<T, TContainer, TCompare>()
489 {
491 }
492
493 //*************************************************************************
495 //*************************************************************************
497 {
499 }
500
501 //*************************************************************************
503 //*************************************************************************
505 {
506 if (&rhs != this)
507 {
509 }
510
511 return *this;
512 }
513
514#if ETL_USING_CPP11
515 //*************************************************************************
517 //*************************************************************************
519 {
520 if (&rhs != this)
521 {
523 }
524
525 return *this;
526 }
527#endif
528 };
529
530 template <typename T, const size_t SIZE, typename TContainer, typename TCompare>
531 ETL_CONSTANT typename priority_queue<T, SIZE, TContainer, TCompare>::size_type priority_queue<T, SIZE, TContainer, TCompare>::MAX_SIZE;
532}
533
534#endif
Definition: priority_queue.h:444
~priority_queue()
Destructor.
Definition: priority_queue.h:496
priority_queue(const priority_queue &rhs)
Copy constructor.
Definition: priority_queue.h:463
priority_queue & operator=(const priority_queue &rhs)
Assignment operator.
Definition: priority_queue.h:504
priority_queue()
Default constructor.
Definition: priority_queue.h:455
priority_queue(TIterator first, TIterator last)
Definition: priority_queue.h:487
#define ETL_ASSERT(b, e)
Definition: error_handler.h:316
ETL_CONSTEXPR exception(string_type reason_, string_type, numeric_type line_)
Constructor.
Definition: exception.h:69
Definition: exception.h:47
bool full() const
Definition: priority_queue.h:343
void pop_into(reference destination)
Definition: priority_queue.h:308
bool empty() const
Definition: priority_queue.h:334
size_type max_size() const
Returns the maximum number of items that can be queued.
Definition: priority_queue.h:325
void assign(TIterator first, TIterator last)
Definition: priority_queue.h:279
void emplace(const T1 &value1, const T2 &value2, const T3 &value3)
Definition: priority_queue.h:241
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:258
ipriority_queue & operator=(const ipriority_queue &rhs)
Assignment operator.
Definition: priority_queue.h:368
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:317
void clone(const ipriority_queue &other)
Make this a clone of the supplied priority queue.
Definition: priority_queue.h:398
const_reference top() const
Definition: priority_queue.h:143
void clear()
Clears the queue to the empty state.
Definition: priority_queue.h:360
void pop()
Definition: priority_queue.h:296
void emplace(const T1 &value1)
Definition: priority_queue.h:207
size_type available() const
Definition: priority_queue.h:352
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:420
void emplace(const T1 &value1, const T2 &value2)
Definition: priority_queue.h:224
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:52