Range Tree in CPP

range_tree.cpp

#include <iostream> 
#include <vector>
#include <algorithm>
#include <time.h>
#include <math.h>


using namespace std;

struct point
{
    double x;
    double y;
    double h;
};

struct rectangle
{
    double x1;
    double x2;
    double y1;
    double y2;
};

struct assosiateNode
{
    double yvalue;
    double hmax;
    assosiateNode *latree;
    assosiateNode *ratree;
    bool isChild;
};

struct Node
{
    double xvalue;
    Node *rtree;
    Node *ltree;
    assosiateNode *ytree;
    bool isChild;
};


//comparator functions
bool xcomp (point p1,point p2) { return p1.x < p2.x; }
bool ycomp (point p1,point p2) { return p1.y < p2.y; }

//swap function
void swap(double *a, double *b)
{
    double temp;
    
    temp = *a;
    *a = *b;
    *b = temp;
}

// assume that recived y-soted array
assosiateNode* BuildassTree(vector<point> Parray,int str,int ed)
{
    //finding hmax
    double maxh = -1;
    
    for(int i = str; i <= ed; i++)
    {
        if(maxh < Parray[i].h)
            maxh = Parray[i].h;
    }
        
    //if contains only one element
    if(str == ed)
    {
        assosiateNode *temp = new assosiateNode;
        temp->hmax = maxh;
        temp->yvalue = Parray[str].y;
        temp->latree = NULL;
        temp->ratree = NULL;
        temp->isChild = true;

        return temp;
    }
    else
    {
        int mid = (str + ed ) / 2;
        assosiateNode *temp = new assosiateNode;
        temp->yvalue = Parray[mid].y;
        temp->isChild = false;
        temp->hmax = maxh;
        temp->latree = BuildassTree(Parray,str, mid);
        temp->ratree = BuildassTree(Parray,mid+1, ed);
              
        return temp;
    }
}


//received sorted array based on x-coordiante
Node* BuildRangeTree(vector<point> Parray, int str, int ed)
{
    vector<point> anotherarray;
    for(int i=str; i <= ed ; i++)
    {
        anotherarray.push_back(Parray[i]);
    }
    
    //sort based on y-coordinate
    sort (anotherarray.begin(), anotherarray.end(), ycomp);
    assosiateNode *Tass = BuildassTree(anotherarray,0,anotherarray.size()-1);
    if(str == ed)
    {
        // creating new node;
        Node *temp = new Node;
        temp->xvalue = Parray[str].x;
        temp->rtree = NULL;
        temp->ltree = NULL;
        temp->isChild = true;
        temp->ytree = Tass;

        return temp;
    }
    else
    {
        int mid = (str + ed) / 2;
        Node *temp = new Node;
        temp->xvalue = Parray[mid].x;
        temp->isChild = false;
        temp->ytree = Tass;
        temp->ltree = BuildRangeTree(Parray, str, mid);
        temp->rtree = BuildRangeTree(Parray, mid+1, ed);
        
        return temp;
    }
}

// asumption that y1 < y2
assosiateNode* Find1DSplitNode(assosiateNode *tree, double y1, double y2)
{
    if(y1 > y2)
    {
        swap(&y1, &y2);
    }
    assosiateNode *temp = tree;
    while( ! temp->isChild && (temp->yvalue >= y2 || temp->yvalue < y1))
    {
       
        if(temp->yvalue >= y2)
        {
       
            temp = temp->latree;
        }
        else
        {
            temp = temp->ratree;
       
        }
    }
    return temp;
}

// asumption that x1 < x2
Node* Find2DSplitNode(Node *tree, double x1, double x2)
{
    if(x1 > x2)
    {
        swap(&x1, &x2);
    }
    Node *temp = tree;
    while(! temp->isChild && (temp->xvalue >= x2 || temp->xvalue < x1))
    {
        if(temp->xvalue >= x2)
        {
            temp = temp->ltree;
        }
        else
            temp = temp->rtree;
    }
    return temp;
}

