EVOLUTION-MANAGER

Edit File: circular_slist_algorithms.hpp

/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
// (C) Copyright Ion Gaztanaga  2006-2014
//
// 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 <cstddef>
#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/algo_type.hpp>

#if defined(BOOST_HAS_PRAGMA_ONCE)
#  pragma once
#endif

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:
//!
//! Typedefs:
//!
//! <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
//!
//! Static functions:
//!
//! <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 node;
 typedef typename NodeTraits::node_ptr node_ptr;
 typedef typename NodeTraits::const_node_ptr const_node_ptr;
 typedef NodeTraits node_traits;

#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)

//! Effects: Constructs an non-used list element, putting the next
 //! pointer to null:
 //! <tt>NodeTraits::get_next(this_node) == node_ptr()</tt>
 //!
 //! Complexity: Constant
 //!
 //! Throws: Nothing.
 static void init(node_ptr this_node);

//! Requires: this_node must be in a circular list or be an empty circular list.
 //!
 //! Effects: Returns true is "this_node" is the only node of a circular list:
 //! or it's a not inserted node:
 //! <tt>return node_ptr() == NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt>
 //!
 //! Complexity: Constant
 //!
 //! Throws: Nothing.
 static bool unique(const_node_ptr this_node);

//! Effects: Returns true is "this_node" has the same state as
 //! if it was inited using "init(node_ptr)"
 //!
 //! Complexity: Constant
 //!
 //! Throws: Nothing.
 static bool inited(const_node_ptr this_node);

//! Requires: prev_node must be in a circular list or be an empty circular list.
 //!
 //! Effects: Unlinks the next node of prev_node from the circular list.
 //!
 //! Complexity: Constant
 //!
 //! Throws: Nothing.
 static void unlink_after(node_ptr prev_node);

//! Requires: prev_node and last_node must be in a circular list
 //! or be an empty circular list.
 //!
 //! Effects: Unlinks the range (prev_node, last_node) from the circular list.
 //!
 //! Complexity: Constant
 //!
 //! Throws: Nothing.
 static void unlink_after(node_ptr prev_node, node_ptr last_node);

//! Requires: prev_node must be a node of a circular list.
 //!
 //! Effects: Links this_node after prev_node in the circular list.
 //!
 //! Complexity: Constant
 //!
 //! Throws: Nothing.
 static void link_after(node_ptr prev_node, node_ptr this_node);

//! Requires: 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.
 //!
 //! Effects: Removes the nodes from (b, e] range from their circular list and inserts
 //! them after p in p's circular list.
 //!
 //! Complexity: Constant
 //!
 //! Throws: Nothing.
 static void transfer_after(node_ptr p, node_ptr b, node_ptr e);

#endif   //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)

//! Effects: Constructs an empty list, making this_node the only
 //! node of the circular list:
 //! <tt>NodeTraits::get_next(this_node) == this_node</tt>.
 //!
 //! Complexity: Constant
 //!
 //! Throws: Nothing.
 BOOST_INTRUSIVE_FORCEINLINE static void init_header(node_ptr this_node)
 { NodeTraits::set_next(this_node, this_node); }

//! Requires: this_node and prev_init_node must be in the same circular list.
 //!
 //! Effects: 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).
 //!
 //! Complexity: Linear to the number of elements between prev_init_node and this_node.
 //!
 //! Throws: Nothing.
 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_previous_node(const node_ptr &prev_init_node, const node_ptr &this_node)
 { return base_t::get_previous_node(prev_init_node, this_node); }

//! Requires: this_node must be in a circular list or be an empty circular list.
 //!
 //! Effects: Returns the previous node of this_node in the circular list.
 //!
 //! Complexity: Linear to the number of elements in the circular list.
 //!
 //! Throws: Nothing.
 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_previous_node(const node_ptr & this_node)
 { return base_t::get_previous_node(this_node, this_node); }

//! Requires: this_node must be in a circular list or be an empty circular list.
 //!
 //! Effects: Returns the previous node of the previous node of this_node in the circular list.
 //!
 //! Complexity: Linear to the number of elements in the circular list.
 //!
 //! Throws: Nothing.
 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_previous_previous_node(const node_ptr & this_node)
 { return get_previous_previous_node(this_node, this_node); }

