intrusive_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) 2016 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_INTRUSIVE_FORWARD_LIST__
00032 #define __ETL_INTRUSIVE_FORWARD_LIST__
00033 
00034 #include "platform.h "
00035 
00036 #ifdef ETL_COMPILER_MICROSOFT
00037 #undef min
00038 #endif
00039 
00040 #include <iterator>
00041 #include <algorithm>
00042 #include <functional>
00043 #include <stddef.h>
00044 
00045 #include "platform.h "
00046 #include "nullptr.h "
00047 #include "type_traits.h "
00048 #include "exception.h "
00049 #include "error_handler.h "
00050 #include "intrusive_links.h "
00051 #include "algorithm.h "
00052 
00053 #undef ETL_FILE
00054 #define ETL_FILE "20"
00055 
00056 namespace etl
00057 {
00058   //***************************************************************************
00059   /// Exception for the intrusive_forward_list.
00060   ///\ingroup intrusive_forward_list
00061   //***************************************************************************
00062   class intrusive_forward_list_exception : public exception
00063   {
00064   public:
00065 
00066     intrusive_forward_list_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
00067       : exception(reason_, file_name_, line_number_)
00068     {
00069     }
00070   };
00071 
00072   //***************************************************************************
00073   /// Empty exception for the intrusive_forward_list.
00074   ///\ingroup intrusive_forward_list
00075   //***************************************************************************
00076   class intrusive_forward_list_empty : public intrusive_forward_list_exception
00077   {
00078   public:
00079 
00080     intrusive_forward_list_empty(string_type file_name_, numeric_type line_number_)
00081       : intrusive_forward_list_exception(ETL_ERROR_TEXT("intrusive_forward_list:empty", ETL_FILE"A"), file_name_, line_number_)
00082     {
00083     }
00084   };
00085 
00086   //***************************************************************************
00087   /// Iterator exception for the intrusive_forward_list.
00088   ///\ingroup intrusive_forward_list
00089   //***************************************************************************
00090   class intrusive_forward_list_iterator_exception : public intrusive_forward_list_exception
00091   {
00092   public:
00093 
00094     intrusive_forward_list_iterator_exception(string_type file_name_, numeric_type line_number_)
00095       : intrusive_forward_list_exception(ETL_ERROR_TEXT("intrusive_forward_list:iterator", ETL_FILE"B"), file_name_, line_number_)
00096     {
00097     }
00098   };
00099 
00100   //***************************************************************************
00101   /// Index exception for the intrusive_forward_list.
00102   ///\ingroup intrusive_forward_list
00103   //***************************************************************************
00104   class intrusive_forward_list_index_exception : public intrusive_forward_list_exception
00105   {
00106   public:
00107 
00108     intrusive_forward_list_index_exception(string_type file_name_, numeric_type line_number_)
00109       : intrusive_forward_list_exception(ETL_ERROR_TEXT("intrusive_forward_list:bounds", ETL_FILE"C"), file_name_, line_number_)
00110     {
00111     }
00112   };
00113 
00114   //***************************************************************************
00115   /// Unsorted exception for the intrusive_forward_list.
00116   ///\ingroup intrusive_list
00117   //***************************************************************************
00118   class intrusive_forward_list_unsorted : public intrusive_forward_list_exception
00119   {
00120   public:
00121 
00122     intrusive_forward_list_unsorted(string_type file_name_, numeric_type line_number_)
00123       : intrusive_forward_list_exception(ETL_ERROR_TEXT("intrusive_forward_list:unsorted", ETL_FILE"D"), file_name_, line_number_)
00124     {
00125     }
00126   };
00127 
00128   //***************************************************************************
00129   /// Base for intrusive forward list.
00130   ///\ingroup intrusive_forward_list
00131   //***************************************************************************
00132   template <typename TLink>
00133   class intrusive_forward_list_base
00134   {
00135   public:
00136 
00137     // Node typedef.
00138     typedef TLink link_type;
00139 
00140     //*************************************************************************
00141     /// Clears the intrusive_forward_list.
00142     //*************************************************************************
00143     void clear()
00144     {
00145       initialise();
00146     }
00147 
00148     //*************************************************************************
00149     /// Assigns a range of values to the intrusive_forward_list.
00150     /// If ETL_THROW_EXCEPTIONS & ETL_DEBUG are defined throws forward_list_iterator if the iterators are reversed.
00151     //*************************************************************************
00152     template <typename TIterator>
00153     void assign(TIterator first, TIterator last)
00154     {
00155 #if defined(ETL_DEBUG)
00156       intmax_t d = std::distance(first, last);
00157       ETL_ASSERT(d >= 0, ETL_ERROR(intrusive_forward_list_iterator_exception));
00158 #endif
00159 
00160       initialise();
00161 
00162       link_type * p_last_link = &start_link;
00163 
00164       // Add all of the elements.
00165       while (first != last)
00166       {
00167         link_type & link = *first++;
00168         etl::link_splice<link_type>(p_last_link, link);
00169         p_last_link = &link;
00170         ++current_size;
00171       }
00172     }
00173 
00174     //*************************************************************************
00175     /// Pushes a value to the front of the intrusive_forward_list.
00176     //*************************************************************************
00177     void push_front(link_type & value)
00178     {
00179       insert_link_after(start_link, value);
00180     }
00181 
00182     //*************************************************************************
00183     /// Removes a value from the front of the intrusive_forward_list.
00184     //*************************************************************************
00185     void pop_front()
00186     {
00187 #if defined(ETL_CHECK_PUSH_POP)
00188       ETL_ASSERT(!empty(), ETL_ERROR(intrusive_forward_list_empty));
00189 #endif
00190       remove_link_after(start_link);
00191     }
00192 
00193     //*************************************************************************
00194     /// Reverses the intrusive_forward_list.
00195     //*************************************************************************
00196     void reverse()
00197     {
00198       if (is_trivial_list())
00199       {
00200         return;
00201       }
00202 
00203       link_type * first = std::nullptr;             // To keep first link
00204       link_type * second = start_link.etl_next; // To keep second link
00205       link_type * track = start_link.etl_next; // Track the list
00206 
00207       while (track != NULL)
00208       {
00209         track = track->etl_next;  // Track point to next link;
00210         second->etl_next = first; // Second link point to first
00211         first = second;          // Move first link to next
00212         second = track;           // Move second link to next
00213       }
00214 
00215       etl::link<link_type>(start_link, first);
00216     }
00217 
00218     //*************************************************************************
00219     /// Returns true if the list has no elements.
00220     //*************************************************************************
00221     bool empty() const
00222     {
00223       return start_link.etl_next == std::nullptr;
00224     }
00225 
00226     //*************************************************************************
00227     /// Returns the number of elements.
00228     //*************************************************************************
00229     size_t size() const
00230     {
00231       return current_size;
00232     }
00233 
00234   protected:
00235 
00236     link_type  start_link; ///< The link that acts as the intrusive_forward_list start.
00237 
00238     size_t current_size; ///< Counts the number of elements in the list.
00239 
00240     //*************************************************************************
00241     /// Is the intrusive_forward_list a trivial length?
00242     //*************************************************************************
00243     bool is_trivial_list() const
00244     {
00245       return (start_link.link_type::etl_next == std::nullptr) || (start_link.link_type::etl_next->etl_next == std::nullptr);;
00246     }
00247 
00248     //*************************************************************************
00249     /// Insert a link.
00250     //*************************************************************************
00251     void insert_link_after(link_type & position, link_type & link)
00252     {
00253       // Connect to the intrusive_forward_list.
00254       etl::link_splice<link_type>(position, link);
00255       ++current_size;
00256     }
00257 
00258     //*************************************************************************
00259     /// Remove a link.
00260     //*************************************************************************
00261     void remove_link_after(link_type & link)
00262     {
00263       link_type * p_next = link.etl_next;
00264 
00265       if (p_next != std::nullptr)
00266       {
00267         etl::unlink_after<link_type>(link);
00268         --current_size;
00269       }
00270     }
00271 
00272     //*************************************************************************
00273     /// Get the head link.
00274     //*************************************************************************
00275     link_type & get_head()
00276     {
00277       return *start_link.etl_next;
00278     }
00279 
00280     //*************************************************************************
00281     /// Get the head link.
00282     //*************************************************************************
00283     const link_type & get_head() const
00284     {
00285       return *start_link.etl_next;
00286     }
00287 
00288     //*************************************************************************
00289     /// Initialise the intrusive_forward_list.
00290     //*************************************************************************
00291     void initialise()
00292     {
00293       start_link.etl_next = std::nullptr;
00294       current_size = 0;
00295     }
00296   };
00297 
00298   //***************************************************************************
00299   /// An intrusive forward list.
00300   ///\ingroup intrusive_forward_list
00301   ///\note TLink must be a base of TValue.
00302   //***************************************************************************
00303   template <typename TValue, typename TLink = etl::forward_link<0> >
00304   class intrusive_forward_list : public etl::intrusive_forward_list_base<TLink>
00305   {
00306   public:
00307 
00308     // Node typedef.
00309     typedef typename etl::intrusive_forward_list_base<TLink>::link_type link_type;
00310 
00311     // STL style typedefs.
00312     typedef TValue            value_type;
00313     typedef value_type*       pointer;
00314     typedef const value_type* const_pointer;
00315     typedef value_type&       reference;
00316     typedef const value_type& const_reference;
00317     typedef size_t            size_type;
00318 
00319     typedef intrusive_forward_list<TValue, TLink> list_type;
00320 
00321     //*************************************************************************
00322     /// iterator.
00323     //*************************************************************************
00324     class iterator : public std::iterator<std::forward_iterator_tag, value_type>
00325     {
00326     public:
00327 
00328       friend class intrusive_forward_list;
00329 
00330       iterator()
00331         : p_value(std::nullptr)
00332       {
00333       }
00334 
00335       iterator(value_type& value)
00336         : p_value(&value)
00337       {
00338       }
00339 
00340       iterator(const iterator& other)
00341         : p_value(other.p_value)
00342       {
00343       }
00344 
00345       iterator& operator ++()
00346       {
00347         // Read the appropriate 'etl_next'.
00348         p_value = static_cast<value_type*>(p_value->link_type::etl_next);
00349         return *this;
00350       }
00351 
00352       iterator operator ++(int)
00353       {
00354         iterator temp(*this);
00355         // Read the appropriate 'etl_next'.
00356         p_value = static_cast<value_type*>(p_value->link_type::etl_next);
00357         return temp;
00358       }
00359 
00360       iterator operator =(const iterator& other)
00361       {
00362         p_value = other.p_value;
00363         return *this;
00364       }
00365 
00366       reference operator *()
00367       {
00368         return *p_value;
00369       }
00370 
00371       const_reference operator *() const
00372       {
00373         return *p_value;
00374       }
00375 
00376       pointer operator &()
00377       {
00378         return p_value;
00379       }
00380 
00381       const_pointer operator &() const
00382       {
00383         return p_value;
00384       }
00385 
00386       pointer operator ->()
00387       {
00388         return p_value;
00389       }
00390 
00391       const_pointer operator ->() const
00392       {
00393         return p_value;
00394       }
00395 
00396       friend bool operator == (const iterator& lhs, const iterator& rhs)
00397       {
00398         return lhs.p_value == rhs.p_value;
00399       }
00400 
00401       friend bool operator != (const iterator& lhs, const iterator& rhs)
00402       {
00403         return !(lhs == rhs);
00404       }
00405 
00406     private:
00407 
00408       value_type* p_value;
00409     };
00410 
00411     //*************************************************************************
00412     /// const_iterator
00413     //*************************************************************************
00414     class const_iterator : public std::iterator<std::forward_iterator_tag, const value_type>
00415     {
00416     public:
00417 
00418       friend class intrusive_forward_list;
00419 
00420       const_iterator()
00421         : p_value(std::nullptr)
00422       {
00423       }
00424 
00425       const_iterator(const value_type& value)
00426         : p_value(&value)
00427       {
00428       }
00429 
00430       const_iterator(const typename intrusive_forward_list::iterator& other)
00431         : p_value(other.p_value)
00432       {
00433       }
00434 
00435       const_iterator(const const_iterator& other)
00436         : p_value(other.p_value)
00437       {
00438       }
00439 
00440       const_iterator& operator ++()
00441       {
00442         // Read the appropriate 'etl_next'.
00443         p_value = static_cast<value_type*>(p_value->link_type::etl_next);
00444         return *this;
00445       }
00446 
00447       const_iterator operator ++(int)
00448       {
00449         const_iterator temp(*this);
00450         // Read the appropriate 'etl_next'.
00451         p_value = static_cast<value_type*>(p_value->link_type::etl_next);
00452         return temp;
00453       }
00454 
00455       const_iterator operator =(const const_iterator& other)
00456       {
00457         p_value = other.p_value;
00458         return *this;
00459       }
00460 
00461       const_reference operator *() const
00462       {
00463         return *p_value;
00464       }
00465 
00466       const_pointer operator &() const
00467       {
00468         return p_value;
00469       }
00470 
00471       const_pointer operator ->() const
00472       {
00473         return p_value;
00474       }
00475 
00476       friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
00477       {
00478         return lhs.p_value == rhs.p_value;
00479       }
00480 
00481       friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
00482       {
00483         return !(lhs == rhs);
00484       }
00485 
00486     private:
00487 
00488       const value_type* p_value;
00489     };
00490 
00491     typedef typename std::iterator_traits<iterator>::difference_type difference_type;
00492 
00493     //*************************************************************************
00494     /// Constructor.
00495     //*************************************************************************
00496     intrusive_forward_list()
00497     {
00498       this->initialise();
00499     }
00500 
00501     //*************************************************************************
00502     /// Destructor.
00503     //*************************************************************************
00504     ~intrusive_forward_list()
00505     {
00506       this->clear();
00507     }
00508 
00509     //*************************************************************************
00510     /// Constructor from range
00511     //*************************************************************************
00512     template <typename TIterator>
00513     intrusive_forward_list(TIterator first, TIterator last)
00514     {
00515       this->assign(first, last);
00516     }
00517 
00518     //*************************************************************************
00519     /// Gets the beginning of the intrusive_forward_list.
00520     //*************************************************************************
00521     iterator begin()
00522     {
00523       return iterator(static_cast<value_type&>(this->get_head()));
00524     }
00525 
00526     //*************************************************************************
00527     /// Gets the beginning of the intrusive_forward_list.
00528     //*************************************************************************
00529     const_iterator begin() const
00530     {
00531       return const_iterator(static_cast<const value_type&>(this->get_head()));
00532     }
00533 
00534     //*************************************************************************
00535     /// Gets before the beginning of the intrusive_forward_list.
00536     //*************************************************************************
00537     iterator before_begin()
00538     {
00539       return iterator(static_cast<value_type&>(this->start_link));
00540     }
00541 
00542     //*************************************************************************
00543     /// Gets before the beginning of the intrusive_forward_list.
00544     //*************************************************************************
00545     const_iterator before_begin() const
00546     {
00547       return const_iterator(static_cast<const value_type&>(this->start_link));
00548     }
00549 
00550     //*************************************************************************
00551     /// Gets the beginning of the intrusive_forward_list.
00552     //*************************************************************************
00553     const_iterator cbegin() const
00554     {
00555       return const_iterator(static_cast<const value_type&>(this->get_head()));
00556     }
00557 
00558     //*************************************************************************
00559     /// Gets the end of the intrusive_forward_list.
00560     //*************************************************************************
00561     iterator end()
00562     {
00563       return iterator();
00564     }
00565 
00566     //*************************************************************************
00567     /// Gets the end of the intrusive_forward_list.
00568     //*************************************************************************
00569     const_iterator end() const
00570     {
00571       return const_iterator();
00572     }
00573 
00574     //*************************************************************************
00575     /// Gets the end of the intrusive_forward_list.
00576     //*************************************************************************
00577     const_iterator cend() const
00578     {
00579       return const_iterator();
00580     }
00581 
00582     //*************************************************************************
00583     /// Gets a reference to the first element.
00584     //*************************************************************************
00585     reference front()
00586     {
00587       return static_cast<value_type&>(this->get_head());
00588     }
00589 
00590     //*************************************************************************
00591     /// Gets a const reference to the first element.
00592     //*************************************************************************
00593     const_reference front() const
00594     {
00595       return static_cast<const value_type&>(this->get_head());;
00596     }
00597 
00598     //*************************************************************************
00599     /// Inserts a value to the intrusive_forward_list after the specified position.
00600     //*************************************************************************
00601     iterator insert_after(iterator position, value_type& value)
00602     {
00603       this->insert_link_after(*position.p_value, value);
00604       return iterator(value);
00605     }
00606 
00607     //*************************************************************************
00608     /// Inserts a range of values to the intrusive_forward_list after the specified position.
00609     //*************************************************************************
00610     template <typename TIterator>
00611     void insert_after(iterator position, TIterator first, TIterator last)
00612     {
00613       while (first != last)
00614       {
00615         // Set up the next free link.
00616         this->insert_link_after(*position.p_value, *first++);
00617         ++position;
00618       }
00619     }
00620 
00621     //*************************************************************************
00622     /// Erases the value at the specified position.
00623     //*************************************************************************
00624     iterator erase_after(iterator position)
00625     {
00626       iterator next(position);
00627       if (next != end())
00628       {
00629         ++next;
00630         if (next != end())
00631         {
00632           ++next;
00633           this->remove_link_after(*position.p_value);
00634         }
00635       }
00636 
00637       return next;
00638     }
00639 
00640     //*************************************************************************
00641     /// Erases a range of elements.
00642     //*************************************************************************
00643     iterator erase_after(iterator first, iterator last)
00644     {
00645       if (first != end() && (first != last))
00646       {
00647         this->current_size -= std::distance(first, last) - 1;
00648 
00649         link_type * p_first = first.p_value;
00650         link_type * p_last = last.p_value;
00651         link_type * p_next = p_first->etl_next;
00652 
00653         // Join the ends.
00654         etl::link<link_type>(p_first, p_last);
00655 
00656         if (p_next == std::nullptr)
00657         {
00658           return end();
00659         }
00660         else
00661         {
00662           return last;
00663         }
00664       }
00665       else
00666       {
00667         return last;
00668       }
00669     }
00670 
00671     //*************************************************************************
00672     /// Removes all but the one element from every consecutive group of equal
00673     /// elements in the container.
00674     //*************************************************************************
00675     template <typename TIsEqual>
00676     void unique(TIsEqual isEqual)
00677     {
00678       if (this->empty())
00679       {
00680         return;
00681       }
00682 
00683       link_type * last    = &this->get_head();
00684       link_type * current = last->etl_next;
00685 
00686       while (current != std::nullptr)
00687       {
00688         // Is this value the same as the last?
00689         if (isEqual(*static_cast<value_type*>(current), *static_cast<value_type*>(last)))
00690         {
00691           this->remove_link_after(*last);
00692         }
00693         else
00694         {
00695           // Move on one.
00696           last = current;
00697         }
00698 
00699         current = last->etl_next;
00700       }
00701     }
00702 
00703     //*************************************************************************
00704     /// Sort using in-place merge sort algorithm.
00705     //*************************************************************************
00706     void sort()
00707     {
00708       sort(std::less<value_type>());
00709     }
00710 
00711     //*************************************************************************
00712     /// Sort using in-place merge sort algorithm.
00713     /// Uses a supplied predicate function or functor.
00714     /// This is not my algorithm. I got it off the web somewhere.
00715     //*************************************************************************
00716     template <typename TCompare>
00717     void sort(TCompare compare)
00718     {
00719       iterator i_left;
00720       iterator i_right;
00721       iterator i_link;
00722       iterator i_head;
00723       iterator i_tail;
00724       int      list_size = 1;
00725       int      number_of_merges;
00726       int      left_size;
00727       int      right_size;
00728 
00729       if (this->is_trivial_list())
00730       {
00731         return;
00732       }
00733 
00734       while (true)
00735       {
00736         i_left = begin();
00737         i_head = before_begin();
00738         i_tail = before_begin();
00739 
00740         number_of_merges = 0;  // Count the number of merges we do in this pass.
00741 
00742         while (i_left != end())
00743         {
00744           ++number_of_merges;  // There exists a merge to be done.
00745           i_right = i_left;
00746           left_size = 0;
00747 
00748           // Step 'list_size' places along from left
00749           for (int i = 0; i < list_size; ++i)
00750           {
00751             ++left_size;
00752 
00753             ++i_right;
00754 
00755             if (i_right == end())
00756             {
00757               break;
00758             }
00759           }
00760 
00761           // If right hasn't fallen off end, we have two lists to merge.
00762           right_size = list_size;
00763 
00764           // Now we have two lists. Merge them.
00765           while (left_size > 0 || (right_size > 0 && i_right != end()))
00766           {
00767             // Decide whether the next link of merge comes from left or right.
00768             if (left_size == 0)
00769             {
00770               // Left is empty. The link must come from right.
00771               i_link = i_right;
00772               ++i_right;
00773               --right_size;
00774             }
00775             else if (right_size == 0 || i_right == end())
00776             {
00777               // Right is empty. The link must come from left.
00778               i_link = i_left;
00779               ++i_left;
00780               --left_size;
00781             }
00782             else if (!compare(*i_right, *i_left))
00783             {
00784               // First link of left is lower or same. The link must come from left.
00785               i_link = i_left;
00786               ++i_left;
00787               --left_size;
00788             }
00789             else
00790             {
00791               // First link of right is lower. The link must come from right.
00792               i_link  = i_right;
00793               ++i_right;
00794               --right_size;
00795             }
00796 
00797             // Add the next link to the merged head.
00798             if (i_head == before_begin())
00799             {
00800               etl::link<link_type>(i_head.p_value, i_link.p_value);
00801               i_head = i_link;
00802               i_tail = i_link;
00803             }
00804             else
00805             {
00806               etl::link<link_type>(i_tail.p_value, i_link.p_value);
00807               i_tail = i_link;
00808             }
00809 
00810             i_tail.p_value->link_type::etl_next = std::nullptr;
00811           }
00812 
00813           // Now left has stepped `list_size' places along, and right has too.
00814           i_left = i_right;
00815         }
00816 
00817         // If we have done only one merge, we're finished.
00818         if (number_of_merges <= 1)   // Allow for number_of_merges == 0, the empty head case
00819         {
00820             return;
00821         }
00822 
00823         // Otherwise repeat, merging lists twice the size
00824         list_size *= 2;
00825       }
00826     }
00827 
00828     //*************************************************************************
00829     // Removes the values specified.
00830     //*************************************************************************
00831     void remove(const_reference value)
00832     {
00833       iterator i_item = begin();
00834       iterator i_last_item = before_begin();
00835 
00836       while (i_item != end())
00837       {
00838         if (*i_item == value)
00839         {
00840           i_item = erase_after(i_last_item);
00841         }
00842         else
00843         {
00844           ++i_item;
00845           ++i_last_item;
00846         }
00847       }
00848     }
00849 
00850     //*************************************************************************
00851     /// Removes according to a predicate.
00852     //*************************************************************************
00853     template <typename TPredicate>
00854     void remove_if(TPredicate predicate)
00855     {
00856       iterator i_item = begin();
00857       iterator i_last_item = before_begin();
00858 
00859       while (i_item != end())
00860       {
00861         if (predicate(*i_item))
00862         {
00863           i_item = erase_after(i_last_item);
00864         }
00865         else
00866         {
00867           ++i_item;
00868           ++i_last_item;
00869         }
00870       }
00871     }
00872 
00873     //*************************************************************************
00874     /// Splice another list into this one.
00875     //*************************************************************************
00876     void splice_after(iterator position, etl::intrusive_forward_list<TValue, TLink>& other)
00877     {
00878       // No point splicing to ourself!
00879       if (&other != this)
00880       {
00881         if (!other.empty())
00882         {
00883           link_type & first = other.get_head();
00884 
00885           if (&other != this)
00886           {
00887             this->current_size += other.size();
00888           }
00889 
00890           link_type & before = *position.p_value;
00891           link_type & after  = *position.p_value->link_type::etl_next;
00892 
00893           etl::link<link_type>(before, first);
00894 
00895           link_type * last = &before;
00896           while (last->link_type::etl_next != std::nullptr)
00897           {
00898             last = last->link_type::etl_next;
00899           }
00900 
00901           etl::link<link_type>(last, after);
00902 
00903           other.initialise();
00904         }
00905       }
00906     }
00907 
00908     //*************************************************************************
00909     /// Splice an element from another list into this one.
00910     //*************************************************************************
00911     void splice(iterator position, etl::intrusive_forward_list<TValue, TLink>& other, iterator isource)
00912     {
00913       link_type & before = *position.p_value;
00914 
00915       etl::unlink<link_type>(*isource.p_value);
00916       etl::link_splice<link_type>(before, *isource.p_value);
00917 
00918       if (&other != this)
00919       {
00920         ++this->current_size;
00921         --other.current_size;
00922       }
00923     }
00924 
00925     //*************************************************************************
00926     /// Splice a range of elements from another list into this one.
00927     //*************************************************************************
00928     void splice_after(iterator position, etl::intrusive_forward_list<TValue, TLink>& other, iterator begin_, iterator end_)
00929     {
00930       if (!other.empty())
00931       {
00932         if (&other != this)
00933         {
00934           size_t n = std::distance(begin_, end_) - 1;
00935           this->current_size += n;
00936           other.current_size -= n;
00937         }
00938 
00939         link_type * first = begin_.p_value;
00940         link_type * last  = first;
00941 
00942         while (last->link_type::etl_next != end_.p_value)
00943         {
00944           last = last->link_type::etl_next;
00945         }
00946 
00947         // Unlink from the source list.
00948         link_type * first_next = first->link_type::etl_next;
00949         etl::unlink_after(*first, *last);
00950 
00951         // Fix our links.
00952         link_type * before = position.p_value;
00953 
00954         etl::link_splice<link_type>(*before, *first_next, *last);
00955       }
00956     }
00957 
00958     //*************************************************************************
00959     /// Merge another list into this one. Both lists should be sorted.
00960     //*************************************************************************
00961     void merge(list_type& other)
00962     {
00963       merge(other, std::less<value_type>());
00964     }
00965 
00966     //*************************************************************************
00967     /// Merge another list into this one. Both lists should be sorted.
00968     //*************************************************************************
00969     template <typename TCompare>
00970     void merge(list_type& other, TCompare compare)
00971     {
00972       if (!other.empty())
00973       {
00974 #if defined(ETL_DEBUG)
00975         ETL_ASSERT(etl::is_sorted(other.begin(), other.end(), compare), ETL_ERROR(intrusive_forward_list_unsorted));
00976         ETL_ASSERT(etl::is_sorted(begin(), end(), compare), ETL_ERROR(intrusive_forward_list_unsorted));
00977 #endif
00978 
00979         value_type* other_begin    = static_cast<value_type*>(&other.get_head());
00980         value_type* other_terminal = std::nullptr;
00981 
00982         value_type* before      = static_cast<value_type*>(&this->start_link);
00983         value_type* before_next = get_next(before);
00984         value_type* terminal    = std::nullptr;
00985 
00986         while ((before->link_type::etl_next != terminal) && (other_begin != other_terminal))
00987         {
00988           // Find the place to insert.
00989           while ((before_next != terminal) && !(compare(*other_begin, *before_next)))
00990           {
00991             before      = before_next;
00992             before_next = get_next(before_next);
00993           }
00994 
00995           // Insert.
00996           if (before_next != terminal)
00997           {
00998             while ((other_begin != other_terminal) && (compare(*other_begin, *before_next)))
00999             {
01000               value_type* value = other_begin;
01001               other_begin = get_next(other_begin);
01002               etl::link_splice<link_type>(*before, *value);
01003               before = get_next(before);
01004             }
01005           }
01006         }
01007 
01008         // Any left over?
01009         if (before_next == terminal)
01010         {
01011           while (other_begin != other_terminal)
01012           {
01013             value_type* value = other_begin;
01014             other_begin = get_next(other_begin);
01015             etl::link_splice<link_type>(*before, *value);
01016             before = get_next(before);
01017           }
01018         }
01019 
01020         this->current_size += other.size();
01021 
01022         other.initialise();
01023       }
01024     }
01025 
01026   private:
01027 
01028     //*************************************************************************
01029     /// Get the next value.
01030     //*************************************************************************
01031     value_type* get_next(link_type* link) const
01032     {
01033       return static_cast<value_type*>(link->etl_next);
01034     }
01035 
01036     // Disabled.
01037     intrusive_forward_list(const intrusive_forward_list& other);
01038     intrusive_forward_list& operator = (const intrusive_forward_list& rhs);
01039   };
01040 }
01041 
01042 #ifdef ETL_COMPILER_MICROSOFT
01043 #define min(a,b) (((a) < (b)) ? (a) : (b))
01044 #endif
01045 
01046 #undef ETL_FILE
01047 
01048 #endif
01049