Stefan Scholz
/
ETL
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.
Embed:
(wiki syntax)
Show/hide line numbers
deque.h
Go to the documentation of this file.
00001 ///\file 00002 00003 /****************************************************************************** 00004 The MIT License(MIT) 00005 00006 Embedded Template Library. 00007 https://github.com/ETLCPP/etl 00008 http://www.etlcpp.com 00009 00010 Copyright(c) 2014 jwellbelove 00011 00012 Permission is hereby granted, free of charge, to any person obtaining a copy 00013 of this software and associated documentation files(the "Software"), to deal 00014 in the Software without restriction, including without limitation the rights 00015 to use, copy, modify, merge, publish, distribute, sublicense, and / or sell 00016 copies of the Software, and to permit persons to whom the Software is 00017 furnished to do so, subject to the following conditions : 00018 00019 The above copyright notice and this permission notice shall be included in all 00020 copies or substantial portions of the Software. 00021 00022 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 00023 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 00024 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE 00025 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 00026 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 00027 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 00028 SOFTWARE. 00029 ******************************************************************************/ 00030 00031 #ifndef __ETL_DEQUE__ 00032 #define __ETL_DEQUE__ 00033 00034 #include <stddef.h> 00035 #include <stdint.h> 00036 #include <iterator> 00037 #include <algorithm> 00038 00039 #include "platform.h " 00040 #include "container.h " 00041 #include "alignment.h " 00042 #include "array.h " 00043 #include "memory.h " 00044 #include "exception.h " 00045 #include "error_handler.h " 00046 #include "debug_count.h " 00047 #include "algorithm.h " 00048 #include "type_traits.h " 00049 #include "parameter_type.h " 00050 00051 #ifdef ETL_COMPILER_MICROSOFT 00052 #undef min 00053 #endif 00054 00055 #undef ETL_FILE 00056 #define ETL_FILE "1" 00057 00058 //***************************************************************************** 00059 ///\defgroup deque deque 00060 /// A double ended queue with the capacity defined at compile time. 00061 ///\ingroup containers 00062 //***************************************************************************** 00063 00064 namespace etl 00065 { 00066 //*************************************************************************** 00067 /// Exception base for deques 00068 ///\ingroup deque 00069 //*************************************************************************** 00070 class deque_exception : public etl::exception 00071 { 00072 public: 00073 00074 deque_exception(string_type reason_, string_type file_name_, numeric_type line_number_) 00075 : exception(reason_, file_name_, line_number_) 00076 { 00077 } 00078 }; 00079 00080 //*************************************************************************** 00081 /// Deque full exception. 00082 ///\ingroup deque 00083 //*************************************************************************** 00084 class deque_full : public etl::deque_exception 00085 { 00086 public: 00087 00088 deque_full(string_type file_name_, numeric_type line_number_) 00089 : etl::deque_exception(ETL_ERROR_TEXT("deque:full", ETL_FILE"A"), file_name_, line_number_) 00090 { 00091 } 00092 }; 00093 00094 //*************************************************************************** 00095 /// Deque empty exception. 00096 ///\ingroup deque 00097 //*************************************************************************** 00098 class deque_empty : public etl::deque_exception 00099 { 00100 public: 00101 00102 deque_empty(string_type file_name_, numeric_type line_number_) 00103 : etl::deque_exception(ETL_ERROR_TEXT("deque:empty", ETL_FILE"B"), file_name_, line_number_) 00104 { 00105 } 00106 }; 00107 00108 //*************************************************************************** 00109 /// Deque out of bounds exception. 00110 ///\ingroup deque 00111 //*************************************************************************** 00112 class deque_out_of_bounds : public etl::deque_exception 00113 { 00114 public: 00115 00116 deque_out_of_bounds(string_type file_name_, numeric_type line_number_) 00117 : etl::deque_exception(ETL_ERROR_TEXT("deque:bounds", ETL_FILE"C"), file_name_, line_number_) 00118 { 00119 } 00120 }; 00121 00122 //*************************************************************************** 00123 ///\ingroup vector 00124 /// Deque incompatible type exception. 00125 //*************************************************************************** 00126 class deque_incompatible_type : public deque_exception 00127 { 00128 public: 00129 00130 deque_incompatible_type(string_type file_name_, numeric_type line_number_) 00131 : deque_exception(ETL_ERROR_TEXT("deque:type", ETL_FILE"D"), file_name_, line_number_) 00132 { 00133 } 00134 }; 00135 00136 //*************************************************************************** 00137 /// The base class for all templated deque types. 00138 ///\ingroup deque 00139 //*************************************************************************** 00140 class deque_base 00141 { 00142 public: 00143 00144 typedef size_t size_type; 00145 00146 //************************************************************************* 00147 /// Gets the current size of the deque. 00148 ///\return The current size of the deque. 00149 //************************************************************************* 00150 size_type size() const 00151 { 00152 return current_size; 00153 } 00154 00155 //************************************************************************* 00156 /// Checks the 'empty' state of the deque. 00157 ///\return <b>true</b> if empty. 00158 //************************************************************************* 00159 bool empty() const 00160 { 00161 return (current_size == 0); 00162 } 00163 00164 //************************************************************************* 00165 /// Checks the 'full' state of the deque. 00166 ///\return <b>true</b> if full. 00167 //************************************************************************* 00168 bool full() const 00169 { 00170 return current_size == CAPACITY; 00171 } 00172 00173 //************************************************************************* 00174 /// Returns the maximum possible size of the deque. 00175 ///\return The maximum size of the deque. 00176 //************************************************************************* 00177 size_type max_size() const 00178 { 00179 return CAPACITY; 00180 } 00181 00182 //************************************************************************* 00183 /// Returns the remaining capacity. 00184 ///\return The remaining capacity. 00185 //************************************************************************* 00186 size_t available() const 00187 { 00188 return max_size() - size(); 00189 } 00190 00191 protected: 00192 00193 //************************************************************************* 00194 /// Constructor. 00195 //************************************************************************* 00196 deque_base(size_t max_size_, size_t buffer_size_) 00197 : current_size(0), 00198 CAPACITY(max_size_), 00199 BUFFER_SIZE(buffer_size_) 00200 { 00201 } 00202 00203 size_type current_size; ///< The current number of elements in the deque. 00204 const size_type CAPACITY; ///< The maximum number of elements in the deque. 00205 const size_type BUFFER_SIZE; ///< The number of elements in the buffer. 00206 etl::debug_count construct_count; ///< Internal debugging. 00207 }; 00208 00209 //*************************************************************************** 00210 /// The base class for all etl::deque classes. 00211 ///\tparam T The type of values this deque should hold. 00212 ///\ingroup deque 00213 //*************************************************************************** 00214 template <typename T> 00215 class ideque : public etl::deque_base 00216 { 00217 public: 00218 00219 typedef T value_type; 00220 typedef size_t size_type; 00221 typedef T& reference; 00222 typedef const T& const_reference; 00223 typedef T* pointer; 00224 typedef const T* const_pointer; 00225 typedef typename std::iterator_traits<pointer>::difference_type difference_type; 00226 00227 protected: 00228 00229 typedef typename etl::parameter_type<T>::type parameter_t; 00230 00231 //************************************************************************* 00232 /// Test for an iterator. 00233 //************************************************************************* 00234 template <typename TIterator> 00235 struct is_iterator : public etl::integral_constant<bool, !etl::is_integral<TIterator>::value && !etl::is_floating_point<TIterator>::value> 00236 { 00237 }; 00238 00239 public: 00240 00241 //************************************************************************* 00242 /// Iterator 00243 //************************************************************************* 00244 struct iterator : public std::iterator<std::random_access_iterator_tag, T> 00245 { 00246 friend class ideque; 00247 00248 //*************************************************** 00249 iterator() 00250 : index(0), 00251 p_deque(0), 00252 p_buffer(0) 00253 { 00254 } 00255 00256 //*************************************************** 00257 iterator(const iterator& other) 00258 : index(other.index), 00259 p_deque(other.p_deque), 00260 p_buffer(other.p_buffer) 00261 { 00262 } 00263 00264 //*************************************************** 00265 iterator& operator ++() 00266 { 00267 index = (static_cast<size_t>(index) == p_deque->BUFFER_SIZE - 1) ? 0 : index + 1; 00268 00269 return *this; 00270 } 00271 00272 //*************************************************** 00273 iterator operator ++(int) 00274 { 00275 iterator previous(*this); 00276 index = (static_cast<size_t>(index) == p_deque->BUFFER_SIZE - 1) ? 0 : index + 1; 00277 00278 return previous; 00279 } 00280 00281 //*************************************************** 00282 iterator& operator +=(difference_type offset) 00283 { 00284 if (offset > 0) 00285 { 00286 index += offset; 00287 index = (static_cast<size_t>(index) > p_deque->BUFFER_SIZE - 1) ? index - p_deque->BUFFER_SIZE : index; 00288 } 00289 else if (offset < 0) 00290 { 00291 operator -= (-offset); 00292 } 00293 00294 return *this; 00295 } 00296 00297 //*************************************************** 00298 iterator& operator -=(difference_type offset) 00299 { 00300 if (offset > 0) 00301 { 00302 index -= offset; 00303 index = (index < 0) ? index + p_deque->BUFFER_SIZE : index; 00304 } 00305 else if (offset < 0) 00306 { 00307 operator += (-offset); 00308 } 00309 00310 return *this; 00311 } 00312 00313 //*************************************************** 00314 iterator& operator --() 00315 { 00316 index = (index == 0) ? p_deque->BUFFER_SIZE - 1 : index - 1; 00317 00318 return *this; 00319 } 00320 00321 //*************************************************** 00322 iterator operator --(int) 00323 { 00324 iterator previous(*this); 00325 index = (index == 0) ? p_deque->BUFFER_SIZE - 1 : index - 1; 00326 00327 return previous; 00328 } 00329 00330 //*************************************************** 00331 reference operator *() 00332 { 00333 return p_buffer[index]; 00334 } 00335 00336 //*************************************************** 00337 const_reference operator *() const 00338 { 00339 return p_buffer[index]; 00340 } 00341 00342 //*************************************************** 00343 pointer operator ->() 00344 { 00345 return &p_buffer[index]; 00346 } 00347 00348 //*************************************************** 00349 const_pointer operator ->() const 00350 { 00351 return &p_buffer[index]; 00352 } 00353 00354 //*************************************************** 00355 bool operator <(const iterator& other) const 00356 { 00357 return ideque::distance(*this, other) > 0; 00358 } 00359 00360 //*************************************************** 00361 friend iterator operator +(const iterator& lhs, difference_type offset) 00362 { 00363 iterator result(lhs); 00364 result += offset; 00365 return result; 00366 } 00367 00368 //*************************************************** 00369 friend iterator operator -(const iterator& lhs, difference_type offset) 00370 { 00371 iterator result(lhs); 00372 result -= offset; 00373 return result; 00374 } 00375 00376 //*************************************************** 00377 friend bool operator == (const iterator& lhs, const iterator& rhs) 00378 { 00379 return lhs.index == rhs.index; 00380 } 00381 00382 //*************************************************** 00383 friend bool operator != (const iterator& lhs, const iterator& rhs) 00384 { 00385 return !(lhs == rhs); 00386 } 00387 00388 //*************************************************** 00389 difference_type get_index() const 00390 { 00391 return index; 00392 } 00393 00394 //*************************************************** 00395 ideque& get_deque() const 00396 { 00397 return *p_deque; 00398 } 00399 00400 //*************************************************** 00401 pointer get_buffer() const 00402 { 00403 return p_buffer; 00404 } 00405 00406 //*************************************************** 00407 void swap(iterator& other) 00408 { 00409 std::swap(index, other.index); 00410 } 00411 00412 private: 00413 00414 //*************************************************** 00415 iterator(difference_type index_, ideque& the_deque, pointer p_buffer_) 00416 : index(index_), 00417 p_deque(&the_deque), 00418 p_buffer(p_buffer_) 00419 { 00420 } 00421 00422 difference_type index; 00423 ideque* p_deque; 00424 pointer p_buffer; 00425 }; 00426 00427 //************************************************************************* 00428 /// Const Iterator 00429 //************************************************************************* 00430 struct const_iterator : public std::iterator<std::random_access_iterator_tag, const T> 00431 { 00432 friend class ideque; 00433 00434 //*************************************************** 00435 const_iterator() 00436 : index(0), 00437 p_deque(0), 00438 p_buffer(0) 00439 { 00440 } 00441 00442 //*************************************************** 00443 const_iterator(const const_iterator& other) 00444 : index(other.index), 00445 p_deque(other.p_deque), 00446 p_buffer(other.p_buffer) 00447 { 00448 } 00449 00450 //*************************************************** 00451 const_iterator(const typename ideque::iterator& other) 00452 : index(other.index), 00453 p_deque(other.p_deque), 00454 p_buffer(other.p_buffer) 00455 { 00456 } 00457 00458 //*************************************************** 00459 const_iterator& operator ++() 00460 { 00461 index = (static_cast<size_t>(index) == p_deque->BUFFER_SIZE - 1) ? 0 : index + 1; 00462 00463 return *this; 00464 } 00465 00466 //*************************************************** 00467 const_iterator operator ++(int) 00468 { 00469 const_iterator previous(*this); 00470 index = (static_cast<size_t>(index) == p_deque->BUFFER_SIZE - 1) ? 0 : index + 1; 00471 00472 return previous; 00473 } 00474 00475 //*************************************************** 00476 const_iterator& operator +=(difference_type offset) 00477 { 00478 if (offset > 0) 00479 { 00480 index += offset; 00481 index = (static_cast<size_t>(index) > p_deque->BUFFER_SIZE - 1) ? index - p_deque->BUFFER_SIZE : index; 00482 } 00483 else if (offset < 0) 00484 { 00485 operator -= (-offset); 00486 } 00487 00488 return *this; 00489 } 00490 00491 //*************************************************** 00492 const_iterator& operator -=(difference_type offset) 00493 { 00494 if (offset > 0) 00495 { 00496 index -= offset; 00497 index = (index < 0) ? static_cast<size_t>(index) + p_deque->BUFFER_SIZE : index; 00498 } 00499 else if (offset < 0) 00500 { 00501 operator += (-offset); 00502 } 00503 00504 return *this; 00505 } 00506 00507 //*************************************************** 00508 const_iterator& operator --() 00509 { 00510 index = (index == 0) ? p_deque->BUFFER_SIZE - 1 : index - 1; 00511 00512 return *this; 00513 } 00514 00515 //*************************************************** 00516 const_iterator operator --(int) 00517 { 00518 const_iterator previous(*this); 00519 index = (index == 0) ? p_deque->BUFFER_SIZE - 1 : index - 1; 00520 00521 return previous; 00522 } 00523 00524 //*************************************************** 00525 const_reference operator *() const 00526 { 00527 return p_buffer[index]; 00528 } 00529 00530 //*************************************************** 00531 const_pointer operator ->() const 00532 { 00533 return &p_buffer[index]; 00534 } 00535 00536 //*************************************************** 00537 bool operator <(const const_iterator& other) const 00538 { 00539 return ideque::distance(*this, other) > 0; 00540 } 00541 00542 //*************************************************** 00543 friend const_iterator operator +(const const_iterator& lhs, difference_type offset) 00544 { 00545 const_iterator result(lhs); 00546 result += offset; 00547 return result; 00548 } 00549 00550 //*************************************************** 00551 friend const_iterator operator -(const const_iterator& lhs, difference_type offset) 00552 { 00553 const_iterator result(lhs); 00554 result -= offset; 00555 return result; 00556 } 00557 00558 //*************************************************** 00559 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs) 00560 { 00561 return lhs.index == rhs.index; 00562 } 00563 00564 //*************************************************** 00565 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs) 00566 { 00567 return !(lhs == rhs); 00568 } 00569 00570 //*************************************************** 00571 difference_type get_index() const 00572 { 00573 return index; 00574 } 00575 00576 //*************************************************** 00577 ideque& get_deque() const 00578 { 00579 return *p_deque; 00580 } 00581 00582 //*************************************************** 00583 pointer get_buffer() const 00584 { 00585 return p_buffer; 00586 } 00587 00588 //*************************************************** 00589 void swap(const_iterator& other) 00590 { 00591 std::swap(index, other.index); 00592 } 00593 00594 private: 00595 00596 //*************************************************** 00597 difference_type distance(difference_type firstIndex, difference_type index_) 00598 { 00599 if (index_ < firstIndex) 00600 { 00601 return p_deque->BUFFER_SIZE + index_ - firstIndex; 00602 } 00603 else 00604 { 00605 return index_ - firstIndex; 00606 } 00607 } 00608 00609 //*************************************************** 00610 const_iterator(difference_type index_, ideque& the_deque, pointer p_buffer_) 00611 : index(index_), 00612 p_deque(&the_deque), 00613 p_buffer(p_buffer_) 00614 { 00615 } 00616 00617 difference_type index; 00618 ideque* p_deque; 00619 pointer p_buffer; 00620 }; 00621 00622 typedef std::reverse_iterator<iterator> reverse_iterator; 00623 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00624 00625 //************************************************************************* 00626 /// Assigns a range to the deque. 00627 //************************************************************************* 00628 template<typename TIterator> 00629 typename etl::enable_if<is_iterator<TIterator>::value, void>::type 00630 assign(TIterator range_begin, TIterator range_end) 00631 { 00632 initialise(); 00633 00634 while (range_begin != range_end) 00635 { 00636 push_back(*range_begin++); 00637 } 00638 } 00639 00640 //************************************************************************* 00641 /// Assigns 'n' copies of a value to the deque. 00642 /// If asserts or exceptions are enabled, throws an etl::deque_full is 'n' is too large. 00643 ///\param n The number of copies to assign. 00644 ///\param value The value to add.< 00645 //************************************************************************* 00646 void assign(size_type n, const value_type& value) 00647 { 00648 ETL_ASSERT(n <= CAPACITY, ETL_ERROR(deque_full)); 00649 00650 initialise(); 00651 00652 _begin.index = 0; 00653 _end.index = 0; 00654 00655 while (n > 0) 00656 { 00657 create_element_back(value); 00658 --n; 00659 } 00660 } 00661 00662 //************************************************************************* 00663 /// Gets a reference to the item at the index. 00664 /// If asserts or exceptions are enabled, throws an etl::deque_out_of_bounds if the index is out of range. 00665 ///\return A reference to the item at the index. 00666 //************************************************************************* 00667 reference at(size_t index) 00668 { 00669 ETL_ASSERT(index < current_size, ETL_ERROR(deque_out_of_bounds)); 00670 00671 iterator result(_begin); 00672 result += index; 00673 00674 return *result; 00675 } 00676 00677 //************************************************************************* 00678 /// Gets a const reference to the item at the index. 00679 /// If asserts or exceptions are enabled, throws an etl::deque_out_of_bounds if the index is out of range. 00680 ///\return A const reference to the item at the index. 00681 //************************************************************************* 00682 const_reference at(size_t index) const 00683 { 00684 ETL_ASSERT(index < current_size, ETL_ERROR(deque_out_of_bounds)); 00685 00686 iterator result(_begin); 00687 result += index; 00688 00689 return *result; 00690 } 00691 00692 //************************************************************************* 00693 /// Gets a reference to the item at the index. 00694 ///\return A reference to the item at the index. 00695 //************************************************************************* 00696 reference operator [](size_t index) 00697 { 00698 iterator result(_begin); 00699 result += index; 00700 00701 return *result; 00702 } 00703 00704 //************************************************************************* 00705 /// Gets a const reference to the item at the index. 00706 ///\return A const reference to the item at the index. 00707 //************************************************************************* 00708 const_reference operator [](size_t index) const 00709 { 00710 iterator result(_begin); 00711 result += index; 00712 00713 return *result; 00714 } 00715 00716 //************************************************************************* 00717 /// Gets a reference to the item at the front of the deque. 00718 ///\return A reference to the item at the front of the deque. 00719 //************************************************************************* 00720 reference front() 00721 { 00722 return *_begin; 00723 } 00724 00725 //************************************************************************* 00726 /// Gets a const reference to the item at the front of the deque. 00727 ///\return A const reference to the item at the front of the deque. 00728 //************************************************************************* 00729 const_reference front() const 00730 { 00731 return *_begin; 00732 } 00733 00734 //************************************************************************* 00735 /// Gets a reference to the item at the back of the deque. 00736 ///\return A reference to the item at the back of the deque. 00737 //************************************************************************* 00738 reference back() 00739 { 00740 return *(_end - 1); 00741 } 00742 00743 //************************************************************************* 00744 /// Gets a const reference to the item at the back of the deque. 00745 ///\return A const reference to the item at the back of the deque. 00746 //************************************************************************* 00747 const_reference back() const 00748 { 00749 return *(_end - 1); 00750 } 00751 00752 //************************************************************************* 00753 /// Gets an iterator to the beginning of the deque. 00754 //************************************************************************* 00755 iterator begin() 00756 { 00757 return _begin; 00758 } 00759 00760 //************************************************************************* 00761 /// Gets a const iterator to the beginning of the deque. 00762 //************************************************************************* 00763 const_iterator begin() const 00764 { 00765 return _begin; 00766 } 00767 00768 //************************************************************************* 00769 /// Gets a const iterator to the beginning of the deque. 00770 //************************************************************************* 00771 const_iterator cbegin() const 00772 { 00773 return _begin; 00774 } 00775 00776 //************************************************************************* 00777 /// Gets an iterator to the end of the deque. 00778 //************************************************************************* 00779 iterator end() 00780 { 00781 return iterator(_end); 00782 } 00783 00784 //************************************************************************* 00785 /// Gets a const iterator to the end of the deque. 00786 //************************************************************************* 00787 const_iterator end() const 00788 { 00789 return iterator(_end); 00790 } 00791 00792 //************************************************************************* 00793 /// Gets a const iterator to the end of the deque. 00794 //************************************************************************* 00795 const_iterator cend() const 00796 { 00797 return const_iterator(_end); 00798 } 00799 00800 //************************************************************************* 00801 /// Gets a reverse iterator to the end of the deque. 00802 //************************************************************************* 00803 reverse_iterator rbegin() 00804 { 00805 return reverse_iterator(end()); 00806 } 00807 00808 //************************************************************************* 00809 /// Gets a const reverse iterator to the end of the deque. 00810 //************************************************************************* 00811 const_reverse_iterator rbegin() const 00812 { 00813 return const_reverse_iterator(end()); 00814 } 00815 00816 //************************************************************************* 00817 /// Gets a const reverse iterator to the end of the deque. 00818 //************************************************************************* 00819 const_reverse_iterator crbegin() const 00820 { 00821 return const_reverse_iterator(cend()); 00822 } 00823 00824 //************************************************************************* 00825 /// Gets a reverse iterator to the beginning of the deque. 00826 //************************************************************************* 00827 reverse_iterator rend() 00828 { 00829 return reverse_iterator(begin()); 00830 } 00831 00832 //************************************************************************* 00833 /// Gets a const reverse iterator to the beginning of the deque. 00834 //************************************************************************* 00835 const_reverse_iterator rend() const 00836 { 00837 return const_reverse_iterator(begin()); 00838 } 00839 00840 //************************************************************************* 00841 /// Gets a const reverse iterator to the beginning of the deque. 00842 //************************************************************************* 00843 const_reverse_iterator crend() const 00844 { 00845 return const_reverse_iterator(cbegin()); 00846 } 00847 00848 //************************************************************************* 00849 /// Clears the deque. 00850 //************************************************************************* 00851 void clear() 00852 { 00853 initialise(); 00854 } 00855 00856 //************************************************************************* 00857 /// Inserts data into the deque. 00858 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is full. 00859 ///\param insert_position>The insert position. 00860 ///\param value>The value to insert. 00861 //************************************************************************* 00862 iterator insert(const_iterator insert_position, const value_type& value) 00863 { 00864 iterator position(insert_position.index, *this, p_buffer); 00865 00866 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 00867 00868 if (insert_position == begin()) 00869 { 00870 create_element_front(value); 00871 position = _begin; 00872 } 00873 else if (insert_position == end()) 00874 { 00875 create_element_back(value); 00876 position = _end - 1; 00877 } 00878 else 00879 { 00880 // Are we closer to the front? 00881 if (std::distance(_begin, position) < std::distance(position, _end - 1)) 00882 { 00883 // Construct the _begin. 00884 create_element_front(*_begin); 00885 00886 // Move the values. 00887 std::copy(_begin + 1, position, _begin); 00888 00889 // Write the new value. 00890 *--position = value; 00891 } 00892 else 00893 { 00894 // Construct the _end. 00895 create_element_back(*(_end - 1)); 00896 00897 // Move the values. 00898 std::copy_backward(position, _end - 2, _end - 1); 00899 00900 // Write the new value. 00901 *position = value; 00902 } 00903 } 00904 00905 return position; 00906 } 00907 00908 //************************************************************************* 00909 /// Emplaces data into the deque. 00910 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is full. 00911 ///\param insert_position>The insert position. 00912 //************************************************************************* 00913 template <typename T1> 00914 iterator emplace(const_iterator insert_position, const T1& value1) 00915 { 00916 iterator position(insert_position.index, *this, p_buffer); 00917 00918 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 00919 00920 void* p; 00921 00922 if (insert_position == begin()) 00923 { 00924 --_begin; 00925 p = etl::addressof(*_begin); 00926 ++current_size; 00927 ++construct_count; 00928 position = _begin; 00929 } 00930 else if (insert_position == end()) 00931 { 00932 p = etl::addressof(*_end); 00933 ++_end; 00934 ++current_size; 00935 ++construct_count; 00936 position = _end - 1; 00937 } 00938 else 00939 { 00940 // Are we closer to the front? 00941 if (std::distance(_begin, position) < std::distance(position, _end - 1)) 00942 { 00943 // Construct the _begin. 00944 create_element_front(*_begin); 00945 00946 // Move the values. 00947 std::copy(_begin + 1, position, _begin); 00948 00949 // Write the new value. 00950 --position; 00951 (*position).~T(); 00952 p = etl::addressof(*position); 00953 } 00954 else 00955 { 00956 // Construct the _end. 00957 create_element_back(*(_end - 1)); 00958 00959 // Move the values. 00960 std::copy_backward(position, _end - 2, _end - 1); 00961 00962 // Write the new value. 00963 (*position).~T(); 00964 p = etl::addressof(*position); 00965 } 00966 } 00967 00968 ::new (p) T(value1); 00969 00970 return position; 00971 } 00972 00973 //************************************************************************* 00974 /// Emplaces data into the deque. 00975 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is full. 00976 ///\param insert_position>The insert position. 00977 //************************************************************************* 00978 template <typename T1, typename T2> 00979 iterator emplace(const_iterator insert_position, const T1& value1, const T2& value2) 00980 { 00981 iterator position(insert_position.index, *this, p_buffer); 00982 00983 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 00984 00985 void* p; 00986 00987 if (insert_position == begin()) 00988 { 00989 --_begin; 00990 p = etl::addressof(*_begin); 00991 ++current_size; 00992 ++construct_count; 00993 position = _begin; 00994 } 00995 else if (insert_position == end()) 00996 { 00997 p = etl::addressof(*_end); 00998 ++_end; 00999 ++current_size; 01000 ++construct_count; 01001 position = _end - 1; 01002 } 01003 else 01004 { 01005 // Are we closer to the front? 01006 if (std::distance(_begin, position) < std::distance(position, _end - 1)) 01007 { 01008 // Construct the _begin. 01009 create_element_front(*_begin); 01010 01011 // Move the values. 01012 std::copy(_begin + 1, position, _begin); 01013 01014 // Write the new value. 01015 --position; 01016 (*position).~T(); 01017 p = etl::addressof(*position); 01018 } 01019 else 01020 { 01021 // Construct the _end. 01022 create_element_back(*(_end - 1)); 01023 01024 // Move the values. 01025 std::copy_backward(position, _end - 2, _end - 1); 01026 01027 // Write the new value. 01028 (*position).~T(); 01029 p = etl::addressof(*position); 01030 } 01031 } 01032 01033 ::new (p) T(value1, value2); 01034 01035 return position; 01036 } 01037 01038 //************************************************************************* 01039 /// Emplaces data into the deque. 01040 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is full. 01041 ///\param insert_position>The insert position. 01042 //************************************************************************* 01043 template <typename T1, typename T2, typename T3> 01044 iterator emplace(const_iterator insert_position, const T1& value1, const T2& value2, const T3& value3) 01045 { 01046 iterator position(insert_position.index, *this, p_buffer); 01047 01048 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01049 01050 void* p; 01051 01052 if (insert_position == begin()) 01053 { 01054 --_begin; 01055 p = etl::addressof(*_begin); 01056 ++current_size; 01057 ++construct_count; 01058 position = _begin; 01059 } 01060 else if (insert_position == end()) 01061 { 01062 p = etl::addressof(*_end); 01063 ++_end; 01064 ++current_size; 01065 ++construct_count; 01066 position = _end - 1; 01067 } 01068 else 01069 { 01070 // Are we closer to the front? 01071 if (std::distance(_begin, position) < std::distance(position, _end - 1)) 01072 { 01073 // Construct the _begin. 01074 create_element_front(*_begin); 01075 01076 // Move the values. 01077 std::copy(_begin + 1, position, _begin); 01078 01079 // Write the new value. 01080 --position; 01081 (*position).~T(); 01082 p = etl::addressof(*position); 01083 } 01084 else 01085 { 01086 // Construct the _end. 01087 create_element_back(*(_end - 1)); 01088 01089 // Move the values. 01090 std::copy_backward(position, _end - 2, _end - 1); 01091 01092 // Write the new value. 01093 (*position).~T(); 01094 p = etl::addressof(*position); 01095 } 01096 } 01097 01098 ::new (p) T(value1, value2, value3); 01099 01100 return position; 01101 } 01102 01103 //************************************************************************* 01104 /// Emplaces data into the deque. 01105 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is full. 01106 ///\param insert_position>The insert position. 01107 //************************************************************************* 01108 template <typename T1, typename T2, typename T3, typename T4> 01109 iterator emplace(const_iterator insert_position, const T1& value1, const T2& value2, const T3& value3, const T4& value4) 01110 { 01111 iterator position(insert_position.index, *this, p_buffer); 01112 01113 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01114 01115 void* p; 01116 01117 if (insert_position == begin()) 01118 { 01119 --_begin; 01120 p = etl::addressof(*_begin); 01121 ++current_size; 01122 ++construct_count; 01123 position = _begin; 01124 } 01125 else if (insert_position == end()) 01126 { 01127 p = etl::addressof(*_end); 01128 ++_end; 01129 ++current_size; 01130 ++construct_count; 01131 position = _end - 1; 01132 } 01133 else 01134 { 01135 // Are we closer to the front? 01136 if (std::distance(_begin, position) < std::distance(position, _end - 1)) 01137 { 01138 // Construct the _begin. 01139 create_element_front(*_begin); 01140 01141 // Move the values. 01142 std::copy(_begin + 1, position, _begin); 01143 01144 // Write the new value. 01145 --position; 01146 (*position).~T(); 01147 p = etl::addressof(*position); 01148 } 01149 else 01150 { 01151 // Construct the _end. 01152 create_element_back(*(_end - 1)); 01153 01154 // Move the values. 01155 std::copy_backward(position, _end - 2, _end - 1); 01156 01157 // Write the new value. 01158 (*position).~T(); 01159 p = etl::addressof(*position); 01160 } 01161 } 01162 01163 ::new (p) T(value1, value2, value3, value4); 01164 01165 return position; 01166 } 01167 01168 //************************************************************************* 01169 /// Inserts 'n' copies of a value into the deque. 01170 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is full. 01171 ///\param insert_position The insert position. 01172 ///\param n The number of values to insert. 01173 ///\param value The value to insert. 01174 //************************************************************************* 01175 iterator insert(const_iterator insert_position, size_type n, const value_type& value) 01176 { 01177 iterator position; 01178 01179 ETL_ASSERT((current_size + n) <= CAPACITY, ETL_ERROR(deque_full)); 01180 01181 if (insert_position == begin()) 01182 { 01183 for (size_t i = 0; i < n; ++i) 01184 { 01185 create_element_front(value); 01186 } 01187 01188 position = _begin; 01189 } 01190 else if (insert_position == end()) 01191 { 01192 for (size_t i = 0; i < n; ++i) 01193 { 01194 create_element_back(value); 01195 } 01196 01197 position = _end - n; 01198 } 01199 else 01200 { 01201 // Non-const insert iterator. 01202 position = iterator(insert_position.index, *this, p_buffer); 01203 01204 // Are we closer to the front? 01205 if (distance(_begin, insert_position) <= difference_type(current_size / 2)) 01206 { 01207 size_t n_insert = n; 01208 size_t n_move = std::distance(begin(), position); 01209 size_t n_create_copy = std::min(n_insert, n_move); 01210 size_t n_create_new = (n_insert > n_create_copy) ? n_insert - n_create_copy : 0; 01211 size_t n_copy_new = (n_insert > n_create_new) ? n_insert - n_create_new : 0; 01212 size_t n_copy_old = n_move - n_create_copy; 01213 01214 // Remember the original start. 01215 iterator from = _begin + n_create_copy - 1; 01216 iterator to; 01217 01218 // Create new. 01219 for (size_t i = 0; i < n_create_new; ++i) 01220 { 01221 create_element_front(value); 01222 } 01223 01224 // Create copy. 01225 for (size_t i = 0; i < n_create_copy; ++i) 01226 { 01227 create_element_front(*from--); 01228 } 01229 01230 // Copy old. 01231 from = position - n_copy_old; 01232 to = _begin + n_create_copy; 01233 etl::copy_n(from, n_copy_old, to); 01234 01235 // Copy new. 01236 to = position - n_create_copy; 01237 std::fill_n(to, n_copy_new, value); 01238 01239 position = _begin + n_move; 01240 } 01241 else 01242 { 01243 size_t n_insert = n; 01244 size_t n_move = std::distance(position, end()); 01245 size_t n_create_copy = std::min(n_insert, n_move); 01246 size_t n_create_new = (n_insert > n_create_copy) ? n_insert - n_create_copy : 0; 01247 size_t n_copy_new = (n_insert > n_create_new) ? n_insert - n_create_new : 0; 01248 size_t n_copy_old = n_move - n_create_copy; 01249 01250 // Create new. 01251 for (size_t i = 0; i < n_create_new; ++i) 01252 { 01253 create_element_back(value); 01254 } 01255 01256 // Create copy. 01257 const_iterator from = position + n_copy_old; 01258 01259 for (size_t i = 0; i < n_create_copy; ++i) 01260 { 01261 create_element_back(*from++); 01262 } 01263 01264 // Copy old. 01265 std::copy_backward(position, position + n_copy_old, position + n_insert + n_copy_old); 01266 01267 // Copy new. 01268 std::fill_n(position, n_copy_new, value); 01269 } 01270 } 01271 01272 return position; 01273 } 01274 01275 //************************************************************************* 01276 /// Inserts a range into the deque. 01277 /// If asserts or exceptions are enabled, throws an etl::deque_empty if the deque is full. 01278 ///\param insert_position>The insert position. 01279 ///\param range_begin The beginning of the range to insert. 01280 ///\param range_end The end of the range to insert. 01281 //************************************************************************* 01282 template<typename TIterator> 01283 typename enable_if<is_iterator<TIterator>::value, iterator>::type 01284 insert(const_iterator insert_position, TIterator range_begin, TIterator range_end) 01285 { 01286 iterator position; 01287 01288 difference_type n = std::distance(range_begin, range_end); 01289 01290 ETL_ASSERT((current_size + n) <= CAPACITY, ETL_ERROR(deque_full)); 01291 01292 if (insert_position == begin()) 01293 { 01294 create_element_front(n, range_begin); 01295 01296 position = _begin; 01297 } 01298 else if (insert_position == end()) 01299 { 01300 for (difference_type i = 0; i < n; ++i) 01301 { 01302 create_element_back(*range_begin++); 01303 } 01304 01305 position = _end - n; 01306 } 01307 else 01308 { 01309 // Non-const insert iterator. 01310 position = iterator(insert_position.index, *this, p_buffer); 01311 01312 // Are we closer to the front? 01313 if (distance(_begin, insert_position) < difference_type(current_size / 2)) 01314 { 01315 size_t n_insert = n; 01316 size_t n_move = std::distance(begin(), position); 01317 size_t n_create_copy = std::min(n_insert, n_move); 01318 size_t n_create_new = (n_insert > n_create_copy) ? n_insert - n_create_copy : 0; 01319 size_t n_copy_new = (n_insert > n_create_new) ? n_insert - n_create_new : 0; 01320 size_t n_copy_old = n_move - n_create_copy; 01321 01322 // Remember the original start. 01323 iterator from; 01324 iterator to; 01325 01326 // Create new. 01327 create_element_front(n_create_new, range_begin); 01328 01329 // Create copy. 01330 create_element_front(n_create_copy, _begin + n_create_new); 01331 01332 // Copy old. 01333 from = position - n_copy_old; 01334 to = _begin + n_create_copy; 01335 etl::copy_n(from, n_copy_old, to); 01336 01337 // Copy new. 01338 to = position - n_create_copy; 01339 range_begin += n_create_new; 01340 etl::copy_n(range_begin, n_copy_new, to); 01341 01342 position = _begin + n_move; 01343 } 01344 else 01345 { 01346 size_t n_insert = n; 01347 size_t n_move = std::distance(position, end()); 01348 size_t n_create_copy = std::min(n_insert, n_move); 01349 size_t n_create_new = (n_insert > n_create_copy) ? n_insert - n_create_copy : 0; 01350 size_t n_copy_new = (n_insert > n_create_new) ? n_insert - n_create_new : 0; 01351 size_t n_copy_old = n_move - n_create_copy; 01352 01353 // Create new. 01354 TIterator item = range_begin + (n - n_create_new); 01355 for (size_t i = 0; i < n_create_new; ++i) 01356 { 01357 create_element_back(*item++); 01358 } 01359 01360 // Create copy. 01361 const_iterator from = position + n_copy_old; 01362 01363 for (size_t i = 0; i < n_create_copy; ++i) 01364 { 01365 create_element_back(*from++); 01366 } 01367 01368 // Copy old. 01369 std::copy_backward(position, position + n_copy_old, position + n_insert + n_copy_old); 01370 01371 // Copy new. 01372 item = range_begin; 01373 etl::copy_n(item, n_copy_new, position); 01374 } 01375 } 01376 01377 return position; 01378 } 01379 01380 //************************************************************************* 01381 /// Erase an item. 01382 /// If asserts or exceptions are enabled, throws an etl::deque_out_of_bounds if the position is out of range. 01383 ///\param erase_position The position to erase. 01384 //************************************************************************* 01385 iterator erase(const_iterator erase_position) 01386 { 01387 iterator position(erase_position.index, *this, p_buffer); 01388 01389 ETL_ASSERT(distance(position) <= difference_type(current_size), ETL_ERROR(deque_out_of_bounds)); 01390 01391 if (position == _begin) 01392 { 01393 destroy_element_front(); 01394 position = begin(); 01395 } 01396 else if (position == _end - 1) 01397 { 01398 destroy_element_back(); 01399 position = end(); 01400 } 01401 else 01402 { 01403 // Are we closer to the front? 01404 if (distance(_begin, position) < difference_type(current_size / 2)) 01405 { 01406 std::copy_backward(_begin, position, position + 1); 01407 destroy_element_front(); 01408 ++position; 01409 } 01410 else 01411 { 01412 std::copy(position + 1, _end, position); 01413 destroy_element_back(); 01414 } 01415 } 01416 01417 return position; 01418 } 01419 01420 //************************************************************************* 01421 /// erase a range. 01422 /// If asserts or exceptions are enabled, throws an etl::deque_out_of_bounds if the iterators are out of range. 01423 ///\param range_begin The beginning of the range to erase. 01424 ///\param range_end The end of the range to erase. 01425 //************************************************************************* 01426 iterator erase(const_iterator range_begin, const_iterator range_end) 01427 { 01428 iterator position(range_begin.index, *this, p_buffer); 01429 01430 ETL_ASSERT((distance(range_begin) <= difference_type(current_size)) && (distance(range_end) <= difference_type(current_size)), ETL_ERROR(deque_out_of_bounds)); 01431 01432 // How many to erase? 01433 size_t length = std::distance(range_begin, range_end); 01434 01435 // At the beginning? 01436 if (position == _begin) 01437 { 01438 for (size_t i = 0; i < length; ++i) 01439 { 01440 destroy_element_front(); 01441 } 01442 01443 position = begin(); 01444 } 01445 // At the end? 01446 else if (position == _end - length) 01447 { 01448 for (size_t i = 0; i < length; ++i) 01449 { 01450 destroy_element_back(); 01451 } 01452 01453 position = end(); 01454 } 01455 else 01456 { 01457 // Copy the smallest number of items. 01458 // Are we closer to the front? 01459 if (distance(_begin, position) < difference_type(current_size / 2)) 01460 { 01461 // Move the items. 01462 std::copy_backward(_begin, position, position + length); 01463 01464 for (size_t i = 0; i < length; ++i) 01465 { 01466 destroy_element_front(); 01467 } 01468 01469 position += length; 01470 } 01471 else 01472 // Must be closer to the back. 01473 { 01474 // Move the items. 01475 std::copy(position + length, _end, position); 01476 01477 for (size_t i = 0; i < length; ++i) 01478 { 01479 destroy_element_back(); 01480 } 01481 } 01482 } 01483 01484 return position; 01485 } 01486 01487 //************************************************************************* 01488 /// Adds an item to the back of the deque. 01489 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is already full. 01490 ///\param item The item to push to the deque. 01491 //************************************************************************* 01492 void push_back(parameter_t item) 01493 { 01494 #if defined(ETL_CHECK_PUSH_POP) 01495 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01496 #endif 01497 create_element_back(item); 01498 } 01499 01500 //************************************************************************* 01501 /// Adds one to the front of the deque and returns a reference to the new element. 01502 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is already full. 01503 ///\return A reference to the item to assign to. 01504 //************************************************************************* 01505 reference push_back() 01506 { 01507 reference r = *_end; 01508 #if defined(ETL_CHECK_PUSH_POP) 01509 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01510 #endif 01511 create_element_back(); 01512 01513 return r; 01514 } 01515 01516 //************************************************************************* 01517 /// Emplaces an item to the back of the deque. 01518 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is already full. 01519 //************************************************************************* 01520 template <typename T1> 01521 void emplace_back(const T1& value1) 01522 { 01523 #if defined(ETL_CHECK_PUSH_POP) 01524 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01525 #endif 01526 01527 ::new (&(*_end)) T(value1); 01528 ++_end; 01529 ++current_size; 01530 ++construct_count; 01531 } 01532 01533 //************************************************************************* 01534 /// Emplaces an item to the back of the deque. 01535 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is already full. 01536 //************************************************************************* 01537 template <typename T1, typename T2> 01538 void emplace_back(const T1& value1, const T2& value2) 01539 { 01540 #if defined(ETL_CHECK_PUSH_POP) 01541 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01542 #endif 01543 01544 ::new (&(*_end)) T(value1, value2); 01545 ++_end; 01546 ++current_size; 01547 ++construct_count; 01548 } 01549 01550 //************************************************************************* 01551 /// Emplaces an item to the back of the deque. 01552 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is already full. 01553 //************************************************************************* 01554 template <typename T1, typename T2, typename T3> 01555 void emplace_back(const T1& value1, const T2& value2, const T3& value3) 01556 { 01557 #if defined(ETL_CHECK_PUSH_POP) 01558 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01559 #endif 01560 01561 ::new (&(*_end)) T(value1, value2, value3); 01562 ++_end; 01563 ++current_size; 01564 ++construct_count; 01565 } 01566 01567 //************************************************************************* 01568 /// Emplaces an item to the back of the deque. 01569 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is already full. 01570 //************************************************************************* 01571 template <typename T1, typename T2, typename T3, typename T4> 01572 void emplace_back(const T1& value1, const T2& value2, const T3& value3, const T4& value4) 01573 { 01574 #if defined(ETL_CHECK_PUSH_POP) 01575 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01576 #endif 01577 01578 ::new (&(*_end)) T(value1, value2, value3, value4); 01579 ++_end; 01580 ++current_size; 01581 ++construct_count; 01582 } 01583 01584 //************************************************************************* 01585 /// Removes the oldest item from the deque. 01586 //************************************************************************* 01587 void pop_back() 01588 { 01589 #if defined(ETL_CHECK_PUSH_POP) 01590 ETL_ASSERT(!empty(), ETL_ERROR(deque_empty)); 01591 #endif 01592 destroy_element_back(); 01593 } 01594 01595 //************************************************************************* 01596 /// Adds an item to the front of the deque. 01597 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is already full. 01598 ///\param item The item to push to the deque. 01599 //************************************************************************* 01600 void push_front(parameter_t item) 01601 { 01602 #if defined(ETL_CHECK_PUSH_POP) 01603 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01604 #endif 01605 create_element_front(item); 01606 } 01607 01608 //************************************************************************* 01609 /// Adds one to the front of the deque and returns a reference to the new element. 01610 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is already full. 01611 ///\return A reference to the item to assign to. 01612 //************************************************************************* 01613 reference push_front() 01614 { 01615 #if defined(ETL_CHECK_PUSH_POP) 01616 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01617 #endif 01618 create_element_front(); 01619 01620 return *_begin; 01621 } 01622 01623 //************************************************************************* 01624 /// Emplaces an item to the front of the deque. 01625 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is already full. 01626 //************************************************************************* 01627 template <typename T1> 01628 void emplace_front(const T1& value1) 01629 { 01630 #if defined(ETL_CHECK_PUSH_POP) 01631 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01632 #endif 01633 01634 --_begin; 01635 ::new (&(*_begin)) T(value1); 01636 ++current_size; 01637 ++construct_count; 01638 } 01639 01640 //************************************************************************* 01641 /// Emplaces an item to the front of the deque. 01642 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is already full. 01643 //************************************************************************* 01644 template <typename T1, typename T2> 01645 void emplace_front(const T1& value1, const T2& value2) 01646 { 01647 #if defined(ETL_CHECK_PUSH_POP) 01648 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01649 #endif 01650 01651 --_begin; 01652 ::new (&(*_begin)) T(value1, value2); 01653 ++current_size; 01654 ++construct_count; 01655 } 01656 01657 //************************************************************************* 01658 /// Emplaces an item to the front of the deque. 01659 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is already full. 01660 //************************************************************************* 01661 template <typename T1, typename T2, typename T3> 01662 void emplace_front(const T1& value1, const T2& value2, const T3& value3) 01663 { 01664 #if defined(ETL_CHECK_PUSH_POP) 01665 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01666 #endif 01667 01668 --_begin; 01669 ::new (&(*_begin)) T(value1, value2, value3); 01670 ++current_size; 01671 ++construct_count; 01672 } 01673 01674 //************************************************************************* 01675 /// Emplaces an item to the front of the deque. 01676 /// If asserts or exceptions are enabled, throws an etl::deque_full if the deque is already full. 01677 //************************************************************************* 01678 template <typename T1, typename T2, typename T3, typename T4> 01679 void emplace_front(const T1& value1, const T2& value2, const T3& value3, const T4& value4) 01680 { 01681 #if defined(ETL_CHECK_PUSH_POP) 01682 ETL_ASSERT(!full(), ETL_ERROR(deque_full)); 01683 #endif 01684 01685 --_begin; 01686 ::new (&(*_begin)) T(value1, value2, value3, value4); 01687 ++current_size; 01688 ++construct_count; 01689 } 01690 01691 //************************************************************************* 01692 /// Removes the oldest item from the deque. 01693 //************************************************************************* 01694 void pop_front() 01695 { 01696 #if defined(ETL_CHECK_PUSH_POP) 01697 ETL_ASSERT(!empty(), ETL_ERROR(deque_empty)); 01698 #endif 01699 destroy_element_front(); 01700 } 01701 01702 //************************************************************************* 01703 /// Resizes the deque. 01704 /// If asserts or exceptions are enabled, throws an etl::deque_full is 'new_size' is too large. 01705 ///\param new_size The new size of the deque. 01706 ///\param value The value to assign if the new size is larger. Default = Default constructed value. 01707 //************************************************************************* 01708 void resize(size_t new_size, const value_type& value = value_type()) 01709 { 01710 ETL_ASSERT(new_size <= CAPACITY, ETL_ERROR(deque_out_of_bounds)); 01711 01712 // Make it smaller? 01713 if (new_size < current_size) 01714 { 01715 while (current_size > new_size) 01716 { 01717 destroy_element_back(); 01718 } 01719 } 01720 // Make it larger? 01721 else if (new_size > current_size) 01722 { 01723 size_t count = new_size - current_size; 01724 01725 for (size_t i = 0; i < count; ++i) 01726 { 01727 create_element_back(value); 01728 } 01729 } 01730 } 01731 01732 //************************************************************************* 01733 /// - operator for iterator 01734 //************************************************************************* 01735 friend difference_type operator -(const iterator& lhs, const iterator& rhs) 01736 { 01737 return distance(rhs, lhs); 01738 } 01739 01740 //************************************************************************* 01741 /// - operator for const_iterator 01742 //************************************************************************* 01743 friend difference_type operator -(const const_iterator& lhs, const const_iterator& rhs) 01744 { 01745 return distance(rhs, lhs); 01746 } 01747 01748 //************************************************************************* 01749 /// - operator for reverse_iterator 01750 //************************************************************************* 01751 friend difference_type operator -(const reverse_iterator& lhs, const reverse_iterator& rhs) 01752 { 01753 return distance(lhs.base(), rhs.base()); 01754 } 01755 01756 //************************************************************************* 01757 /// - operator for const_reverse_iterator 01758 //************************************************************************* 01759 friend difference_type operator -(const const_reverse_iterator& lhs, const const_reverse_iterator& rhs) 01760 { 01761 return distance(lhs.base(), rhs.base()); 01762 } 01763 01764 //************************************************************************* 01765 /// Assignment operator. 01766 //************************************************************************* 01767 ideque& operator =(const ideque& rhs) 01768 { 01769 if (&rhs != this) 01770 { 01771 assign(rhs.begin(), rhs.end()); 01772 } 01773 01774 return *this; 01775 } 01776 01777 #ifdef ETL_IDEQUE_REPAIR_ENABLE 01778 //************************************************************************* 01779 /// Fix the internal pointers after a low level memory copy. 01780 //************************************************************************* 01781 virtual void repair() = 0; 01782 #endif 01783 01784 protected: 01785 01786 //************************************************************************* 01787 /// Constructor. 01788 //************************************************************************* 01789 ideque(pointer p_buffer_, size_t max_size_, size_t buffer_size_) 01790 : deque_base(max_size_, buffer_size_), 01791 p_buffer(p_buffer_) 01792 { 01793 } 01794 01795 //********************************************************************* 01796 /// Initialise the deque. 01797 //********************************************************************* 01798 void initialise() 01799 { 01800 while (current_size > 0) 01801 { 01802 destroy_element_back(); 01803 } 01804 01805 _begin = iterator(0, *this, p_buffer); 01806 _end = iterator(0, *this, p_buffer); 01807 } 01808 01809 //************************************************************************* 01810 /// Fix the internal pointers after a low level memory copy. 01811 //************************************************************************* 01812 void repair(pointer p_buffer_) 01813 { 01814 p_buffer = p_buffer_; 01815 01816 _begin = iterator(_begin.index, *this, p_buffer); 01817 _end = iterator(_end.index, *this, p_buffer); 01818 } 01819 01820 iterator _begin; ///Iterator to the _begin item in the deque. 01821 iterator _end; ///Iterator to the _end item in the deque. 01822 pointer p_buffer; ///The buffer for the deque. 01823 01824 private: 01825 01826 //********************************************************************* 01827 /// Create a new element with a default value at the front. 01828 //********************************************************************* 01829 void create_element_front() 01830 { 01831 --_begin; 01832 ::new (&(*_begin)) T(); 01833 ++current_size; 01834 ++construct_count; 01835 } 01836 01837 //********************************************************************* 01838 /// Create a new elements from a range at the front. 01839 //********************************************************************* 01840 template <typename TIterator> 01841 void create_element_front(size_t n, TIterator from) 01842 { 01843 if (n == 0) 01844 { 01845 return; 01846 } 01847 01848 if (!empty()) 01849 { 01850 --_begin; 01851 --n; 01852 } 01853 01854 if (n > 0) 01855 { 01856 _begin -= n; 01857 } 01858 01859 iterator item = _begin; 01860 01861 do 01862 { 01863 ::new (&(*item++)) T(*from); 01864 ++from; 01865 ++current_size; 01866 ++construct_count; 01867 } while (n-- != 0); 01868 } 01869 01870 //********************************************************************* 01871 /// Create a new element with a default value at the back. 01872 //********************************************************************* 01873 void create_element_back() 01874 { 01875 ::new (&(*_end)) T(); 01876 ++_end; 01877 ++current_size; 01878 ++construct_count; 01879 } 01880 01881 //********************************************************************* 01882 /// Create a new element with a default value at the front. 01883 //********************************************************************* 01884 void create_element_front(parameter_t value) 01885 { 01886 --_begin; 01887 ::new (&(*_begin)) T(value); 01888 ++current_size; 01889 ++construct_count; 01890 } 01891 01892 //********************************************************************* 01893 /// Create a new element with a value at the back 01894 //********************************************************************* 01895 void create_element_back(parameter_t value) 01896 { 01897 ::new (&(*_end)) T(value); 01898 ++_end; 01899 ++current_size; 01900 ++construct_count; 01901 } 01902 01903 //********************************************************************* 01904 /// Destroy an element at the front. 01905 //********************************************************************* 01906 void destroy_element_front() 01907 { 01908 (*_begin).~T(); 01909 --current_size; 01910 --construct_count; 01911 ++_begin; 01912 } 01913 01914 //********************************************************************* 01915 /// Destroy an element at the back. 01916 //********************************************************************* 01917 void destroy_element_back() 01918 { 01919 --_end; 01920 (*_end).~T(); 01921 --current_size; 01922 --construct_count; 01923 } 01924 01925 //************************************************************************* 01926 /// Measures the distance between two iterators. 01927 //************************************************************************* 01928 template <typename TIterator1, typename TIterator2> 01929 static difference_type distance(const TIterator1& range_begin, const TIterator2& range_end) 01930 { 01931 difference_type distance1 = distance(range_begin); 01932 difference_type distance2 = distance(range_end); 01933 01934 return distance2 - distance1; 01935 } 01936 01937 //************************************************************************* 01938 /// Measures the distance from the _begin iterator to the specified iterator. 01939 //************************************************************************* 01940 template <typename TIterator> 01941 static difference_type distance(const TIterator& other) 01942 { 01943 const difference_type index = other.get_index(); 01944 const difference_type reference_index = other.get_deque()._begin.index; 01945 const size_t buffer_size = other.get_deque().BUFFER_SIZE; 01946 01947 if (index < reference_index) 01948 { 01949 return buffer_size + index - reference_index; 01950 } 01951 else 01952 { 01953 return index - reference_index; 01954 } 01955 } 01956 01957 // Disable copy construction. 01958 ideque(const ideque&); 01959 }; 01960 01961 //*************************************************************************** 01962 /// A fixed capacity double ended queue. 01963 ///\note The deque allocates one more element than the specified maximum size. 01964 ///\tparam T The type of items this deque holds. 01965 ///\tparam MAX_SIZE_ The capacity of the deque 01966 ///\ingroup deque 01967 //*************************************************************************** 01968 template <typename T, const size_t MAX_SIZE_> 01969 class deque : public etl::ideque<T> 01970 { 01971 public: 01972 01973 static const size_t MAX_SIZE = MAX_SIZE_; 01974 01975 private: 01976 01977 static const size_t BUFFER_SIZE = MAX_SIZE + 1; 01978 01979 public: 01980 01981 typedef T value_type; 01982 typedef T* pointer; 01983 typedef const T* const_pointer; 01984 typedef T& reference; 01985 typedef const T& const_reference; 01986 typedef size_t size_type; 01987 typedef typename std::iterator_traits<pointer>::difference_type difference_type; 01988 01989 //************************************************************************* 01990 /// Default constructor. 01991 //************************************************************************* 01992 deque() 01993 : etl::ideque<T>(reinterpret_cast<T*>(&buffer[0]), MAX_SIZE, BUFFER_SIZE) 01994 { 01995 etl::ideque<T>::initialise(); 01996 } 01997 01998 //************************************************************************* 01999 /// Destructor. 02000 //************************************************************************* 02001 ~deque() 02002 { 02003 etl::ideque<T>::initialise(); 02004 } 02005 02006 //************************************************************************* 02007 /// Copy constructor. 02008 //************************************************************************* 02009 deque(const deque& other) 02010 : etl::ideque<T>(reinterpret_cast<T*>(&buffer[0]), MAX_SIZE, BUFFER_SIZE) 02011 { 02012 if (this != &other) 02013 { 02014 etl::ideque<T>::assign(other.begin(), other.end()); 02015 } 02016 } 02017 02018 //************************************************************************* 02019 /// Assigns data to the deque. 02020 //************************************************************************* 02021 template <typename TIterator> 02022 deque(TIterator begin_, TIterator end_) 02023 : etl::ideque<T>(reinterpret_cast<T*>(&buffer[0]), MAX_SIZE, BUFFER_SIZE) 02024 { 02025 etl::ideque<T>::assign(begin_, end_); 02026 } 02027 02028 //************************************************************************* 02029 /// Assigns data to the deque. 02030 //************************************************************************* 02031 explicit deque(size_t n, typename etl::ideque<T>::parameter_t value = value_type()) 02032 : etl::ideque<T>(reinterpret_cast<T*>(&buffer[0]), MAX_SIZE, BUFFER_SIZE) 02033 { 02034 etl::ideque<T>::assign(n, value); 02035 } 02036 02037 //************************************************************************* 02038 /// Assignment operator. 02039 //************************************************************************* 02040 deque& operator =(const deque& rhs) 02041 { 02042 if (&rhs != this) 02043 { 02044 etl::ideque<T>::assign(rhs.begin(), rhs.end()); 02045 } 02046 02047 return *this; 02048 } 02049 02050 //************************************************************************* 02051 /// Fix the internal pointers after a low level memory copy. 02052 //************************************************************************* 02053 void repair() 02054 { 02055 #if ETL_CPP11_TYPE_TRAITS_IS_TRIVIAL_SUPPORTED 02056 ETL_ASSERT(std::is_trivially_copyable<T>::value, ETL_ERROR(etl::deque_incompatible_type)); 02057 #endif 02058 02059 etl::ideque<T>::repair(reinterpret_cast<T*>(&buffer[0])); 02060 } 02061 02062 private: 02063 02064 /// The uninitialised buffer of T used in the deque. 02065 typename etl::aligned_storage<sizeof(T), etl::alignment_of<T>::value>::type buffer[BUFFER_SIZE]; 02066 }; 02067 } 02068 02069 //*************************************************************************** 02070 /// Equal operator. 02071 ///\param lhs Reference to the _begin deque. 02072 ///\param rhs Reference to the second deque. 02073 ///\return <b>true</b> if the arrays are equal, otherwise <b>false</b> 02074 ///\ingroup deque 02075 //*************************************************************************** 02076 template <typename T> 02077 bool operator ==(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs) 02078 { 02079 return (lhs.size() == rhs.size()) && std::equal(lhs.begin(), lhs.end(), rhs.begin()); 02080 } 02081 02082 //*************************************************************************** 02083 /// Not equal operator. 02084 ///\param lhs Reference to the _begin deque. 02085 ///\param rhs Reference to the second deque. 02086 ///\return <b>true</b> if the arrays are not equal, otherwise <b>false</b> 02087 ///\ingroup deque 02088 //*************************************************************************** 02089 template <typename T> 02090 bool operator !=(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs) 02091 { 02092 return !(lhs == rhs); 02093 } 02094 02095 //*************************************************************************** 02096 /// Less than operator. 02097 ///\param lhs Reference to the _begin deque. 02098 ///\param rhs Reference to the second deque. 02099 ///\return <b>true</b> if the _begin deque is lexicographically less than the second, otherwise <b>false</b> 02100 ///\ingroup deque 02101 //*************************************************************************** 02102 template <typename T> 02103 bool operator <(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs) 02104 { 02105 return std::lexicographical_compare(lhs.begin(), 02106 lhs.end(), 02107 rhs.begin(), 02108 rhs.end()); 02109 } 02110 02111 //*************************************************************************** 02112 /// Less than or equal operator. 02113 ///\param lhs Reference to the _begin deque. 02114 ///\param rhs Reference to the second deque. 02115 ///\return <b>true</b> if the _begin deque is lexicographically less than or equal to the second, otherwise <b>false</b> 02116 ///\ingroup deque 02117 //*************************************************************************** 02118 template <typename T> 02119 bool operator <=(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs) 02120 { 02121 return !(lhs > rhs); 02122 } 02123 02124 //*************************************************************************** 02125 /// Greater than operator. 02126 ///\param lhs Reference to the _begin deque. 02127 ///\param rhs Reference to the second deque. 02128 ///\return <b>true</b> if the _begin deque is lexicographically greater than the second, otherwise <b>false</b> 02129 ///\ingroup deque 02130 //*************************************************************************** 02131 template <typename T> 02132 bool operator >(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs) 02133 { 02134 return (rhs < lhs); 02135 } 02136 02137 //*************************************************************************** 02138 /// Greater than or equal operator. 02139 ///\param "lhs Reference to the _begin deque. 02140 ///\param "rhs Reference to the second deque. 02141 ///\return <b>true</b> if the _begin deque is lexicographically greater than or equal to the second, otherwise <b>false</b> 02142 ///\ingroup deque 02143 //*************************************************************************** 02144 template <typename T> 02145 bool operator >=(const etl::ideque<T>& lhs, const etl::ideque<T>& rhs) 02146 { 02147 return !(lhs < rhs); 02148 } 02149 02150 #undef ETL_FILE 02151 02152 #ifdef ETL_COMPILER_MICROSOFT 02153 #define min(a,b) (((a) < (b)) ? (a) : (b)) 02154 #endif 02155 02156 #endif 02157
Generated on Tue Jul 12 2022 14:05:40 by
1.7.2