Class IntervalTree::Node

Nested Relationships

This class is a nested type of Template Class IntervalTree.

Class Documentation

class Node

Used to track Interval<>s stored in an IntervalTree<>

Public Functions

inline Node() = default

Construcst an instance of Node.

inline ~Node()

Destroys this instance of Node.

Public Members

Interval<EndPointType> mInterval = {0, 0}

This Node's Interval<>

ValueType mValue = {}

This Node's ValueType value.

EndPointType mMax = {0}

This Node's subtree's maximum end point value.

Node *mLeft = {nullptr}

A pointer to this Node's left child.

Node *mRight = {nullptr}

A pointer to this Node's right child.

int mBalance = {0}

A value indicating this Node's balance factor.

Public Static Functions

template<typename EnumerationFunctionType>
static inline void EnumerateOverlappingIntervals(Node const *node, Interval<EndPointType> const &interval, EnumerationFunctionType enumerationFunction)

Recursivley enumerates all Interval<>s that overlap a given Interval<> under a given Node, calling a given enumeration function for each.

Note

This function must have a signature compatible with void(Interval<EndPointType>, ValueType)

Parameters

  • <EnumerationFunctionType> -- The type of function to call for each overlapping Interval<>

  • node -- [in] A pointer to the Node under which to search recursively for overlapping Interval<>s

  • interval -- [in] The Interval<> to find overlapping Interval<>s for

  • enumerationFunction -- [in] The function to call for each overlapping Interval<>

static inline Node *Add(Node *node, Interval<EndPointType> const &interval, bool &added, Node **itr)

Adds or finds a given Interval<> under a given Node.

Parameters

  • node -- [in] The Node to add or find the given Interval<> under

  • interval -- [in] The Interval<> to add or find

  • added -- [in] Whether or not a new Node has been added

  • itr -- [out] A pointer to a pointer to the added or found Node

static inline void ComputeMax(Node *node)

Computes the max end point value for the subtree at a given Node.

Parameters

node -- [in] A pointer to the Node to compute the max end point value for

static inline Node *RotateLeft(Node *node)

Rotates a given Node and its immediate right and right->left children to the left.

Parameters

node -- [in] A pointer to the Node to rotate left

static inline Node *RotateRight(Node *node)

Rotates a given Node and its immediate left and left->right children to the right.

Parameters

node -- [in] A pointer to the Node to rotate right