A node in a red/black tree. More...

#include <IpMap.h>

Inherited by IpMap::Node [protected].

Collaboration diagram for ts::detail::RBNode:

Public Types
enum	Color { RED, BLACK }
	Node colors. More...
enum	Direction { NONE, LEFT, RIGHT }
	Directional constants. More...
typedef RBNode	self
	self reference type
Public Member Functions
self *	getChild (Direction d) const
	Get a child by direction.
Direction	getChildDirection (self *const &n) const
	Determine which child a node is.
self *	getParent () const
	Get the parent node.
Color	getColor () const
Direction	flip (Direction d)
	Reverse a direction.
int	validate ()
	Perform internal validation checks.
	RBNode ()
	Default constructor.
virtual	~RBNode ()
	Destructor (force virtual).
self *	rotate (Direction d)
	Rotate the subtree rooted at this node.
self *	setChild (self *n, Direction d)
	Set the child node in direction d to n.
self *	remove ()
	Remove this node from the tree.
void	clearChild (Direction dir)
void	replaceWith (self *n)
	Replace this node with another node.
self *	rebalanceAfterInsert ()
	Rebalance the tree starting at this node.
self *	rebalanceAfterRemove (Color c, Direction d)
	Rebalance the tree after a deletion.
self *	rippleStructureFixup ()
	Invoke `structure_fixup()` on this node and all of its ancestors.
Subclass hook methods

virtual void	structureFixup ()
	Structural change notification.
virtual bool	structureValidate ()
	Called from `validate` to perform any additional validation checks.
Data Fields
Color	_color
	node color
self *	_parent
	parent node (needed for rotations)
self *	_left
	left child
self *	_right
	right child
self *	_next
	Next node.
self *	_prev
	Previous node.

Detailed Description

A node in a red/black tree.

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

Definition at line 66 of file IpMap.h.

Member Typedef Documentation

typedef RBNode ts::detail::RBNode::self

self reference type

Reimplemented in IpMap::Node.

Definition at line 67 of file IpMap.h.

Member Enumeration Documentation

enum ts::detail::RBNode::Color

Node colors.

Enumerator:

RED
BLACK

Definition at line 70 of file IpMap.h.

enum ts::detail::RBNode::Direction

Directional constants.

Enumerator:

NONE
LEFT
RIGHT

Definition at line 73 of file IpMap.h.

Constructor & Destructor Documentation

ts::detail::RBNode::RBNode ( ) [inline]

Default constructor.

Definition at line 115 of file IpMap.h.

virtual ts::detail::RBNode::~RBNode ( ) [inline, virtual]

Destructor (force virtual).

Definition at line 125 of file IpMap.h.

Member Function Documentation

void ts::detail::RBNode::clearChild ( Direction dir ) [inline]

Definition at line 163 of file IpMap.h.

References _left, _right, LEFT, and RIGHT.

Referenced by rotate().

Direction ts::detail::RBNode::flip ( Direction d ) [inline]

Reverse a direction.

Returns:: LEFT if d is RIGHT, RIGHT if d is LEFT, NONE otherwise.

Definition at line 105 of file IpMap.h.

References LEFT, and RIGHT.

Referenced by rebalanceAfterInsert(), and rotate().

RBNode * ts::detail::RBNode::getChild ( Direction d ) const [inline]

Get a child by direction.

Returns:: The child in the direction d if it exists, NULL if not.

Parameters:

d

The direction of the desired child

Definition at line 114 of file IpMap.cc.

References _left, _right, LEFT, and RIGHT.

Referenced by rotate().

Direction ts::detail::RBNode::getChildDirection ( self *const & n ) const [inline]

Determine which child a node is.

Returns:: LEFT if n is the left child, RIGHT if n is the right child, NONE if n is not a child

Parameters:

n

The presumed child node

Definition at line 87 of file IpMap.h.

References _left, _right, LEFT, NONE, and RIGHT.

Referenced by replaceWith(), and rotate().

Color ts::detail::RBNode::getColor ( ) const [inline]

Returns:: The color of the node.

Definition at line 99 of file IpMap.h.

