inet::IntervalTree Class Reference

Interval tree. More...

#include <IntervalTree.h>

Classes
struct	Interval
	Interval trees implemented using red-black-trees as described in the book Introduction_To_Algorithms_ by Cormen, Leisserson, and Rivest. More...
struct	it_recursion_node
	Class describes the information needed when we take the right branch in searching for intervals but possibly come back and check the left branch as well. More...
class	Node
	The node for interval tree. More...

Public Member Functions
	IntervalTree ()
	~IntervalTree ()
void	print () const
	Print the whole interval tree. More...
const Interval *	deleteNode (Node *node)
	Delete one node of the interval tree. More...
void	deleteNode (const Interval *ivl)
	delete node stored a given interval More...
Node *	insert (const Interval *new_interval)
	Insert one node of the interval tree. More...
Node *	getMinimum (Node *node) const
Node *	getMaximum (Node *node) const
Node *	getPredecessor (Node *node) const
	get the predecessor of a given node More...
Node *	getSuccessor (Node *node) const
	Get the successor of a given node. More...
std::deque< const Interval * >	query (simtime_t low, simtime_t high)
	Return result for a given query. More...

Protected Member Functions
void	leftRotate (Node *node)
	left rotation of tree node More...
void	rightRotate (Node *node)
	right rotation of tree node More...
void	recursiveInsert (Node *node)
	recursively insert a node More...
void	recursivePrint (Node *node) const
	recursively print a subtree More...
Node *	recursiveSearch (Node *node, const Interval *ivl) const
	recursively find the node corresponding to the interval More...
void	fixupMaxHigh (Node *node)
	Travels up to the root fixing the max_high fields after an insertion or deletion. More...
void	deleteFixup (Node *node)

Protected Attributes
Node *	root = nullptr
Node *	nil = nullptr

Private Attributes
unsigned int	recursion_node_stack_size = 0
it_recursion_node *	recursion_node_stack = nullptr
unsigned int	current_parent = 0
unsigned int	recursion_node_stack_top = 0

Friends
class	IntervalTreeTest

Detailed Description

Interval tree.

Constructor & Destructor Documentation

IntervalTree()

inet::IntervalTree::IntervalTree

(

)

the following are used for the query function

{
    nil = new Node;
    nil->left = nil->right = nil->parent = nil;
    nil->red = false;
    nil->key = nil->high = nil->max_high = -SimTime::getMaxTime(); // -std::numeric_limits<double>::max();
    nil->stored_interval = nullptr;
 
    root = new Node;
    root->parent = root->left = root->right = nil;
    root->key = root->high = root->max_high = SimTime::getMaxTime(); // std::numeric_limits<double>::max();
    root->red = false;
    root->stored_interval = nullptr;
 
    recursion_node_stack_size = 128;
    recursion_node_stack = (it_recursion_node *)malloc(recursion_node_stack_size * sizeof(it_recursion_node));
    recursion_node_stack_top = 1;
    recursion_node_stack[0].start_node = nullptr;
}

~IntervalTree()

inet::IntervalTree::~IntervalTree

(

)

{
    Node *x = root->left;
    std::deque<Node *> nodes_to_free;
 
    if (x != nil) {
        if (x->left != nil) {
            nodes_to_free.push_back(x->left);
        }
        if (x->right != nil) {
            nodes_to_free.push_back(x->right);
        }
 
        delete x;
        while (nodes_to_free.size() > 0) {
            x = nodes_to_free.back();
            nodes_to_free.pop_back();
            if (x->left != nil) {
                nodes_to_free.push_back(x->left);
            }
            if (x->right != nil) {
                nodes_to_free.push_back(x->right);
            }
            delete x;
        }
    }
    delete nil;
    delete root;
    free(recursion_node_stack);
}

Member Function Documentation

deleteFixup()

void inet::IntervalTree::deleteFixup ( Node *  node )

protected

