#include <bslalg_rbtreeutil.h>

Static Public Member Functions
static const RbTreeNode *	leftmost (const RbTreeNode *subtree)
static RbTreeNode *	leftmost (RbTreeNode *subtree)
static const RbTreeNode *	rightmost (const RbTreeNode *subtree)
static RbTreeNode *	rightmost (RbTreeNode *subtree)
static const RbTreeNode *	next (const RbTreeNode *node)
static RbTreeNode *	next (RbTreeNode *node)
static const RbTreeNode *	previous (const RbTreeNode *node)
static RbTreeNode *	previous (RbTreeNode *node)
template<class NODE_VALUE_COMPARATOR , class VALUE >
static const RbTreeNode *	find (const RbTreeAnchor &tree, NODE_VALUE_COMPARATOR &comparator, const VALUE &value)
template<class NODE_VALUE_COMPARATOR , class VALUE >
static RbTreeNode *	find (RbTreeAnchor &tree, NODE_VALUE_COMPARATOR &comparator, const VALUE &value)
template<class NODE_VALUE_COMPARATOR , class VALUE >
static const RbTreeNode *	lowerBound (const RbTreeAnchor &tree, NODE_VALUE_COMPARATOR &comparator, const VALUE &value)
template<class NODE_VALUE_COMPARATOR , class VALUE >
static RbTreeNode *	lowerBound (RbTreeAnchor &tree, NODE_VALUE_COMPARATOR &comparator, const VALUE &value)
template<class NODE_VALUE_COMPARATOR , class VALUE >
static const RbTreeNode *	upperBound (const RbTreeAnchor &tree, NODE_VALUE_COMPARATOR &comparator, const VALUE &value)
template<class NODE_VALUE_COMPARATOR , class VALUE >
static RbTreeNode *	upperBound (RbTreeAnchor &tree, NODE_VALUE_COMPARATOR &comparator, const VALUE &value)
template<class FACTORY >
static void	copyTree (RbTreeAnchor result, const RbTreeAnchor &original, FACTORY nodeFactory)
template<class FACTORY >
static void	moveTree (RbTreeAnchor result, RbTreeAnchor original, FACTORY nodeFactory, FACTORY originalNodeFactory)
template<class FACTORY >
static void	deleteTree (RbTreeAnchor tree, FACTORY nodeFactory)
template<class NODE_VALUE_COMPARATOR , class VALUE >
static RbTreeNode *	findInsertLocation (bool insertAsLeftChildFlag, RbTreeAnchor tree, NODE_VALUE_COMPARATOR &comparator, const VALUE &value)
template<class NODE_VALUE_COMPARATOR , class VALUE >
static RbTreeNode *	findInsertLocation (bool insertAsLeftChildFlag, RbTreeAnchor tree, NODE_VALUE_COMPARATOR &comparator, const VALUE &value, RbTreeNode *hint)
template<class NODE_VALUE_COMPARATOR , class VALUE >
static RbTreeNode *	findUniqueInsertLocation (int comparisonResult, RbTreeAnchor tree, NODE_VALUE_COMPARATOR &comparator, const VALUE &value)
template<class NODE_VALUE_COMPARATOR , class VALUE >
static RbTreeNode *	findUniqueInsertLocation (int comparisonResult, RbTreeAnchor tree, NODE_VALUE_COMPARATOR &comparator, const VALUE &value, RbTreeNode *hint)
template<class NODE_COMPARATOR >
static void	insert (RbTreeAnchor tree, const NODE_COMPARATOR &comparator, RbTreeNode newNode)
static void	insertAt (RbTreeAnchor tree, RbTreeNode parentNode, bool leftChildFlag, RbTreeNode *newNode)
static void	remove (RbTreeAnchor tree, RbTreeNode node)
static void	swap (RbTreeAnchor a, RbTreeAnchor b)
static bool	isLeftChild (const RbTreeNode *node)
static bool	isRightChild (const RbTreeNode *node)
static void	rotateLeft (RbTreeNode *node)
static void	rotateRight (RbTreeNode *node)
static void	printTreeStructure (FILE file, const RbTreeNode subtree, void(printNodeValueCallback)(FILE , const RbTreeNode *), int level=0, int spacesPerLevel=4)
template<class NODE_COMPARATOR >
static int	validateRbTree (const RbTreeNode *rootNode, const NODE_COMPARATOR &comparator)
template<class NODE_COMPARATOR >
static int	validateRbTree (const RbTreeNode errorNode, const char errorDescription, const RbTreeNode *rootNode, const NODE_COMPARATOR &comparator)
template<class NODE_COMPARATOR >
static bool	isWellFormed (const RbTreeAnchor &tree, const NODE_COMPARATOR &comparator)

