text: /////////////////////////////////////////////////////////////////////////////
  //
  // (C) Copyright Olaf Krzikalla 2004-2006.
  // (C) Copyright Ion Gaztanaga  2006-2007
  //
  // Distributed under the Boost Software License, Version 1.0.
  //    (See accompanying file LICENSE_1_0.txt or copy at
  //          http://www.boost.org/LICENSE_1_0.txt)
  //
  // See http://www.boost.org/libs/intrusive for documentation.
  //
  /////////////////////////////////////////////////////////////////////////////
  
  #ifndef BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP
  #define BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP
  
  #include <boost/intrusive/detail/config_begin.hpp>
  #include <boost/intrusive/intrusive_fwd.hpp>
  #include <cstddef>
  
  namespace boost {
  namespace intrusive {
  
  //! circular_list_algorithms provides basic algorithms to manipulate nodes
  //! forming a circular doubly linked list. An empty circular list is formed by a node
  //! whose pointers point to itself.
  //!
  //! circular_list_algorithms is configured with a NodeTraits class, which encapsulates the
  //! information about the node to be manipulated. NodeTraits must support the
  //! following interface:
  //!
  //! <b>Typedefs</b>:
  //!
  //! <tt>node</tt>: The type of the node that forms the circular list
  //!
  //! <tt>node_ptr</tt>: A pointer to a node
  //!
  //! <tt>const_node_ptr</tt>: A pointer to a const node
  //!
  //! <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
  {
     public:
     typedef typename NodeTraits::node            node;
     typedef typename NodeTraits::node_ptr        node_ptr;
     typedef typename NodeTraits::const_node_ptr  const_node_ptr;
     typedef NodeTraits                           node_traits;
  
     //! <b>Effects</b>: Constructs an non-used list element, so that
     //! inited(this_node) == true
     //! 
     //! <b>Complexity</b>: Constant 
     //! 
     //! <b>Throws</b>: Nothing.
     static void init(node_ptr this_node)
     {
        NodeTraits::set_next(this_node, node_ptr(0));
        NodeTraits::set_previous(this_node, node_ptr(0));
     }
  
     //! <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>Throws</b>: Nothing.
     static bool inited(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>Throws</b>: Nothing.
     static void init_header(node_ptr this_node)
     {
        NodeTraits::set_next(this_node, this_node);
        NodeTraits::set_previous(this_node, this_node);
     }
  
  
     //! <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>Throws</b>: Nothing.
     static bool unique(const_node_ptr this_node)
     {
        node_ptr next = NodeTraits::get_next(this_node);
        return !next || next == this_node;
     }
  
     //! <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>: Constant 
     //! 
     //! <b>Throws</b>: Nothing.
     static std::size_t count(const_node_ptr this_node) 
     {
        std::size_t result = 0;
        const_node_ptr p = this_node;
        do{
           p = NodeTraits::get_next(p);
           ++result;
        }while (p != this_node);
        return result;
     }
  
     //! <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>Throws</b>: Nothing.
     static node_ptr unlink(node_ptr this_node)
     {
        if(NodeTraits::get_next(this_node)){
           node_ptr next(NodeTraits::get_next(this_node));
           node_ptr prev(NodeTraits::get_previous(this_node));
           NodeTraits::set_next(prev, next);
           NodeTraits::set_previous(next, prev);
           return next;
        }
        else{
           return this_node;
        }
     }
  
     //! <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>Throws</b>: Nothing.
     static void unlink(node_ptr b, node_ptr e)
     {
        if (b != e) {
           node_ptr prevb(NodeTraits::get_previous(b));
           NodeTraits::set_previous(e, prevb);
           NodeTraits::set_next(prevb, e);
        }
     }
  
     //! <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>Throws</b>: Nothing.
     static void link_before(node_ptr nxt_node, node_ptr this_node)
     {
        node_ptr prev(NodeTraits::get_previous(nxt_node));
        NodeTraits::set_previous(this_node, prev);
        NodeTraits::set_next(prev, this_node);
        NodeTraits::set_previous(nxt_node, this_node);
        NodeTraits::set_next(this_node, nxt_node);
     }
  
     //! <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>Throws</b>: Nothing.
     static void link_after(node_ptr prev_node, node_ptr this_node)
     {
        node_ptr next(NodeTraits::get_next(prev_node));
        NodeTraits::set_previous(this_node, prev_node);
        NodeTraits::set_next(this_node, next);
        NodeTraits::set_previous(next, this_node);
        NodeTraits::set_next(prev_node, this_node);
     }
  
     //! <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>Throws</b>: Nothing.
  /*
     static void swap_nodes(node_ptr this_node, node_ptr other_node)
     {
  
        if (other_node == this_node)
           return;
        bool empty1 = unique(this_node);
        bool empty2 = unique(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));
  
        //Do the swap
        NodeTraits::set_next(this_node, next_other);
        NodeTraits::set_next(other_node, next_this);
  
        NodeTraits::set_previous(this_node, prev_other);
        NodeTraits::set_previous(other_node, prev_this);
  
        if (empty2){
           init(this_node);
        }
        else{
           NodeTraits::set_next(prev_other, this_node);
           NodeTraits::set_previous(next_other, this_node);
        }
        if (empty1){
           init(other_node);
        }
        else{
           NodeTraits::set_next(prev_this, other_node);
           NodeTraits::set_previous(next_this, other_node);
        }
     }
  */
  
     //Watanabe version
     private: 
     static void swap_prev(node_ptr this_node, 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(node_ptr this_node, 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(node_ptr this_node, node_ptr other_node) 
     {
        if (other_node == this_node)
           return;
        bool this_inited  = inited(this_node);
        bool other_inited = inited(other_node);
        if(this_inited){
           init_header(this_node);
        }
        if(other_inited){
           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); 
  
        if(this_inited){
           init(other_node);
        }
        if(other_inited){
           init(this_node);
        }
     }
  
     //! <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 
     //    [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>Throws</b>: Nothing.
     static void transfer(node_ptr p, node_ptr b, node_ptr e)
     {
        if (b != e) {
           node_ptr prev_p(NodeTraits::get_previous(p));
           node_ptr prev_b(NodeTraits::get_previous(b));
           node_ptr prev_e(NodeTraits::get_previous(e));
           NodeTraits::set_next(prev_e, p);
           NodeTraits::set_previous(p, prev_e);
           NodeTraits::set_next(prev_b, e);
           NodeTraits::set_previous(e, prev_b);
           NodeTraits::set_next(prev_p, b);
           NodeTraits::set_previous(b, prev_p);
        }
     }
  
     //! <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. 
     //!   If p == i or p == NodeTraits::get_next(i), this function is a null operation.
     //! 
     //! <b>Complexity</b>: Constant 
     //! 
     //! <b>Throws</b>: Nothing.
     static void transfer(node_ptr p, node_ptr i)
     {
        node_ptr n(NodeTraits::get_next(i));
        if(n != p && i != p){
           node_ptr prev_p(NodeTraits::get_previous(p));
           node_ptr prev_i(NodeTraits::get_previous(i));
           NodeTraits::set_next(prev_p, i);
           NodeTraits::set_previous(i, prev_p);
           NodeTraits::set_next(i, p);
           NodeTraits::set_previous(p, i);
           NodeTraits::set_previous(n, prev_i);
           NodeTraits::set_next(prev_i, n);
  
        }
     }
  
     //! <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(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);
           transfer(f, n, i);
           f = n;
        }
     }
  
     //! <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(node_ptr p, std::size_t n)
     {
        //Null shift, nothing to do
        if(!n) return;
        node_ptr first  = NodeTraits::get_next(p);
        //size() == 0 or 1, nothing to do
        if(first == NodeTraits::get_previous(p)) return;
        unlink(p);
        //Now get the new first node
        while(n--){
           first = NodeTraits::get_next(first);
        }
        link_before(first, p);
     }
  
     //! <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(node_ptr p, std::size_t n)
     {
        //Null shift, nothing to do
        if(!n)   return;
        node_ptr last  = NodeTraits::get_previous(p);
        //size() == 0 or 1, nothing to do
        if(last == NodeTraits::get_next(p))   return;
  
        unlink(p);
        //Now get the new last node
        while(n--){
           last = NodeTraits::get_previous(last);
        }
        link_after(last, p);
     }
  };
  
  } //namespace intrusive 
  } //namespace boost 
  
  #include <boost/intrusive/detail/config_end.hpp>
  
  #endif //BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP
  