{
    Node *w;
    Node *root_left_node = root->left;
 
    while ((!x->red) && (root_left_node != x)) {
        if (x == x->parent->left) {
            w = x->parent->right;
            if (w->red) {
                w->red = false;
                x->parent->red = true;
                leftRotate(x->parent);
                w = x->parent->right;
            }
            if ((!w->right->red) && (!w->left->red)) {
                w->red = true;
                x = x->parent;
            }
            else {
                if (!w->right->red) {
                    w->left->red = false;
                    w->red = true;
                    rightRotate(w);
                    w = x->parent->right;
                }
                w->red = x->parent->red;
                x->parent->red = false;
                w->right->red = false;
                leftRotate(x->parent);
                x = root_left_node;
            }
        }
        else {
            w = x->parent->left;
            if (w->red) {
                w->red = false;
                x->parent->red = true;
                rightRotate(x->parent);
                w = x->parent->left;
            }
            if ((!w->right->red) && (!w->left->red)) {
                w->red = true;
                x = x->parent;
            }
            else {
                if (!w->left->red) {
                    w->right->red = false;
                    w->red = true;
                    leftRotate(w);
                    w = x->parent->left;
                }
                w->red = x->parent->red;
                x->parent->red = false;
                w->left->red = false;
                rightRotate(x->parent);
                x = root_left_node;
            }
        }
    }
    x->red = false;
}

Referenced by deleteNode().

deleteNode() [1/2]

void inet::IntervalTree::deleteNode

(

const Interval *

ivl

)

delete node stored a given interval

{
    Node *node = recursiveSearch(root, ivl);
    if (node != nil)
        deleteNode(node);
}

deleteNode() [2/2]

const IntervalTree::Interval * inet::IntervalTree::deleteNode

(

Node *

node

)

Delete one node of the interval tree.

y should not be nil in this case y is the node to splice out and x is its child

{
    Node *y;
    Node *x;
    const Interval *node_to_delete = z->stored_interval;
 
    y = ((z->left == nil) || (z->right == nil)) ? z : getSuccessor(z);
    x = (y->left == nil) ? y->right : y->left;
    if (root == (x->parent = y->parent)) {
        root->left = x;
    }
    else {
        if (y == y->parent->left) {
            y->parent->left = x;
        }
        else {
            y->parent->right = x;
        }
    }
 
    if (y != z) {
        y->max_high = -SimTime::getMaxTime(); // -std::numeric_limits<double>::max();
        y->left = z->left;
        y->right = z->right;
        y->parent = z->parent;
        z->left->parent = z->right->parent = y;
        if (z == z->parent->left)
            z->parent->left = y;
        else
            z->parent->right = y;
 
        fixupMaxHigh(x->parent);
        if (!(y->red)) {
            y->red = z->red;
            deleteFixup(x);
        }
        else
            y->red = z->red;
        delete z;
    }
    else {
        fixupMaxHigh(x->parent);
        if (!(y->red))
            deleteFixup(x);
        delete y;
    }
 
    return node_to_delete;
}

Referenced by deleteNode(), and inet::physicallayer::VectorCommunicationCache::removeNonInterferingTransmissions().

fixupMaxHigh()

void inet::IntervalTree::fixupMaxHigh ( Node *  node )

protected

Travels up to the root fixing the max_high fields after an insertion or deletion.

{
    while (x != root) {
        x->max_high = std::max(x->high, std::max(x->left->max_high, x->right->max_high));
        x = x->parent;
    }
}

Referenced by deleteNode(), and insert().

getMaximum()

IntervalTree::Node * inet::IntervalTree::getMaximum

(

Node *

node

)

const

{
    while (x->right != nil)
        x = x->right;
    return x;
}

Referenced by getPredecessor().

getMinimum()

IntervalTree::Node * inet::IntervalTree::getMinimum

(

Node *

node

)

const

{
    while (x->left != nil)
        x = x->left;
    return x;
}

Referenced by getSuccessor().

getPredecessor()

IntervalTree::Node * inet::IntervalTree::getPredecessor

(

Node *

node

)