//! Requires: this_node and p must be in the same circular list.
 //!
 //! Effects: Returns the previous node of the previous node of this_node in the
 //! circular list starting. the search from p. The first node checked
 //! for equality is NodeTraits::get_next((NodeTraits::get_next(p)).
 //!
 //! Complexity: Linear to the number of elements in the circular list.
 //!
 //! Throws: Nothing.
 static node_ptr get_previous_previous_node(node_ptr p, const node_ptr & this_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;
 }

//! Requires: this_node must be in a circular list or be an empty circular list.
 //!
 //! Effects: Returns the number of nodes in a circular list. If the circular list
 //! is empty, returns 1.
 //!
 //! Complexity: Linear
 //!
 //! Throws: Nothing.
 static std::size_t count(const 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;
 }

//! Requires: this_node must be in a circular list, be an empty circular list or be inited.
 //!
 //! Effects: Unlinks the node from the circular list.
 //!
 //! Complexity: Linear to the number of elements in the circular list
 //!
 //! Throws: Nothing.
 BOOST_INTRUSIVE_FORCEINLINE static void unlink(node_ptr this_node)
 {
 if(NodeTraits::get_next(this_node))
 base_t::unlink_after(get_previous_node(this_node));
 }

//! Requires: nxt_node must be a node of a circular list.
 //!
 //! Effects: Links this_node before nxt_node in the circular list.
 //!
 //! Complexity: Linear to the number of elements in the circular list.
 //!
 //! Throws: Nothing.
 BOOST_INTRUSIVE_FORCEINLINE static void link_before (node_ptr nxt_node, node_ptr this_node)
 { base_t::link_after(get_previous_node(nxt_node), this_node); }

//! Requires: this_node and other_node must be nodes inserted
 //! in circular lists or be empty circular lists.
 //!
 //! Effects: 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.
 //!
 //! Complexity: Linear to number of elements of both lists
 //!
 //! Throws: Nothing.
 static void swap_nodes(node_ptr this_node, node_ptr other_node)
 {
 if (other_node == this_node)
 return;
 const node_ptr this_next = NodeTraits::get_next(this_node);
 const node_ptr other_next = NodeTraits::get_next(other_node);
 const bool this_null = !this_next;
 const bool other_null = !other_next;
 const bool this_empty = this_next == this_node;
 const bool other_empty = other_next == other_node;

if(!(other_null || other_empty)){
         NodeTraits::set_next(this_next == other_node ? other_node : get_previous_node(other_node), this_node );
      }
      if(!(this_null | this_empty)){
         NodeTraits::set_next(other_next == this_node ? this_node  : get_previous_node(this_node), other_node );
      }
      NodeTraits::set_next(this_node,  other_empty ? this_node  : (other_next == this_node ? other_node : other_next) );
      NodeTraits::set_next(other_node, this_empty  ? other_node : (this_next == other_node ? this_node :  this_next ) );
   }

//! Effects: Reverses the order of elements in the list.
 //!
 //! Throws: Nothing.
 //!
 //! Complexity: 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);
 }
 }

//! Effects: Moves the node p n positions towards the end of the list.
 //!
 //! Returns: The previous node of p after the function if there has been any movement,
 //! Null if n leads to no movement.
 //!
 //! Throws: Nothing.
 //!
 //! Complexity: 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 node_ptr();
 node_ptr first = NodeTraits::get_next(p);

//count() == 1 or 2, nothing to do
      if(NodeTraits::get_next(first) == p)
         return node_ptr();

bool end_found = false;
      node_ptr new_last = node_ptr();

//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 node_ptr();
 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;
   }

//! Effects: Moves the node p n positions towards the beginning of the list.
 //!
 //! Returns: The previous node of p after the function if there has been any movement,
 //! Null if n leads equals to no movement.
 //!
 //! Throws: Nothing.
 //!
 //! Complexity: 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 node_ptr();
 node_ptr first = node_traits::get_next(p);

//count() == 1 or 2, nothing to do
      if(node_traits::get_next(first) == p) return node_ptr();

//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 node_ptr();

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;
   }
};

/// @cond

template<class NodeTraits>
struct get_algo<CircularSListAlgorithms, NodeTraits>
{
 typedef circular_slist_algorithms<NodeTraits> type;
};

/// @endcond

} //namespace intrusive
} //namespace boost

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

#endif //BOOST_INTRUSIVE_CIRCULAR_SLIST_ALGORITHMS_HPP