| Home | Libraries | People | FAQ | More

## Class template circular_list_algorithms

boost::intrusive::circular_list_algorithms

## Synopsis

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

    template<typename NodeTraits>
    class circular_list_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;

      // member classes/structs/unions

      struct stable_partition_info {

        // public data members
        std::size_t num_1st_partition;
        std::size_t num_2nd_partition;
        node_ptr beg_2st_partition;
      };

      // public static functions
      static void init(const node_ptr &);
      static bool inited(const const_node_ptr &);
      static void init_header(const node_ptr &);
      static bool unique(const const_node_ptr &);
      static std::size_t count(const const_node_ptr &);
      static node_ptr unlink(const node_ptr &);
      static void unlink(const node_ptr &, const node_ptr &);
      static void link_before(const node_ptr &, const node_ptr &);
      static void link_after(const node_ptr &, const node_ptr &);
      static void swap_nodes(const node_ptr &, const node_ptr &);
      static void transfer(const node_ptr &, const node_ptr &, const node_ptr &);
      static void transfer(const node_ptr &, const node_ptr &);
      static void reverse(const node_ptr &);
      static void move_backwards(const node_ptr &, std::size_t);
      static void move_forward(const node_ptr &, std::size_t);
      static std::size_t distance(const const_node_ptr &, const const_node_ptr &);
      template<typename Pred>
        static void stable_partition(node_ptr, const node_ptr &, Pred,
                                     stable_partition_info &);

      // private static functions
      static void swap_prev(const node_ptr &, const node_ptr &);
      static void swap_next(const node_ptr &, const node_ptr &);
    };

## Description

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:

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_previous(const_node_ptr n);`

`static void set_previous(node_ptr n, node_ptr prev);`

`static node_ptr get_next(const_node_ptr n);`

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

### `circular_list_algorithms` public static functions

1.     static void init(const node_ptr & this_node);

   Effects: Constructs an non-used list element, so that inited(this_node) == true

   Complexity: Constant

   Throws: Nothing.

2.     static bool inited(const const_node_ptr & this_node);

   Effects: Returns true is "this_node" is in a non-used state as if it was initialized by the "init" function.

   Complexity: Constant

   Throws: Nothing.

3.     static void init_header(const node_ptr & this_node);

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

   Complexity: Constant

   Throws: Nothing.

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

   Complexity: Constant

   Throws: Nothing.

5.     static std::size_t count(const 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.

6.     static node_ptr unlink(const node_ptr & this_node);

   Requires: this_node must be in a circular list or be an empty circular list.

   Effects: Unlinks the node from the circular list.

   Complexity: Constant

   Throws: Nothing.

7.     static void unlink(const node_ptr & b, const node_ptr & e);

   Requires: b and e must be nodes of the same circular list or an empty range.

   Effects: Unlinks the node [b, e) from the circular list.

   Complexity: Constant

   Throws: Nothing.

8.     static void link_before(const node_ptr & nxt_node, const 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: Constant

   Throws: Nothing.

9.     static void link_after(const node_ptr & prev_node, const 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.

10.     static void swap_nodes(const node_ptr & this_node,
                               const node_ptr & other_node);

11.     static void transfer(const node_ptr & p, const node_ptr & b,
                             const 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 or may not be an iterator in Effects: Removes the nodes from [b, e) range from their circular list and inserts them before p in p's circular list.

    Complexity: Constant

    Throws: Nothing.

12.     static void transfer(const node_ptr & p, const node_ptr & i);

    Requires: i must a node of a circular list and p must be a node of a different circular list.

    Effects: 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.

    Complexity: Constant

    Throws: Nothing.

13.     static void reverse(const node_ptr & p);

    Effects: Reverses the order of elements in the list.

    Throws: Nothing.

    Complexity: This function is linear time.

14.     static void move_backwards(const node_ptr & p, std::size_t n);

    Effects: Moves the node p n positions towards the end of the list.

    Throws: Nothing.

    Complexity: Linear to the number of moved positions.

15.     static void move_forward(const node_ptr & p, std::size_t n);

    Effects: Moves the node p n positions towards the beginning of the list.

    Throws: Nothing.

    Complexity: Linear to the number of moved positions.

16.     static std::size_t
        distance(const const_node_ptr & f, const const_node_ptr & l);

    Requires: f and l must be in a circular list.

    Effects: Returns the number of nodes in the range [f, l).

    Complexity: Linear

    Throws: Nothing.

17.     template<typename Pred>
          static void stable_partition(node_ptr beg, const node_ptr & end, Pred pred,
                                       stable_partition_info & info);

### `circular_list_algorithms` private static functions

1.     static void swap_prev(const node_ptr & this_node, const 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: Constant

   Throws: Nothing.

2.     static void swap_next(const node_ptr & this_node, const node_ptr & other_node);