circular_slist_algorithms provides basic algorithms to manipulate nodes forming a circular singly linked list. More...

#include <intrusive_fwd.hpp>

Public Types
typedef NodeTraits::node	node

typedef NodeTraits::node_ptr	node_ptr

typedef NodeTraits::const_node_ptr	const_node_ptr

typedef NodeTraits	node_traits

Static Public Member Functions
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) == this_node`. More...

static node_ptr	get_previous_node (const node_ptr &prev_init_node, const node_ptr &this_node)
	Requires: this_node and prev_init_node must be in the same circular list. More...

static node_ptr	get_previous_node (const node_ptr &this_node)
	Requires: this_node must be in a circular list or be an empty circular list. More...

static node_ptr	get_previous_previous_node (const node_ptr &this_node)
	Requires: this_node must be in a circular list or be an empty circular list. More...

static node_ptr	get_previous_previous_node (node_ptr p, const node_ptr &this_node)
	Requires: this_node and p must be in the same circular list. More...

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. More...

static void	unlink (const node_ptr &this_node)
	Requires: this_node must be in a circular list, be an empty circular list or be inited. More...

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. More...

static void	swap_nodes (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. More...

static void	reverse (const node_ptr &p)
	Effects: Reverses the order of elements in the list. More...

static node_ptr	move_backwards (const node_ptr &p, std::size_t n)
	Effects: Moves the node p n positions towards the end of the list. More...

static node_ptr	move_forward (const node_ptr &p, std::size_t n)
	Effects: Moves the node p n positions towards the beginning of the list. More...

Detailed Description

template<class NodeTraits>
singleton boost::intrusive::circular_slist_algorithms< NodeTraits >

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);

Member Typedef Documentation

template<class NodeTraits >

typedef NodeTraits::const_node_ptr boost::intrusive::circular_slist_algorithms< NodeTraits >::const_node_ptr

template<class NodeTraits >

typedef NodeTraits::node boost::intrusive::circular_slist_algorithms< NodeTraits >::node

template<class NodeTraits >

typedef NodeTraits::node_ptr boost::intrusive::circular_slist_algorithms< NodeTraits >::node_ptr

template<class NodeTraits >

typedef NodeTraits boost::intrusive::circular_slist_algorithms< NodeTraits >::node_traits

Member Function Documentation

template<class NodeTraits >

static std::size_t boost::intrusive::circular_slist_algorithms< NodeTraits >::count ( const const_node_ptr & this_node )

inlinestatic

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.

References boost::multiprecision::backends::p.

template<class NodeTraits >

static node_ptr boost::intrusive::circular_slist_algorithms< NodeTraits >::get_previous_node	(	const node_ptr &	prev_init_node,
		const node_ptr &	this_node
	)

inlinestatic

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.

Referenced by boost::intrusive::circular_slist_algorithms< NodeTraits >::link_before(), boost::intrusive::circular_slist_algorithms< NodeTraits >::swap_nodes(), and boost::intrusive::circular_slist_algorithms< NodeTraits >::unlink().

template<class NodeTraits >

static node_ptr boost::intrusive::circular_slist_algorithms< NodeTraits >::get_previous_node ( const node_ptr & this_node )

inlinestatic

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.

template<class NodeTraits >

static node_ptr boost::intrusive::circular_slist_algorithms< NodeTraits >::get_previous_previous_node ( const node_ptr & this_node )

inlinestatic

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.

template<class NodeTraits >

static node_ptr boost::intrusive::circular_slist_algorithms< NodeTraits >::get_previous_previous_node	(	node_ptr	p,
		const node_ptr &	this_node
	)

inlinestatic

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.

References boost::multiprecision::backends::p.

template<class NodeTraits >

static void boost::intrusive::circular_slist_algorithms< NodeTraits >::init_header ( const node_ptr & this_node )

inlinestatic

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.

template<class NodeTraits >

static void boost::intrusive::circular_slist_algorithms< NodeTraits >::link_before	(	const node_ptr &	nxt_node,
		const node_ptr &	this_node
	)

inlinestatic

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.

References boost::intrusive::circular_slist_algorithms< NodeTraits >::get_previous_node().

template<class NodeTraits >

static node_ptr boost::intrusive::circular_slist_algorithms< NodeTraits >::move_backwards	(	const node_ptr &	p,
		std::size_t	n
	)

inlinestatic

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.

References boost::xpressive::first, boost::multiprecision::backends::i, and boost::n.

template<class NodeTraits >

static node_ptr boost::intrusive::circular_slist_algorithms< NodeTraits >::move_forward	(	const node_ptr &	p,
		std::size_t	n
	)

inlinestatic

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.

References boost::distance(), and boost::xpressive::first.

template<class NodeTraits >

static void boost::intrusive::circular_slist_algorithms< NodeTraits >::reverse ( const node_ptr & p )

inlinestatic

Effects: Reverses the order of elements in the list.

Throws: Nothing.

Complexity: This function is linear to the contained elements.

References boost::multiprecision::backends::i.

template<class NodeTraits >

static void boost::intrusive::circular_slist_algorithms< NodeTraits >::swap_nodes	(	const node_ptr &	this_node,
		const node_ptr &	other_node
	)

inlinestatic

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.

References boost::intrusive::circular_slist_algorithms< NodeTraits >::get_previous_node().

template<class NodeTraits >

static void boost::intrusive::circular_slist_algorithms< NodeTraits >::unlink ( const node_ptr & this_node )

inlinestatic

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.

References boost::intrusive::circular_slist_algorithms< NodeTraits >::get_previous_node().

The documentation for this singleton was generated from the following file:

boost_1_57_0/boost/intrusive/circular_slist_algorithms.hpp

Public Types

Static Public Member Functions

Detailed Description

template<class NodeTraits> singleton boost::intrusive::circular_slist_algorithms< NodeTraits >

Member Typedef Documentation

Member Function Documentation

template<class NodeTraits>
singleton boost::intrusive::circular_slist_algorithms< NodeTraits >