Boost  v1.57.0
doxygen for www.boost.org
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
boost::intrusive::circular_list_algorithms< NodeTraits > Singleton Reference

circular_list_algorithms provides basic algorithms to manipulate nodes forming a circular doubly linked list. More...

#include <intrusive_fwd.hpp>

Classes

struct  stable_partition_info
 

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 (const node_ptr &this_node)
 Effects: Constructs an non-used list element, so that inited(this_node) == true More...
 
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. More...
 
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. More...
 
static bool unique (const const_node_ptr &this_node)
 Requires: this_node must be in a circular list or be an empty 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 node_ptr unlink (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 &b, const node_ptr &e)
 Requires: b and e must be nodes of the same circular list or an empty range. 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 link_after (const node_ptr &prev_node, const node_ptr &this_node)
 Requires: prev_node must be a node of a circular list. More...
 
static void swap_nodes (const node_ptr &this_node, const node_ptr &other_node)
 
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. More...
 
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. More...
 
static void reverse (const node_ptr &p)
 Effects: Reverses the order of elements in the list. More...
 
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. More...
 
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. More...
 
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. More...
 
template<class Pred >
static void stable_partition (node_ptr beg, const node_ptr &end, Pred pred, stable_partition_info &info)
 

Detailed Description

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

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

Member Typedef Documentation

template<class NodeTraits >
typedef NodeTraits::const_node_ptr boost::intrusive::circular_list_algorithms< NodeTraits >::const_node_ptr
template<class NodeTraits >
typedef NodeTraits::node boost::intrusive::circular_list_algorithms< NodeTraits >::node
template<class NodeTraits >
typedef NodeTraits::node_ptr boost::intrusive::circular_list_algorithms< NodeTraits >::node_ptr
template<class NodeTraits >
typedef NodeTraits boost::intrusive::circular_list_algorithms< NodeTraits >::node_traits

Member Function Documentation

template<class NodeTraits >
static std::size_t boost::intrusive::circular_list_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.

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::size().

template<class NodeTraits >
static std::size_t boost::intrusive::circular_list_algorithms< NodeTraits >::distance ( const const_node_ptr f,
const const_node_ptr l 
)
inlinestatic

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.

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

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::erase(), and boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::splice().

template<class NodeTraits >
static void boost::intrusive::circular_list_algorithms< NodeTraits >::init_header ( const node_ptr this_node)
inlinestatic
template<class NodeTraits >
static void boost::intrusive::circular_list_algorithms< NodeTraits >::link_after ( const node_ptr prev_node,
const node_ptr this_node 
)
inlinestatic

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.

References boost::next().

Referenced by boost::intrusive::circular_list_algorithms< NodeTraits >::move_forward().

template<class NodeTraits >
static void boost::intrusive::circular_list_algorithms< NodeTraits >::link_before ( const node_ptr nxt_node,
const node_ptr this_node 
)
inlinestatic
template<class NodeTraits >
static void boost::intrusive::circular_list_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.

Throws: Nothing.

Complexity: Linear to the number of moved positions.

References boost::xpressive::first, boost::intrusive::circular_list_algorithms< NodeTraits >::link_before(), and boost::intrusive::circular_list_algorithms< NodeTraits >::unlink().

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::shift_forward().

template<class NodeTraits >
static void boost::intrusive::circular_list_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.

Throws: Nothing.

Complexity: Linear to the number of moved positions.

References boost::last, boost::intrusive::circular_list_algorithms< NodeTraits >::link_after(), and boost::intrusive::circular_list_algorithms< NodeTraits >::unlink().

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::shift_backwards().

template<class NodeTraits >
static void boost::intrusive::circular_list_algorithms< NodeTraits >::reverse ( const node_ptr p)
inlinestatic

Effects: Reverses the order of elements in the list.

Throws: Nothing.

Complexity: This function is linear time.

References boost::multiprecision::backends::i, boost::n, and boost::intrusive::circular_list_algorithms< NodeTraits >::transfer().

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::reverse().

template<class NodeTraits >
static void boost::intrusive::circular_list_algorithms< NodeTraits >::transfer ( const node_ptr p,
const node_ptr b,
const node_ptr e 
)
inlinestatic

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.

Referenced by boost::intrusive::circular_list_algorithms< NodeTraits >::reverse(), and boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::splice().

template<class NodeTraits >
static void boost::intrusive::circular_list_algorithms< NodeTraits >::transfer ( const node_ptr p,
const node_ptr i 
)
inlinestatic

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.

References boost::n.

template<class NodeTraits >
static bool boost::intrusive::circular_list_algorithms< NodeTraits >::unique ( const const_node_ptr this_node)
inlinestatic

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.

References boost::next().

Referenced by boost::intrusive::list_impl< ValueTraits, SizeType, ConstantTimeSize, HeaderHolder >::empty().

template<class NodeTraits >
static void boost::intrusive::circular_list_algorithms< NodeTraits >::unlink ( const node_ptr b,
const node_ptr e 
)
inlinestatic

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.


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