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