Detailed Description

This struct provides a namespace for a suite of utility functions that operate on elements of type RbTreeNode.

Each method of this class, other than copyTree, provides the no-throw exception guarantee if the client-supplied comparator provides the no-throw guarantee, and provides the strong guarantee otherwise (see bsldoc_glossary). copyTree provides the strong guarantee.

See Component bslalg_rbtreeutil

Member Function Documentation

static const RbTreeNode* bslalg::RbTreeUtil::leftmost ( const RbTreeNode * subtree ) [static]

static RbTreeNode* bslalg::RbTreeUtil::leftmost ( RbTreeNode * subtree ) [static]

Return the address of the leftmost node in the specified subtree, and subtree if subtree has no left child. The behavior is undefined unless 0 != subtree, and subtree refers to a valid binary tree. Note that the value held by the returned node will not compare greater than that of any other node in subtree (as determined by the comparator used to organize the red-black subtree data).

static const RbTreeNode* bslalg::RbTreeUtil::rightmost ( const RbTreeNode * subtree ) [static]

static RbTreeNode* bslalg::RbTreeUtil::rightmost ( RbTreeNode * subtree ) [static]

Return the address of the rightmost node in the specified subtree, and subtree if subtree has no right child. The behavior is undefined unless 0 != subtree and subtree refers to a valid binary tree. Note that the value held by the returned node will not compare less than that of any other node in subtree (as determined by the comparator used to organize the red-black subtree data).

static const RbTreeNode* bslalg::RbTreeUtil::next ( const RbTreeNode * node ) [static]

static RbTreeNode* bslalg::RbTreeUtil::next ( RbTreeNode * node ) [static]

Return the address of the node that follows the specified node in an in-order traversal of the binary tree to which node belongs, or the tree's sentinel node if node is the rightmost node in the tree. The behavior is undefined unless node is a member of a valid binary tree, and is not a sentinel node. Note that if the tree does not contain duplicate values, then the returned node will have the smallest value greater than that of node.

static const RbTreeNode* bslalg::RbTreeUtil::previous ( const RbTreeNode * node ) [static]

static RbTreeNode* bslalg::RbTreeUtil::previous ( RbTreeNode * node ) [static]

Return the address of the node that precedes the specified node in an in-order traversal of the binary tree to which node belongs, or the tree's rightmost node if node is the sentinel node of the tree. The behavior is undefined unless or node is a non-leftmost member of a valid binary tree or is a sentinel node. Note that if the tree does not contain duplicate values, then the returned node will have the largest value less than that of node.

template<class NODE_VALUE_COMPARATOR , class VALUE >

static const RbTreeNode* bslalg::RbTreeUtil::find	(	const RbTreeAnchor &	tree,
		NODE_VALUE_COMPARATOR &	comparator,
		const VALUE &	value
	)			`[static]`

template<class NODE_VALUE_COMPARATOR , class VALUE >

static RbTreeNode* bslalg::RbTreeUtil::find	(	RbTreeAnchor &	tree,
		NODE_VALUE_COMPARATOR &	comparator,
		const VALUE &	value
	)			`[static]`

Return the address of the leftmost node holding the specified value in the specified tree (organized according to the specified comparator) if found, and return 'tree.sentinel() otherwise. COMPARATOR shall be a functor providing two methods that can be called as if they had the following signatures:

          bool operator()(const RbTreeNode&, const VALUE&) const;
          bool operator()(const VALUE&, const RbTreeNode&) const;

The behavior is undefined unless comparator provides a strict weak ordering on objects of type VALUE, and tree is well-formed (see isWellFormed).

template<class NODE_VALUE_COMPARATOR , class VALUE >