References _color.

Referenced by ts::detail::operator==().

self* ts::detail::RBNode::getParent ( ) const [inline]

Get the parent node.

Returns:: A Node* to the parent node or a nil Node* if no parent.

Definition at line 96 of file IpMap.h.

References _parent.

RBNode * ts::detail::RBNode::rebalanceAfterInsert ( )

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.

Returns:: The root node of the tree after the rebalance.

Definition at line 185 of file IpMap.cc.

References flip(), RED, and rippleStructureFixup().

RBNode * ts::detail::RBNode::rebalanceAfterRemove	(	Color	c,
		Direction	d
	)

Rebalance the tree after a deletion.

Rebalance tree after a deletion Called on the spliced in node or its parent, whichever is not NIL.

Called on the lowest modified node.

Returns:: The new root of the tree.

This modifies the tree structure only if c is BLACK.

Parameters:

	c	The color of the removed node.
	d	Direction of removed node from parent

Definition at line 310 of file IpMap.cc.

References _color, _parent, BLACK, LEFT, NONE, RED, RIGHT, and rippleStructureFixup().

RBNode * ts::detail::RBNode::remove ( )

Remove this node from the tree.

The tree is rebalanced after removal.

Returns:: The new root node.

Definition at line 227 of file IpMap.cc.

References _color, _left, _next, _parent, _right, NONE, and replaceWith().

void ts::detail::RBNode::replaceWith ( self * n )

Replace this node with another node.

This is presumed to be non-order modifying so the next reference is not updated.

Parameters:

n

Node to put in place of this node.

Definition at line 168 of file IpMap.cc.

References _color, _left, _parent, _right, getChildDirection(), LEFT, RIGHT, and setChild().

Referenced by remove().

RBNode * ts::detail::RBNode::rippleStructureFixup ( )

Invoke structure_fixup() on this node and all of its ancestors.

Definition at line 156 of file IpMap.cc.

References structureFixup().

Referenced by rebalanceAfterInsert(), and rebalanceAfterRemove().

RBNode * ts::detail::RBNode::rotate ( Direction d )

Rotate the subtree rooted at this node.

The node is rotated in to the position of one of its children. Which child is determined by the direction parameter d. The child in the other direction becomes the new root of the subtree.

If the parent pointer is set, then the child pointer of the original parent is updated so that the tree is left in a consistent state.

Note:: If there is no child in the other direction, the rotation fails and the original node is returned. It is not required that a child exist in the direction specified by d.

Returns:: The new root node for the subtree.

Parameters:

d

The direction to rotate

Definition at line 122 of file IpMap.cc.

References _parent, clearChild(), flip(), getChild(), getChildDirection(), NONE, setChild(), and structureFixup().

RBNode * ts::detail::RBNode::setChild	(	self *	n,
		Direction	d
	)

Set the child node in direction d to n.

The d child is set to the node n. The pointers in this node and n are set correctly. This can only be called if there is no child node already present.

Returns:: n.

Parameters:

	n	The node to set as the child
	d	The direction of the child

Definition at line 147 of file IpMap.cc.

References _left, _parent, _right, LEFT, and RIGHT.

Referenced by ts::detail::IpMapBase< N >::append(), ts::detail::IpMapBase< N >::prepend(), replaceWith(), and rotate().

virtual void ts::detail::RBNode::structureFixup ( ) [inline, virtual]

Structural change notification.

This method is called if the structure of the subtree rooted at this node was changed.

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

Definition at line 177 of file IpMap.h.

Referenced by rippleStructureFixup(), and rotate().

virtual bool ts::detail::RBNode::structureValidate ( ) [inline, virtual]

Called from validate to perform any additional validation checks.

Clients should chain this if they wish to perform additional checks.

Returns:: true if the validation is successful, false otherwise.

Note:: The base method simply returns true.

Definition at line 184 of file IpMap.h.

Referenced by validate().

int ts::detail::RBNode::validate ( )

Perform internal validation checks.

Ensure that the local information associated with each node is correct globally This should only be called on debug builds as it breaks any efficiencies we have gained from our tree structure.