diff options
Diffstat (limited to 'boost/intrusive/circular_list_algorithms.hpp')
| -rw-r--r-- | boost/intrusive/circular_list_algorithms.hpp | 120 |
1 files changed, 107 insertions, 13 deletions
diff --git a/boost/intrusive/circular_list_algorithms.hpp b/boost/intrusive/circular_list_algorithms.hpp index 282f4741a1..1e888a1cae 100644 --- a/boost/intrusive/circular_list_algorithms.hpp +++ b/boost/intrusive/circular_list_algorithms.hpp @@ -1,7 +1,7 @@ ///////////////////////////////////////////////////////////////////////////// // // (C) Copyright Olaf Krzikalla 2004-2006. -// (C) Copyright Ion Gaztanaga 2006-2012 +// (C) Copyright Ion Gaztanaga 2006-2014 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -14,8 +14,14 @@ #ifndef BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP #define BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> +#include <boost/intrusive/detail/algo_type.hpp> +#include <boost/core/no_exceptions_support.hpp> #include <cstddef> namespace boost { @@ -63,8 +69,9 @@ class circular_list_algorithms //! <b>Throws</b>: Nothing. static void init(const node_ptr &this_node) { - NodeTraits::set_next(this_node, node_ptr()); - NodeTraits::set_previous(this_node, node_ptr()); + const node_ptr null_node((node_ptr())); + NodeTraits::set_next(this_node, null_node); + NodeTraits::set_previous(this_node, null_node); } //! <b>Effects</b>: Returns true is "this_node" is in a non-used state @@ -134,15 +141,10 @@ class circular_list_algorithms static node_ptr unlink(const node_ptr &this_node) { node_ptr next(NodeTraits::get_next(this_node)); - if(next){ - node_ptr prev(NodeTraits::get_previous(this_node)); - NodeTraits::set_next(prev, next); - NodeTraits::set_previous(next, prev); - return next; - } - else{ - return this_node; - } + node_ptr prev(NodeTraits::get_previous(this_node)); + NodeTraits::set_next(prev, next); + NodeTraits::set_previous(next, prev); + return next; } //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range. @@ -174,7 +176,7 @@ class circular_list_algorithms NodeTraits::set_previous(this_node, prev); NodeTraits::set_next(this_node, nxt_node); //nxt_node might be an alias for prev->next_ - //so use it before update it before NodeTraits::set_next(prev, ...) + //so use it before NodeTraits::set_next(prev, ...) //is called and the reference changes it's value NodeTraits::set_previous(nxt_node, this_node); NodeTraits::set_next(prev, this_node); @@ -403,8 +405,100 @@ class circular_list_algorithms } link_after(last, p); } + + //! <b>Requires</b>: f and l must be in a circular list. + //! + //! <b>Effects</b>: Returns the number of nodes in the range [f, l). + //! + //! <b>Complexity</b>: Linear + //! + //! <b>Throws</b>: Nothing. + static std::size_t distance(const const_node_ptr &f, const const_node_ptr &l) + { + const_node_ptr i(f); + std::size_t result = 0; + while(i != l){ + i = NodeTraits::get_next(i); + ++result; + } + return result; + } + + struct stable_partition_info + { + std::size_t num_1st_partition; + std::size_t num_2nd_partition; + node_ptr beg_2st_partition; + }; + + template<class Pred> + static void stable_partition(node_ptr beg, const node_ptr &end, Pred pred, stable_partition_info &info) + { + node_ptr bcur = node_traits::get_previous(beg); + node_ptr cur = beg; + node_ptr new_f = end; + + std::size_t num1 = 0, num2 = 0; + while(cur != end){ + if(pred(cur)){ + ++num1; + bcur = cur; + cur = node_traits::get_next(cur); + } + else{ + ++num2; + node_ptr last_to_remove = bcur; + new_f = cur; + bcur = cur; + cur = node_traits::get_next(cur); + BOOST_TRY{ + //Main loop + while(cur != end){ + if(pred(cur)){ //Might throw + ++num1; + //Process current node + node_traits::set_next (last_to_remove, cur); + node_traits::set_previous(cur, last_to_remove); + last_to_remove = cur; + node_ptr nxt = node_traits::get_next(cur); + node_traits::set_next (bcur, nxt); + node_traits::set_previous(nxt, bcur); + cur = nxt; + } + else{ + ++num2; + bcur = cur; + cur = node_traits::get_next(cur); + } + } + } + BOOST_CATCH(...){ + node_traits::set_next (last_to_remove, new_f); + node_traits::set_previous(new_f, last_to_remove); + throw; + } + BOOST_CATCH_END + node_traits::set_next(last_to_remove, new_f); + node_traits::set_previous(new_f, last_to_remove); + break; + } + } + info.num_1st_partition = num1; + info.num_2nd_partition = num2; + info.beg_2st_partition = new_f; + } }; +/// @cond + +template<class NodeTraits> +struct get_algo<CircularListAlgorithms, NodeTraits> +{ + typedef circular_list_algorithms<NodeTraits> type; +}; + +/// @endcond + } //namespace intrusive } //namespace boost |