Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

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

  // member classes/structs/unions

  struct stable_partition_info {

    // public data members
     num_1st_partition;
     num_2nd_partition;
     beg_2st_partition;
  };

  // public static functions
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   (, ) ;
   (, ) ;
   (, ) ;
   (, ) ;
   (, , ) ;
   (, ) ;
   () ;
   (, ) ;
   (, ) ;
   (, ) ;
  template<typename Pred> 
     (, , , 
                                 );

  // private static functions
   (, ) ;
   (, ) ;
};

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

  1.  ( this_node) ;

    Effects: Constructs an non-used list element, so that inited(this_node) == true

    Complexity: Constant

    Throws: Nothing.

  2.  ( this_node) ;

    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.

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

    Complexity: Constant

    Throws: Nothing.

  4.  ( this_node) ;

    Effects: Returns true if this_node_points to an empty list.

    Complexity: Constant

    Throws: Nothing.

  5.  ( 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: return NodeTraits::get_next(this_node) == this_node

    Complexity: Constant

    Throws: Nothing.

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

  7.  ( this_node) ;

    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.

  8.  ( b,  e) ;

    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.

  9.  ( 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: Constant

    Throws: Nothing.

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

  11.  ( 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: Constant

    Throws: Nothing.

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

  13.  ( p,  i) ;

    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.

  14.  ( p) ;

    Effects: Reverses the order of elements in the list.

    Throws: Nothing.

    Complexity: This function is linear time.

  15.  ( p,  n) ;

    Effects: Moves the node p n positions towards the end of the list.

    Throws: Nothing.

    Complexity: Linear to the number of moved positions.

  16.  ( p,  n) ;

    Effects: Moves the node p n positions towards the beginning of the list.

    Throws: Nothing.

    Complexity: Linear to the number of moved positions.

  17.  ( f,  l) ;

    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.

  18. template<typename Pred> 
       ( beg,  end,  pred, 
                                    info);

circular_list_algorithms private static functions

  1.  ( this_node,  other_node) ;
  2.  ( this_node,  other_node) ;

PrevUpHomeNext