boost/intrusive/circular_list_algorithms.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Olaf Krzikalla 2004-2006.
   4 // (C) Copyright Ion Gaztanaga  2006-2008
   5 //
   6 // Distributed under the Boost Software License, Version 1.0.
   7 //    (See accompanying file LICENSE_1_0.txt or copy at
   8 //          http://www.boost.org/LICENSE_1_0.txt)
   9 //
  10 // See http://www.boost.org/libs/intrusive for documentation.
  11 //
  12 /////////////////////////////////////////////////////////////////////////////
  13
  14 #ifndef BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP
  15 #define BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP
  16
  17 #include <boost/intrusive/detail/config_begin.hpp>
  18 #include <boost/intrusive/intrusive_fwd.hpp>
  19 #include <cstddef>
  20
  21 namespace boost {
  22 namespace intrusive {
  23
  24 //! circular_list_algorithms provides basic algorithms to manipulate nodes
  25 //! forming a circular doubly linked list. An empty circular list is formed by a node
  26 //! whose pointers point to itself.
  27 //!
  28 //! circular_list_algorithms is configured with a NodeTraits class, which encapsulates the
  29 //! information about the node to be manipulated. NodeTraits must support the
  30 //! following interface:
  31 //!
  32 //! <b>Typedefs</b>:
  33 //!
  34 //! <tt>node</tt>: The type of the node that forms the circular list
  35 //!
  36 //! <tt>node_ptr</tt>: A pointer to a node
  37 //!
  38 //! <tt>const_node_ptr</tt>: A pointer to a const node
  39 //!
  40 //! <b>Static functions</b>:
  41 //!
  42 //! <tt>static node_ptr get_previous(const_node_ptr n);</tt>
  43 //!
  44 //! <tt>static void set_previous(node_ptr n, node_ptr prev);</tt>
  45 //!
  46 //! <tt>static node_ptr get_next(const_node_ptr n);</tt>
  47 //!
  48 //! <tt>static void set_next(node_ptr n, node_ptr next);</tt>
  49 template<class NodeTraits>
  50 class circular_list_algorithms
  51 {
  52    public:
  53    typedef typename NodeTraits::node            node;
  54    typedef typename NodeTraits::node_ptr        node_ptr;
  55    typedef typename NodeTraits::const_node_ptr  const_node_ptr;
  56    typedef NodeTraits                           node_traits;
  57
  58    //! <b>Effects</b>: Constructs an non-used list element, so that
  59    //! inited(this_node) == true
  60    //!
  61    //! <b>Complexity</b>: Constant
  62    //!
  63    //! <b>Throws</b>: Nothing.
  64    static void init(node_ptr this_node)
  65    {
  66       NodeTraits::set_next(this_node, node_ptr(0));
  67       NodeTraits::set_previous(this_node, node_ptr(0));
  68    }
  69
  70    //! <b>Effects</b>: Returns true is "this_node" is in a non-used state
  71    //! as if it was initialized by the "init" function.
  72    //!
  73    //! <b>Complexity</b>: Constant
  74    //!
  75    //! <b>Throws</b>: Nothing.
  76    static bool inited(const_node_ptr this_node)
  77    {  return !NodeTraits::get_next(this_node); }
  78
  79    //! <b>Effects</b>: Constructs an empty list, making this_node the only
  80    //!   node of the circular list:
  81    //!  <tt>NodeTraits::get_next(this_node) == NodeTraits::get_previous(this_node)
  82    //!  == this_node</tt>.
  83    //!
  84    //! <b>Complexity</b>: Constant
  85    //!
  86    //! <b>Throws</b>: Nothing.
  87    static void init_header(node_ptr this_node)
  88    {
  89       NodeTraits::set_next(this_node, this_node);
  90       NodeTraits::set_previous(this_node, this_node);
  91    }
  92
  93
  94    //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
  95    //!
  96    //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list:
  97    //!  <tt>return NodeTraits::get_next(this_node) == this_node</tt>
  98    //!
  99    //! <b>Complexity</b>: Constant
 100    //!
 101    //! <b>Throws</b>: Nothing.
 102    static bool unique(const_node_ptr this_node)
 103    {
 104       node_ptr next = NodeTraits::get_next(this_node);
 105       return !next || next == this_node;
 106    }
 107
 108    //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
 109    //!
 110    //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list
 111    //!  is empty, returns 1.
 112    //!
 113    //! <b>Complexity</b>: Constant
 114    //!
 115    //! <b>Throws</b>: Nothing.
 116    static std::size_t count(const_node_ptr this_node)
 117    {
 118       std::size_t result = 0;
 119       const_node_ptr p = this_node;
 120       do{
 121          p = NodeTraits::get_next(p);
 122          ++result;
 123       }while (p != this_node);
 124       return result;
 125    }
 126
 127    //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
 128    //!
 129    //! <b>Effects</b>: Unlinks the node from the circular list.
 130    //!
 131    //! <b>Complexity</b>: Constant
 132    //!
 133    //! <b>Throws</b>: Nothing.
 134    static node_ptr unlink(node_ptr this_node)
 135    {
 136       if(NodeTraits::get_next(this_node)){
 137          node_ptr next(NodeTraits::get_next(this_node));
 138          node_ptr prev(NodeTraits::get_previous(this_node));
 139          NodeTraits::set_next(prev, next);
 140          NodeTraits::set_previous(next, prev);
 141          return next;
 142       }
 143       else{
 144          return this_node;
 145       }
 146    }
 147
 148    //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.
 149    //!
 150    //! <b>Effects</b>: Unlinks the node [b, e) from the circular list.
 151    //!
 152    //! <b>Complexity</b>: Constant
 153    //!
 154    //! <b>Throws</b>: Nothing.
 155    static void unlink(node_ptr b, node_ptr e)
 156    {
 157       if (b != e) {
 158          node_ptr prevb(NodeTraits::get_previous(b));
 159          NodeTraits::set_previous(e, prevb);
 160          NodeTraits::set_next(prevb, e);
 161       }
 162    }
 163
 164    //! <b>Requires</b>: nxt_node must be a node of a circular list.
 165    //!
 166    //! <b>Effects</b>: Links this_node before nxt_node in the circular list.
 167    //!
 168    //! <b>Complexity</b>: Constant
 169    //!
 170    //! <b>Throws</b>: Nothing.
 171    static void link_before(node_ptr nxt_node, node_ptr this_node)
 172    {
 173       node_ptr prev(NodeTraits::get_previous(nxt_node));
 174       NodeTraits::set_previous(this_node, prev);
 175       NodeTraits::set_next(prev, this_node);
 176       NodeTraits::set_previous(nxt_node, this_node);
 177       NodeTraits::set_next(this_node, nxt_node);
 178    }
 179
 180    //! <b>Requires</b>: prev_node must be a node of a circular list.
 181    //!
 182    //! <b>Effects</b>: Links this_node after prev_node in the circular list.
 183    //!
 184    //! <b>Complexity</b>: Constant
 185    //!
 186    //! <b>Throws</b>: Nothing.
 187    static void link_after(node_ptr prev_node, node_ptr this_node)
 188    {
 189       node_ptr next(NodeTraits::get_next(prev_node));
 190       NodeTraits::set_previous(this_node, prev_node);
 191       NodeTraits::set_next(this_node, next);
 192       NodeTraits::set_previous(next, this_node);
 193       NodeTraits::set_next(prev_node, this_node);
 194    }
 195
 196    //! <b>Requires</b>: this_node and other_node must be nodes inserted
 197    //!  in circular lists or be empty circular lists.
 198    //!
 199    //! <b>Effects</b>: Swaps the position of the nodes: this_node is inserted in
 200    //!   other_nodes position in the second circular list and the other_node is inserted
 201    //!   in this_node's position in the first circular list.
 202    //!
 203    //! <b>Complexity</b>: Constant
 204    //!
 205    //! <b>Throws</b>: Nothing.
 206 /*
 207    static void swap_nodes(node_ptr this_node, node_ptr other_node)
 208    {
 209
 210       if (other_node == this_node)
 211          return;
 212       bool empty1 = unique(this_node);
 213       bool empty2 = unique(other_node);
 214
 215       node_ptr next_this(NodeTraits::get_next(this_node));
 216       node_ptr prev_this(NodeTraits::get_previous(this_node));
 217       node_ptr next_other(NodeTraits::get_next(other_node));
 218       node_ptr prev_other(NodeTraits::get_previous(other_node));
 219
 220       //Do the swap
 221       NodeTraits::set_next(this_node, next_other);
 222       NodeTraits::set_next(other_node, next_this);
 223
 224       NodeTraits::set_previous(this_node, prev_other);
 225       NodeTraits::set_previous(other_node, prev_this);
 226
 227       if (empty2){
 228          init(this_node);
 229       }
 230       else{
 231          NodeTraits::set_next(prev_other, this_node);
 232          NodeTraits::set_previous(next_other, this_node);
 233       }
 234       if (empty1){
 235          init(other_node);
 236       }
 237       else{
 238          NodeTraits::set_next(prev_this, other_node);
 239          NodeTraits::set_previous(next_this, other_node);
 240       }
 241    }
 242 */
 243
 244    //Watanabe version
 245    private:
 246    static void swap_prev(node_ptr this_node, node_ptr other_node)
 247    {
 248       node_ptr temp(NodeTraits::get_previous(this_node));
 249       NodeTraits::set_previous(this_node, NodeTraits::get_previous(other_node));
 250       NodeTraits::set_previous(other_node, temp);
 251    }
 252    static void swap_next(node_ptr this_node, node_ptr other_node)
 253    {
 254       node_ptr temp(NodeTraits::get_next(this_node));
 255       NodeTraits::set_next(this_node, NodeTraits::get_next(other_node));
 256       NodeTraits::set_next(other_node, temp);
 257    }
 258
 259    public:
 260    static void swap_nodes(node_ptr this_node, node_ptr other_node)
 261    {
 262       if (other_node == this_node)
 263          return;
 264       bool this_inited  = inited(this_node);
 265       bool other_inited = inited(other_node);
 266       if(this_inited){
 267          init_header(this_node);
 268       }
 269       if(other_inited){
 270          init_header(other_node);
 271       }
 272
 273       node_ptr next_this(NodeTraits::get_next(this_node));
 274       node_ptr prev_this(NodeTraits::get_previous(this_node));
 275       node_ptr next_other(NodeTraits::get_next(other_node));
 276       node_ptr prev_other(NodeTraits::get_previous(other_node));
 277       //these first two swaps must happen before the other two
 278       swap_prev(next_this, next_other);
 279       swap_next(prev_this, prev_other);
 280       swap_next(this_node, other_node);
 281       swap_prev(this_node, other_node);
 282
 283       if(this_inited){
 284          init(other_node);
 285       }
 286       if(other_inited){
 287          init(this_node);
 288       }
 289    }
 290
 291    //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.
 292    //!   and p must be a node of a different circular list or may not be an iterator in
 293    //    [b, e).
 294    //!
 295    //! <b>Effects</b>: Removes the nodes from [b, e) range from their circular list and inserts
 296    //!   them before p in p's circular list.
 297    //!
 298    //! <b>Complexity</b>: Constant
 299    //!
 300    //! <b>Throws</b>: Nothing.
 301    static void transfer(node_ptr p, node_ptr b, node_ptr e)
 302    {
 303       if (b != e) {
 304          node_ptr prev_p(NodeTraits::get_previous(p));
 305          node_ptr prev_b(NodeTraits::get_previous(b));
 306          node_ptr prev_e(NodeTraits::get_previous(e));
 307          NodeTraits::set_next(prev_e, p);
 308          NodeTraits::set_previous(p, prev_e);
 309          NodeTraits::set_next(prev_b, e);
 310          NodeTraits::set_previous(e, prev_b);
 311          NodeTraits::set_next(prev_p, b);
 312          NodeTraits::set_previous(b, prev_p);
 313       }
 314    }
 315
 316    //! <b>Requires</b>: i must a node of a circular list
 317    //!   and p must be a node of a different circular list.
 318    //!
 319    //! <b>Effects</b>: Removes the node i from its circular list and inserts
 320    //!   it before p in p's circular list.
 321    //!   If p == i or p == NodeTraits::get_next(i), this function is a null operation.
 322    //!
 323    //! <b>Complexity</b>: Constant
 324    //!
 325    //! <b>Throws</b>: Nothing.
 326    static void transfer(node_ptr p, node_ptr i)
 327    {
 328       node_ptr n(NodeTraits::get_next(i));
 329       if(n != p && i != p){
 330          node_ptr prev_p(NodeTraits::get_previous(p));
 331          node_ptr prev_i(NodeTraits::get_previous(i));
 332          NodeTraits::set_next(prev_p, i);
 333          NodeTraits::set_previous(i, prev_p);
 334          NodeTraits::set_next(i, p);
 335          NodeTraits::set_previous(p, i);
 336          NodeTraits::set_previous(n, prev_i);
 337          NodeTraits::set_next(prev_i, n);
 338
 339       }
 340    }
 341
 342    //! <b>Effects</b>: Reverses the order of elements in the list.
 343    //!
 344    //! <b>Throws</b>: Nothing.
 345    //!
 346    //! <b>Complexity</b>: This function is linear time.
 347    static void reverse(node_ptr p)
 348    {
 349       node_ptr f(NodeTraits::get_next(p));
 350       node_ptr i(NodeTraits::get_next(f)), e(p);
 351
 352       while(i != e) {
 353          node_ptr n = i;
 354          i = NodeTraits::get_next(i);
 355          transfer(f, n, i);
 356          f = n;
 357       }
 358    }
 359
 360    //! <b>Effects</b>: Moves the node p n positions towards the end of the list.
 361    //!
 362    //! <b>Throws</b>: Nothing.
 363    //!
 364    //! <b>Complexity</b>: Linear to the number of moved positions.
 365    static void move_backwards(node_ptr p, std::size_t n)
 366    {
 367       //Null shift, nothing to do
 368       if(!n) return;
 369       node_ptr first  = NodeTraits::get_next(p);
 370       //size() == 0 or 1, nothing to do
 371       if(first == NodeTraits::get_previous(p)) return;
 372       unlink(p);
 373       //Now get the new first node
 374       while(n--){
 375          first = NodeTraits::get_next(first);
 376       }
 377       link_before(first, p);
 378    }
 379
 380    //! <b>Effects</b>: Moves the node p n positions towards the beginning of the list.
 381    //!
 382    //! <b>Throws</b>: Nothing.
 383    //!
 384    //! <b>Complexity</b>: Linear to the number of moved positions.
 385    static void move_forward(node_ptr p, std::size_t n)
 386    {
 387       //Null shift, nothing to do
 388       if(!n)   return;
 389       node_ptr last  = NodeTraits::get_previous(p);
 390       //size() == 0 or 1, nothing to do
 391       if(last == NodeTraits::get_next(p))   return;
 392
 393       unlink(p);
 394       //Now get the new last node
 395       while(n--){
 396          last = NodeTraits::get_previous(last);
 397       }
 398       link_after(last, p);
 399    }
 400 };
 401
 402 } //namespace intrusive
 403 } //namespace boost
 404
 405 #include <boost/intrusive/detail/config_end.hpp>
 406
 407 #endif //BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP