inet::IntervalTree Class Reference

Interval tree. More...

#include <IntervalTree.h>

Public Member Functions
	IntervalTree ()
	~IntervalTree ()
void	print () const
	Print the whole interval tree. More...
const Interval *	deleteNode (IntervalTreeNode *node)
	Delete one node of the interval tree. More...
void	deleteNode (const Interval *ivl)
	delete node stored a given interval More...
IntervalTreeNode *	insert (const Interval *new_interval)
	Insert one node of the interval tree. More...
IntervalTreeNode *	getMinimum (IntervalTreeNode *node) const
IntervalTreeNode *	getMaximum (IntervalTreeNode *node) const
IntervalTreeNode *	getPredecessor (IntervalTreeNode *node) const
	get the predecessor of a given node More...
IntervalTreeNode *	getSuccessor (IntervalTreeNode *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 (IntervalTreeNode *node)
	left rotation of tree node More...
void	rightRotate (IntervalTreeNode *node)
	right rotation of tree node More...
void	recursiveInsert (IntervalTreeNode *node)
	recursively insert a node More...
void	recursivePrint (IntervalTreeNode *node) const
	recursively print a subtree More...
IntervalTreeNode *	recursiveSearch (IntervalTreeNode *node, const Interval *ivl) const
	recursively find the node corresponding to the interval More...
void	fixupMaxHigh (IntervalTreeNode *node)
	Travels up to the root fixing the max_high fields after an insertion or deletion. More...
void	deleteFixup (IntervalTreeNode *node)

Protected Attributes
IntervalTreeNode *	root = nullptr
IntervalTreeNode *	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

inet::IntervalTree::IntervalTree

(

)

the following are used for the query function

{
    nil = new IntervalTreeNode;
    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 IntervalTreeNode;
    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;
}

inet::IntervalTree::~IntervalTree

(

)

{
    IntervalTreeNode* x = root->left;
    std::deque<IntervalTreeNode*> 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

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

protected

{
    IntervalTreeNode* w;
    IntervalTreeNode* 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;
}

const Interval * inet::IntervalTree::deleteNode

(

IntervalTreeNode *

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

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

{
    IntervalTreeNode* y;
    IntervalTreeNode* 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;
}

void inet::IntervalTree::deleteNode

(

const Interval *

ivl

)

delete node stored a given interval

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

void inet::IntervalTree::fixupMaxHigh ( IntervalTreeNode *  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;
    }
}

IntervalTreeNode * inet::IntervalTree::getMaximum

(

IntervalTreeNode *

node

)

const

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

IntervalTreeNode * inet::IntervalTree::getMinimum

(

IntervalTreeNode *

node

)

const

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

IntervalTreeNode * inet::IntervalTree::getPredecessor

(

IntervalTreeNode *

node

)

const

get the predecessor of a given node

{
    IntervalTreeNode* 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;
    }
}

IntervalTreeNode * inet::IntervalTree::getSuccessor

(

IntervalTreeNode *

node

)

const

Get the successor of a given node.

{
    IntervalTreeNode* 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;
    }
}

IntervalTreeNode * inet::IntervalTree::insert

(

const Interval *

new_interval

)

Insert one node of the interval tree.

use sentinel instead of checking for root

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

{
    IntervalTreeNode* y;
    IntervalTreeNode* x;
    IntervalTreeNode* new_node;

    x = new IntervalTreeNode(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;
}

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

protected

left rotation of tree node

{
    IntervalTreeNode* 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));
}

void inet::IntervalTree::print

(

)

const

Print the whole interval tree.

{
    recursivePrint(root->left);
}

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

Return result for a given query.

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

{
    std::deque<const Interval*> result_stack;
    IntervalTreeNode* 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;
}

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

protected

recursively insert a node

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

{
    IntervalTreeNode* x;
    IntervalTreeNode* 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;
}

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

protected

recursively print a subtree

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

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

protected

recursively find the node corresponding to the interval

{
    if (node != nil)
    {
        if (node->stored_interval == ivl)
            return node;

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

    return nil;
}

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

protected

right rotation of tree node

{
    IntervalTreeNode* 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));
}

Friends And Related Function Documentation

friend class IntervalTreeTest

friend

Member Data Documentation

unsigned int inet::IntervalTree::current_parent = 0

private

IntervalTreeNode* inet::IntervalTree::nil = nullptr

protected

it_recursion_node* inet::IntervalTree::recursion_node_stack = nullptr

private

unsigned int inet::IntervalTree::recursion_node_stack_size = 0

private

unsigned int inet::IntervalTree::recursion_node_stack_top = 0

private

IntervalTreeNode* inet::IntervalTree::root = nullptr

protected

---

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

• IntervalTree.h
• IntervalTree.cc