bslalg_rbtreenode.h

Go to the documentation of this file.

/// @file bslalg_rbtreenode.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslalg_rbtreenode.h                                                -*-C++-*-
#ifndef INCLUDED_BSLALG_RBTREENODE
#define INCLUDED_BSLALG_RBTREENODE
 
#include <bsls_ident.h>
BSLS_IDENT("$Id$ $CSID$")
 
/// @defgroup bslalg_rbtreenode bslalg_rbtreenode
/// @brief  Provide a base class for a red-black binary tree node.
/// @addtogroup bsl
/// @{
/// @addtogroup bslalg
/// @{
/// @addtogroup bslalg_rbtreenode
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslalg_rbtreenode-purpose"> Purpose</a>
/// * <a href="#bslalg_rbtreenode-classes"> Classes </a>
/// * <a href="#bslalg_rbtreenode-description"> Description </a>
///   * <a href="#bslalg_rbtreenode-storing-color-information"> Storing Color Information </a>
///   * <a href="#bslalg_rbtreenode-usage"> Usage </a>
///     * <a href="#bslalg_rbtreenode-example-1-creating-a-function-to-print-a-red-black-tree"> Example 1: Creating a Function to Print a Red Black Tree </a>
///     * <a href="#bslalg_rbtreenode-example-2-creating-a-simple-red-black-tree"> Example 2: Creating a Simple Red-Black Tree </a>
///     * <a href="#bslalg_rbtreenode-example-3-creating-a-function-to-validate-a-red-black-tree"> Example 3: Creating a Function To Validate a Red-Black Tree </a>
///
/// # Purpose {#bslalg_rbtreenode-purpose}
/// Provide a base class for a red-black binary tree node.
///
/// # Classes {#bslalg_rbtreenode-classes}
///
/// -  bslalg::RbTreeNode: base class for a red-black binary tree node
///
/// @see  bslalg_rbtreeutil
///
/// # Description {#bslalg_rbtreenode-description}
/// This component provides a single POD-like class, `RbTreeNode`,
/// used to represent a node in a red-black binary search tree.  An `RbTreeNode`
/// provides the address to its parent, left-child, and right-child nodes, as
/// well as providing a "color" (red or black).  `RbTreeNode` does not, however,
/// contain "payload" data (e.g., a value), as it is intended to work with
/// generalized tree operations (see @ref bslalg_rbtreenodeutil ).  Clients creating
/// a red-black binary search tree must define their own node type that
/// incorporates `RbTreeNode` (generally via inheritance), and that maintains
/// the "key" value and any associated data.
///
/// ## Storing Color Information {#bslalg_rbtreenode-storing-color-information}
///
///
/// To reduce the memory footprint of the `RbTreeNode`, the color information is
/// stored at the least-significant-bit (LSB) of the parent node.  The address
/// of the parent node and the color can be accessed through bit-wise
/// operations.  This is possible because all memory addresses are at least
/// 4-bytes aligned, therefore, the 2 LSB of any pointer are always 0.
///
/// ## Usage {#bslalg_rbtreenode-usage}
///
///
/// This section illustrates intended usage of this component.
///
/// ### Example 1: Creating a Function to Print a Red Black Tree {#bslalg_rbtreenode-example-1-creating-a-function-to-print-a-red-black-tree}
///
///
/// This example demonstrates creating a function that prints, to a `FILE`, a
/// tree of `RbTreeNode` objects.
///
/// First, we define the signature of a function, `printTree`, that accepts, in
/// addition to an output file and root node, a function pointer argument
/// (supplied by clients) used to print each node's value, note that a node's
/// value is not accessible through `RbTreeNode`:
/// @code
/// void printTree(FILE             *output,
///                const RbTreeNode *rootNode,
///                void (*printNodeValueCallback)(FILE *, const RbTreeNode *))
/// {
/// @endcode
/// Now, we define the body of `printTree`, which is a recursive function that
/// performs a prefix traversal of the supplied binary tree, printing the value
/// and color of `rootNode` before recursively printing its left and then right
/// sub-trees.
/// @code
///     if (0 == rootNode) {
///         return;                                                   // RETURN
///     }
///     fprintf(output, " [ ");
///
///     // Print the value and color of 'rootNode'.
///
///     printNodeValueCallback(output, rootNode);
///     fprintf(output,
///             ": %s",
///             rootNode->color() == RbTreeNode::BSLALG_RED ? "RED" : "BLACK");
///
///     // Recursively call 'printTree' on the left and right sub-trees.
///
///     printTree(output, rootNode->leftChild(), printNodeValueCallback);
///     printTree(output, rootNode->rightChild(), printNodeValueCallback);
///     fprintf(output, " ]");
/// }
/// @endcode
/// Notice that we use `FILE` in the context of this usage example to avoid a
/// dependency of standard library streams.  Finally, we will use `printTree` to
/// print a description of a tree in the next example.
///
/// ### Example 2: Creating a Simple Red-Black Tree {#bslalg_rbtreenode-example-2-creating-a-simple-red-black-tree}
///
///
/// This example demonstrates creating a simple tree of integer values using
/// `RbTreeNode`.  Note that, in practice, clients should use associated
/// utilities to manage such a tree (see @ref bslalg_rbtreenodeutil ).
///
/// First, we define a node-type, `IntTreeNode`, that inherits from
///`RbTreeNode`:
/// @code
/// struct IntTreeNode : public RbTreeNode {
///     // A red-black tree node containing an integer data-value.
///
///     int d_value;  // "payload" value represented by the node
/// };
/// @endcode
/// Then, we define a function `printIntNodeValue` to print the value of an
/// integer node.  Note that this function's signature matches that
/// required by `printTree` (defined in the preceding example):
/// @code
/// void printIntTreeNodeValue(FILE *output, const RbTreeNode *node)
/// {
///    BSLS_ASSERT(0 != node);
///
///    fprintf(output, "%d", static_cast<const IntTreeNode*>(node)->d_value);
/// }
/// @endcode
/// Next, we define `main` for our test, and create three nodes that we'll use
/// to construct a tree:
/// @code
/// int main(int argc, const char *argv[])
/// {
///     IntTreeNode A, B, C;
/// @endcode
/// Then, we describe the structure of the tree we wish to construct.
/// @code
///
///                 A (value: 2, BLACK)
///               /       \.
///              /         \.
///   B (value: 1, RED)   C ( value: 3, RED )
/// @endcode
/// Now, we set the properties for the nodes `A`, `B`, and `C` to form a valid
/// tree whose structure matches that description:
/// @code
///     A.d_value = 2;
///     A.setColor(RbTreeNode::BSLALG_BLACK);
///     A.setParent(0);
///     A.setLeftChild(&B);
///     A.setRightChild(&C);
///
///     B.d_value = 1;
///     B.setColor(RbTreeNode::BSLALG_RED);
///     B.setParent(&A);
///     B.setLeftChild(0);
///     B.setRightChild(0);
///
///     C.d_value = 3;
///     C.setColor(RbTreeNode::BSLALG_RED);
///     C.setParent(&A);
///     C.setLeftChild(0);
///     C.setRightChild(0);
/// @endcode
/// Finally, we use the `printTree` function with the `printIntTreeNodeValue`
/// function to print the structure of our tree to `stdout`:
/// @code
///     printTree(stdout, &A, printIntTreeNodeValue);
/// }
/// @endcode
/// Resulting in a single line of console output:
/// @code
/// [ 2: BLACK [ 1: RED ] [ 3: RED ] ]
/// @endcode
///
/// ### Example 3: Creating a Function To Validate a Red-Black Tree {#bslalg_rbtreenode-example-3-creating-a-function-to-validate-a-red-black-tree}
///
///
/// This example demonstrates creating a function to validate the properties of
/// a red-black tree.
///
/// First, we declare the signature of a function `validateRbTree`, which takes
/// two arguments: (1) the address to the root node of a tree, and (2) a
/// comparator function, which is used to compare the payload values of the tree
/// nodes.  Note that the parameterized comparator is needed because a node's
/// value is not accessible through the supplied `RbTreeNode`.
/// @code
/// template <class NODE_COMPARATOR>
/// int validateRbTree(const RbTreeNode       *rootNode,
///                    const NODE_COMPARATOR&  comparator);
///     // Return the uniform number of black nodes between every leaf node in
///     // the tree and the specified 'rootNode', 0 if 'rootNode' is 0, and a
///     // negative value if 'rootNode' does not refer to a valid red-black
///     // binary-search tree that is ordered according to the specified
///     // 'comparator'.  'rootNode' is considered a valid red-black binary
///     // search-tree if it obeys the following rules:
///     //
///     //: 1 All nodes in the left sub-tree of 'rootNode' are ordered at or
///     //:   before 'rootNode' (as determined by 'comparator'), and all nodes
///     //:   in the right sub-tree are ordered at or after 'rootNode'.
///     //:
///     //: 2 Both children of 'rootNode' refer to 'rootNode' as a parent.
///     //:
///     //: 3 If 'rootNode' is red, its children are either black or 0.
///     //:
///     //: 4 Every path from 'rootNode' to a leaf contains the same number of
///     //:   black nodes (the uniform number of black nodes in every path is
///     //:   returned by this function if valid).
///     //:
///     //: 5 Rules (1-4) are obeyed, recursively, by the left and right
///     //:   sub-trees of 'rootNode'.
///     //
///     // Note that this particular specification of the constraints of a
///     // red-black tree does not require the presense of black-colored NIL
///     // leaf-nodes; instead NULL children are implicitly assumed to be NIL
///     // leaf-nodes (as is typically the case for C/C++ implementations).
///     // This specification also does not require the root node to be
///     // colored black, as there's no practical benefit to enforcing that
///     // constraint.
/// @endcode
/// Then, we declare the signature for an auxiliary function,
/// `validateRbTreeRaw`, that accepts, additionally, the address of minimum
/// and maximum value nodes, and is needed to recursively apply rule 1:
/// @code
/// template <class NODE_COMPARATOR>
/// int validateRbTreeRaw(const RbTreeNode *rootNode,
///                       const RbTreeNode *minNodeValue,
///                       const RbTreeNode *maxNodeValue,
///                       NODE_COMPARATOR   comparator);
///
///     // Return the uniform number of black nodes between every leaf node in
///     // the tree and the specified 'rootNode', 0 if 'rootNode' is 0, and a
///     // negative value if (1) 'rootNode' does not refer to a valid red-black
///     // binary search tree that is ordered according to the specified
///     // 'comparator', (2) the specified 'minNodeValue' is not 0 and there is
///     // at least 1 node in the tree ordered before 'minNodeValue', or (3)
///     // the specified 'maxNodeValue' is not 0 and there is at least 1 node
///     // in the tree ordered after 'maxNodeValue'.
/// @endcode
/// Now, we define the implementation of `validateRbTree`, which simply
/// delegates to `validateRbTreeRaw`.
/// @code
/// template <class NODE_COMPARATOR>
/// int validateRbTree(const RbTreeNode *rootNode,
///                    NODE_COMPARATOR   comparator)
/// {
///     return validateRbTreeRaw(rootNode, 0, 0, comparator);
/// }
/// @endcode
/// Finally, we define the implementation of `validateRbTreeRaw`, which tests if
/// `rootNode` violates any of the rules defined in the `validateRbTree` method
/// documentation, and then recursively calls `validateRbTreeRaw` on the left
/// and right sub-trees or `rootNode`:
/// @code
/// template <class NODE_COMPARATOR>
/// int validateRbTreeRaw(const RbTreeNode *rootNode,
///                       const RbTreeNode *minNodeValue,
///                       const RbTreeNode *maxNodeValue,
///                       NODE_COMPARATOR   comparator)
/// {
///     enum { INVALID_RBTREE = -1 };
///
///     // The black-height of a empty tree is considered 0.
///
///     if (0 == rootNode) {
///         return 0;                                                 // RETURN
///     }
///
///     // Rule 1.
///
///     if ((minNodeValue && comparator(*rootNode, *minNodeValue)) ||
///         (maxNodeValue && comparator(*maxNodeValue, *rootNode))) {
///         return INVALID_RBTREE;                                    // RETURN
///     }
///
///     // Rule 2.
///
///     const RbTreeNode *left  = rootNode->leftChild();
///     const RbTreeNode *right = rootNode->rightChild();
///     if ((left  && left->parent()  != rootNode) ||
///         (right && right->parent() != rootNode)) {
///         return INVALID_RBTREE;                                    // RETURN
///     }
///
///     // Rule 3.
///
///     if (RbTreeNode::BSLALG_RED == rootNode->color()) {
///         if ((left  && left->color()  != RbTreeNode::BSLALG_BLACK) ||
///             (right && right->color() != RbTreeNode::BSLALG_BLACK)) {
///             return INVALID_RBTREE;                                // RETURN
///         }
///     }
///
///     // Recursively validate the left and right sub-tree's and obtain their
///     // black-height in order to apply rule 5.
///
///     int leftDepth  = validateRbTreeRaw(rootNode->leftChild(),
///                                        minNodeValue,
///                                        rootNode,
///                                        comparator);
///
///     int rightDepth = validateRbTreeRaw(rootNode->rightChild(),
///                                        rootNode,
///                                        maxNodeValue,
///                                        comparator);
///
///     if (leftDepth < 0 || rightDepth < 0) {
///         return INVALID_RBTREE;                                    // RETURN
///     }
///
///     // Rule 4.
///
///     if (leftDepth != rightDepth) {
///         return INVALID_RBTREE;                                    // RETURN
///     }
///
///     return (rootNode->color() == RbTreeNode::BSLALG_BLACK)
///         ? leftDepth + 1
///         : leftDepth;
/// }
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslalg
 * @{
 */
/** @addtogroup bslalg_rbtreenode
 * @{
 */
 
#include <bslscm_version.h>
 
#include <bslmf_assert.h>
 
#include <bsls_assert.h>
#include <bsls_types.h>
#include <bsls_platform.h>
 
 
namespace bslalg {
 
                        // ================
                        // class RbTreeNode
                        // ================
 
/// This POD-like `class` describes a node suitable for use in a red-black
/// binary search tree, holding the addresses of the parent, left-child, and
/// right-child nodes (any of which may be 0), as well as a "color" (red or
/// black).  This class is a "POD-like" to facilitate efficient allocation
/// and use in the context of a container implementation.  In order to meet
/// the essential requirements of a POD type, this `class` does not define a
/// constructor or destructor.  However its data members are private.  Since
/// this class will be aligned to a word boundary, a pointer type will be a
/// multiple of 4.  This class use this property to reduce its size by
/// storing the color information in the least significant bit of the parent
/// pointer.  Note that this type does not contain any "payload" member
/// data: Clients creating a red-black binary search tree must define an
/// appropriate node type that incorporates `RbTreeNode` (generally via
/// inheritance), and that holds the "key" value and any associated data.
///
/// See @ref bslalg_rbtreenode 
class RbTreeNode {
 
  public:
    // TYPES
    enum Color{
        BSLALG_RED   = 0,
        BSLALG_BLACK = 1
    };
 
  private:
    // DATA
    RbTreeNode *d_parentWithColor_p;  // parent of this node (may be 0) with
                                      // the color information stored in the
                                      // least significant bit
 
    RbTreeNode *d_left_p;             // left-child of this node (may be 0)
 
    RbTreeNode *d_right_p;            // right-child of this node (may be 0)
 
 
  private:
    // PRIVATE CLASS METHODS
 
    /// Return the specified `value` as an `unsigned int`.
    static bsls::Types::UintPtr toInt(RbTreeNode *value);
 
    /// Return the specified `value` as `RbTreeNode *`.
    static RbTreeNode *toNode(bsls::Types::UintPtr value);
 
  public:
     RbTreeNode() = default;
        // Create a 'RbTreeNode' object having uninitialized values.
 
     RbTreeNode(const RbTreeNode& original) = default;
        // Create a 'RbTreeNode' object having the same value as the specified
        // 'original' object.
 
     ~RbTreeNode() = default;
        // Destroy this object.
 
    // MANIPULATORS
     RbTreeNode& operator= (const RbTreeNode& rhs) = default;
        // Assign to this object the value of the specified 'rhs' object, and
        // return a reference providing modifiable access to this object.
 
    /// Set the color of this node to black.  Note that this operation is
    /// at least as fast as (and potentially faster than) `setColor`.
    void makeBlack();
 
    /// Set the color of this node to red.    Note that this operation is
    /// at least as fast as (and potentially faster than) `setColor`.
    void makeRed();
 
    /// Set the parent of this node to the specified `address`.  If
    /// `address` is 0, then this node will have not have a parent node
    /// (i.e., it will be the root node).  The behavior is undefined unless
    /// `address` is aligned to at least two bytes.
    void setParent(RbTreeNode *address);
 
    /// Set the left child of this node to the specified `address`.  If
    /// `address` is 0, then this node will not have a left child.
    void setLeftChild(RbTreeNode *address);
 
    /// Set the right child of this node to the specified `address`.  If
    /// `address` is 0, then this node will not have a right child.
    void setRightChild(RbTreeNode *address);
 
    /// Set the color of this node to the specified `value`.
    void setColor(Color value);
 
    /// Set the color of this node to the alternative color.  If this
    /// node's color is red, set it to black, and set it to red otherwise.
    /// Note that this operation is at least as fast as (and potentially
    /// faster than) `setColor`.
    void toggleColor();
 
    /// Reset this object to have the specified `parent`, `leftChild`,
    /// `rightChild`, and `color` property values.
    void reset(RbTreeNode *parent,
               RbTreeNode *leftChild,
               RbTreeNode *rightChild,
               Color       color);
 
    /// Return the address of the (modifiable) parent of this node if one
    /// exists, and 0 otherwise.
    RbTreeNode *parent();
 
    /// Return the address of the (modifiable) left child of this node if
    /// one exists, and 0 otherwise.
    RbTreeNode *leftChild();
 
    /// Return the address of the (modifiable) right child of this node if
    /// one exists, and 0 otherwise.
    RbTreeNode *rightChild();
 
    // ACCESSORS
 
    /// Return the address of the parent of this node if one exists, and 0
    /// otherwise.
    const RbTreeNode *parent() const;
 
    /// Return `true` if this node is black.
    bool isBlack() const;
 
    /// Return `true` if this node is red.
    bool isRed() const;
 
    /// Return the address of the left child of this node if one exists,
    /// and 0 otherwise.
    const RbTreeNode *leftChild() const;
 
    /// Return the address of the right child of this node if one exists,
    /// and 0 otherwise.
    const RbTreeNode *rightChild() const;
 
    /// Return the color of this node.
    Color color() const;
};
 
// ============================================================================
//                      INLINE FUNCTION DEFINITIONS
// ============================================================================
 
// PRIVATE METHODS
inline
bsls::Types::UintPtr RbTreeNode::toInt(RbTreeNode *value)
{
#if  defined(BSLS_PLATFORM_HAS_PRAGMA_GCC_DIAGNOSTIC) && \
    !defined(BSLS_PLATFORM_CMP_CLANG)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
#endif
 
    return reinterpret_cast<bsls::Types::UintPtr>(value);
 
#if  defined(BSLS_PLATFORM_HAS_PRAGMA_GCC_DIAGNOSTIC) && \
    !defined(BSLS_PLATFORM_CMP_CLANG)
#pragma GCC diagnostic pop
#endif
}
 
inline
RbTreeNode *RbTreeNode::toNode(bsls::Types::UintPtr value)
{
    return reinterpret_cast<RbTreeNode *>(value);
}
 
// MANIPULATORS
inline
void RbTreeNode::makeBlack()
{
    d_parentWithColor_p = toNode(toInt(d_parentWithColor_p) | 0x01);
}
 
inline
void RbTreeNode::makeRed()
{
    d_parentWithColor_p = toNode(toInt(d_parentWithColor_p) & ~0x01);
}
 
inline
void RbTreeNode::setParent(RbTreeNode *address)
{
    BSLS_ASSERT_SAFE(0 == (toInt(address) & 0x01));
 
    d_parentWithColor_p =
                  toNode(toInt(address) | (toInt(d_parentWithColor_p) & 0x01));
}
 
inline
void RbTreeNode::setLeftChild(RbTreeNode *address)
{
    d_left_p = address;
}
 
inline
void RbTreeNode::setRightChild(RbTreeNode *address)
{
    d_right_p = address;
}
 
inline
void RbTreeNode::setColor(Color value)
{
    d_parentWithColor_p = toNode((toInt(d_parentWithColor_p) & ~0x01) | value);
}
 
inline
void RbTreeNode::toggleColor()
{
    BSLMF_ASSERT(0 == BSLALG_RED);
    BSLMF_ASSERT(1 == BSLALG_BLACK);
 
    d_parentWithColor_p = toNode(toInt(d_parentWithColor_p) ^ 0x01);
}
 
inline
void RbTreeNode::reset(RbTreeNode *parent,
                       RbTreeNode *leftChild,
                       RbTreeNode *rightChild,
                       Color       color)
{
    BSLS_ASSERT_SAFE(0 == (toInt(parent) & 0x01));
 
    d_parentWithColor_p = toNode(toInt(parent) | color);
    d_left_p = leftChild;
    d_right_p = rightChild;
}
 
inline
RbTreeNode *RbTreeNode::parent()
{
    return toNode(toInt(d_parentWithColor_p) & ~0x01);
}
 
inline
RbTreeNode *RbTreeNode::leftChild()
{
    return d_left_p;
}
 
inline
RbTreeNode *RbTreeNode::rightChild()
{
    return d_right_p;
}
 
// ACCESSORS
inline
const RbTreeNode *RbTreeNode::parent() const
{
    return toNode(toInt(d_parentWithColor_p) & ~0x01);
}
 
inline
bool RbTreeNode::isBlack() const
{
    return toInt(d_parentWithColor_p) & 0x01;
}
 
inline
bool RbTreeNode::isRed() const
{
    return !isBlack();
}
 
inline
const RbTreeNode *RbTreeNode::leftChild() const
{
    return d_left_p;
}
 
inline
const RbTreeNode *RbTreeNode::rightChild() const
{
    return d_right_p;
}
 
inline
RbTreeNode::Color RbTreeNode::color() const
{
    return static_cast<Color>(toInt(d_parentWithColor_p) & 0x01);
}
 
}  // close package namespace
 
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2013 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ----------------------------- END-OF-FILE ----------------------------------
 
/** @} */
/** @} */
/** @} */