boost/intrusive/list_algorithms.hpp

   1 /////////////////////////////////////////////////////////////////////////////\r
   2 //\r
   3 // (C) Copyright Olaf Krzikalla 2004-2006.\r
   4 // (C) Copyright Ion Gaztañaga  2006-2007\r
   5 //\r
   6 // Distributed under the Boost Software License, Version 1.0.\r
   7 //    (See accompanying file LICENSE_1_0.txt or copy at\r
   8 //          http://www.boost.org/LICENSE_1_0.txt)\r
   9 //\r
  10 // See http://www.boost.org/libs/intrusive for documentation.\r
  11 //\r
  12 /////////////////////////////////////////////////////////////////////////////\r
  13 \r
  14 #ifndef BOOST_INTRUSIVE_LIST_ALGORITHMS_HPP\r
  15 #define BOOST_INTRUSIVE_LIST_ALGORITHMS_HPP\r
  16 \r
  17 #include "detail/config_begin.hpp"\r
  18 #include <iterator>\r
  19 #include <boost/assert.hpp>\r
  20 #include "detail/pointer_type.hpp"\r
  21 #include "detail/pointer_to_other.hpp"\r
  22 #include <boost/get_pointer.hpp>\r
  23 #include <cstddef>\r
  24 \r
  25 namespace boost {\r
  26 namespace intrusive {\r
  27 \r
  28 //! list_algorithms provides basic algorithms to manipulate nodes\r
  29 //! forming a circular doubly linked list. An empty circular list is formed by a node\r
  30 //! whose pointers point to itself.\r
  31 //!\r
  32 //! list_algorithms is configured with a NodeTraits class, which encapsulates the\r
  33 //! information about the node to be manipulated. NodeTraits must support the\r
  34 //! following interface:\r
  35 //!\r
  36 //! <b>Typedefs</b>:\r
  37 //!\r
  38 //! <tt>node</tt>: The type of the node that forms the circular list\r
  39 //!\r
  40 //! <tt>node_ptr</tt>: A pointer to a node\r
  41 //!\r
  42 //! <tt>const_node_ptr</tt>: A pointer to a const node\r
  43 //!\r
  44 //! <b>Static functions</b>:\r
  45 //!\r
  46 //! <tt>static node_ptr get_previous(const_node_ptr n);</tt>\r
  47 //! \r
  48 //! <tt>static void set_previous(node_ptr n, node_ptr prev);</tt>\r
  49 //! \r
  50 //! <tt>static node_ptr get_next(const_node_ptr n);</tt>\r
  51 //! \r
  52 //! <tt>static void set_next(node_ptr n, node_ptr next);</tt>\r
  53 template<class NodeTraits>\r
  54 class list_algorithms\r
  55 {\r
  56    public:\r
  57    typedef typename NodeTraits::node_ptr        node_ptr;\r
  58    typedef typename NodeTraits::const_node_ptr const_node_ptr;\r
  59 \r
  60    //! <b>Effects</b>: Constructs an empty list, making this_node the only\r
  61    //!   node of the circular list:\r
  62    //!  <tt>NodeTraits::get_next(this_node) == NodeTraits::get_previous(this_node)\r
  63    //!  == this_node</tt>.\r
  64    //! \r
  65    //! <b>Complexity</b>: Constant \r
  66    //! \r
  67    //! <b>Throws</b>: Nothing.\r
  68    static void init(node_ptr this_node)\r
  69    {\r
  70       NodeTraits::set_next(this_node, this_node);\r
  71       NodeTraits::set_previous(this_node, this_node);\r
  72    }  \r
  73 \r
  74    //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.\r
  75    //! \r
  76    //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list:\r
  77    //!  <tt>return NodeTraits::get_next(this_node) == this_node</tt>\r
  78    //! \r
  79    //! <b>Complexity</b>: Constant \r
  80    //! \r
  81    //! <b>Throws</b>: Nothing.\r
  82    static bool unique(const_node_ptr this_node)  \r
  83    {  return NodeTraits::get_next(this_node) == this_node;  }\r
  84 \r
  85    //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.\r
  86    //! \r
  87    //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list\r
  88    //!  is empty, returns 1.\r
  89    //! \r
  90    //! <b>Complexity</b>: Constant \r
  91    //! \r
  92    //! <b>Throws</b>: Nothing.\r
  93    static std::size_t count(const_node_ptr this_node) \r
  94    {\r
  95       std::size_t result = 0;\r
  96       const_node_ptr p = this_node;\r
  97       do{\r
  98          p = NodeTraits::get_next(p);\r
  99          ++result;\r
 100       }while (p != this_node);\r
 101       return result;\r
 102    }\r
 103 \r
 104    //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.\r
 105    //! \r
 106    //! <b>Effects</b>: Unlinks the node from the circular list.\r
 107    //! \r
 108    //! <b>Complexity</b>: Constant \r
 109    //! \r
 110    //! <b>Throws</b>: Nothing.\r
 111    static node_ptr unlink(node_ptr this_node)\r
 112    {\r
 113       node_ptr next(NodeTraits::get_next(this_node));\r
 114       node_ptr prev(NodeTraits::get_previous(this_node));\r
 115       NodeTraits::set_next(prev, next);\r
 116       NodeTraits::set_previous(next, prev);\r
 117       return next;\r
 118    }\r
 119 \r
 120    //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.\r
 121    //! \r
 122    //! <b>Effects</b>: Unlinks the node [b, e) from the circular list.\r
 123    //! \r
 124    //! <b>Complexity</b>: Constant \r
 125    //! \r
 126    //! <b>Throws</b>: Nothing.\r
 127    static void unlink(node_ptr b, node_ptr e)\r
 128    {\r
 129       if (b != e) {\r
 130          node_ptr prev(NodeTraits::get_previous(b));\r
 131          node_ptr next(NodeTraits::get_next(e));\r
 132          NodeTraits::set_previous(next, prev);\r
 133          NodeTraits::set_next(prev, next);\r
 134       }\r
 135    }\r
 136 \r
 137    //! <b>Requires</b>: nxt_node must be a node of a circular list.\r
 138    //! \r
 139    //! <b>Effects</b>: Links this_node before nxt_node in the circular list.\r
 140    //! \r
 141    //! <b>Complexity</b>: Constant \r
 142    //! \r
 143    //! <b>Throws</b>: Nothing.\r
 144    static void link_before(node_ptr nxt_node, node_ptr this_node)\r
 145    {\r
 146       node_ptr prev(NodeTraits::get_previous(nxt_node));\r
 147       NodeTraits::set_previous(this_node, prev);\r
 148       NodeTraits::set_next(prev, this_node);\r
 149       NodeTraits::set_previous(nxt_node, this_node);\r
 150       NodeTraits::set_next(this_node, nxt_node);\r
 151    }\r
 152 \r
 153    //! <b>Requires</b>: prev_node must be a node of a circular list.\r
 154    //! \r
 155    //! <b>Effects</b>: Links this_node after prev_node in the circular list.\r
 156    //! \r
 157    //! <b>Complexity</b>: Constant \r
 158    //! \r
 159    //! <b>Throws</b>: Nothing.\r
 160    static void link_after(node_ptr prev_node, node_ptr this_node)\r
 161    {\r
 162       node_ptr next(NodeTraits::get_next(prev_node));\r
 163       NodeTraits::set_previous(this_node, prev_node);\r
 164       NodeTraits::set_next(this_node, next);\r
 165       NodeTraits::set_previous(next, this_node);\r
 166       NodeTraits::set_next(prev_node, this_node);\r
 167    }\r
 168 \r
 169    //! <b>Requires</b>: this_node and other_node must be nodes inserted\r
 170    //!  in circular lists or be empty circular lists.\r
 171    //! \r
 172    //! <b>Effects</b>: Swaps the position of the nodes: this_node is inserted in\r
 173    //!   other_nodes position in the second circular list and the other_node is inserted\r
 174    //!   in this_node's position in the first circular list.\r
 175    //! \r
 176    //! <b>Complexity</b>: Constant \r
 177    //! \r
 178    //! <b>Throws</b>: Nothing.\r
 179    static void swap_nodes(node_ptr this_node, node_ptr other_node)\r
 180    {\r
 181       if (other_node == this_node)\r
 182          return;\r
 183       bool empty1 = unique(this_node);\r
 184       bool empty2 = unique(other_node);\r
 185 \r
 186       node_ptr next_this(NodeTraits::get_next(this_node));\r
 187       node_ptr prev_this(NodeTraits::get_previous(this_node));\r
 188       node_ptr next_other(NodeTraits::get_next(other_node));\r
 189       node_ptr prev_other(NodeTraits::get_previous(other_node));\r
 190 \r
 191       //Do the swap\r
 192       NodeTraits::set_next(this_node, next_other);\r
 193       NodeTraits::set_next(other_node, next_this);\r
 194 \r
 195       NodeTraits::set_previous(this_node, prev_other);\r
 196       NodeTraits::set_previous(other_node, prev_this);\r
 197 \r
 198       if (empty2){\r
 199          init(this_node);\r
 200       }\r
 201       else{\r
 202          NodeTraits::set_next(prev_other, this_node);\r
 203          NodeTraits::set_previous(next_other, this_node);\r
 204       }\r
 205       if (empty1){\r
 206          init(other_node);\r
 207       }\r
 208       else{\r
 209          NodeTraits::set_next(prev_this, other_node);\r
 210          NodeTraits::set_previous(next_this, other_node);\r
 211       }\r
 212    }\r
 213 \r
 214    //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.\r
 215    //!   and p must be a node of a different circular list or may not be an iterator in \r
 216    //    [b, e).\r
 217    //! \r
 218    //! <b>Effects</b>: Removes the nodes from [b, e) range from their circular list and inserts\r
 219    //!   them before p in p's circular list.\r
 220    //! \r
 221    //! <b>Complexity</b>: Constant \r
 222    //! \r
 223    //! <b>Throws</b>: Nothing.\r
 224    static void transfer(node_ptr p, node_ptr b, node_ptr e)\r
 225    {\r
 226       if (b != e) {\r
 227          node_ptr prev_p(NodeTraits::get_previous(p));\r
 228          node_ptr prev_e(NodeTraits::get_previous(e));\r
 229          node_ptr prev_b(NodeTraits::get_previous(b));\r
 230          NodeTraits::set_next(prev_e, p);\r
 231          NodeTraits::set_previous(p, prev_e);\r
 232          NodeTraits::set_next(prev_b, e);\r
 233          NodeTraits::set_previous(e, prev_b);\r
 234          NodeTraits::set_next(prev_p, b);\r
 235          NodeTraits::set_previous(b, prev_p);\r
 236       }\r
 237    }\r
 238 \r
 239    //! <b>Requires</b>: i must a node of a circular list\r
 240    //!   and p must be a node of a different circular list.\r
 241    //! \r
 242    //! <b>Effects</b>: Removes the node i from its circular list and inserts\r
 243    //!   it before p in p's circular list. \r
 244    //!   If p == i or p == NodeTraits::get_next(i), this function is a null operation.\r
 245    //! \r
 246    //! <b>Complexity</b>: Constant \r
 247    //! \r
 248    //! <b>Throws</b>: Nothing.\r
 249    static void transfer(node_ptr p, node_ptr i)\r
 250    {\r
 251       node_ptr n(NodeTraits::get_next(i));\r
 252       if(n != p && i != p){\r
 253          node_ptr prev_p(NodeTraits::get_previous(p));\r
 254          node_ptr prev_i(NodeTraits::get_previous(i));\r
 255          NodeTraits::set_next(prev_p, i);\r
 256          NodeTraits::set_previous(i, prev_p);\r
 257          NodeTraits::set_next(i, p);\r
 258          NodeTraits::set_previous(p, i);\r
 259          NodeTraits::set_previous(n, prev_i);\r
 260          NodeTraits::set_next(prev_i, n);\r
 261 \r
 262       }\r
 263    }\r
 264 \r
 265    //! <b>Effects</b>: Reverses the order of elements in the list. \r
 266    //! \r
 267    //! <b>Throws</b>: Nothing.\r
 268    //! \r
 269    //! <b>Complexity</b>: This function is linear time.\r
 270    static void reverse(node_ptr p)\r
 271    {\r
 272       node_ptr f(NodeTraits::get_next(p));\r
 273       node_ptr i(NodeTraits::get_next(f)), e(p);\r
 274       \r
 275       while(i != e) {\r
 276          node_ptr n = i;\r
 277          i = NodeTraits::get_next(i);\r
 278          transfer(f, n, i);\r
 279          f = n;\r
 280       }\r
 281    }\r
 282 };\r
 283 \r
 284 } //namespace intrusive \r
 285 } //namespace boost \r
 286 \r
 287 #include "detail/config_end.hpp"\r
 288 \r
 289 #endif //BOOST_INTRUSIVE_LIST_ALGORITHMS_HPP\r