bslalg::RbTreeUtil_Validator Struct Reference

#include <bslalg_rbtreeutil.h>

List of all members.

Static Public Member Functions
template<class NODE_COMPARATOR >
static int	validateRbTree (const RbTreeNode **errorNode, const char **errorDescription, const RbTreeNode *rootNode, const RbTreeNode *minNodeValue, const RbTreeNode *maxNodeValue, const NODE_COMPARATOR &comparator)
static bool	isWellFormedAnchor (const RbTreeAnchor &tree)

---

Detailed Description

This struct provides a namespace for auxiliary functions used to validate a red-black binary search tree.

See Component bslalg_rbtreeutil

---

Member Function Documentation

template<class NODE_COMPARATOR >

static int bslalg::RbTreeUtil_Validator::validateRbTree	(	const RbTreeNode **	errorNode,
		const char **	errorDescription,
		const RbTreeNode *	rootNode,
		const RbTreeNode *	minNodeValue,
		const RbTreeNode *	maxNodeValue,
		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) that contains no nodes whose value is less than the specified minNodeValue (if not 0) or greater-than the specified maxNodeValue (if not 0). If rootNode does not refer to a valid red-black tree containing nodes whose values are between the specified minNodeValue and maxNodeValue (inclusively) then load errorNode and errorDescription with 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.

static bool bslalg::RbTreeUtil_Validator::isWellFormedAnchor

(

const RbTreeAnchor &

tree

)

[static]

Return true if the specified tree is well-formed, without confirming that it refers to a valid-red-black tree, and false otherwise. This method will return true if all of the following are true:

1. tree.firstNode() must refer to tree.sentinel() if tree.rootNode() is 0, and leftmost(tree.rootNode())' otherwise.
2. tree.nodeCount() must be the count of nodes in tree (not including the sentinel node).
3. tree.sentinel()->leftchild() is tree.rootNode(), and (if tree.rootNode() is not 0), tree.rootNode()->parent() is 'tree.sentinel().
4. 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 this function provides a non-templatized implementation for several criteria of a well-formed tree (but not the complete set verified by RbTreeUtil::isWellFormed).

---

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

• bslalg_rbtreeutil.h