code/include/swoc/RBTree.h

// SPDX-License-Identifier: Apache-2.0
// Copyright Apache Software Foundation 2019
/** @file

   Red/Black tree.
*/

#pragma once

#include "swoc/swoc_version.h"
#include "swoc/IntrusiveDList.h"

#include <string>

namespace swoc { inline namespace SWOC_VERSION_NS { namespace detail {
/** A node in a red/black tree.

    This class provides only the basic tree operations. The container must provide the search and
    decision logic. This enables this class to be a base class for templated nodes with much less
    code duplication.

    @internal The primary point of a custom implementation is to hook on rotation events which
    are used to update additional tree data. This provides a significant performance boost
    for range based uses of this class.
*/
struct RBNode {
  using self_type = RBNode; ///< self reference type

  /// Node colors
  enum class Color {
    RED,
    BLACK,
  };

  /// Directional constants
  enum class Direction {
    NONE,
    LEFT,
    RIGHT,
  };

  /// Default constructor.
  RBNode() = default;

  /// Force virtual destructor.
  virtual ~RBNode() {}

  /** Get the child in direction @a dir.
   *
   * @param d Child direction.
   * @return A pointer to the child node, or @c nullptr if no child in that direction.
   */
  self_type *child_at(Direction d) const;

  /** Get the direction of a child node @a n.
   *
   * @param n Child node.
   * @return Direction of the child if @a n is a child, @c Direction::NONE if not.
   */
  Direction direction_of(self_type *const &n) const;

  /// @return The color of the node.
  Color color() const;

  /// @return The left most descendant of @a this, or @a null ptr if no left child.
  self_type *left_most_descendant() const;

  /** Reverse a direction
      @return @c LEFT if @a d is @c RIGHT, @c RIGHT if @a d is @c LEFT,
      @c NONE otherwise.
  */
  Direction flip(Direction d);

  /** Perform internal validation checks.
      @return 0 on failure, black height of the tree on success.
  */
  int validate();

  /** Rotate the subtree rooted at this node in the direction @a dir.
   *
   * @param dir Direction of rotatoin.
   * @return The root node after rotation.
   *
   * @a this node is rotated in to the position of its @a dir child and the child in the other
   * direction becomes the new root node for the subtree. This operation is a no-op if there
   * is no other child.
   *
   * If @a this node has a parent then that parent's child pointer is updated as needed.
   */
  self_type *rotate(Direction dir);

  /** Set the @a dir child of @a this node to @a child.
   *
   * @param child Node to set as the child.
   * @param dir Direction of the child location.
   * @return @a child
   *
   * The internal pointers in both @a this and @a child are updated as needed. It is an error
   * to call this if the specified child is already set.
   */
  self_type *set_child(self_type *child, Direction dir);

  /** Remove this node from the tree.
      The tree is rebalanced after removal.
      @return The new root node.
  */
  self_type *remove();

  /** Remove the @a dir child.
   *
   * @param dir Direction of child to remove.
   *
   * The pointers in @a this and the child are updated as needed. It is not an error if there
   * is no child in the direction @a dir.
   */
  void clear_child(Direction dir);

  /** @name Subclass hook methods */
  //@{
  /** Structural change notification.

      This method is called if the structure of the subtree rooted at this node was changed. This
      makes it possible to keep subtree information nodes synchronized with the state of the tree
      efficiently.

      This is intended a hook. The base method is empty so that subclasses are not required to
      override.

      @internal This is the primary reason for this class.
  */
  virtual void
  structure_fixup() {}

  /** Called from @c validate to perform any additional validation checks.
      Clients should chain this if they wish to perform additional checks.
      @return @c true if the validation is successful, @c false otherwise.
  */
  virtual bool structure_validate();
  //@}

  /** Replace @a this node with @a n.
   *
   * @param n Replacement node.
   *
   * Invariant: this is a non-order modifying replacement.
   */
  void replace_with(self_type *n);

  //! Rebalance the tree starting at this node
  /** The tree is rebalanced so that all of the invariants are
      true. The (potentially new) root of the tree is returned.

      @return The root node of the tree after the rebalance.
  */
  self_type *rebalance_after_insert();

  /** Rebalance the tree after a deletion.
      Called on the lowest modified node.
      @return The new root of the tree.
  */
  /** Rebalance the tree root at @a this node after a removal.
   *
   * @param c The color of the removed node.
   * @param d The direction of the removed node from @a this.
   * @return The new root node.
   *
   * Invariant: @a this is the parent of the removed node.
   */
  self_type *rebalance_after_remove(Color c, Direction dir);

  /** Invoke @c structure_fixup on @a this node and its parents to the root.
   *
   * @return @a The root node.
   *
   * @note This is used by the base class to inform subclasses of structure changes, starting
   * from a leaf node up to the root node.
   */
  self_type *ripple_structure_fixup();

  /**
   * @brief  Recursively build a balanced RB tree from a sorted linked list.
   *
   * Constraints:
   *  - The list is sorted in ascending order.
   *  - A copy (not reference) of the head pointer is passed in.
   *
   * @param head         Copy of the head pointer of the list.
   * @param n            Number of nodes being processed at the current level.
   * @return self_type*  The root node of the tree.
   */
  static self_type * buildTree(self_type*& head, int n);

  //! Called by buildTree above.
  static self_type * buildTree(self_type*& head, int n, bool isBlack);

  /**
   * @brief Recursively print the tree in a human-readable format.
   *
   * @param root   Root node of the tree.
   * @param indent Indentation string.
   * @param last   Flag to indicate if the node is the last node.
   */
  static void printTree(self_type* root, std::string indent = "", bool last = true);

  Color _color{Color::RED};    ///< node color
  self_type *_parent{nullptr}; ///< parent node (needed for rotations)
  self_type *_left{nullptr};   ///< left child
  self_type *_right{nullptr};  ///< right child
  self_type *_next{nullptr};   ///< Next node.
  self_type *_prev{nullptr};   ///< Previous node.

  /// Support for @c IntrusiveDList
  struct Linkage {
    /// @return Reference to internal pointer to the next element.
    static self_type *&
    next_ptr(self_type *t) {
      return swoc::ptr_ref_cast<self_type>(t->_next);
    }
    /// @return Reference to the internal pointer to the previous element.
    static self_type *&
    prev_ptr(self_type *t) {
      return swoc::ptr_ref_cast<self_type>(t->_prev);
    }
  };
};

// --- Implementation ---

inline auto
RBNode::direction_of(self_type *const &n) const -> Direction {
  return (n == _left) ? Direction::LEFT : (n == _right) ? Direction::RIGHT : Direction::NONE;
}

inline RBNode::Color
RBNode::color() const {
  return _color;
}

inline RBNode::Direction
RBNode::flip(RBNode::Direction d) {
  return Direction::LEFT == d ? Direction::RIGHT : Direction::RIGHT == d ? Direction::LEFT : Direction::NONE;
}

inline void
RBNode::clear_child(RBNode::Direction dir) {
  if (Direction::LEFT == dir)
    _left = nullptr;
  else if (Direction::RIGHT == dir)
    _right = nullptr;
}

inline bool
RBNode::structure_validate() {
  return true;
}

}}} // namespace swoc::SWOC_VERSION_NS::detail