diff options
Diffstat (limited to 'boost/intrusive/circular_list_algorithms.hpp')
| -rw-r--r-- | boost/intrusive/circular_list_algorithms.hpp | 176 |
1 files changed, 88 insertions, 88 deletions
diff --git a/boost/intrusive/circular_list_algorithms.hpp b/boost/intrusive/circular_list_algorithms.hpp index c5de423b62..282f4741a1 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-2009 +// (C) Copyright Ion Gaztanaga 2006-2012 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -40,11 +40,11 @@ namespace intrusive { //! <b>Static functions</b>: //! //! <tt>static node_ptr get_previous(const_node_ptr n);</tt> -//! +//! //! <tt>static void set_previous(node_ptr n, node_ptr prev);</tt> -//! +//! //! <tt>static node_ptr get_next(const_node_ptr n);</tt> -//! +//! //! <tt>static void set_next(node_ptr n, node_ptr next);</tt> template<class NodeTraits> class circular_list_algorithms @@ -57,9 +57,9 @@ class circular_list_algorithms //! <b>Effects</b>: Constructs an non-used list element, so that //! inited(this_node) == true - //! - //! <b>Complexity</b>: Constant - //! + //! + //! <b>Complexity</b>: Constant + //! //! <b>Throws</b>: Nothing. static void init(const node_ptr &this_node) { @@ -69,20 +69,20 @@ class circular_list_algorithms //! <b>Effects</b>: Returns true is "this_node" is in a non-used state //! as if it was initialized by the "init" function. - //! - //! <b>Complexity</b>: Constant - //! + //! + //! <b>Complexity</b>: Constant + //! //! <b>Throws</b>: Nothing. - static bool inited(const const_node_ptr &this_node) + static bool inited(const const_node_ptr &this_node) { return !NodeTraits::get_next(this_node); } //! <b>Effects</b>: Constructs an empty list, making this_node the only //! node of the circular list: //! <tt>NodeTraits::get_next(this_node) == NodeTraits::get_previous(this_node) //! == this_node</tt>. - //! - //! <b>Complexity</b>: Constant - //! + //! + //! <b>Complexity</b>: Constant + //! //! <b>Throws</b>: Nothing. static void init_header(const node_ptr &this_node) { @@ -92,12 +92,12 @@ class circular_list_algorithms //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list. - //! + //! //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list: //! <tt>return NodeTraits::get_next(this_node) == this_node</tt> - //! - //! <b>Complexity</b>: Constant - //! + //! + //! <b>Complexity</b>: Constant + //! //! <b>Throws</b>: Nothing. static bool unique(const const_node_ptr &this_node) { @@ -106,14 +106,14 @@ class circular_list_algorithms } //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list. - //! + //! //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list //! is empty, returns 1. - //! - //! <b>Complexity</b>: Linear - //! + //! + //! <b>Complexity</b>: Linear + //! //! <b>Throws</b>: Nothing. - static std::size_t count(const const_node_ptr &this_node) + static std::size_t count(const const_node_ptr &this_node) { std::size_t result = 0; const_node_ptr p = this_node; @@ -125,11 +125,11 @@ class circular_list_algorithms } //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list. - //! + //! //! <b>Effects</b>: Unlinks the node from the circular list. - //! - //! <b>Complexity</b>: Constant - //! + //! + //! <b>Complexity</b>: Constant + //! //! <b>Throws</b>: Nothing. static node_ptr unlink(const node_ptr &this_node) { @@ -146,11 +146,11 @@ class circular_list_algorithms } //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range. - //! + //! //! <b>Effects</b>: Unlinks the node [b, e) from the circular list. - //! - //! <b>Complexity</b>: Constant - //! + //! + //! <b>Complexity</b>: Constant + //! //! <b>Throws</b>: Nothing. static void unlink(const node_ptr &b, const node_ptr &e) { @@ -162,11 +162,11 @@ class circular_list_algorithms } //! <b>Requires</b>: nxt_node must be a node of a circular list. - //! + //! //! <b>Effects</b>: Links this_node before nxt_node in the circular list. - //! - //! <b>Complexity</b>: Constant - //! + //! + //! <b>Complexity</b>: Constant + //! //! <b>Throws</b>: Nothing. static void link_before(const node_ptr &nxt_node, const node_ptr &this_node) { @@ -181,11 +181,11 @@ class circular_list_algorithms } //! <b>Requires</b>: prev_node must be a node of a circular list. - //! + //! //! <b>Effects</b>: Links this_node after prev_node in the circular list. - //! - //! <b>Complexity</b>: Constant - //! + //! + //! <b>Complexity</b>: Constant + //! //! <b>Throws</b>: Nothing. static void link_after(const node_ptr &prev_node, const node_ptr &this_node) { @@ -201,13 +201,13 @@ class circular_list_algorithms //! <b>Requires</b>: this_node and other_node must be nodes inserted //! in circular lists or be empty circular lists. - //! + //! //! <b>Effects</b>: Swaps the position of the nodes: this_node is inserted in //! other_nodes position in the second circular list and the other_node is inserted //! in this_node's position in the first circular list. - //! - //! <b>Complexity</b>: Constant - //! + //! + //! <b>Complexity</b>: Constant + //! //! <b>Throws</b>: Nothing. /* static void swap_nodes(const node_ptr &this_node, const node_ptr &other_node) @@ -248,22 +248,22 @@ class circular_list_algorithms */ //Watanabe version - private: - static void swap_prev(const node_ptr &this_node, const node_ptr &other_node) - { - node_ptr temp(NodeTraits::get_previous(this_node)); - NodeTraits::set_previous(this_node, NodeTraits::get_previous(other_node)); - NodeTraits::set_previous(other_node, temp); - } - static void swap_next(const node_ptr &this_node, const node_ptr &other_node) - { - node_ptr temp(NodeTraits::get_next(this_node)); - NodeTraits::set_next(this_node, NodeTraits::get_next(other_node)); - NodeTraits::set_next(other_node, temp); - } - - public: - static void swap_nodes(const node_ptr &this_node, const node_ptr &other_node) + private: + static void swap_prev(const node_ptr &this_node, const node_ptr &other_node) + { + node_ptr temp(NodeTraits::get_previous(this_node)); + NodeTraits::set_previous(this_node, NodeTraits::get_previous(other_node)); + NodeTraits::set_previous(other_node, temp); + } + static void swap_next(const node_ptr &this_node, const node_ptr &other_node) + { + node_ptr temp(NodeTraits::get_next(this_node)); + NodeTraits::set_next(this_node, NodeTraits::get_next(other_node)); + NodeTraits::set_next(other_node, temp); + } + + public: + static void swap_nodes(const node_ptr &this_node, const node_ptr &other_node) { if (other_node == this_node) return; @@ -276,15 +276,15 @@ class circular_list_algorithms init_header(other_node); } - node_ptr next_this(NodeTraits::get_next(this_node)); - node_ptr prev_this(NodeTraits::get_previous(this_node)); - node_ptr next_other(NodeTraits::get_next(other_node)); - node_ptr prev_other(NodeTraits::get_previous(other_node)); - //these first two swaps must happen before the other two - swap_prev(next_this, next_other); - swap_next(prev_this, prev_other); - swap_next(this_node, other_node); - swap_prev(this_node, other_node); + node_ptr next_this(NodeTraits::get_next(this_node)); + node_ptr prev_this(NodeTraits::get_previous(this_node)); + node_ptr next_other(NodeTraits::get_next(other_node)); + node_ptr prev_other(NodeTraits::get_previous(other_node)); + //these first two swaps must happen before the other two + swap_prev(next_this, next_other); + swap_next(prev_this, prev_other); + swap_next(this_node, other_node); + swap_prev(this_node, other_node); if(this_inited){ init(other_node); @@ -295,14 +295,14 @@ class circular_list_algorithms } //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range. - //! and p must be a node of a different circular list or may not be an iterator in + //! and p must be a node of a different circular list or may not be an iterator in // [b, e). - //! + //! //! <b>Effects</b>: Removes the nodes from [b, e) range from their circular list and inserts //! them before p in p's circular list. - //! - //! <b>Complexity</b>: Constant - //! + //! + //! <b>Complexity</b>: Constant + //! //! <b>Throws</b>: Nothing. static void transfer(const node_ptr &p, const node_ptr &b, const node_ptr &e) { @@ -321,13 +321,13 @@ class circular_list_algorithms //! <b>Requires</b>: i must a node of a circular list //! and p must be a node of a different circular list. - //! + //! //! <b>Effects</b>: Removes the node i from its circular list and inserts - //! it before p in p's circular list. + //! it before p in p's circular list. //! If p == i or p == NodeTraits::get_next(i), this function is a null operation. - //! - //! <b>Complexity</b>: Constant - //! + //! + //! <b>Complexity</b>: Constant + //! //! <b>Throws</b>: Nothing. static void transfer(const node_ptr &p, const node_ptr &i) { @@ -345,16 +345,16 @@ class circular_list_algorithms } } - //! <b>Effects</b>: Reverses the order of elements in the list. - //! + //! <b>Effects</b>: Reverses the order of elements in the list. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: This function is linear time. static void reverse(const node_ptr &p) { node_ptr f(NodeTraits::get_next(p)); node_ptr i(NodeTraits::get_next(f)), e(p); - + while(i != e) { node_ptr n = i; i = NodeTraits::get_next(i); @@ -364,9 +364,9 @@ class circular_list_algorithms } //! <b>Effects</b>: Moves the node p n positions towards the end of the list. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of moved positions. static void move_backwards(const node_ptr &p, std::size_t n) { @@ -384,9 +384,9 @@ class circular_list_algorithms } //! <b>Effects</b>: Moves the node p n positions towards the beginning of the list. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of moved positions. static void move_forward(const node_ptr &p, std::size_t n) { @@ -405,8 +405,8 @@ class circular_list_algorithms } }; -} //namespace intrusive -} //namespace boost +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> |