const

get the predecessor of a given node

{
    Node *y;
 
    if (nil != x->left)
        return getMaximum(x->left);
    else {
        y = x->parent;
        while (y != nil && x == y->left) {
            x = y;
            y = y->parent;
        }
        return y;
    }
}

getSuccessor()

IntervalTree::Node * inet::IntervalTree::getSuccessor

(

Node *

node

)

const

Get the successor of a given node.

{
    Node *y;
 
    if (nil != x->right)
        return getMinimum(x->right);
    else {
        y = x->parent;
        while (y != nil && x == y->right) {
            x = y;
            y = y->parent;
        }
        return y;
    }
}

Referenced by deleteNode().

insert()

IntervalTree::Node * inet::IntervalTree::insert

(

const Interval *

new_interval

)

Insert one node of the interval tree.

use sentinel instead of checking for root

{
    Node *y;
    Node *x;
    Node *new_node;
 
    x = new Node(new_interval);
    recursiveInsert(x);
    fixupMaxHigh(x->parent);
    new_node = x;
    x->red = true;
    while (x->parent->red) {
        if (x->parent == x->parent->parent->left) {
            y = x->parent->parent->right;
            if (y->red) {
                x->parent->red = false;
                y->red = false;
                x->parent->parent->red = true;
                x = x->parent->parent;
            }
            else {
                if (x == x->parent->right) {
                    x = x->parent;
                    leftRotate(x);
                }
                x->parent->red = false;
                x->parent->parent->red = true;
                rightRotate(x->parent->parent);
            }
        }
        else {
            y = x->parent->parent->left;
            if (y->red) {
                x->parent->red = false;
                y->red = false;
                x->parent->parent->red = true;
                x = x->parent->parent;
            }
            else {
                if (x == x->parent->left) {
                    x = x->parent;
                    rightRotate(x);
                }
                x->parent->red = false;
                x->parent->parent->red = true;
                leftRotate(x->parent->parent);
            }
        }
    }
    root->left->red = false;
    return new_node;
}

Referenced by inet::physicallayer::CommunicationCacheBase::setCachedInterval().

leftRotate()

void inet::IntervalTree::leftRotate ( Node *  node )

protected

left rotation of tree node

{
    Node *y;
 
    y = x->right;
    x->right = y->left;
 
    if (y->left != nil)
        y->left->parent = x;
 
    y->parent = x->parent;
 
    if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
 
    y->left = x;
    x->parent = y;
 
    x->max_high = std::max(x->left->max_high, std::max(x->right->max_high, x->high));
    y->max_high = std::max(x->max_high, std::max(y->right->max_high, y->high));
}

Referenced by deleteFixup(), and insert().

print()

void inet::IntervalTree::print

(

)

const

Print the whole interval tree.

{
    recursivePrint(root->left);
}

query()

std::deque< const IntervalTree::Interval * > inet::IntervalTree::query	(	simtime_t	low,
		simtime_t	high
	)

Return result for a given query.

{
    std::deque<const Interval *> result_stack;
    Node *x = root->left;
    bool run = (x != nil);
 
    current_parent = 0;
 
    while (run) {
        if (overlap(low, high, x->key, x->high)) {
            result_stack.push_back(x->stored_interval);
            recursion_node_stack[current_parent].try_right_branch = true;
        }
        if (x->left->max_high >= low) {
            if (recursion_node_stack_top == recursion_node_stack_size) {
                recursion_node_stack_size *= 2;
                recursion_node_stack = (it_recursion_node *)realloc(recursion_node_stack,
                        recursion_node_stack_size * sizeof(it_recursion_node));
                if (recursion_node_stack == nullptr)
                    exit(1);
            }
            recursion_node_stack[recursion_node_stack_top].start_node = x;
            recursion_node_stack[recursion_node_stack_top].try_right_branch = false;
            recursion_node_stack[recursion_node_stack_top].parent_index = current_parent;
            current_parent = recursion_node_stack_top++;
            x = x->left;
        }
        else
            x = x->right;
 
        run = (x != nil);
        while ((!run) && (recursion_node_stack_top > 1)) {
            if (recursion_node_stack[--recursion_node_stack_top].try_right_branch) {
                x = recursion_node_stack[recursion_node_stack_top].start_node->right;
                current_parent = recursion_node_stack[recursion_node_stack_top].parent_index;
                recursion_node_stack[current_parent].try_right_branch = true;
                run = (x != nil);
            }
        }
    }
    return result_stack;
}

