forward_list.h

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_FORWARD_LIST__
00032 #define __ETL_FORWARD_LIST__
00033 
00034 #include <iterator>
00035 #include <algorithm>
00036 #include <functional>
00037 #include <stddef.h>
00038 
00039 #include "platform.h "
00040 #include "pool.h "
00041 #include "container.h "
00042 #include "exception.h "
00043 #include "error_handler.h "
00044 #include "debug_count.h "
00045 #include "nullptr.h "
00046 #include "type_traits.h "
00047 #include "parameter_type.h "
00048 
00049 #ifdef ETL_COMPILER_MICROSOFT
00050 #undef min
00051 #endif
00052 
00053 #undef ETL_FILE
00054 #define ETL_FILE "6"
00055 
00056 //*****************************************************************************
00057 ///\defgroup forward_list forward_list
00058 /// A linked forward_list with the capacity defined at compile time.
00059 ///\ingroup containers
00060 //*****************************************************************************
00061 
00062 namespace etl
00063 {
00064   //***************************************************************************
00065   /// Exception for the forward_list.
00066   ///\ingroup forward_list
00067   //***************************************************************************
00068   class forward_list_exception : public etl::exception
00069   {
00070   public:
00071 
00072     forward_list_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
00073       : exception(reason_, file_name_, line_number_)
00074     {
00075     }
00076   };
00077 
00078   //***************************************************************************
00079   /// Full exception for the forward_list.
00080   ///\ingroup forward_list
00081   //***************************************************************************
00082   class forward_list_full : public etl::forward_list_exception
00083   {
00084   public:
00085 
00086     forward_list_full(string_type file_name_, numeric_type line_number_)
00087       : etl::forward_list_exception(ETL_ERROR_TEXT("forward_list:full", ETL_FILE"A"), file_name_, line_number_)
00088     {
00089     }
00090   };
00091 
00092   //***************************************************************************
00093   /// Empty exception for the forward_list.
00094   ///\ingroup forward_list
00095   //***************************************************************************
00096   class forward_list_empty : public etl::forward_list_exception
00097   {
00098   public:
00099 
00100     forward_list_empty(string_type file_name_, numeric_type line_number_)
00101       : etl::forward_list_exception(ETL_ERROR_TEXT("forward_list:empty", ETL_FILE"B"), file_name_, line_number_)
00102     {
00103     }
00104   };
00105 
00106   //***************************************************************************
00107   /// Iterator exception for the forward_list.
00108   ///\ingroup forward_list
00109   //***************************************************************************
00110   class forward_list_iterator : public etl::forward_list_exception
00111   {
00112   public:
00113 
00114     forward_list_iterator(string_type file_name_, numeric_type line_number_)
00115       : etl::forward_list_exception(ETL_ERROR_TEXT("forward_list:iterator", ETL_FILE"C"), file_name_, line_number_)
00116     {
00117     }
00118   };
00119 
00120   //***************************************************************************
00121   /// The base class for all forward_lists.
00122   ///\ingroup forward_list
00123   //***************************************************************************
00124   class forward_list_base
00125   {
00126   protected:
00127 
00128     //*************************************************************************
00129     /// The node element in the forward_list.
00130     //*************************************************************************
00131     struct node_t
00132     {
00133       node_t()
00134         : next(std::nullptr)
00135       {
00136       }
00137 
00138       node_t* next;
00139     };
00140 
00141   public:
00142 
00143     typedef size_t size_type; ///< The type used for determining the size of forward_list.
00144 
00145     //*************************************************************************
00146     /// Gets the size of the forward_list.
00147     //*************************************************************************
00148     size_type size() const
00149     {
00150       return p_node_pool->size();
00151     }
00152 
00153     //*************************************************************************
00154     /// Gets the maximum possible size of the forward_list.
00155     //*************************************************************************
00156     size_type max_size() const
00157     {
00158       return MAX_SIZE;
00159     }
00160 
00161     //*************************************************************************
00162     /// Checks to see if the forward_list is empty.
00163     //*************************************************************************
00164     bool empty() const
00165     {
00166       return p_node_pool->empty();
00167     }
00168 
00169     //*************************************************************************
00170     /// Checks to see if the forward_list is full.
00171     //*************************************************************************
00172     bool full() const
00173     {
00174       return p_node_pool->full();
00175     }
00176 
00177     //*************************************************************************
00178     /// Returns the remaining capacity.
00179     ///\return The remaining capacity.
00180     //*************************************************************************
00181     size_t available() const
00182     {
00183       return p_node_pool->available();
00184     }
00185 
00186     //*************************************************************************
00187     /// Reverses the forward_list.
00188     //*************************************************************************
00189     void reverse()
00190     {
00191       if (is_trivial_list())
00192       {
00193         return;
00194       }
00195 
00196       node_t* p_last = &start_node;
00197       node_t* p_current = p_last->next;
00198       node_t* p_next = p_current->next;
00199 
00200       p_current->next = std::nullptr;
00201 
00202       while (p_next != std::nullptr)
00203       {
00204         p_last = p_current;
00205         p_current = p_next;
00206         p_next = p_current->next;
00207 
00208         p_current->next = p_last;
00209       }
00210 
00211       join(&start_node, p_current);
00212     }
00213 
00214   protected:
00215 
00216     //*************************************************************************
00217     /// The constructor that is called from derived classes.
00218     //*************************************************************************
00219     forward_list_base(etl::ipool& node_pool_, size_type max_size_)
00220       : p_node_pool(&node_pool_),
00221         MAX_SIZE(max_size_)
00222     {
00223     }
00224 
00225     //*************************************************************************
00226     /// Get the head node.
00227     //*************************************************************************
00228     node_t& get_head()
00229     {
00230       return *start_node.next;
00231     }
00232 
00233     //*************************************************************************
00234     /// Get the head node.
00235     //*************************************************************************
00236     const node_t& get_head() const
00237     {
00238       return *start_node.next;
00239     }
00240 
00241     //*************************************************************************
00242     /// Insert a node.
00243     //*************************************************************************
00244     inline void insert_node_after(node_t& position, node_t& node)
00245     {
00246       // Connect to the forward_list.
00247       join(&node, position.next);
00248       join(&position, &node);
00249     }
00250 
00251     //*************************************************************************
00252     /// Is the forward_list a trivial length?
00253     //*************************************************************************
00254     bool is_trivial_list() const
00255     {
00256       return (size() < 2);
00257     }
00258 
00259     //*************************************************************************
00260     /// Join two nodes.
00261     //*************************************************************************
00262     void join(node_t* left, node_t* right)
00263     {
00264       left->next = right;
00265     }
00266 
00267     node_t           start_node;      ///< The node that acts as the forward_list start.
00268     etl::ipool*      p_node_pool;     ///< The pool of data nodes used in the list.
00269     const size_type  MAX_SIZE;        ///< The maximum size of the forward_list.
00270     etl::debug_count construct_count; ///< Internal debugging.
00271   };
00272 
00273   //***************************************************************************
00274   /// A templated base for all etl::forward_list types.
00275   ///\ingroup forward_list
00276   //***************************************************************************
00277   template <typename T>
00278   class iforward_list : public etl::forward_list_base
00279   {
00280   public:
00281 
00282     typedef T        value_type;
00283     typedef T*       pointer;
00284     typedef const T* const_pointer;
00285     typedef T&       reference;
00286     typedef const T& const_reference;
00287     typedef size_t   size_type;
00288 
00289   protected:
00290 
00291     typedef typename etl::parameter_type<T>::type parameter_t;
00292 
00293     //*************************************************************************
00294     /// The data node element in the forward_list.
00295     //*************************************************************************
00296     struct data_node_t : public node_t
00297     {
00298       explicit data_node_t(parameter_t value_)
00299         : value(value_)
00300       {}
00301 
00302       T value;
00303     };
00304 
00305   public:
00306 
00307     //*************************************************************************
00308     /// iterator.
00309     //*************************************************************************
00310     class iterator : public std::iterator<std::forward_iterator_tag, T>
00311     {
00312     public:
00313 
00314       friend class iforward_list;
00315 
00316       iterator()
00317         : p_node(std::nullptr)
00318       {
00319       }
00320 
00321       iterator(node_t& node)
00322         : p_node(&node)
00323       {
00324       }
00325 
00326       iterator(const iterator& other)
00327         : p_node(other.p_node)
00328       {
00329       }
00330 
00331       iterator& operator ++()
00332       {
00333         p_node = p_node->next;
00334         return *this;
00335       }
00336 
00337       iterator operator ++(int)
00338       {
00339         iterator temp(*this);
00340         p_node = p_node->next;
00341         return temp;
00342       }
00343 
00344       iterator operator =(const iterator& other)
00345       {
00346         p_node = other.p_node;
00347         return *this;
00348       }
00349 
00350       reference operator *()
00351       {
00352         return iforward_list::data_cast(p_node)->value;
00353       }
00354 
00355       const_reference operator *() const
00356       {
00357         return iforward_list::data_cast(p_node)->value;
00358       }
00359 
00360       pointer operator &()
00361       {
00362         return &(iforward_list::data_cast(p_node)->value);
00363       }
00364 
00365       const_pointer operator &() const
00366       {
00367         return &(iforward_list::data_cast(p_node)->value);
00368       }
00369 
00370       pointer operator ->()
00371       {
00372         return &(iforward_list::data_cast(p_node)->value);
00373       }
00374 
00375       const_pointer operator ->() const
00376       {
00377         return &(iforward_list::data_cast(p_node)->value);
00378       }
00379 
00380       friend bool operator == (const iterator& lhs, const iterator& rhs)
00381       {
00382         return lhs.p_node == rhs.p_node;
00383       }
00384 
00385       friend bool operator != (const iterator& lhs, const iterator& rhs)
00386       {
00387         return !(lhs == rhs);
00388       }
00389 
00390     private:
00391 
00392       node_t* p_node;
00393     };
00394 
00395     //*************************************************************************
00396     /// const_iterator
00397     //*************************************************************************
00398     class const_iterator : public std::iterator<std::forward_iterator_tag, const T>
00399     {
00400     public:
00401 
00402       friend class iforward_list;
00403 
00404       const_iterator()
00405         : p_node(std::nullptr)
00406       {
00407       }
00408 
00409       const_iterator(node_t& node)
00410         : p_node(&node)
00411       {
00412       }
00413 
00414       const_iterator(const node_t& node)
00415         : p_node(&node)
00416       {
00417       }
00418 
00419       const_iterator(const typename iforward_list::iterator& other)
00420         : p_node(other.p_node)
00421       {
00422       }
00423 
00424       const_iterator(const const_iterator& other)
00425         : p_node(other.p_node)
00426       {
00427       }
00428 
00429       const_iterator& operator ++()
00430       {
00431         p_node = p_node->next;
00432         return *this;
00433       }
00434 
00435       const_iterator operator ++(int)
00436       {
00437         const_iterator temp(*this);
00438         p_node = p_node->next;
00439         return temp;
00440       }
00441 
00442       const_iterator operator =(const const_iterator& other)
00443       {
00444         p_node = other.p_node;
00445         return *this;
00446       }
00447 
00448       const_reference operator *() const
00449       {
00450         return iforward_list::data_cast(p_node)->value;
00451       }
00452 
00453       const_pointer operator &() const
00454       {
00455         return &(iforward_list::data_cast(p_node)->value);
00456       }
00457 
00458       const_pointer operator ->() const
00459       {
00460         return &(iforward_list::data_cast(p_node)->value);
00461       }
00462 
00463       friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
00464       {
00465         return lhs.p_node == rhs.p_node;
00466       }
00467 
00468       friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
00469       {
00470         return !(lhs == rhs);
00471       }
00472 
00473     private:
00474 
00475       const node_t* p_node;
00476     };
00477 
00478     typedef typename std::iterator_traits<iterator>::difference_type difference_type;
00479 
00480     //*************************************************************************
00481     /// Gets the beginning of the forward_list.
00482     //*************************************************************************
00483     iterator begin()
00484     {
00485       return iterator(data_cast(get_head()));
00486     }
00487 
00488     //*************************************************************************
00489     /// Gets the beginning of the forward_list.
00490     //*************************************************************************
00491     const_iterator begin() const
00492     {
00493       return const_iterator(data_cast(get_head()));
00494     }
00495 
00496     //*************************************************************************
00497     /// Gets before the beginning of the forward_list.
00498     //*************************************************************************
00499     iterator before_begin()
00500     {
00501       return iterator(static_cast<data_node_t&>(start_node));
00502     }
00503 
00504     //*************************************************************************
00505     /// Gets before the beginning of the forward_list.
00506     //*************************************************************************
00507     const_iterator before_begin() const
00508     {
00509       return const_iterator(static_cast<const data_node_t&>(start_node));
00510     }
00511 
00512     //*************************************************************************
00513     /// Gets the beginning of the forward_list.
00514     //*************************************************************************
00515     const_iterator cbegin() const
00516     {
00517       return const_iterator(get_head());
00518     }
00519 
00520     //*************************************************************************
00521     /// Gets the end of the forward_list.
00522     //*************************************************************************
00523     iterator end()
00524     {
00525       return iterator();
00526     }
00527 
00528     //*************************************************************************
00529     /// Gets the end of the forward_list.
00530     //*************************************************************************
00531     const_iterator end() const
00532     {
00533       return const_iterator();
00534     }
00535 
00536     //*************************************************************************
00537     /// Gets the end of the forward_list.
00538     //*************************************************************************
00539     const_iterator cend() const
00540     {
00541       return const_iterator();
00542     }
00543 
00544     //*************************************************************************
00545     /// Clears the forward_list.
00546     //*************************************************************************
00547     void clear()
00548     {
00549       initialise();
00550     }
00551 
00552     //*************************************************************************
00553     /// Gets a reference to the first element.
00554     //*************************************************************************
00555     reference front()
00556     {
00557       return data_cast(get_head()).value;
00558     }
00559 
00560     //*************************************************************************
00561     /// Gets a const reference to the first element.
00562     //*************************************************************************
00563     const_reference front() const
00564     {
00565       return data_cast(get_head()).value;
00566     }
00567 
00568     //*************************************************************************
00569     /// Assigns a range of values to the forward_list.
00570     /// If asserts or exceptions are enabled throws etl::forward_list_full if the forward_list does not have enough free space.
00571     /// If ETL_THROW_EXCEPTIONS & ETL_DEBUG are defined throws forward_list_iterator if the iterators are reversed.
00572     //*************************************************************************
00573     template <typename TIterator>
00574     void assign(TIterator first, TIterator last)
00575     {
00576 #if defined(ETL_DEBUG)
00577       difference_type d = std::distance(first, last);
00578       ETL_ASSERT(d >= 0, ETL_ERROR(forward_list_iterator));
00579 #endif
00580 
00581       initialise();
00582 
00583       node_t* p_last_node = &start_node;
00584 
00585       // Add all of the elements.
00586       while (first != last)
00587       {
00588         ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
00589 
00590         data_node_t& data_node = allocate_data_node(*first++);
00591         join(p_last_node, &data_node);
00592         data_node.next = std::nullptr;
00593         p_last_node = &data_node;
00594       }
00595     }
00596 
00597     //*************************************************************************
00598     /// Assigns 'n' copies of a value to the forward_list.
00599     //*************************************************************************
00600     void assign(size_t n, parameter_t value)
00601     {
00602       ETL_ASSERT(n <= MAX_SIZE, ETL_ERROR(forward_list_full));
00603 
00604       initialise();
00605 
00606       node_t* p_last_node = &start_node;
00607 
00608       // Add all of the elements.
00609       while (size() < n)
00610       {
00611         data_node_t& data_node = allocate_data_node(value);
00612         join(p_last_node, &data_node);
00613         data_node.next = std::nullptr;
00614         p_last_node = &data_node;
00615       }
00616     }
00617 
00618     //*************************************************************************
00619     /// Adds a node to the front of the forward_list so a new value can be assigned to front().
00620     //*************************************************************************
00621     void push_front()
00622     {
00623       push_front(T());
00624     }
00625 
00626     //*************************************************************************
00627     /// Pushes a value to the front of the forward_list.
00628     //*************************************************************************
00629     void push_front(parameter_t value)
00630     {
00631 #if defined(ETL_CHECK_PUSH_POP)
00632       ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
00633 #endif
00634 
00635       data_node_t& data_node = allocate_data_node(value);
00636       insert_node_after(start_node, data_node);
00637     }
00638 
00639     //*************************************************************************
00640     /// Emplaces a value to the front of the list..
00641     //*************************************************************************
00642     template <typename T1>
00643     void emplace_front(const T1& value1)
00644     {
00645 #if defined(ETL_CHECK_PUSH_POP)
00646       ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
00647 #endif
00648       data_node_t* p_data_node = p_node_pool->allocate<data_node_t>();
00649       ::new (&(p_data_node->value)) T(value1);
00650       ++construct_count;
00651       insert_node_after(start_node, *p_data_node);
00652     }
00653 
00654     //*************************************************************************
00655     /// Emplaces a value to the front of the list..
00656     //*************************************************************************
00657     template <typename T1, typename T2>
00658     void emplace_front(const T1& value1, const T2& value2)
00659     {
00660 #if defined(ETL_CHECK_PUSH_POP)
00661       ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
00662 #endif
00663       data_node_t* p_data_node = p_node_pool->allocate<data_node_t>();
00664       ::new (&(p_data_node->value)) T(value1, value2);
00665       ++construct_count;
00666       insert_node_after(start_node, *p_data_node);
00667     }
00668 
00669     //*************************************************************************
00670     /// Emplaces a value to the front of the list..
00671     //*************************************************************************
00672     template <typename T1, typename T2, typename T3>
00673     void emplace_front(const T1& value1, const T2& value2, const T3& value3)
00674     {
00675 #if defined(ETL_CHECK_PUSH_POP)
00676       ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
00677 #endif
00678       data_node_t* p_data_node = p_node_pool->allocate<data_node_t>();
00679       ::new (&(p_data_node->value)) T(value1, value2, value3);
00680       ++construct_count;
00681       insert_node_after(start_node, *p_data_node);
00682     }
00683 
00684     //*************************************************************************
00685     /// Emplaces a value to the front of the list..
00686     //*************************************************************************
00687     template <typename T1, typename T2, typename T3, typename T4>
00688     void emplace_front(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
00689     {
00690 #if defined(ETL_CHECK_PUSH_POP)
00691       ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
00692 #endif
00693       data_node_t* p_data_node = p_node_pool->allocate<data_node_t>();
00694       ::new (&(p_data_node->value)) T(value1, value2, value3, value4);
00695       ++construct_count;
00696       insert_node_after(start_node, *p_data_node);
00697     }
00698 
00699     //*************************************************************************
00700     /// Removes a value from the front of the forward_list.
00701     //*************************************************************************
00702     void pop_front()
00703     {
00704 #if defined(ETL_CHECK_PUSH_POP)
00705       ETL_ASSERT(!empty(), ETL_ERROR(forward_list_empty));
00706 #endif
00707       remove_node_after(start_node);
00708     }
00709 
00710     //*************************************************************************
00711     /// Resizes the forward_list.
00712     //*************************************************************************
00713     void resize(size_t n)
00714     {
00715       resize(n, T());
00716     }
00717 
00718     //*************************************************************************
00719     /// Resizes the forward_list.
00720     /// If asserts or exceptions are enabled, will throw an etl::forward_list_full
00721     /// if <b>n</b> is larger than the maximum size.
00722     //*************************************************************************
00723     void resize(size_t n, T value)
00724     {
00725       ETL_ASSERT(n <= MAX_SIZE, ETL_ERROR(forward_list_full));
00726 
00727       size_t i = 0;
00728       iterator i_node = begin();
00729       iterator i_last_node;
00730 
00731       // Find where we're currently at.
00732       while ((i < n) && (i_node != end()))
00733       {
00734         ++i;
00735         i_last_node = i_node;
00736         ++i_node;
00737       }
00738 
00739       if (i_node != end())
00740       {
00741         // Reduce.
00742         erase_after(i_last_node, end());
00743       }
00744       else if (i_node == end())
00745       {
00746         // Increase.
00747         while (i < n)
00748         {
00749           i_last_node = insert_after(i_last_node, value);
00750           ++i;
00751         }
00752       }
00753     }
00754 
00755     //*************************************************************************
00756     /// Inserts a value to the forward_list after the specified position.
00757     //*************************************************************************
00758     iterator insert_after(iterator position, parameter_t value)
00759     {
00760       ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
00761 
00762       data_node_t& data_node = allocate_data_node(value);
00763       insert_node_after(*position.p_node, data_node);
00764 
00765       return iterator(data_node);
00766     }
00767 
00768     //*************************************************************************
00769     /// Emplaces a value to the forward_list after the specified position.
00770     //*************************************************************************
00771     template <typename T1>
00772     iterator emplace_after(iterator position, const T1& value1)
00773     {
00774       ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
00775 
00776       data_node_t* p_data_node = p_node_pool->allocate<data_node_t>();
00777       ::new (&(p_data_node->value)) T(value1);
00778       ++construct_count;
00779       insert_node_after(*position.p_node, *p_data_node);
00780 
00781       return iterator(*p_data_node);
00782     }
00783 
00784     //*************************************************************************
00785     /// Emplaces a value to the forward_list after the specified position.
00786     //*************************************************************************
00787     template <typename T1, typename T2>
00788     iterator emplace_after(iterator position, const T1& value1, const T2& value2)
00789     {
00790       ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
00791 
00792       data_node_t* p_data_node = p_node_pool->allocate<data_node_t>();
00793       ::new (&(p_data_node->value)) T(value1, value2);
00794       ++construct_count;
00795       insert_node_after(*position.p_node, *p_data_node);
00796 
00797       return iterator(*p_data_node);
00798     }
00799 
00800     //*************************************************************************
00801     /// Emplaces a value to the forward_list after the specified position.
00802     //*************************************************************************
00803     template <typename T1, typename T2, typename T3>
00804     iterator emplace_after(iterator position, const T1& value1, const T2& value2, const T3& value3)
00805     {
00806       ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
00807 
00808       data_node_t* p_data_node = p_node_pool->allocate<data_node_t>();
00809       ::new (&(p_data_node->value)) T(value1, value2, value3);
00810       ++construct_count;
00811       insert_node_after(*position.p_node, *p_data_node);
00812 
00813       return iterator(*p_data_node);
00814     }
00815 
00816     //*************************************************************************
00817     /// Emplaces a value to the forward_list after the specified position.
00818     //*************************************************************************
00819     template <typename T1, typename T2, typename T3, typename T4>
00820     iterator emplace_after(iterator position, const T1& value1, const T2& value2, const T3& value3, const T4& value4)
00821     {
00822       ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
00823 
00824       data_node_t* p_data_node = p_node_pool->allocate<data_node_t>();
00825       ::new (&(p_data_node->value)) T(value1, value2, value3, value4);
00826       ++construct_count;
00827       insert_node_after(*position.p_node, *p_data_node);
00828 
00829       return iterator(*p_data_node);
00830     }
00831 
00832     //*************************************************************************
00833     /// Inserts 'n' copies of a value to the forward_list after the specified position.
00834     //*************************************************************************
00835     void insert_after(iterator position, size_t n, parameter_t value)
00836     {
00837       ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
00838 
00839       for (size_t i = 0; !full() && (i < n); ++i)
00840       {
00841         // Set up the next free node.
00842         data_node_t& data_node = allocate_data_node(value);
00843         insert_node_after(*position.p_node, data_node);
00844       }
00845     }
00846 
00847     //*************************************************************************
00848     /// Inserts a range of values to the forward_list after the specified position.
00849     //*************************************************************************
00850     template <typename TIterator>
00851     void insert_after(iterator position, TIterator first, TIterator last)
00852     {
00853 #if defined(ETL_DEBUG)
00854       difference_type d = std::distance(first, last);
00855       ETL_ASSERT((d + size()) <= MAX_SIZE, ETL_ERROR(forward_list_full));
00856 #endif
00857 
00858       while (first != last)
00859       {
00860         // Set up the next free node.
00861         data_node_t& data_node = allocate_data_node(*first++);
00862         insert_node_after(*position.p_node, data_node);
00863         ++position;
00864       }
00865     }
00866 
00867     //*************************************************************************
00868     /// Erases the value at the specified position.
00869     //*************************************************************************
00870     iterator erase_after(iterator position)
00871     {
00872       iterator next(position);
00873       if (next != end())
00874       {
00875         ++next;
00876         if (next != end())
00877         {
00878           ++next;
00879           remove_node_after(*position.p_node);
00880         }
00881       }
00882 
00883       return next;
00884     }
00885 
00886     //*************************************************************************
00887     /// Erases a range of elements.
00888     //*************************************************************************
00889     iterator erase_after(iterator first, iterator last)
00890     {
00891       if (first != end() && (first != last))
00892       {
00893         node_t* p_first = first.p_node;
00894         node_t* p_last = last.p_node;
00895         node_t* p_next = p_first->next;
00896 
00897         // Join the ends.
00898         join(p_first, p_last);
00899 
00900         p_first = p_next;
00901 
00902         // Erase the ones in between.
00903         while (p_first != p_last)
00904         {
00905           p_next = p_first->next;                               // Remember the next node.
00906           destroy_data_node(static_cast<data_node_t&>(*p_first)); // Destroy the pool object.
00907           p_first = p_next;                                     // Move to the next node.
00908         }
00909 
00910         if (p_next == std::nullptr)
00911         {
00912           return end();
00913         }
00914         else
00915         {
00916           return iterator(*p_last);
00917         }
00918       }
00919       else
00920       {
00921         return end();
00922       }
00923     }
00924 
00925     //*************************************************************************
00926     /// Erases the value at the specified position.
00927     //*************************************************************************
00928     void move_after(const_iterator from_before, const_iterator to_before)
00929     {
00930       if (from_before == to_before) // Can't move to after yourself!
00931       {
00932         return;
00933       }
00934 
00935       node_t* p_from_before = const_cast<node_t*>(from_before.p_node); // We're not changing the value, just it's position.
00936       node_t* p_to_before = const_cast<node_t*>(to_before.p_node);   // We're not changing the value, just it's position.
00937 
00938       node_t* p_from = p_from_before->next;
00939 
00940       // Disconnect from the list.
00941       join(p_from_before, p_from->next);
00942 
00943       // Attach it to the new position.
00944       join(p_from, p_to_before->next);
00945       join(p_to_before, p_from);
00946     }
00947 
00948     //*************************************************************************
00949     /// Moves a range from one position to another within the list.
00950     /// Moves a range at position 'first_before'/'last' to the position before 'to_before'.
00951     //*************************************************************************
00952     void move_after(const_iterator first_before, const_iterator last, const_iterator to_before)
00953     {
00954       if ((first_before == to_before) || (last == to_before))
00955       {
00956         return; // Can't more to before yourself!
00957       }
00958 
00959 #if defined(ETL_DEBUG)
00960       // Check that we are not doing an illegal move!
00961       for (const_iterator item = first_before; item != last; ++item)
00962       {
00963         ETL_ASSERT(item != to_before, ETL_ERROR(forward_list_iterator));
00964       }
00965 #endif
00966 
00967       node_t* p_first_before = const_cast<node_t*>(first_before.p_node); // We're not changing the value, just it's position.
00968       node_t* p_last = const_cast<node_t*>(last.p_node);         // We're not changing the value, just it's position.
00969       node_t* p_to_before = const_cast<node_t*>(to_before.p_node);    // We're not changing the value, just it's position.
00970       node_t* p_first = p_first_before->next;
00971       node_t* p_final = p_first_before;
00972 
00973       // Find the last node that will be moved.
00974       while (p_final->next != p_last)
00975       {
00976         p_final = p_final->next;
00977       }
00978 
00979       // Disconnect from the list.
00980       join(p_first_before, p_final->next);
00981 
00982       // Attach it to the new position.
00983       join(p_final, p_to_before->next);
00984       join(p_to_before, p_first);
00985     }
00986 
00987     //*************************************************************************
00988     /// Removes all but the first element from every consecutive group of equal
00989     /// elements in the container.
00990     //*************************************************************************
00991     void unique()
00992     {
00993       unique(std::equal_to<T>());
00994     }
00995 
00996     //*************************************************************************
00997     /// Removes all but the one element from every consecutive group of equal
00998     /// elements in the container.
00999     //*************************************************************************
01000     template <typename TIsEqual>
01001     void unique(TIsEqual isEqual)
01002     {
01003       if (empty())
01004       {
01005         return;
01006       }
01007 
01008       node_t* last = &get_head();
01009       node_t* current = last->next;
01010 
01011       while (current != std::nullptr)
01012       {
01013         // Is this value the same as the last?
01014         if (isEqual(data_cast(current)->value, data_cast(last)->value))
01015         {
01016           remove_node_after(*last);
01017         }
01018         else
01019         {
01020           // Move on one.
01021           last = current;
01022         }
01023 
01024         current = last->next;
01025       }
01026     }
01027 
01028     //*************************************************************************
01029     /// Sort using in-place merge sort algorithm.
01030     /// Uses 'less-than operator as the predicate.
01031     //*************************************************************************
01032     void sort()
01033     {
01034       sort(std::less<T>());
01035     }
01036 
01037     //*************************************************************************
01038     /// Sort using in-place merge sort algorithm.
01039     /// Uses a supplied predicate function or functor.
01040     /// This is not my algorithm. I got it off the web somewhere.
01041     //*************************************************************************
01042     template <typename TCompare>
01043     void sort(TCompare compare)
01044     {
01045       iterator p_left;
01046       iterator p_right;
01047       iterator p_node;
01048       iterator p_head;
01049       iterator p_tail;
01050       int      list_size = 1;
01051       int      number_of_merges;
01052       int      left_size;
01053       int      right_size;
01054 
01055       if (is_trivial_list())
01056       {
01057         return;
01058       }
01059 
01060       while (true)
01061       {
01062         p_left = begin();
01063         p_head = before_begin();
01064         p_tail = before_begin();
01065 
01066         number_of_merges = 0;  // Count the number of merges we do in this pass.
01067 
01068         while (p_left != end())
01069         {
01070           ++number_of_merges;  // There exists a merge to be done.
01071           p_right = p_left;
01072           left_size = 0;
01073 
01074           // Step 'list_size' places along from left
01075           for (int i = 0; i < list_size; ++i)
01076           {
01077             ++left_size;
01078 
01079             ++p_right;
01080 
01081             if (p_right == end())
01082             {
01083               break;
01084             }
01085           }
01086 
01087           // If right hasn't fallen off end, we have two lists to merge.
01088           right_size = list_size;
01089 
01090           // Now we have two lists. Merge them.
01091           while (left_size > 0 || (right_size > 0 && p_right != end()))
01092           {
01093             // Decide whether the next node of merge comes from left or right.
01094             if (left_size == 0)
01095             {
01096               // Left is empty. The node must come from right.
01097               p_node = p_right;
01098               ++p_right;
01099               --right_size;
01100             }
01101             else if (right_size == 0 || p_right == end())
01102             {
01103               // Right is empty. The node must come from left.
01104               p_node = p_left;
01105               ++p_left;
01106               --left_size;
01107             }
01108             else if (!compare(*p_right, *p_left))
01109             {
01110               // First node of left is lower or same. The node must come from left.
01111               p_node = p_left;
01112               ++p_left;
01113               --left_size;
01114             }
01115             else
01116             {
01117               // First node of right is lower. The node must come from right.
01118               p_node = p_right;
01119               ++p_right;
01120               --right_size;
01121             }
01122 
01123             // Add the next node to the merged head.
01124             if (p_head == before_begin())
01125             {
01126               join(p_head.p_node, p_node.p_node);
01127               p_head = p_node;
01128               p_tail = p_node;
01129             }
01130             else
01131             {
01132               join(p_tail.p_node, p_node.p_node);
01133               p_tail = p_node;
01134             }
01135 
01136             p_tail.p_node->next = std::nullptr;
01137           }
01138 
01139           // Now left has stepped `list_size' places along, and right has too.
01140           p_left = p_right;
01141         }
01142 
01143         // If we have done only one merge, we're finished.
01144         if (number_of_merges <= 1)   // Allow for number_of_merges == 0, the empty head case
01145         {
01146           return;
01147         }
01148 
01149         // Otherwise repeat, merging lists twice the size
01150         list_size *= 2;
01151       }
01152     }
01153 
01154     //*************************************************************************
01155     // Removes the values specified.
01156     //*************************************************************************
01157     void remove(parameter_t value)
01158     {
01159       iterator i_item = begin();
01160       iterator i_last_item = before_begin();
01161 
01162       while (i_item != end())
01163       {
01164         if (*i_item == value)
01165         {
01166           i_item = erase_after(i_last_item);
01167         }
01168         else
01169         {
01170           ++i_item;
01171           ++i_last_item;
01172         }
01173       }
01174     }
01175 
01176     //*************************************************************************
01177     /// Removes according to a predicate.
01178     //*************************************************************************
01179     template <typename TPredicate>
01180     void remove_if(TPredicate predicate)
01181     {
01182       iterator i_item = begin();
01183       iterator i_last_item = before_begin();
01184 
01185       while (i_item != end())
01186       {
01187         if (predicate(*i_item))
01188         {
01189           i_item = erase_after(i_last_item);
01190         }
01191         else
01192         {
01193           ++i_item;
01194           ++i_last_item;
01195         }
01196       }
01197     }
01198 
01199     //*************************************************************************
01200     /// Assignment operator.
01201     //*************************************************************************
01202     iforward_list& operator = (const iforward_list& rhs)
01203     {
01204       if (&rhs != this)
01205       {
01206         assign(rhs.cbegin(), rhs.cend());
01207       }
01208 
01209       return *this;
01210     }
01211 
01212   protected:
01213 
01214     //*************************************************************************
01215     /// Constructor.
01216     //*************************************************************************
01217     iforward_list(etl::ipool& node_pool, size_t max_size_)
01218       : forward_list_base(node_pool, max_size_)
01219     {
01220     }
01221 
01222     //*************************************************************************
01223     /// Initialise the forward_list.
01224     //*************************************************************************
01225     void initialise()
01226     {
01227       if (!empty())
01228       {
01229         node_t* p_first = start_node.next;
01230         node_t* p_next;
01231 
01232         // Erase the ones in between.
01233         while (p_first != std::nullptr)
01234         {
01235           p_next = p_first->next;                                 // Remember the next node.
01236           destroy_data_node(static_cast<data_node_t&>(*p_first)); // Destroy the pool object.
01237           p_first = p_next;                                       // Move to the next node.
01238         }
01239       }
01240 
01241       start_node.next = std::nullptr;
01242     }
01243 
01244   private:
01245 
01246     //*************************************************************************
01247     /// Downcast a node_t* to a data_node_t*
01248     //*************************************************************************
01249     static data_node_t* data_cast(node_t* p_node)
01250     {
01251       return static_cast<data_node_t*>(p_node);
01252     }
01253 
01254     //*************************************************************************
01255     /// Downcast a node_t& to a data_node_t&
01256     //*************************************************************************
01257     static data_node_t& data_cast(node_t& node)
01258     {
01259       return static_cast<data_node_t&>(node);
01260     }
01261 
01262     //*************************************************************************
01263     /// Downcast a const node_t* to a const data_node_t*
01264     //*************************************************************************
01265     static const data_node_t* data_cast(const node_t* p_node)
01266     {
01267       return static_cast<const data_node_t*>(p_node);
01268     }
01269 
01270     //*************************************************************************
01271     /// Downcast a const node_t& to a const data_node_t&
01272     //*************************************************************************
01273     static const data_node_t& data_cast(const node_t& node)
01274     {
01275       return static_cast<const data_node_t&>(node);
01276     }
01277 
01278     //*************************************************************************
01279     /// Remove a node.
01280     //*************************************************************************
01281     void remove_node_after(node_t& node)
01282     {
01283       // The node to erase.
01284       node_t* p_node = node.next;
01285 
01286       if (p_node != std::nullptr)
01287       {
01288         // Disconnect the node from the forward_list.
01289         join(&node, p_node->next);
01290 
01291         // Destroy the pool object.
01292         destroy_data_node(static_cast<data_node_t&>(*p_node));
01293       }
01294     }
01295 
01296     //*************************************************************************
01297     /// Allocate a data_node_t.
01298     //*************************************************************************
01299     data_node_t& allocate_data_node(parameter_t value)
01300     {
01301       data_node_t* p_node = p_node_pool->allocate<data_node_t>();
01302       ::new (&(p_node->value)) T(value);
01303       ++construct_count;
01304 
01305       return *p_node;
01306     }
01307 
01308     //*************************************************************************
01309     /// Destroy a data_node_t.
01310     //*************************************************************************
01311     void destroy_data_node(data_node_t& node)
01312     {
01313       node.value.~T();
01314       p_node_pool->release(&node);
01315       --construct_count;
01316     }
01317 
01318     // Disable copy construction.
01319     iforward_list(const iforward_list&);
01320   };
01321 
01322   //*************************************************************************
01323   /// A templated forward_list implementation that uses a fixed size pool.
01324   ///\note 'merge' and 'splice_after' and are not supported.
01325   //*************************************************************************
01326   template <typename T, const size_t MAX_SIZE_>
01327   class forward_list : public etl::iforward_list<T>
01328   {
01329   public:
01330 
01331     static const size_t MAX_SIZE = MAX_SIZE_;
01332 
01333   public:
01334 
01335     typedef T        value_type;
01336     typedef T*       pointer;
01337     typedef const T* const_pointer;
01338     typedef T&       reference;
01339     typedef const T& const_reference;
01340     typedef size_t   size_type;
01341 
01342     //*************************************************************************
01343     /// Default constructor.
01344     //*************************************************************************
01345     forward_list()
01346       : etl::iforward_list<T>(node_pool, MAX_SIZE)
01347     {
01348       etl::iforward_list<T>::initialise();
01349     }
01350 
01351     //*************************************************************************
01352     /// Construct from size and value.
01353     //*************************************************************************
01354     explicit forward_list(size_t initial_size, typename etl::iforward_list<T>::parameter_t value = T())
01355       : etl::iforward_list<T>(node_pool, MAX_SIZE)
01356     {
01357       etl::iforward_list<T>::assign(initial_size, value);
01358     }
01359 
01360     //*************************************************************************
01361     /// Copy constructor.
01362     //*************************************************************************
01363     forward_list(const forward_list& other)
01364       : etl::iforward_list<T>(node_pool, MAX_SIZE)
01365     {
01366       etl::iforward_list<T>::assign(other.cbegin(), other.cend());
01367     }
01368 
01369     //*************************************************************************
01370     /// Construct from range.
01371     //*************************************************************************
01372     template <typename TIterator>
01373     forward_list(TIterator first, TIterator last)
01374       : etl::iforward_list<T>(node_pool, MAX_SIZE)
01375     {
01376       etl::iforward_list<T>::assign(first, last);
01377     }
01378 
01379     //*************************************************************************
01380     /// Destructor.
01381     //*************************************************************************
01382     ~forward_list()
01383     {
01384       etl::iforward_list<T>::initialise();
01385     }
01386 
01387     //*************************************************************************
01388     /// Assignment operator.
01389     //*************************************************************************
01390     forward_list& operator = (const forward_list& rhs)
01391     {
01392       if (&rhs != this)
01393       {
01394         etl::iforward_list<T>::assign(rhs.cbegin(), rhs.cend());
01395       }
01396 
01397       return *this;
01398     }
01399 
01400   private:
01401 
01402     /// The pool of nodes used in the list.
01403     etl::pool<typename etl::iforward_list<T>::data_node_t, MAX_SIZE> node_pool;
01404   };
01405 }
01406 
01407 //*************************************************************************
01408 /// Equal operator.
01409 ///\param lhs Reference to the first forward_list.
01410 ///\param rhs Reference to the second forward_list.
01411 ///\return <b>true</b> if the arrays are equal, otherwise <b>false</b>.
01412 //*************************************************************************
01413 template <typename T>
01414 bool operator ==(const etl::iforward_list<T>& lhs, const etl::iforward_list<T>& rhs)
01415 {
01416   return (lhs.size() == rhs.size()) &&
01417     std::equal(lhs.begin(), lhs.end(), rhs.begin());
01418 }
01419 
01420 //*************************************************************************
01421 /// Not equal operator.
01422 ///\param lhs Reference to the first forward_list.
01423 ///\param rhs Reference to the second forward_list.
01424 ///\return <b>true</b> if the arrays are not equal, otherwise <b>false</b>.
01425 //*************************************************************************
01426 template <typename T>
01427 bool operator !=(const etl::iforward_list<T>& lhs, const etl::iforward_list<T>& rhs)
01428 {
01429   return !(lhs == rhs);
01430 }
01431 
01432 //*************************************************************************
01433 /// Less than operator.
01434 ///\param lhs Reference to the first forward_list.
01435 ///\param rhs Reference to the second forward_list.
01436 ///\return <b>true</b> if the first forward_list is lexicographically less than the
01437 /// second, otherwise <b>false</b>.
01438 //*************************************************************************
01439 template <typename T>
01440 bool operator <(const etl::iforward_list<T>& lhs, const etl::iforward_list<T>& rhs)
01441 {
01442   return std::lexicographical_compare(lhs.begin(),
01443     lhs.end(),
01444     rhs.begin(),
01445     rhs.end());
01446 }
01447 
01448 //*************************************************************************
01449 /// Greater than operator.
01450 ///\param lhs Reference to the first forward_list.
01451 ///\param rhs Reference to the second forward_list.
01452 ///\return <b>true</b> if the first forward_list is lexicographically greater than the
01453 /// second, otherwise <b>false</b>.
01454 //*************************************************************************
01455 template <typename T>
01456 bool operator >(const etl::iforward_list<T>& lhs, const etl::iforward_list<T>& rhs)
01457 {
01458   return (rhs < lhs);
01459 }
01460 
01461 //*************************************************************************
01462 /// Less than or equal operator.
01463 ///\param lhs Reference to the first forward_list.
01464 ///\param rhs Reference to the second forward_list.
01465 ///\return <b>true</b> if the first forward_list is lexicographically less than or equal
01466 /// to the second, otherwise <b>false</b>.
01467 //*************************************************************************
01468 template <typename T>
01469 bool operator <=(const etl::iforward_list<T>& lhs, const etl::iforward_list<T>& rhs)
01470 {
01471   return !(lhs > rhs);
01472 }
01473 
01474 //*************************************************************************
01475 /// Greater than or equal operator.
01476 ///\param lhs Reference to the first forward_list.
01477 ///\param rhs Reference to the second forward_list.
01478 ///\return <b>true</b> if the first forward_list is lexicographically greater than or
01479 /// equal to the second, otherwise <b>false</b>.
01480 //*************************************************************************
01481 template <typename T>
01482 bool operator >=(const etl::iforward_list<T>& lhs, const etl::iforward_list<T>& rhs)
01483 {
01484   return !(lhs < rhs);
01485 }
01486 
01487 #ifdef ETL_COMPILER_MICROSOFT
01488 #define min(a,b) (((a) < (b)) ? (a) : (b))
01489 #endif
01490 
01491 #undef ETL_FILE
01492 
01493 #endif
01494