static void init(node_ptr this_node) noexcept;

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

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: or it's a not inserted node: return node_ptr() == NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node

Complexity: Constant

Throws: Nothing.

static bool inited(const_node_ptr this_node) noexcept;

Effects: Returns true is "this_node" has the same state as if it was inited using "init(node_ptr)"

Complexity: Constant

Throws: Nothing.

static void unlink_after(node_ptr prev_node) noexcept;

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, node_ptr last_node) noexcept;

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 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 transfer_after(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.

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 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) == this_node.

Complexity: Constant

Throws: Nothing.

static node_ptr end_node(const_node_ptr p) noexcept;

Requires: 'p' is the first node of a list.

Effects: Returns a pointer to a node that represents the "end" (one past end) node

Complexity: Constant time.

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 is_sentinel(const_node_ptr this_node) noexcept;

Effects: Returns true if this_node points to a sentinel node.

Complexity: Constant

Throws: Nothing.

static void set_sentinel(node_ptr this_node) noexcept;

Effects: Marks this node as a "sentinel" node, a special state that is different from "empty", that can be used to mark a special state of the list

Complexity: Constant

Throws: Nothing.

static node_ptr 
get_previous_node(node_ptr prev_init_node, node_ptr this_node) noexcept;

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.

static node_ptr get_previous_node(node_ptr this_node) noexcept;

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.

static node_ptr get_previous_previous_node(node_ptr this_node) noexcept;

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.

static node_ptr 
get_previous_previous_node(node_ptr p, node_ptr this_node) noexcept;

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 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 void unlink(node_ptr this_node) noexcept;

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.

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

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: Linear to number of elements of both lists

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 to the contained elements.

template<typename NodePtrCompare> 
  static node_ptr 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.

Returns: The last node of the sorted list (p if the list has no other nodes).

Complexity: Approximately N log N comparisons, 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 node_ptr 
  merge(node_ptr p, node_ptr x, NodePtrCompare comp, 
        node_ptr p_last = node_ptr(), node_ptr x_last = node_ptr());

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.

"p_last" and "x_last" are optional: the last nodes of both lists, if they are known, which avoids traversing the lists to find them (otherwise null pointers can be passed).

Returns: The last node that was transferred from x's list, or a null pointer if x's list had no other nodes.

Complexity: Linear: it performs at most N + M - 1 comparisons, where N and M are the number of nodes of each list. If the last node of x's list is transferred after all the nodes of p's list, a traversal of the remaining nodes of x's list is needed.

Throws: If "comp" throws. Basic guarantee: all the nodes of x's list are moved to p's list in unspecified order.

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

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_forward(node_ptr p, std::size_t n) noexcept;

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 void transfer_after(node_ptr p, node_ptr other) noexcept;

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

Effects: Transfers all nodes from other after p in p's list.

Complexity: Linear

Throws: Nothing.

template<typename Disposer> 
  static std::size_t 
  detach_and_dispose(node_ptr p, Disposer disposer) noexcept;

Requires: "disposer" must be an object function taking a node_ptr parameter and shouldn't throw.

Effects: Unlinks all nodes reachable from p (but not p) and calls void disposer::operator()(node_ptr) for every node of the list where p is linked.

Returns: The number of disposed nodes

Complexity: Linear to the number of element of the list.

Throws: Nothing.