| Home | Libraries | People | FAQ | More

## Class template circular_slist_algorithms

boost::intrusive::circular_slist_algorithms

## Synopsis

    // In header: <boost/intrusive/circular_slist_algorithms.hpp>

    template<typename NodeTraits>
    class circular_slist_algorithms {
    public:
      // types
      typedef NodeTraits::node           node;
      typedef NodeTraits::node_ptr       node_ptr;
      typedef NodeTraits::const_node_ptr const_node_ptr;
      typedef NodeTraits                 node_traits;

      // public static functions
      static void init(node_ptr);
      static bool unique(const_node_ptr);
      static bool inited(const_node_ptr);
      static void unlink_after(node_ptr);
      static void unlink_after(node_ptr, node_ptr);
      static void link_after(node_ptr, node_ptr);
      static void transfer_after(node_ptr, node_ptr, node_ptr);
      static void init_header(node_ptr);
      static node_ptr get_previous_node(node_ptr, node_ptr);
      static node_ptr get_previous_node(node_ptr);
      static node_ptr get_previous_previous_node(node_ptr);
      static node_ptr get_previous_previous_node(node_ptr, node_ptr);
      static std::size_t count(const_node_ptr);
      static void unlink(node_ptr);
      static void link_before(node_ptr, node_ptr);
      static void swap_nodes(node_ptr, node_ptr);
      static void reverse(node_ptr);
      static node_ptr move_backwards(node_ptr, std::size_t);
      static node_ptr move_forward(node_ptr, std::size_t);
    };

## Description

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:

`node`: The type of the node that forms the circular list

`node_ptr`: A pointer to a node

`const_node_ptr`: A pointer to a const node

Static functions:

`static node_ptr get_next(const_node_ptr n);`

`static void set_next(node_ptr n, node_ptr next);`

### `circular_slist_algorithms` public static functions

1.     static void init(node_ptr this_node);

   Effects: Constructs an non-used list element, putting the next pointer to null: `NodeTraits::get_next(this_node) == 0`

   Complexity: Constant

   Throws: Nothing.

2.     static bool unique(const_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: `return !NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node`

   Complexity: Constant

   Throws: Nothing.

3.     static bool inited(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.

4.     static void unlink_after(node_ptr prev_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.

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

6.     static void link_after(node_ptr prev_node, node_ptr this_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.

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

   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.

8.     static void init_header(node_ptr this_node);

   Effects: Constructs an empty list, making this_node the only node of the circular list: `NodeTraits::get_next(this_node) == this_node`.

   Complexity: Constant

   Throws: Nothing.

9.     static node_ptr get_previous_node(node_ptr prev_init_node, node_ptr 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.

10.     static node_ptr get_previous_node(node_ptr 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.

11.     static node_ptr get_previous_previous_node(node_ptr 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.

12.     static node_ptr
        get_previous_previous_node(node_ptr prev_prev_init_node, node_ptr this_node);

    Requires: this_node and prev_prev_init_node 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 prev_init_node. The first node checked for equality is NodeTraits::get_next((NodeTraits::get_next(prev_prev_init_node)).

    Complexity: Linear to the number of elements in the circular list.

    Throws: Nothing.

13.     static std::size_t count(const_node_ptr this_node);

    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.

14.     static void unlink(node_ptr this_node);

    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.

15.     static void link_before(node_ptr nxt_node, node_ptr 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.

16.     static void swap_nodes(node_ptr this_node, node_ptr other_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.

17.     static void reverse(node_ptr p);

    Effects: Reverses the order of elements in the list.

    Throws: Nothing.

    Complexity: This function is linear to the contained elements.

18.     static node_ptr move_backwards(node_ptr p, std::size_t n);

    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.

19.     static node_ptr move_forward(node_ptr p, std::size_t n);

    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.