RBTree.h

Go to the documentation of this file.

// SPDX-License-Identifier: Apache-2.0
// Copyright Apache Software Foundation 2019
 
#pragma once
 
#include "swoc/swoc_version.h"
#include "swoc/IntrusiveDList.h"
 
#include <string>
 
namespace swoc { inline namespace SWOC_VERSION_NS { namespace detail {
struct RBNode {
  using self_type = RBNode; 

  enum class Color {
    RED,
    BLACK,
  };

  enum class Direction {
    NONE,
    LEFT,
    RIGHT,
  };

  RBNode() = default;

  virtual ~RBNode() {}

  self_type *child_at(Direction d) const;

  Direction direction_of(self_type *const &n) const;

  Color color() const;

  self_type *left_most_descendant() const;

  Direction flip(Direction d);

  int validate();

  self_type *rotate(Direction dir);

  self_type *set_child(self_type *child, Direction dir);

  self_type *remove();

  void clear_child(Direction dir);


  virtual void
  structure_fixup() {}

  virtual bool structure_validate();

  void replace_with(self_type *n);


  self_type *rebalance_after_insert();

  self_type *rebalance_after_remove(Color c, Direction dir);

  self_type *ripple_structure_fixup();

  static self_type * buildTree(self_type*& head, int n);

  static self_type * buildTree(self_type*& head, int n, bool isBlack);

  static void printTree(self_type* root, std::string indent = "", bool last = true);
 
  Color _color{Color::RED};    
  self_type *_parent{nullptr}; 
  self_type *_left{nullptr};   
  self_type *_right{nullptr};  
  self_type *_next{nullptr};   
  self_type *_prev{nullptr};   

  struct Linkage {
    static self_type *&
    next_ptr(self_type *t) {
      return swoc::ptr_ref_cast<self_type>(t->_next);
    }

    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