Referenced by inet::physicallayer::CommunicationCacheBase::computeInterferingTransmissions().

recursiveInsert()

void inet::IntervalTree::recursiveInsert ( Node *  node )

protected

recursively insert a node

Inserts z into the tree as if it were a regular binary tree.

{
    Node *x;
    Node *y;
 
    z->left = z->right = nil;
    y = root;
    x = root->left;
    while (x != nil) {
        y = x;
        if (x->key > z->key)
            x = x->left;
        else
            x = x->right;
    }
    z->parent = y;
    if ((y == root) || (y->key > z->key))
        y->left = z;
    else
        y->right = z;
}

Referenced by insert().

recursivePrint()

void inet::IntervalTree::recursivePrint ( Node *  node ) const

protected

recursively print a subtree

{
    if (x != nil) {
        recursivePrint(x->left);
        x->print(nil, root);
        recursivePrint(x->right);
    }
}

Referenced by print().

recursiveSearch()

IntervalTree::Node * inet::IntervalTree::recursiveSearch ( Node *  node, const Interval *  ivl  ) const

protected

recursively find the node corresponding to the interval

{
    if (node != nil) {
        if (node->stored_interval == ivl)
            return node;
 
        Node *left = recursiveSearch(node->left, ivl);
        if (left != nil)
            return left;
        Node *right = recursiveSearch(node->right, ivl);
        if (right != nil)
            return right;
    }
 
    return nil;
}

Referenced by deleteNode().

rightRotate()

void inet::IntervalTree::rightRotate ( Node *  node )

protected

right rotation of tree node

{
    Node *x;
 
    x = y->left;
    y->left = x->right;
 
    if (nil != x->right)
        x->right->parent = y;
 
    x->parent = y->parent;
    if (y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x;
 
    x->right = y;
    y->parent = x;
 
    y->max_high = std::max(y->left->max_high, std::max(y->right->max_high, y->high));
    x->max_high = std::max(x->left->max_high, std::max(y->max_high, x->high));
}

Referenced by deleteFixup(), and insert().

Friends And Related Function Documentation

IntervalTreeTest

friend class IntervalTreeTest

friend

Member Data Documentation

current_parent

unsigned int inet::IntervalTree::current_parent = 0

private

Referenced by query().

nil

Node* inet::IntervalTree::nil = nullptr

protected

Referenced by deleteNode(), getMaximum(), getMinimum(), getPredecessor(), getSuccessor(), IntervalTree(), leftRotate(), inet::IntervalTree::Node::print(), query(), recursiveInsert(), recursivePrint(), recursiveSearch(), rightRotate(), and ~IntervalTree().

recursion_node_stack

it_recursion_node* inet::IntervalTree::recursion_node_stack = nullptr

private

Referenced by IntervalTree(), query(), and ~IntervalTree().

recursion_node_stack_size

unsigned int inet::IntervalTree::recursion_node_stack_size = 0

private

Referenced by IntervalTree(), and query().

recursion_node_stack_top

unsigned int inet::IntervalTree::recursion_node_stack_top = 0

private

Referenced by IntervalTree(), and query().

root

Node* inet::IntervalTree::root = nullptr

protected

Referenced by deleteFixup(), deleteNode(), fixupMaxHigh(), insert(), IntervalTree(), inet::IntervalTree::Node::print(), print(), query(), recursiveInsert(), recursivePrint(), and ~IntervalTree().

---

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

• IntervalTree.h
• IntervalTree.cc