![]() |
Home | Libraries | People | FAQ | More |
boost::intrusive::circular_slist_algorithms
// In header: <boost/intrusive/circular_slist_algorithms.hpp> template<typename NodeTraits> class circular_slist_algorithms { public: // types typedef ; typedef ; typedef ; typedef NodeTraits ; // public static functions void (); bool (); bool (); void (); void (, ); void (, ); void (, , ); void (); (const , const ); (const ); (const ); (, const ); (const ); void (); void (, ); void (, ); void (); (, ); (, ); };
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 functionsvoid ( this_node);
Effects: Constructs an non-used list element, putting the next pointer to null: NodeTraits::get_next(this_node) == node_ptr()
Complexity: Constant
Throws: Nothing.
bool ( 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 node_ptr() == NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node
Complexity: Constant
Throws: Nothing.
bool ( 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.
void ( 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.
void ( prev_node, 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.
void ( prev_node, 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.
void ( p, b, 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.
void ( 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.
(const prev_init_node, const 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.
(const 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.
(const 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.
( p, const 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.
(const 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.
void ( 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.
void ( nxt_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.
void ( this_node, 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.
void ( p);
Effects: Reverses the order of elements in the list.
Throws: Nothing.
Complexity: This function is linear to the contained elements.
( p, 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.
( p, 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.