A node in the range tree. More...

#include <DiscreteRange.h>

Inheritance diagram for swoc::DiscreteSpace< METRIC, PAYLOAD >::Node:

Collaboration diagram for swoc::DiscreteSpace< METRIC, PAYLOAD >::Node:

Public Types
using	Linkage = swoc::IntrusiveLinkageRebind<self_type, super_type::Linkage>
	Linkage for `IntrusiveDList`.

Public Types inherited from swoc::detail::RBNode
enum class	Color { RED , BLACK }
	Node colors. More...

enum class	Direction { NONE , LEFT , RIGHT }
	Directional constants. More...

using	self_type = RBNode
	self reference type

Public Member Functions
	Node ()=default
	Construct empty node.

	Node (range_type const &range, PAYLOAD const &payload)
	Construct from range and payload.

	Node (METRIC const &min, METRIC const &max, PAYLOAD const &payload)
	Construct from two metrics and a payload.

PAYLOAD &	payload ()

self_type &	assign (range_type const &range)

self_type &	assign (PAYLOAD const &payload)

range_type const &	range () const

self_type &	assign_min (METRIC const &m, bool update_tree=true)

self_type &	assign_max (METRIC const &m, bool update_tree=true)

METRIC const &	min () const

METRIC const &	max () const

void	structure_fixup () override

self_type *	left ()

self_type *	right ()

Public Member Functions inherited from swoc::detail::RBNode
	RBNode ()=default
	Default constructor.

virtual	~RBNode ()
	Force virtual destructor.

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 bool	structure_validate ()

void	replace_with (self_type *n)

self_type *	rebalance_after_insert ()
	Rebalance the tree starting at this node.

self_type *	rebalance_after_remove (Color c, Direction dir)

self_type *	ripple_structure_fixup ()

Friends
class	DiscreteSpace

Additional Inherited Members
static self_type *	buildTree (self_type *&head, int n)
	Recursively build a balanced RB tree from a sorted linked list.

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

static void	printTree (self_type *root, std::string indent="", bool last=true)
	Recursively print the tree in a human-readable format.

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.

Detailed Description

template<typename METRIC, typename PAYLOAD>
class swoc::DiscreteSpace< METRIC, PAYLOAD >::Node

A node in the range tree.

Definition at line 717 of file DiscreteRange.h.

Member Typedef Documentation

◆ Linkage

template<typename METRIC, typename PAYLOAD>

using swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::Linkage = swoc::IntrusiveLinkageRebind<self_type, super_type::Linkage>

Linkage for IntrusiveDList.

Definition at line 728 of file DiscreteRange.h.

Constructor & Destructor Documentation

◆ Node() [1/2]

template<typename METRIC, typename PAYLOAD>

swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::Node	(	range_type const &	range,
		PAYLOAD const &	payload )

inline

Construct from range and payload.

Definition at line 733 of file DiscreteRange.h.

◆ Node() [2/2]

template<typename METRIC, typename PAYLOAD>

swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::Node	(	METRIC const &	min,
		METRIC const &	max,
		PAYLOAD const &	payload )

inline

Construct from two metrics and a payload.

Definition at line 736 of file DiscreteRange.h.

Member Function Documentation

◆ assign() [1/2]

template<typename METRIC, typename PAYLOAD>

auto swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::assign ( PAYLOAD const & payload )

Set the payload for this node.

Parameters

payload Payload to use.

Returns: this

Definition at line 1056 of file DiscreteRange.h.

◆ assign() [2/2]

template<typename METRIC, typename PAYLOAD>

auto swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::assign ( DiscreteSpace::range_type const & range )

Set the range of a node.

Parameters

range Range to use.

Returns: this

Definition at line 1049 of file DiscreteRange.h.

◆ assign_max()

template<typename METRIC, typename PAYLOAD>

self_type & swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::assign_max	(	METRIC const &	m,
		bool	update_tree = true )

inline

Definition at line 771 of file DiscreteRange.h.

◆ assign_min()

template<typename METRIC, typename PAYLOAD>

self_type & swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::assign_min	(	METRIC const &	m,
		bool	update_tree = true )

inline

Definition at line 761 of file DiscreteRange.h.

◆ left()

template<typename METRIC, typename PAYLOAD>

self_type * swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::left ( )

inline

Definition at line 793 of file DiscreteRange.h.

◆ max()

template<typename METRIC, typename PAYLOAD>

METRIC const & swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::max ( ) const

inline

Definition at line 786 of file DiscreteRange.h.

◆ min()

template<typename METRIC, typename PAYLOAD>

METRIC const & swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::min ( ) const

inline

Definition at line 781 of file DiscreteRange.h.

◆ payload()

template<typename METRIC, typename PAYLOAD>

PAYLOAD & swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::payload ( )

Returns: The payload in the node.

Definition at line 1043 of file DiscreteRange.h.

◆ range()

template<typename METRIC, typename PAYLOAD>

range_type const & swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::range ( ) const

inline

Definition at line 756 of file DiscreteRange.h.

◆ right()

template<typename METRIC, typename PAYLOAD>

self_type * swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::right ( )

inline

Definition at line 798 of file DiscreteRange.h.

◆ structure_fixup()

template<typename METRIC, typename PAYLOAD>

void swoc::DiscreteSpace< METRIC, PAYLOAD >::Node::structure_fixup ( )

overridevirtual

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.

Reimplemented from swoc::detail::RBNode.

Definition at line 1063 of file DiscreteRange.h.

Friends And Related Symbol Documentation

◆ DiscreteSpace

template<typename METRIC, typename PAYLOAD>

friend class DiscreteSpace

friend

Definition at line 720 of file DiscreteRange.h.

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

DiscreteRange.h

Public Types

Public Member Functions

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Linkage

Constructor & Destructor Documentation

◆ Node() [1/2]

◆ Node() [2/2]

Member Function Documentation

◆ assign() [1/2]

◆ assign() [2/2]

◆ assign_max()

◆ assign_min()

◆ left()

◆ max()

◆ min()

◆ payload()

◆ range()

◆ right()

◆ structure_fixup()

Friends And Related Symbol Documentation

◆ DiscreteSpace