/////////////////////////////////////////////////////////////////////////////

//

// (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_SLIST_ALGORITHMS_HPP

#define BOOST_INTRUSIVE_CIRCULAR_SLIST_ALGORITHMS_HPP



#include <boost/intrusive/detail/config_begin.hpp>

#include <boost/intrusive/intrusive_fwd.hpp>

#include <boost/intrusive/detail/common_slist_algorithms.hpp>

#include <boost/intrusive/detail/assert.hpp>

#include <cstddef>



namespace boost {

namespace intrusive {



//! circular_slist_algorithms provides basic algorithms to manipulate nodes

//! forming a circular singly linked list. An empty circular list is formed by a node

//! whose pointer to the next node points to itself.

//!

//! circular_slist_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_next(const_node_ptr n);</tt>

//! 

//! <tt>static void set_next(node_ptr n, node_ptr next);</tt>

template<class NodeTraits>

class circular_slist_algorithms

   /// @cond

   : public detail::common_slist_algorithms<NodeTraits>

   /// @endcond

{

   /// @cond

   typedef detail::common_slist_algorithms<NodeTraits> base_t;

   /// @endcond

   public:

   typedef typename NodeTraits::node_ptr        node_ptr;

   typedef typename NodeTraits::const_node_ptr  const_node_ptr;

   typedef NodeTraits                           node_traits;



   #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED



   //! <b>Effects</b>: Constructs an non-used list element, putting the next

   //!   pointer to null:

   //!  <tt>NodeTraits::get_next(this_node) == 0

   //! 

   //! <b>Complexity</b>: Constant 

   //! 

   //! <b>Throws</b>: Nothing.

   static void init(node_ptr 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:

   //!  or it's a not inserted node:

   //!  <tt>return !NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt>

   //! 

   //! <b>Complexity</b>: Constant 

   //! 

   //! <b>Throws</b>: Nothing.

   static bool unique(const_node_ptr this_node);



   //! <b>Effects</b>: Returns true is "this_node" has the same state as

   //!  if it was inited using "init(node_ptr)"

   //! 

   //! <b>Complexity</b>: Constant 

   //! 

   //! <b>Throws</b>: Nothing.

   static bool inited(const_node_ptr this_node);



   //! <b>Requires</b>: prev_node must be in a circular list or be an empty circular list.

   //! 

   //! <b>Effects</b>: Unlinks the next node of prev_node from the circular list.

   //! 

   //! <b>Complexity</b>: Constant 

   //! 

   //! <b>Throws</b>: Nothing.

   static void unlink_after(node_ptr prev_node);



   //! <b>Requires</b>: prev_node and last_node must be in a circular list

   //!  or be an empty circular list.

   //!

   //! <b>Effects</b>: Unlinks the range (prev_node, last_node) from the circular list.

   //!

   //! <b>Complexity</b>: Constant 

   //!

   //! <b>Throws</b>: Nothing.

   static void unlink_after(node_ptr prev_node, node_ptr last_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);



   //! <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.

   //! 

   //! <b>Effects</b>: Removes the nodes from (b, e] range from their circular list and inserts

   //!   them after p in p's circular list.

   //! 

   //! <b>Complexity</b>: Constant 

   //! 

   //! <b>Throws</b>: Nothing.

   static void transfer_after(node_ptr p, node_ptr b, node_ptr e);



   #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED



   //! <b>Effects</b>: Constructs an empty list, making this_node the only

   //!   node of the circular list:

   //!  <tt>NodeTraits::get_next(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);  } 



   //! <b>Requires</b>: this_node and prev_init_node must be in the same circular list.

   //! 

   //! <b>Effects</b>: Returns the previous node of this_node in the circular list starting.

   //!   the search from prev_init_node. The first node checked for equality

   //!   is NodeTraits::get_next(prev_init_node).

   //! 

   //! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node.

   //! 

   //! <b>Throws</b>: Nothing.

   static node_ptr get_previous_node(node_ptr prev_init_node, node_ptr this_node)

   {  return base_t::get_previous_node(prev_init_node, this_node);   }



   //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.

   //! 

   //! <b>Effects</b>: Returns the previous node of this_node in the circular list.

   //! 

   //! <b>Complexity</b>: Linear to the number of elements in the circular list.

   //! 

   //! <b>Throws</b>: Nothing.

   static node_ptr get_previous_node(node_ptr this_node)

   {  return base_t::get_previous_node(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 the previous node of the previous node of this_node in the circular list.

   //! 

   //! <b>Complexity</b>: Linear to the number of elements in the circular list.

   //! 

   //! <b>Throws</b>: Nothing.

   static node_ptr get_previous_previous_node(node_ptr this_node)

   {  return get_previous_previous_node(this_node, this_node); }



   //! <b>Requires</b>: this_node and prev_prev_init_node must be in the same circular list.

   //! 

   //! <b>Effects</b>: Returns the previous node of the previous node of this_node in the

   //!   circular list starting. the search from prev_init_node. The first node checked

   //!   for equality is NodeTraits::get_next((NodeTraits::get_next(prev_prev_init_node)).

   //! 

   //! <b>Complexity</b>: Linear to the number of elements in the circular list.

   //! 

   //! <b>Throws</b>: Nothing.

   static node_ptr get_previous_previous_node(node_ptr prev_prev_init_node, node_ptr this_node)

   {

      node_ptr p = prev_prev_init_node;

      node_ptr p_next = NodeTraits::get_next(p);

      node_ptr p_next_next = NodeTraits::get_next(p_next);

      while (this_node != p_next_next){

         p = p_next;

         p_next = p_next_next;

         p_next_next = NodeTraits::get_next(p_next);

      }

      return p;

   }



   //! <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, be an empty circular list or be inited.

   //! 

   //! <b>Effects</b>: Unlinks the node from the circular list.

   //! 

   //! <b>Complexity</b>: Linear to the number of elements in the circular list 

   //! 

   //! <b>Throws</b>: Nothing.

   static void unlink(node_ptr this_node)

   {

      if(NodeTraits::get_next(this_node))

         base_t::unlink_after(get_previous_node(this_node));

   }



   //! <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>: Linear to the number of elements in the circular list. 

   //! 

   //! <b>Throws</b>: Nothing.

   static void link_before (node_ptr nxt_node, node_ptr this_node)

   {  base_t::link_after(get_previous_node(nxt_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>: Linear to number of elements of both lists 

   //! 

   //! <b>Throws</b>: Nothing.

   static void swap_nodes(node_ptr this_node, node_ptr other_node)

   {

      if (other_node == this_node)

         return;

      bool this_inited  = base_t::inited(this_node);

      bool other_inited = base_t::inited(other_node);

      if(this_inited){

         base_t::init_header(this_node);

      }

      if(other_inited){

         base_t::init_header(other_node);

      }



      bool empty1 = base_t::unique(this_node);

      bool empty2 = base_t::unique(other_node);

      node_ptr prev_this (get_previous_node(this_node));

      node_ptr prev_other(get_previous_node(other_node));



      node_ptr this_next (NodeTraits::get_next(this_node));

      node_ptr other_next(NodeTraits::get_next(other_node));

      NodeTraits::set_next(this_node, other_next);

      NodeTraits::set_next(other_node, this_next);

      NodeTraits::set_next(empty1 ? other_node : prev_this, other_node);

      NodeTraits::set_next(empty2 ? this_node  : prev_other, this_node);



      if(this_inited){

         base_t::init(other_node);

      }

      if(other_inited){

         base_t::init(this_node);

      }

   }



   //! <b>Effects</b>: Reverses the order of elements in the list. 

   //! 

   //! <b>Throws</b>: Nothing.

   //! 

   //! <b>Complexity</b>: This function is linear to the contained elements.

   static void reverse(node_ptr p)

   {

      node_ptr i = NodeTraits::get_next(p), e(p); 

      for (;;) {

         node_ptr nxt(NodeTraits::get_next(i));

         if (nxt == e)

            break;

         base_t::transfer_after(e, i, nxt);

      }

   }



   //! <b>Effects</b>: Moves the node p n positions towards the end of the list.

   //!

   //! <b>Returns</b>: The previous node of p after the function if there has been any movement,

   //!   Null if n leads to no movement.

   //!

   //! <b>Throws</b>: Nothing.

   //! 

   //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.

   static node_ptr move_backwards(node_ptr p, std::size_t n)

   {

      //Null shift, nothing to do

      if(!n) return 0;

      node_ptr first  = NodeTraits::get_next(p);



      //count() == 1 or 2, nothing to do

      if(NodeTraits::get_next(first) == p)

         return 0;



      bool end_found = false;

      node_ptr new_last(0);



      //Now find the new last node according to the shift count.

      //If we find p before finding the new last node

      //unlink p, shortcut the search now that we know the size of the list

      //and continue.

      for(std::size_t i = 1; i <= n; ++i){

         new_last = first;

         first = NodeTraits::get_next(first);

         if(first == p){

            //Shortcut the shift with the modulo of the size of the list

            n %= i;

            if(!n)

               return 0;

            i = 0;

            //Unlink p and continue the new first node search

            first = NodeTraits::get_next(p);

            base_t::unlink_after(new_last);

            end_found = true;

         }

      }



      //If the p has not been found in the previous loop, find it

      //starting in the new first node and unlink it

      if(!end_found){

         base_t::unlink_after(base_t::get_previous_node(first, p));

      }



      //Now link p after the new last node

      base_t::link_after(new_last, p);

      return new_last;

   }



   //! <b>Effects</b>: Moves the node p n positions towards the beginning of the list.

   //! 

   //! <b>Returns</b>: The previous node of p after the function if there has been any movement,

   //!   Null if n leads equals to no movement.

   //! 

   //! <b>Throws</b>: Nothing.

   //! 

   //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.

   static node_ptr move_forward(node_ptr p, std::size_t n)

   {

      //Null shift, nothing to do

      if(!n) return 0;

      node_ptr first  = node_traits::get_next(p);



      //count() == 1 or 2, nothing to do

      if(node_traits::get_next(first) == p) return 0;



      //Iterate until p is found to know where the current last node is.

      //If the shift count is less than the size of the list, we can also obtain

      //the position of the new last node after the shift.

      node_ptr old_last(first), next_to_it, new_last(p);

      std::size_t distance = 1;

      while(p != (next_to_it = node_traits::get_next(old_last))){

         if(++distance > n)

            new_last = node_traits::get_next(new_last);

         old_last = next_to_it;

      }

      //If the shift was bigger or equal than the size, obtain the equivalent

      //forward shifts and find the new last node.

      if(distance <= n){

         //Now find the equivalent forward shifts.

         //Shortcut the shift with the modulo of the size of the list

         std::size_t new_before_last_pos = (distance - (n % distance))% distance;

         //If the shift is a multiple of the size there is nothing to do

         if(!new_before_last_pos)   return 0;

         

         for( new_last = p

            ; new_before_last_pos--

            ; new_last = node_traits::get_next(new_last)){

            //empty

         }

      }



      //Now unlink p and link it after the new last node

      base_t::unlink_after(old_last);

      base_t::link_after(new_last, p);

      return new_last;

   }

};



} //namespace intrusive 

} //namespace boost 



#include <boost/intrusive/detail/config_end.hpp>



#endif //BOOST_INTRUSIVE_CIRCULAR_SLIST_ALGORITHMS_HPP