double Range1Dquery(assosiateNode *tree, double y1, double y2)
{
        
        assosiateNode *split = Find1DSplitNode(tree, y1, y2);       
        
        if(split->isChild)
        {
       
            if(y1 <= split->yvalue && y2 >= split->yvalue)
                return split->hmax;
            else 
                return -1;                        
        }
        else
        {
            double maxh = -1;

            // right of the path
            assosiateNode *leftnode = split->latree;
            while(!leftnode->isChild)
            {
                if (y1 <= leftnode->yvalue)
                {
                    double k = leftnode->ratree->hmax;
                    if( maxh < k)
                    maxh = k; 
                    leftnode = leftnode->latree;
                }
                else
                    leftnode = leftnode->ratree;
           }
           
           if(y1 <= leftnode->yvalue && y2 >= leftnode->yvalue)
           {
                double k = leftnode->hmax;
                if( maxh < k)
                    maxh = k; 
           }
           // left of the path
            assosiateNode *rightnode = split->ratree;
            while(!rightnode->isChild)
            {
                if (y2 >= rightnode->yvalue)
                {
                    double k = rightnode->latree->hmax;
                    if(maxh < k)
                        maxh = k;
                    rightnode = rightnode->ratree;
                }
                else
                    rightnode = rightnode->latree;
           }
           
           if(y1 <= rightnode->yvalue && y2 >= rightnode->yvalue)
           {
                double k = rightnode->hmax;
                if( maxh < k)
                    maxh = k; 
           }
            return maxh;
        }
}


double Range2Dquery(Node *tree, rectangle R)
{
        Node *split = Find2DSplitNode(tree, R.x1, R.x2); 
       
        if(split->isChild)
        {
            if(R.x1 <= split->xvalue && R.x2 >= split->xvalue)
                return Range1Dquery(split->ytree, R.y1, R.y2);
            else 
                return -1;                        
        }
        else
        {
            double maxh = -1;
            // right of the path
            Node *leftnode = split->ltree;
            
            while(! leftnode->isChild)
            {
                if (R.x1 <= leftnode->xvalue)
                {
                    double k = Range1Dquery(leftnode->rtree->ytree, R.y1, R.y2);
                    if( maxh < k)
                    maxh = k; 
                    leftnode = leftnode->ltree;
                }
                else
                {
                    leftnode = leftnode->rtree;
                }
           }
           
           
            if(R.x1 <= leftnode->xvalue && R.x2 >= leftnode->xvalue)
            {
                 double k = Range1Dquery(leftnode->ytree, R.y1, R.y2);
                 if( maxh < k)
                      maxh = k;                      
            }
            
           // left of the path
            Node *rightnode = split->rtree;
            while(! rightnode->isChild)
            {
                if (R.x2 >= rightnode->xvalue)
                {
                    double k = Range1Dquery(rightnode->ltree->ytree, R.y1, R.y2); 
                    if(maxh < k)
                        maxh = k;
                    rightnode = rightnode->rtree;
                }
                else
                    rightnode = rightnode->ltree;
           }
           
           if(R.x1 <= rightnode->xvalue && R.x2 >= rightnode->xvalue)
           {
             double k = Range1Dquery(rightnode->ytree, R.y1, R.y2);
             if( maxh < k)
                  maxh = k;                      
           }
            return maxh;
        }
}

//unit testing
void printArray(vector<point> test)
{
    for(int i = 0; i < test.size(); i++)
    {
        cout << i << "\t" << test[i].x << "\t" << test[i].y << "\t" << test[i].h << endl;
    }
}

void inorderAssTree(assosiateNode *root)
{
    if(root == NULL)
        return;
        
    inorderAssTree(root->latree);
    cout << root->yvalue << "\t" ;
    inorderAssTree(root->ratree);    
}

void inorderRangeTree(Node *root)
{
 
    if(root == NULL)
        return;
        
    inorderRangeTree(root->ltree);
    cout << root->xvalue << "\t" ;
    inorderRangeTree(root->rtree);
   // inorderAssTree(root->ytree);
}




int main()
{
    // make points, before calling build2DrangeTree() sort based on x-coordiante
    
    vector<point> test;
    
    srand (time(NULL));
    
    for(int i = 0; i < 16; i++)
    {
        point temp;
        temp.x = rand() % 100 + 1;
        temp.y = rand() % 100 + 1;
        temp.h = rand() % 100 + 1;
       
        test.push_back(temp);
               
    }
    
    sort (test.begin(), test.end(), xcomp);
    cout << "test elements: after sorting based on X " << endl;
    printArray(test);
    
    Node *root = BuildRangeTree(test, 0, test.size()-1);
    
    rectangle R;
    R.x1 = 20;
    R.x2 = 60;
    R.y1 = 10;
    R.y2 = 78;
    
    cout << " Final Answer" << Range2Dquery(root, R) << endl;
    
    return 0;
}