boost/intrusive/slist_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_SLIST_ALGORITHMS_HPP\r
  15 #define BOOST_INTRUSIVE_SLIST_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 //! slist_algorithms provides basic algorithms to manipulate nodes\r
  29 //! forming a circular singly linked list. An empty circular list is formed by a node\r
  30 //! whose pointer to the next node points to itself.\r
  31 //!\r
  32 //! slist_algorithms is configured with a NodeTraits class, which capsulates 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_next(const_node_ptr n);</tt>\r
  47 //! \r
  48 //! <tt>static void set_next(node_ptr n, node_ptr next);</tt>\r
  49 template<class NodeTraits>\r
  50 class slist_algorithms\r
  51 {\r
  52    public:\r
  53    typedef typename NodeTraits::node_ptr        node_ptr;\r
  54    typedef typename NodeTraits::const_node_ptr  const_node_ptr;\r
  55 \r
  56    //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.\r
  57    //! \r
  58    //! <b>Effects</b>: Returns the previous node of this_node in the circular list.\r
  59    //! \r
  60    //! <b>Complexity</b>: Linear to the number of elements in the circular list.\r
  61    //! \r
  62    //! <b>Throws</b>: Nothing.\r
  63    static node_ptr get_previous_node(node_ptr this_node)\r
  64    {\r
  65       node_ptr p = this_node;\r
  66       while (this_node != NodeTraits::get_next(p))\r
  67          p = NodeTraits::get_next(p);\r
  68       return p;\r
  69    }\r
  70 \r
  71    //! <b>Requires</b>: this_node and prev_init_node must be in the same circular list.\r
  72    //! \r
  73    //! <b>Effects</b>: Returns the previous node of this_node in the circular list starting.\r
  74    //!   the search from prev_init_node. The first node checked for equality\r
  75    //!   is NodeTraits::get_next(prev_init_node).\r
  76    //! \r
  77    //! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node.\r
  78    //! \r
  79    //! <b>Throws</b>: Nothing.\r
  80    static node_ptr get_previous_node(node_ptr prev_init_node, node_ptr this_node)\r
  81    {\r
  82       node_ptr p = prev_init_node;\r
  83       while (this_node != NodeTraits::get_next(p))\r
  84          p = NodeTraits::get_next(p);\r
  85       return p;\r
  86    }\r
  87 \r
  88    //! <b>Effects</b>: Constructs an empty list, making this_node the only\r
  89    //!   node of the circular list:\r
  90    //!  <tt>NodeTraits::get_next(this_node) == NodeTraits::get_previous(this_node)\r
  91    //!  == this_node</tt>.\r
  92    //! \r
  93    //! <b>Complexity</b>: Constant \r
  94    //! \r
  95    //! <b>Throws</b>: Nothing.\r
  96    static void init(node_ptr this_node)  \r
  97    {  NodeTraits::set_next(this_node, this_node);  }  \r
  98 \r
  99    //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.\r
 100    //! \r
 101    //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list:\r
 102    //!  <tt>return NodeTraits::get_next(this_node) == this_node</tt>\r
 103    //! \r
 104    //! <b>Complexity</b>: Constant \r
 105    //! \r
 106    //! <b>Throws</b>: Nothing.\r
 107    static bool unique(const_node_ptr this_node)  \r
 108    {  return NodeTraits::get_next(this_node) == this_node; }\r
 109 \r
 110    //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.\r
 111    //! \r
 112    //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list\r
 113    //!  is empty, returns 1.\r
 114    //! \r
 115    //! <b>Complexity</b>: Constant \r
 116    //! \r
 117    //! <b>Throws</b>: Nothing.\r
 118    static std::size_t count(const_node_ptr this_node) \r
 119    {\r
 120       std::size_t result = 0;\r
 121       const_node_ptr p = this_node;\r
 122       do{\r
 123          p = NodeTraits::get_next(p);\r
 124          ++result;\r
 125       } while (p != this_node);\r
 126       return result;\r
 127    }\r
 128 \r
 129    //! <b>Requires</b>: prev_node must be in a circular list or be an empty circular list.\r
 130    //! \r
 131    //! <b>Effects</b>: Unlinks the next node of prev_node from the circular list.\r
 132    //! \r
 133    //! <b>Complexity</b>: Constant \r
 134    //! \r
 135    //! <b>Throws</b>: Nothing.\r
 136    static void unlink_after(node_ptr prev_node)\r
 137    {\r
 138       node_ptr this_node(NodeTraits::get_next(prev_node));\r
 139       NodeTraits::set_next(prev_node, NodeTraits::get_next(this_node));\r
 140       NodeTraits::set_next(this_node, this_node);\r
 141    }\r
 142 \r
 143    //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.\r
 144    //! \r
 145    //! <b>Effects</b>: Unlinks the node from the circular list.\r
 146    //! \r
 147    //! <b>Complexity</b>: Linear to the number of elements in the circular list \r
 148    //! \r
 149    //! <b>Throws</b>: Nothing.\r
 150    static void unlink(node_ptr this_node)\r
 151    {  unlink_after(get_previous_node(this_node)); }\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       NodeTraits::set_next(this_node, NodeTraits::get_next(prev_node));\r
 163       NodeTraits::set_next(prev_node, this_node);\r
 164    }\r
 165 \r
 166    //! <b>Requires</b>: nxt_node must be a node of a circular list.\r
 167    //! \r
 168    //! <b>Effects</b>: Links this_node before nxt_node in the circular list.\r
 169    //! \r
 170    //! <b>Complexity</b>: Linear to the number of elements in the circular list. \r
 171    //! \r
 172    //! <b>Throws</b>: Nothing.\r
 173    static void link_before (node_ptr nxt_node, node_ptr this_node)\r
 174    {  link_after(get_previous_node(nxt_node), this_node);   }\r
 175 \r
 176    //! <b>Requires</b>: this_node and other_node must be nodes inserted\r
 177    //!  in circular lists or be empty circular lists.\r
 178    //! \r
 179    //! <b>Effects</b>: Swaps the position of the nodes: this_node is inserted in\r
 180    //!   other_nodes position in the second circular list and the other_node is inserted\r
 181    //!   in this_node's position in the first circular list.\r
 182    //! \r
 183    //! <b>Complexity</b>: Linear to number of elements of both lists \r
 184    //! \r
 185    //! <b>Throws</b>: Nothing.\r
 186    static void swap_nodes(node_ptr this_node, node_ptr other_node)\r
 187    {\r
 188       if (other_node == this_node)\r
 189          return;\r
 190       bool empty1 = unique(this_node);\r
 191       bool empty2 = unique(other_node);\r
 192       node_ptr prev_this (get_previous_node(this_node));\r
 193       node_ptr prev_other(get_previous_node(other_node));\r
 194 \r
 195       node_ptr this_next (NodeTraits::get_next(this_node));\r
 196       node_ptr other_next(NodeTraits::get_next(other_node));\r
 197       NodeTraits::set_next(this_node, other_next);\r
 198       NodeTraits::set_next(other_node, this_next);\r
 199       NodeTraits::set_next(empty1 ? other_node : prev_this, other_node);\r
 200       NodeTraits::set_next(empty2 ? this_node  : prev_other, this_node);\r
 201    }\r
 202 \r
 203    //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.\r
 204    //!   and p must be a node of a different circular list.\r
 205    //! \r
 206    //! <b>Effects</b>: Removes the nodes from [b, e) range from their circular list and inserts\r
 207    //!   them after p in p's circular list.\r
 208    //! \r
 209    //! <b>Complexity</b>: Constant \r
 210    //! \r
 211    //! <b>Throws</b>: Nothing.\r
 212    static void transfer_after(node_ptr p, node_ptr b, node_ptr e)\r
 213    {\r
 214       if (p != b && p != e) {\r
 215          node_ptr next_b = NodeTraits::get_next(b);\r
 216          node_ptr next_e = NodeTraits::get_next(e);\r
 217          node_ptr next_p = NodeTraits::get_next(p);\r
 218          NodeTraits::set_next(b, next_e);\r
 219          NodeTraits::set_next(e, next_p);\r
 220          NodeTraits::set_next(p, next_b);\r
 221       }\r
 222    }\r
 223 \r
 224    //! <b>Effects</b>: Reverses the order of elements in the list. \r
 225    //! \r
 226    //! <b>Throws</b>: Nothing.\r
 227    //! \r
 228    //! <b>Complexity</b>: This function is linear to the contained elements.\r
 229    static void reverse(node_ptr p)\r
 230    {\r
 231       node_ptr i = NodeTraits::get_next(p), e(p); \r
 232       for (;;) {\r
 233          node_ptr nxt(NodeTraits::get_next(i));\r
 234          if (nxt == e)\r
 235             break;\r
 236          transfer_after(e, i, nxt);\r
 237       }\r
 238    }\r
 239 };\r
 240 \r
 241 } //namespace intrusive \r
 242 } //namespace boost \r
 243 \r
 244 #include "detail/config_end.hpp"\r
 245 \r
 246 #endif //BOOST_INTRUSIVE_SLIST_ALGORITHMS_HPP\r