static const RbTreeNode* bslalg::RbTreeUtil::lowerBound	(	const RbTreeAnchor &	tree,
		NODE_VALUE_COMPARATOR &	comparator,
		const VALUE &	value
	)			`[static]`

template<class NODE_VALUE_COMPARATOR , class VALUE >

static RbTreeNode* bslalg::RbTreeUtil::lowerBound	(	RbTreeAnchor &	tree,
		NODE_VALUE_COMPARATOR &	comparator,
		const VALUE &	value
	)			`[static]`

Return the address of the leftmost node holding the smallest value greater-than or equal-to value in the specified tree (organized according to the specified 'comparator) if found, and return tree.sentinel() if value is greater-than the rightmost node in tree. COMPARATOR shall be a functor providing two methods that can be called as if they had the following signatures:

          bool operator()(const RbTreeNode&, const VALUE&) const;
          bool operator()(const VALUE&, const RbTreeNode&) const;

The behavior is undefined unless comparator provides a strict weak ordering on objects of type VALUE, and tree is well-formed (isWellFormed). Note that this function returns the first position before which value could be inserted into tree while preserving its ordering.

template<class NODE_VALUE_COMPARATOR , class VALUE >

static const RbTreeNode* bslalg::RbTreeUtil::upperBound	(	const RbTreeAnchor &	tree,
		NODE_VALUE_COMPARATOR &	comparator,
		const VALUE &	value
	)			`[static]`

template<class NODE_VALUE_COMPARATOR , class VALUE >

static RbTreeNode* bslalg::RbTreeUtil::upperBound	(	RbTreeAnchor &	tree,
		NODE_VALUE_COMPARATOR &	comparator,
		const VALUE &	value
	)			`[static]`

Return the address of the leftmost node holding the smallest value greater-than value in the specified tree (organized according to the specified 'comparator) if found, and return tree.sentinel() if value is greater-than or equal-to the rightmost node in tree. COMPARATOR shall be a functor providing two methods that can be called as if they had the following signatures:

          bool operator()(const RbTreeNode&, const VALUE&) const;
          bool operator()(const VALUE&, const RbTreeNode&) const;

The behavior is undefined unless comparator provides a strict weak ordering on objects of type VALUE, and tree is well-formed (isWellFormed). Note that this function returns the last position before which value could be inserted into tree while preserving its ordering.

template<class FACTORY >

static void bslalg::RbTreeUtil::copyTree	(	RbTreeAnchor *	result,
		const RbTreeAnchor &	original,
		FACTORY *	nodeFactory
	)			`[static]`

Load, into the specified result, a collection of newly created nodes having the same red-black tree structure as that of the specified original tree, where each node in the returned tree is created by invoking nodeFactory->createNode on the corresponding original node; if an exception occurs, use nodeFactory->deleteNode to destroy any newly created nodes, and propagate the exception to the caller (i.e., this operation provides the strong exception guarantee). FACTORY shall be a class providing two methods that can be called as if they had the following signatures:

          RbTreeNode *createNode(const RbTreeNode&);
          void deleteNode(RbTreeNode *);

The behavior is undefined unless result is an empty tree, original is a well-formed (see isWellFormed), and nodeFactory->deleteNode does not throw.

template<class FACTORY >

static void bslalg::RbTreeUtil::moveTree	(	RbTreeAnchor *	result,
		RbTreeAnchor *	original,
		FACTORY *	nodeFactory,
		FACTORY *	originalNodeFactory
	)			`[static]`

Load into the specified result, using the specified nodeFactory to create and delete nodes, a collection of newly created nodes with the same (red-black) tree structure as that of the specified original tree, which uses the specified originalNodeFactory to create and delete nodes, where the value attribute of each node in result is constructed from explicitly moving the value attribute of the corresponding node in original. original is left in a valid but unspecified state. If an exception occurs, both result and original are left in a valid but unspecified state. The behavior is undefined unless result is an empty tree, original is well-formed (see isWellFormed), and nodeFactory->deleteNode and originalNodeFactory->deleteNode do not throw.

template<class FACTORY >

static void bslalg::RbTreeUtil::deleteTree	(	RbTreeAnchor *	tree,
		FACTORY *	nodeFactory
	)			`[static]`

Call nodeFactory->deleteNode on each node in tree and reset tree to an empty state. FACTORY shall be a class providing a method that can be called as if it has the following signature:

          void deleteNode(RbTreeNode *);

The behavior is undefined unless tree is a valid binary tree, and nodeFactory->deleteNode does not throw.

template<class NODE_VALUE_COMPARATOR , class VALUE >

static RbTreeNode* bslalg::RbTreeUtil::findInsertLocation	(	bool *	insertAsLeftChildFlag,
		RbTreeAnchor *	tree,
		NODE_VALUE_COMPARATOR &	comparator,
		const VALUE &	value
	)			`[static]`

template<class NODE_VALUE_COMPARATOR , class VALUE >

static RbTreeNode* bslalg::RbTreeUtil::findInsertLocation	(	bool *	insertAsLeftChildFlag,
		RbTreeAnchor *	tree,
		NODE_VALUE_COMPARATOR &	comparator,
		const VALUE &	value,
		RbTreeNode *	hint
	)			`[static]`

Return the address of the node that would be the parent a node holding the specified value, if it were to be inserted into the specified tree (organized according to the specified comparator), and load, into the specified insertAsLeftChildFlag, true if value would be held as the returned node's left child, and false if value would be held in its right child, unless tree is empty, in which case return tree->sentinel() and load true into insertAsLeftChildFlag. Optionally specify a hint, suggesting a node in tree that might be the immediate successor of a node holding value if it were to be inserted into tree. If the supplied hint is the successor, this operation will take amortized constant time; otherwise, it will take O(log(N)) operations, where N is the number of nodes in the tree. If a node holding value is inserted as suggested by this method, the resulting tree will be an ordered binary tree, but may require rebalancing (and re-coloring) to again be a valid red-black tree. COMPARATOR shall be a functor providing two methods that can be called as if they have the following signatures:

          bool operator()(const RbTreeNode&, const VALUE&) const;
          bool operator()(const VALUE&, const RbTreeNode&) const;

The behavior is undefined unless comparator provides a strict weak ordering on objects of type VALUE, tree is well-formed (see isWellFormed), and hint, if supplied, is a node in tree. Note that this operation is intended to be used in conjunction with the insertAt method.

template<class NODE_VALUE_COMPARATOR , class VALUE >

static RbTreeNode* bslalg::RbTreeUtil::findUniqueInsertLocation	(	int *	comparisonResult,
		RbTreeAnchor *	tree,
		NODE_VALUE_COMPARATOR &	comparator,
		const VALUE &	value
	)			`[static]`

template<class NODE_VALUE_COMPARATOR , class VALUE >

static RbTreeNode* bslalg::RbTreeUtil::findUniqueInsertLocation	(	int *	comparisonResult,
		RbTreeAnchor *	tree,
		NODE_VALUE_COMPARATOR &	comparator,
		const VALUE &	value,
		RbTreeNode *	hint
	)			`[static]`

Return the address of the node holding the specified value in the specified tree (organized according to the specified comparator) if found, and the address of the node that would be the parent for value otherwise; load, into the specified comparisonResult, 0 if value is found, a negative number if value would be held in its left child, and a positive number if value would be held in its right child, unless tree is empty, in which case load a negative number into comparisonResult and return tree->sentinel(). Optionally specify a hint, suggesting a node in tree that might be the immediate successor of a node holding value if it were to be inserted into tree. If the supplied hint is the successor, this operation will take amortized constant time; otherwise, it will take O(log(N)) operations, where N is the number of nodes in the tree. If a node holding value is inserted as suggested by this method, the resulting tree will be an ordered binary tree, but may require rebalancing (and re-coloring) to again be a valid red-black tree. COMPARATOR shall be a functor providing two methods that can be called as if they have the following signatures:

          bool operator()(const RbTreeNode&, const VALUE&) const;
          bool operator()(const VALUE&, const RbTreeNode&) const;

The behavior is undefined unless comparator provides a strict weak ordering on objects of type VALUE, tree is well-formed (see isWellFormed), and hint, if supplied, is a node in tree. Note that this operation is intended to be used in conjunction with the insertAt method.

template<class NODE_COMPARATOR >

static void bslalg::RbTreeUtil::insert	(	RbTreeAnchor *	tree,
		const NODE_COMPARATOR &	comparator,
		RbTreeNode *	newNode
	)			`[static]`

Insert the specified newNode into the specified tree, organized according to the specified comparator. The resulting tree will be well-formed (see isWellFormed). NODE_COMPARATOR shall be a functor providing a method that can be called as if it had the following signatures:

          bool operator()(const RbTreeNode&, const RbTreeNode&) const;

The behavior is undefined unless comparator provides a strict weak ordering on objects of type VALUE, and tree is well-formed (see isWellFormed).

static void bslalg::RbTreeUtil::insertAt	(	RbTreeAnchor *	tree,
		RbTreeNode *	parentNode,
		bool	leftChildFlag,
		RbTreeNode *	newNode
	)			`[static]`

Insert the specified newNode into the specified tree as either the left or right child of the specified parentNode, as indicated by the specified leftChildFlag, and then rebalance the tree so that it is a valid red-black tree (see validateRbTree). The behavior is undefined unless tree is well-formed (see isWellFormed), and, if tree is empty, parentNode is tree->sentinel() and leftChildFlag is true, or, if tree is not empty, parentNode is a node in tree whose left or right child (as indicated by leftChildFlag) is 0 where if newNode were attached as that child (without rebalancing) tree would still form an ordered binary tree (though not necessarily a valid red-black tree). Note that this operation is intended to be used in conjunction with the findInsertLocation or findUniqueInsertLocation methods.

static void bslalg::RbTreeUtil::remove	(	RbTreeAnchor *	tree,
		RbTreeNode *	node
	)			`[static]`

Remove the specified node from the specified tree, and then rebalance tree so that it again forms a valid red-black tree (see validateRbTree). The behavior is undefined unless tree is well-formed (see isWellFormed).

static void bslalg::RbTreeUtil::swap	(	RbTreeAnchor *	a,
		RbTreeAnchor *	b
	)			`[static]`

Efficiently exchange the nodes in the specified a tree with the nodes in the specified b tree. This method provides the no-throw exception-safety guarantee. The behavior is undefined unless a and b are well-formed (see isWellFormed).

static bool bslalg::RbTreeUtil::isLeftChild ( const RbTreeNode * node ) [static]

Return true if the specified node is the left child of its parent, and false otherwise. The behavior is undefined unless 0 != node->parent().

static bool bslalg::RbTreeUtil::isRightChild ( const RbTreeNode * node ) [static]

Return true if the specified node is the left child of its parent, and false otherwise. The behavior is undefined unless 0 != node->parent().

static void bslalg::RbTreeUtil::rotateLeft ( RbTreeNode * node ) [static]

Perform counter-clockwise rotation on the specified node: Rotate the node's right child (the pivot) to be the node's parent, and attach the pivot's left child as the node's right child.

             (node)              (pivot)
             /    \              /     \.
            a   (pivot)  --->  (node)   c
                 /   \         /    \.
                b     c       a      b

The behavior is undefined unless node->rightChild() is not 0, node->parent() is not 0, and node's parent refers to node as one of its children. Note that this operation maintains the ordering of the subtree rooted at node. Also note this operation will successfully rotate the root node of an unbalanced, but otherwise well-formed, tree referred to by a RbTreeAnchor object (see isWellFormed) because the parent of the root node is the tree's sentinel node (i.e., not 0), which refers to the root node as its left child, and an RbTreeAnchor object returns the left child of the sentinel node as the root of the tree.

static void bslalg::RbTreeUtil::rotateRight ( RbTreeNode * node ) [static]

Perform clockwise rotation on the specified node: Rotate the node's left child (the pivot) to be the node's parent, and attach the pivot's right child as the node's left child.

               (node)            (pivot)
               /    \            /     \.
           (pivot)   c   --->   a     (node)
            /  \                      /    \.
           a    b                    b      c

The behavior is undefined unless node->leftChild() is not 0, node->parent() is not 0, and node's parent refers to node as one of its children. Note that this operation maintains the ordering of the subtree rooted at node. Also note this operation will successfully rotate the root node of an unbalanced, but otherwise well-formed, tree referred to by a RbTreeAnchor object (see isWellFormed) because the parent of the root node is the tree's sentinel node (i.e., not 0), which refers to the root node as its left child, and an RbTreeAnchor object returns the left child of the sentinel node as the root of the tree.

static void bslalg::RbTreeUtil::printTreeStructure	(	FILE *	file,
		const RbTreeNode *	subtree,
		void()(FILE , const RbTreeNode *)	printNodeValueCallback,
		int	level = `0`,
		int	spacesPerLevel = `4`
	)			`[static]`

Write a description of the structure of the specified subtree to the specified output file in a human-readable format, using the specified printValueCallback to render the value of each node. Optionally specify an initial indentation level, whose absolute value is incremented recursively for nested objects. If level is specified, optionally specify spacesPerLevel, whose absolute value indicates the number of spaces per indentation level for this and all of its nested objects. If level is negative, suppress indentation of the first line. If spacesPerLevel is negative, format the entire output on one line, suppressing all but the initial indentation (as governed by level). The behavior is undefined unless node is 0, or the root of a valid binary tree. Note that the implementation of this function is recursive and expensive to perform, it is intended for debugging purposes only. Also note that the format is not fully specified, and can change without notice.

template<class NODE_COMPARATOR >

static int bslalg::RbTreeUtil::validateRbTree	(	const RbTreeNode *	rootNode,
		const NODE_COMPARATOR &	comparator
	)			`[static]`

template<class NODE_COMPARATOR >

static int bslalg::RbTreeUtil::validateRbTree	(	const RbTreeNode **	errorNode,
		const char **	errorDescription,
		const RbTreeNode *	rootNode,
		const NODE_COMPARATOR &	comparator
	)			`[static]`

Return the (common) number of black nodes on each path from the specified rootNode to a leaf in the tree, 0 if rootNode is 0, and a negative number if rootNode does not refer to a valid red-black binary search tree, ordered according to the specified comparator. Optionally specify errorNode and errorDescription in which to load the address of a node violating a red-black tree constraint and a description of that violation, respectively. The behavior is undefined unless rootNode is 0, or refers to a valid binary tree.

Each node of a red-black tree is colored either red or black; null nodes are considered black. Four requirements must be satisfied for rootNode to refer to a valid red-black binary search tree:

For each node in the tree, no descendents to the left of that node would order after that node (according to the comparator), and no descendents to the right of that node would order before it.
For each node in the tree, each non-null child of that node refers to that node as its parent.
If a node in the tree is colored red, all its children are colored black or are null (which is considered black).
For each node in the tree, every path from that node to a leaf contains the same number of black nodes, where null children are considered black leaf nodes.

The behavior is undefined unless rootNode is 0, or refers to a valid binary tree. Note that the implementation of this function is recursive and has linear complexity with respect to the number of nodes in tree, it is intended for debugging purposes only.

template<class NODE_COMPARATOR >

static bool bslalg::RbTreeUtil::isWellFormed	(	const RbTreeAnchor &	tree,
		const NODE_COMPARATOR &	comparator
	)			`[static]`

Return true if the specified tree is well-formed and refers to a valid red-black tree, and false otherwise. For a RbTreeAnchor to be considered well-formed all of the following must be true:

tree.rootNode() must refer to a valid red-black tree, whose nodes are organized according to comparator (see validateRbTree).
tree.firstNode() must refer to tree.sentinel() if tree.rootNode() is 0, and leftmost(tree.rootNode())' otherwise.
tree.nodeCount() must be the count of nodes in tree (not including the sentinel node).
tree.sentinel()->leftchild() is tree.rootNode(), and (if tree.rootNode() is not 0) tree.rootNode()->parent() is tree.sentinel().
tree.rootNode() is 0 or tree.rootNode().isBlack() is true

The behavior is undefined unless tree.rootNode() is 0 or refers to a valid binary tree. Note that the implementation of this function is recursive and has linear complexity with respect to the number of nodes in tree, it is intended for debugging purposes only. Note also that the final condition, that the root node be either 0 or colored black, is not a canonical requirement of a red-black tree but an additional invariant enforced by the methods of RbTreeUtil to simplify the implementations.

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

bslalg_rbtreeutil.h

bslalg::RbTreeUtil Struct Reference

Static Public Member Functions

Detailed Description

Member Function Documentation