Class template circular_list

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(node_ptr) noexcept;
  static bool inited(const_node_ptr) noexcept;
  static void init_header(node_ptr) noexcept;
  static bool is_empty(const_node_ptr) noexcept;
  static bool unique(const_node_ptr) noexcept;
  static std::size_t count(const_node_ptr) noexcept;
  static node_ptr unlink(node_ptr) noexcept;
  static void unlink(node_ptr, node_ptr) noexcept;
  static void link_before(node_ptr, node_ptr) noexcept;
  static void link_after(node_ptr, node_ptr) noexcept;
  static void swap_nodes(node_ptr, node_ptr) noexcept;
  static void transfer(node_ptr, node_ptr, node_ptr) noexcept;
  static void transfer(node_ptr, node_ptr) noexcept;
  static void reverse(node_ptr) noexcept;
  template<typename NodePtrCompare> static void sort(node_ptr, NodePtrCompare);
  template<typename NodePtrCompare> 
    static void merge(node_ptr, node_ptr, NodePtrCompare);
  static void move_backwards(node_ptr, std::size_t) noexcept;
  static void move_forward(node_ptr, std::size_t) noexcept;
  static std::size_t distance(const_node_ptr, const_node_ptr) noexcept;
  template<typename Pred> 
    static void stable_partition(node_ptr, node_ptr, Pred, 
                                 stable_partition_info &);

  // private static functions
  static void priv_relink_sorted(node_ptr, node_ptr, node_ptr) noexcept;
  static void swap_prev(node_ptr, node_ptr) noexcept;
  static void swap_next(node_ptr, node_ptr) noexcept;
};

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

```
static void init(node_ptr this_node) noexcept;
```
Effects: Constructs an non-used list element, so that inited(this_node) == true

Complexity: Constant

Throws: Nothing.
```
static bool inited(const_node_ptr this_node) noexcept;
```
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.
```
static void init_header(node_ptr this_node) noexcept;
```
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.
```
static bool is_empty(const_node_ptr this_node) noexcept;
```
Effects: Returns true if this_node_points to an empty list.

Complexity: Constant

Throws: Nothing.
```
static bool unique(const_node_ptr this_node) noexcept;
```
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.
```
static std::size_t count(const_node_ptr this_node) noexcept;
```
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 node_ptr unlink(node_ptr this_node) noexcept;
```
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.
```
static void unlink(node_ptr b, node_ptr e) noexcept;
```
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.
```
static void link_before(node_ptr nxt_node, node_ptr this_node) noexcept;
```
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.
```
static void link_after(node_ptr prev_node, node_ptr this_node) noexcept;
```
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 swap_nodes(node_ptr this_node, node_ptr other_node) noexcept;
```
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.
```
static void transfer(node_ptr p, node_ptr b, node_ptr e) noexcept;
```
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.
```
static void transfer(node_ptr p, node_ptr i) noexcept;
```
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.
```
static void reverse(node_ptr p) noexcept;
```
Effects: Reverses the order of elements in the list.

Throws: Nothing.

Complexity: This function is linear time.
```
template<typename NodePtrCompare> 
  static void sort(node_ptr p, NodePtrCompare comp);
```
Requires: p must be a node of a circular list (typically its header). "comp" must be a function object that induces a strict weak ordering on node_ptrs: comp(a, b) returns true if node a must be placed before node b.

Effects: Stable sorts, according to "comp", all the nodes of the list that follow p (for a circular list, all nodes except p). p is not compared and keeps its position.

Complexity: Approximately N log N comparisons and linear extra memory accesses, where N is the number of nodes. Uses a fixed amount of stack memory.

Throws: If "comp" throws. Basic guarantee: all nodes remain in the list in unspecified order.
```
template<typename NodePtrCompare> 
  static void merge(node_ptr p, node_ptr x, NodePtrCompare comp);
```
Requires: p and x must be nodes of two different circular lists (typically their headers). The nodes that follow p in its list and the nodes that follow x in its list must be sorted according to "comp", a function object that induces a strict weak ordering on node_ptrs: comp(a, b) returns true if node a must be placed before node b.

Effects: Removes all the nodes of x's list (except x) and inserts them in order in p's list. The merge is stable: if a node of p's list is equivalent to a node of x's list, the node of p's list goes first.

Complexity: Linear: it performs at most N + M - 1 comparisons, where N and M are the number of nodes of each list.

Throws: If "comp" throws. Basic guarantee: all the nodes of x's list are moved to p's list in unspecified order.
```
static void move_backwards(node_ptr p, std::size_t n) noexcept;
```
Effects: Moves the node p n positions towards the end of the list.

Throws: Nothing.

Complexity: Linear to the number of moved positions.
```
static void move_forward(node_ptr p, std::size_t n) noexcept;
```
Effects: Moves the node p n positions towards the beginning of the list.

Throws: Nothing.

Complexity: Linear to the number of moved positions.
```
static std::size_t distance(const_node_ptr f, const_node_ptr l) noexcept;
```
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.

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

`circular_list_algorithms` private static functions

static void priv_relink_sorted(node_ptr p, node_ptr head, node_ptr tail) noexcept;

static void swap_prev(node_ptr this_node, node_ptr other_node) noexcept;

static void swap_next(node_ptr this_node, node_ptr other_node) noexcept;