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