|
Home | Libraries | People | FAQ | More |
boost::intrusive::avltree_algorithms
// In header: <boost/intrusive/avltree_algorithms.hpp> template<typename NodeTraits> class avltree_algorithms { public: // types typedef ; typedef ; typedef ; typedef ; typedef ; typedef ; // public static functions () ; () ; () ; (, ) ; (, ) ; (, , , ) ; (, ) ; (, , ) ; () ; () ; () ; () ; () ; () ; () ; () ; (, ) ; template<typename NodePtrCompare> (, , , ); template<typename NodePtrCompare> (, , , ); template<typename Cloner, typename Disposer> (, , , ); template<typename Disposer> (, ) ; template<typename KeyType, typename KeyNodePtrCompare> (, , ); template<typename KeyType, typename KeyNodePtrCompare> (, , ); template<typename KeyType, typename KeyNodePtrCompare> (, , ); template<typename KeyType, typename KeyNodePtrCompare> (, , ); template<typename KeyType, typename KeyNodePtrCompare> (, , , , , ); template<typename KeyType, typename KeyNodePtrCompare> (, , ); template<typename NodePtrCompare> (, , ); template<typename NodePtrCompare> (, , ); template<typename NodePtrCompare> (, , , ); (, , ) ; (, ) ; (, ) ; template<typename KeyType, typename KeyNodePtrCompare> (, , , ); template<typename KeyType, typename KeyNodePtrCompare> (, , , , ); (, , ) ; () ; };
avltree_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 binary search tree
node_ptr: A pointer to a node
const_node_ptr: A pointer to a const node
balance: The type of the balance factor
Static functions:
static node_ptr get_parent(const_node_ptr n);
static void set_parent(node_ptr n, node_ptr parent);
static node_ptr get_left(const_node_ptr n);
static void set_left(node_ptr n, node_ptr left);
static node_ptr get_right(const_node_ptr n);
static void set_right(node_ptr n, node_ptr right);
static balance get_balance(const_node_ptr n);
static void set_balance(node_ptr n, balance b);
static balance negative();
static balance zero();
static balance positive();
avltree_algorithms public static functions( n) ;
Requires: 'n' is a node of the tree or a header node.
Effects: Returns the header of the tree.
Complexity: Logarithmic.
Throws: Nothing.
( header) ;
Requires: 'header' is the header node of a tree.
Effects: Returns the first node of the tree, the header if the tree is empty.
Complexity: Constant time.
Throws: Nothing.
( header) ;
Requires: 'header' is the header node of a tree.
Effects: Returns the header of the tree.
Complexity: Constant time.
Throws: Nothing.
( header1, header2) ;
Requires: header1 and header2 must be the header nodes of two trees.
Effects: Swaps two trees. After the function header1 will contain links to the second tree and header2 will have links to the first tree.
Complexity: Constant.
Throws: Nothing.
( node1, node2) ;
Requires: node1 and node2 can't be header nodes of two trees.
Effects: Swaps two nodes. After the function node1 will be inserted in the position node2 before the function. node2 will be inserted in the position node1 had before the function.
Complexity: Logarithmic.
Throws: Nothing.
Note: This function will break container ordering invariants if node1 and node2 are not equivalent according to the ordering rules.
Experimental function
( node1, header1, node2, header2) ;
Requires: node1 and node2 can't be header nodes of two trees with header header1 and header2.
Effects: Swaps two nodes. After the function node1 will be inserted in the position node2 before the function. node2 will be inserted in the position node1 had before the function.
Complexity: Constant.
Throws: Nothing.
Note: This function will break container ordering invariants if node1 and node2 are not equivalent according to the ordering rules.
Experimental function
( node_to_be_replaced, new_node) ;
Requires: node_to_be_replaced must be inserted in a tree and new_node must not be inserted in a tree.
Effects: Replaces node_to_be_replaced in its position in the tree with new_node. The tree does not need to be rebalanced
Complexity: Logarithmic.
Throws: Nothing.
Note: This function will break container ordering invariants if new_node is not equivalent to node_to_be_replaced according to the ordering rules. This function is faster than erasing and inserting the node, since no rebalancing and comparison is needed. Experimental function
( node_to_be_replaced, header, new_node) ;
Requires: node_to_be_replaced must be inserted in a tree with header "header" and new_node must not be inserted in a tree.
Effects: Replaces node_to_be_replaced in its position in the tree with new_node. The tree does not need to be rebalanced
Complexity: Constant.
Throws: Nothing.
Note: This function will break container ordering invariants if new_node is not equivalent to node_to_be_replaced according to the ordering rules. This function is faster than erasing and inserting the node, since no rebalancing or comparison is needed. Experimental function
( n) ;
Requires: 'n' is a tree node but not the header.
Effects: Unlinks the node and rebalances the tree.
Complexity: Average complexity is constant time.
Throws: Nothing.
( header) ;
Requires: header is the header of a tree.
Effects: Unlinks the leftmost node from the tree, and updates the header link to the new leftmost node.
Complexity: Average complexity is constant time.
Throws: Nothing.
Notes: This function breaks the tree and the tree can only be used for more unlink_leftmost_without_rebalance calls. This function is normally used to achieve a step by step controlled destruction of the tree.
( n) ;
Requires: 'n' is a node of the tree or a node initialized by init(...) or init_node.
Effects: Returns true if the node is initialized by init() or init_node().
Complexity: Constant time.
Throws: Nothing.
( header) ;
Requires: 'header' the header of the tree.
Effects: Returns the number of nodes of the tree.
Complexity: Linear time.
Throws: Nothing.
( n) ;
Requires: 'n' is a node from the tree except the header.
Effects: Returns the next node of the tree.
Complexity: Average constant time.
Throws: Nothing.
( n) ;
Requires: 'n' is a node from the tree except the leftmost node.
Effects: Returns the previous node of the tree.
Complexity: Average constant time.
Throws: Nothing.
( n) ;
Requires: 'n' must not be part of any tree.
Effects: After the function unique(node) == true.
Complexity: Constant.
Throws: Nothing.
Nodes: If node is inserted in a tree, this function corrupts the tree.
( header) ;
Requires: header must not be part of any tree.
Effects: Initializes the header to represent an empty tree. unique(header) == true.
Complexity: Constant.
Throws: Nothing.
Nodes: If header is inserted in a tree, this function corrupts the tree.
( header, z) ;
Requires: header must be the header of a tree, z a node of that tree and z != header.
Effects: Erases node "z" from the tree with header "header".
Complexity: Amortized constant time.
Throws: Nothing.
template<typename NodePtrCompare> ( header1, comp, header2, z);
Requires: header1 and header2 must be the headers of trees tree1 and tree2 respectively, z a non-header node of tree1. NodePtrCompare is the comparison function of tree1..
Effects: Transfers node "z" from tree1 to tree2 if tree1 does not contain a node that is equivalent to z.
Returns: True if the node was trasferred, false otherwise.
Complexity: Logarithmic.
Throws: If the comparison throws.
template<typename NodePtrCompare> ( header1, comp, header2, z);
Requires: header1 and header2 must be the headers of trees tree1 and tree2 respectively, z a non-header node of tree1. NodePtrCompare is the comparison function of tree1..
Effects: Transfers node "z" from tree1 to tree2.
Complexity: Logarithmic.
Throws: If the comparison throws.
template<typename Cloner, typename Disposer> ( source_header, target_header, cloner, disposer);
Requires: "cloner" must be a function object taking a node_ptr and returning a new cloned node of it. "disposer" must take a node_ptr and shouldn't throw.
Effects: First empties targetclass functor call throws.