BloombergLP::bslalg::RbTreeUtil::findUniqueInsertLocation

Synopses

Declared in <bslalg_rbtreeutil.h>

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_VALUE_COMPARATOR,
    class VALUE>
static
RbTreeNode*
findUniqueInsertLocation(
    int* comparisonResult,
    RbTreeAnchor* tree,
    NODE_VALUE_COMPARATOR& comparator,
    VALUE const& value);

» more...

Return the address of the node holding the specified value in the specified tree, or the parent for value otherwise, using the specified hint to improve performance when it is the immediate successor.

template<
    class NODE_VALUE_COMPARATOR,
    class VALUE>
static
RbTreeNode*
findUniqueInsertLocation(
    int* comparisonResult,
    RbTreeAnchor* tree,
    NODE_VALUE_COMPARATOR& comparator,
    VALUE const& value,
    RbTreeNode* hint);

» more...