RTree in CPP

rtree.cpp

/*
 * main.cpp
 *
 *  Created on: 12-Mar-2015
 *      Author: gangireddy
 * 
 * R-tree implemenatation in cpp
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <set>
#include <queue>
#include <time.h>
#define E 0.001

using namespace std;

int rpt = 0, nextPointer = 0, dim, maxSize, minSize;

struct Point
{
    float p[5];
};

struct Rectangle
{
    float p1[5];
    float p2[5];
};

struct KNNNode
{
    float dist;
    int filePointer;
    Rectangle key;
    bool isData;
};

struct RtreeNode
{
    vector<Rectangle> keys;         // point also consider as rectangle with zero area
    vector<int> filePointers;       // first pointer is special pointer
 //   vector<int> numberofElements;    // used in the enlargement
    bool isLeaf;                   // it will set based on the special pointer value
};

class mycomparison
{
public:
    bool operator() (const KNNNode& lhs, const KNNNode &rhs) const
    {
        return lhs.dist >= rhs.dist;
    }
};

//file structure: is_child, fp 1, val 1, fp 2, val 2, size 2,..., fp n, val n.
//val : 2 * d floating values
void printNode(RtreeNode node)
{
    for(int t = 0; t < node.keys.size(); t++)
    {
        printf("%d\t", node.filePointers[t]);
        for(int i = 0; i < 2 * dim; i++)
        {
            if( i / dim == 0)
               printf("%f\t", node.keys[t].p1[i%dim]);
            else
               printf("%f\t", node.keys[t].p2[i%dim]);
        }
        printf("\n");
    }
}

RtreeNode loadIntoMemory(int fp)
{
    RtreeNode node;
    char fname[33];
    int temp;
    float temp2;
   // bool stopit = false;
    sprintf(fname, "%d.rtree", fp);
    FILE *infile = fopen(fname, "rb");
    if(infile != NULL)
    {
        //special pointer
        fread((char*)&temp, sizeof(temp), 1, infile);
        if(temp >= 0)
            node.isLeaf = false;
        else
            node.isLeaf = true;
        while(1)
        {
            Rectangle rec;
            if(fread((char*)&temp, sizeof(temp), 1, infile) == 0)
                break;
            node.filePointers.push_back(temp);
            //fread((char*)&temp, sizeof(temp), 1, infile);
            //node.numberofElements.push_back(temp);
            //printf("loading keys \n");
            for(int i = 0; i < 2 * dim; i++)
            {
                fread((char*)&temp2, sizeof(temp2), 1, infile);
                if(i / dim == 0)
                    rec.p1[i % dim] = temp2;
                else
                    rec.p2[i % dim] = temp2;
            }
            node.keys.push_back(rec);
        }
        fclose(infile);
    }
    else
    {
        node.isLeaf = true;
    }

    return node;
}

//writebackfile
void writeBacktoMemory(RtreeNode node, int fpt)
{
    char fname[33];
    int temp;
    sprintf(fname, "%d.rtree", fpt);
    FILE *outfile = fopen(fname, "wb");
    //leaf pointer
    if(node.isLeaf)
        temp = -1;
    else
        temp = 1;
    fwrite((char*)&temp, sizeof(temp), 1, outfile);
    for(int j = 0; j < node.keys.size(); j++)
    {
        fwrite((char*)&node.filePointers[j], sizeof(node.filePointers[j]), 1, outfile);
   //     fwrite((char*)&node.numberofElements[j], sizeof(node.numberofElements[j]), 1, outfile);
        for(int i = 0; i < 2 * dim; i++)
        {
            if(i / dim == 0)
                fwrite((char*)&node.keys[j].p1[i % dim], sizeof(float), 1, outfile);
            else
                fwrite((char*)&node.keys[j].p2[i % dim], sizeof(float), 1, outfile);
        }
    }
    fclose(outfile);
    node.filePointers.clear();
    node.keys.clear();
}

//find area of rectangle
float findArea(Rectangle r)
{
    float area = 1;
    for(int i = 0; i < dim; i++)
        area *= (max(r.p2[i], r.p1[i]) - min(r.p2[i], r.p1[i]));

    return area;
}

float findDistance(Point p, Rectangle r)
{
    float distance = 0, temp;
    for(int i = 0; i < dim; i++)
        if(!(p.p[i] >= r.p1[i] && p.p[i] <= r.p2[i]))
        {
            temp = min(fabs(p.p[i] - r.p1[i]), fabs(p.p[i] - r.p2[i]));
            distance += (temp * temp);
        }

    return sqrt(distance);
}

bool isInRange(float p[5], float range, Point p1)
{
    float distance = 0, temp;
    for(int i = 0; i < dim; i++)
    {
        temp = fabs(p[i] - p1.p[i]);
        distance += (temp * temp);
    }
    if(sqrt(distance) <= range)
        return true;
    else
        return false;
}

bool isInsert(Rectangle r1, Rectangle r2)
{
    bool ans = true;
    for(int i = 0; i < dim; i++)
    {
        if(r1.p2[i] < r2.p1[i] || r1.p1[i] > r2.p2[i])
            ans = false;
    }

    return ans;
}

//pick next
int pickNext(RtreeNode &node, Rectangle r1, Rectangle r2, set<int> &comp)
{
    float maxdiff = 0;
    Rectangle d1, d2;
    int next;
    float r1area = findArea(r1), r2area = findArea(r2);
    for(set<int>::iterator i = comp.begin(); i != comp.end(); i++)
    {
        int temp = *i;
        float d1area = 0, d2area = 0;
        for(int k = 0; k < 2 * dim; k++)
        {
            if(k / dim == 0)
                d1.p1[k % dim] = min(node.keys[temp].p1[k % dim], r1.p1[k % dim]);
            else
                d1.p2[k % dim] = max(node.keys[temp].p2[k % dim], r1.p2[k % dim]);
        }
        for(int k = 0; k < 2 * dim; k++)
        {
            if(k / dim == 0)
                d2.p1[k % dim] = min(node.keys[temp].p1[k % dim], r2.p1[k % dim]);
            else
                d2.p2[k % dim] = max(node.keys[temp].p2[k % dim], r2.p2[k % dim]);
        }
        d1area = (findArea(d1) - r1area);
        d2area = (findArea(d2) - r2area);
        float curr = max(d2area, d1area) - min(d2area, d1area);
        if(maxdiff <= curr)
        {
            maxdiff = curr;
            next = temp;
        }
    }
    return next;
}

void printRectangle(Rectangle r)
{
    for(int k = 0; k < 2 * dim; k++)
    {
        if(k / dim == 0)
            printf("%f\t", r.p1[k % dim]);
        else
            printf("%f\t", r.p2[k % dim]);
    }
    printf("\n");
}
// parent and index of child
pair<RtreeNode,int>  splitNode(RtreeNode parent, int cpt)    //return parent file pointer and node
{
    RtreeNode node;
    Rectangle q, group1, group2, q1, q2;
    int e1 = 0, e2 = 1, next;
    pair<RtreeNode,int> ans;
    vector<int> sep1, sep2;
    int arr[maxSize + 1];
    for(int i =0; i < maxSize + 1; i++)
        arr[i] = i;
    set<int> notComp(arr, arr + (maxSize + 1));
    if(cpt == -1) // root case,
    {
        node = parent;
    }
    else
    {
        node = loadIntoMemory(parent.filePointers[cpt]);
    }
    //printNode(node);
    //printf("printing Node:\n");
    float deadSpace = 0, currDead;
    //pick seeds
    for(int i = 0; i < maxSize + 1; i++)
    {
        for(int j = i + 1; j < maxSize + 1; j++)
        {
            //printf("checking %d\n", i+j);
            for(int k = 0; k < 2 * dim; k++)
            {
                if(k / dim == 0)
                    q.p1[k % dim] = min(node.keys[i].p1[k % dim], node.keys[j].p1[k % dim]);
                else
                    q.p2[k % dim] = max(node.keys[i].p2[k % dim], node.keys[j].p2[k % dim]);
            }
            currDead = (findArea(q) - findArea(node.keys[e1]) - findArea(node.keys[e2]));
            if(deadSpace < currDead)
            {
                e1 = i;
                e2 = j;
                deadSpace = currDead;
            }
        }
    }
    //printf("%d\t%d\n: e1 ns ", e1, e2);
    group1 = node.keys[e1];
    sep1.push_back(e1);
    group2 = node.keys[e2];
    sep2.push_back(e2);
    notComp.erase(notComp.find(e1));
    notComp.erase(notComp.find(e2));
    for(int i = 0; i < maxSize - 1; i++)
    {
        if(min(sep1.size(), sep2.size()) + (maxSize - i) <= minSize)
        {
            for(int k = 0; k < 2 * dim; k++)
            {
                if(k / dim == 0)
                    q1.p1[k % dim] = min(group1.p1[k % dim], node.keys[i].p1[k % dim]);
                else
                    q1.p2[k % dim] = max(group1.p2[k % dim], node.keys[i].p2[k % dim]);
            }
            if(sep1.size() < sep2.size())
            {
                sep1.push_back(i);
                group1 = q1;
            }
            else
            {
                sep2.push_back(i);
                group2 = q1;
            }
           // notComp.erase(notComp.find(i));
        }
        else
        {
            next = pickNext(node, group1, group2, notComp);
            //printf("next returned is %d\n", next);
            for(int k = 0; k < 2 * dim; k++)
            {
                if(k / dim == 0)
                    q1.p1[k % dim] = min(group1.p1[k % dim], node.keys[next].p1[k % dim]);
                else
                    q1.p2[k % dim] = max(group1.p2[k % dim], node.keys[next].p2[k % dim]);
            }
            for(int k = 0; k < 2 * dim; k++)
            {
                if(k / dim == 0)
                    q2.p1[k % dim] = min(group2.p1[k % dim], node.keys[next].p1[k % dim]);
                else
                    q2.p2[k % dim] = max(group2.p2[k % dim], node.keys[next].p2[k % dim]);
            }
            //assign next to particular group
            if(findArea(q1) - findArea(q2) < -E)
            {
                sep1.push_back(next);
                group1 = q1;
            }
            else if(max(findArea(q1), findArea(q2)) - min(findArea(q1), findArea(q2)) < E)
            {
                if(findArea(group1) - findArea(group2) < -E)
                {
                    sep1.push_back(next);
                    group1 = q1;
                }
                else if(fabs(findArea(group1) - findArea(group2)) < E)
                {
                    if(sep1.size() < sep2.size())
                    {
                        sep1.push_back(next);
                        group1 = q1;
                    }
                    else
                    {
                        sep2.push_back(next);
                        group2 = q2;
                    }
                }
                else
                {
                    sep2.push_back(next);
                    group2 = q2;
                }
            }
            else
            {
                sep2.push_back(next);
                group2 = q2;
            }
            notComp.erase(notComp.find(next));
        }
    }

    //create two new nodes one with previous name and another with new name and new node types same as split node types
    RtreeNode child, newChild;
    child.isLeaf = node.isLeaf;
    newChild.isLeaf = node.isLeaf;
    for(int i = 0; i < sep1.size(); i++)
    {
        child.keys.push_back(node.keys[sep1[i]]);
        child.filePointers.push_back(node.filePointers[sep1[i]]);
    }
    for(int i = 0; i < sep2.size(); i++)
    {
        newChild.keys.push_back(node.keys[sep2[i]]);
        newChild.filePointers.push_back(node.filePointers[sep2[i]]);
    }

    // adjust parent pointers
    if(cpt == -1)   //root case
    {
        int nxt = nextPointer++;
        writeBacktoMemory(child, rpt);
        writeBacktoMemory(newChild, nxt);
        ans.first.keys.push_back(group1);
        ans.first.keys.push_back(group2);
        ans.first.filePointers.push_back(rpt);
        ans.first.filePointers.push_back(nxt);
        ans.first.isLeaf = false;
        ans.second = nextPointer++;
    }
    else
    {
        int nxt = nextPointer++;
        writeBacktoMemory(child, parent.filePointers[cpt]);
        writeBacktoMemory(newChild, nxt);
        parent.keys[cpt] = group1;
        parent.keys.push_back(group2);
        parent.filePointers.push_back(nxt);
        ans.first = parent;
        ans.second = -1;
    }

    return ans;
}


void insertKey(float p[5], int pointer)
{

    stack< pair<int,int> > path;              // this is the path that follow to reach child
    int ans = rpt, npt;                     // ans = file pointer, npt = index
    pair<int,int> ppt(-1, -1), cpt(-1, -1); // first = file pointer, second = index
    RtreeNode node = loadIntoMemory(ans);   // it will store the leaf node that should
    Rectangle r, modKey;
    //init r value
    for(int i = 0; i < 2 * dim; i++)
    {
        if(i / dim == 0)
            r.p1[i % dim] = p[i % dim];
        else
            r.p2[i % dim] = p[i % dim];
    }
    //init mod key
    for(int i = 0; i < 2 * dim; i++)
    {
    if(i / dim == 0)
        modKey.p1[i % dim] = p[i % dim];
    else
        modKey.p2[i % dim] = p[i % dim];
    }
    //intial case
    if(node.keys.size() == 0)
    {
        node.keys.push_back(r);
        node.filePointers.push_back(pointer);
        node.isLeaf = true;
        int fpt = nextPointer++;
        writeBacktoMemory(node, fpt);
        rpt = fpt;
    }
    else
    {
        //choose child
        while(!node.isLeaf)
        {
            npt = 0;
            float present = 1.0;
            for(int i = 0; i < node.filePointers.size(); i++)
            {
                Rectangle enlarge;
                float incArea;
                for(int k = 0; k < 2 * dim; k++)
                {
                if(k / dim == 0)
                    enlarge.p1[k % dim] = min(node.keys[i].p1[k % dim], p[k % dim]);
                else
                    enlarge.p2[k % dim] = max(node.keys[i].p2[k % dim], p[k % dim]);
                }
                incArea = fabs(findArea(enlarge) - findArea(node.keys[i]));
                if(incArea < present)
                {
                    npt = i;
                    present = incArea;
                }
                else if(fabs(incArea - present) < E)
                {
                    //handle conflict based on area
                    if(findArea(node.keys[i]) < findArea(node.keys[npt]))
                        npt = i;
                }
            }
            path.push(make_pair(ans, npt));     // filepointer and index in that file
            ans = node.filePointers[npt];
            node = loadIntoMemory(ans);
            //printf("%d\t%d\n", ans, npt);
        }
        //place object in node
        node.keys.push_back(r);
        node.filePointers.push_back(pointer);

        //move along the path adjust tree and split node if necessary
        RtreeNode next = node, parent;
        //only root case, node itself root
        if(path.empty())
        {
            if(next.keys.size() <= maxSize)    // no overload then everything is normal
            {
                writeBacktoMemory(next, rpt);
            }
            else                                    // overloaded, split it
            {
                pair<RtreeNode, int> spl = splitNode(next, -1);
                writeBacktoMemory(spl.first, spl.second);
                rpt = spl.second;
            }
        }

        //handle the path by traversing along path
        while(!path.empty())
        {
            ppt = path.top();
            path.pop();
            parent = loadIntoMemory(ppt.first);
            writeBacktoMemory(next, parent.filePointers[ppt.second]);
            if(next.keys.size() <= maxSize)    // no overload then everything is normal
            {
                for(int i = 0; i < 2 * dim;i++)
                {
                if(i / dim == 0)
                    modKey.p1[i % dim] = min(parent.keys[ppt.second].p1[i % dim], modKey.p1[i % dim]);
                else
                    modKey.p2[i % dim] = max(parent.keys[ppt.second].p2[i % dim], modKey.p2[i % dim]);
                }
                //reached to top, no
                if(path.empty())
                {
                    parent.keys[ppt.second] = modKey;
                    writeBacktoMemory(parent, rpt);
                    break;
                }
                else
                {
                    parent.keys[ppt.second] = modKey;
                    next = parent;
                }
            }
            else
            {
                //moved to top
                if(path.empty())
                {
                    pair<RtreeNode, int> spl = splitNode(parent, ppt.second);
                    if(spl.first.keys.size() <= maxSize)
                    {
                        writeBacktoMemory(spl.first, rpt);
                    }
                    else
                    {
                        //root split
                        spl = splitNode(spl.first, -1);
                        writeBacktoMemory(spl.first, spl.second);
                        rpt = spl.second;
                    }
                    break;
                }
                else
                {
                    pair<RtreeNode, int> spl = splitNode(parent, ppt.second);
                    next = spl.first;
                    //adjust tree
                    for(int i = 0; i < 2 * dim;i++)
                    {
                        if(i / dim == 0)
                            modKey.p1[i % dim] = min(spl.first.keys[ppt.second].p1[i % dim], modKey.p1[i % dim]);
                        else
                            modKey.p2[i % dim] = max(spl.first.keys[ppt.second].p2[i % dim], modKey.p2[i % dim]);
                    }
                    for(int i = 0; i < 2 * dim;i++)
                    {
                        if(i / dim == 0)
                            modKey.p1[i % dim] = min(spl.first.keys[spl.first.keys.size()-1].p1[i % dim], modKey.p1[i % dim]);
                        else
                            modKey.p2[i % dim] = max(spl.first.keys[spl.first.keys.size()-1].p2[i % dim], modKey.p2[i % dim]);
                    }
                }
            }
        }
    }
}

void windowQuery(vector<Point> &ans, int nodePointer, Rectangle query)
{
    RtreeNode node = loadIntoMemory(nodePointer);
    if(!node.isLeaf)
    {
        for(int i = 0; i < node.keys.size(); i++)
        {
            if(isInsert(node.keys[i], query))
                windowQuery(ans, node.filePointers[i], query);
        }
    }
    else
    {
        Point temp;
        for(int i = 0; i < node.keys.size(); i++)
        {
            if(isInsert(node.keys[i], query))
            {
                for(int j = 0; j < dim; j++)
                    temp.p[j] = node.keys[i].p1[j];
                ans.push_back(temp);
            }
        }
    }
}

void kNNQuery(vector<Point> &ans, int rootPointer, Point query, int k)
{
    /*
    1. push root along with key and dist = 0 in min heap based on dist
    2. pop next element from heap
    3. if next == internal node, pop it and push all its children along with calculated kdRegion and dist
    4. if next == leaf, push data KDpoint in it
    5. if next == isData and count < k, report it
    */
    priority_queue<KNNNode,std::vector<KNNNode>, mycomparison> PQ;
    KNNNode temp, temp2;
    int counter = 0;
    Point tempPoint;
    temp.filePointer = rpt;
    for(int i = 0; i < 2 * dim; i++)
    {
        if(i / dim == 0)
            temp.key.p1[i % dim] = 0.0;
        else
            temp.key.p2[i % dim] = 1.0;
    }
    temp.dist = 0.0;
    temp.isData = false;
    PQ.push(temp);
    while(!PQ.empty())
    {
        temp = PQ.top();
        PQ.pop();
        if(!temp.isData)
        {
            RtreeNode node = loadIntoMemory(temp.filePointer);
            if(node.isLeaf)
            {
                //loaf all knnndoes as data points with actual distance
                for(int i = 0; i < node.keys.size(); i++)
                {
                    temp2.filePointer = 0;
                    temp2.dist = findDistance(query, node.keys[i]);
                    temp2.isData = true;
                    temp2.key = node.keys[i];
                    PQ.push(temp2);
                }
            }
            else
            {
                for(int i = 0; i < node.keys.size(); i++)
                {
                    temp2.filePointer = node.filePointers[i];
                    temp2.dist = findDistance(query, node.keys[i]);
                    temp2.isData = false;
                    temp2.key = node.keys[i];
                    PQ.push(temp2);
                }
            }
        }
        else
        {
            if(counter < k)
            {
                counter++;
                for(int j = 0; j < dim; j++)
                    tempPoint.p[j] = temp.key.p1[j];
                ans.push_back(tempPoint);
            }
            else
            {
                break;
            }
        }
    }
}

void pointQuery(vector<Point> &ans, float p[5])
{
    Rectangle query;
    for(int k = 0; k < 2 * dim; k++)
    {
        if(k / dim == 0)
            query.p1[k % dim] = p[k % dim];
        else
            query.p2[k % dim] = p[k % dim];
    }
    windowQuery(ans, rpt, query);
}

void rangeQuery(vector<Point> &ans, float p[5], float range)
{
    vector<Point> temp;
    Rectangle query;
    for(int k = 0; k < 2 * dim; k++)
    {
        if(k / dim == 0)
            query.p1[k % dim] = p[k % dim] - range;
        else
            query.p2[k % dim] = p[k % dim] + range;
    }
    windowQuery(temp, rpt, query);
    //refining window
    for(int i = 0; i < temp.size(); i++)
    {
        if(isInRange(p, range, temp[i]))
            ans.push_back(temp[i]);
    }
}

void BuildTree(FILE *fp, FILE *fpdata)
{
    int i, j = 0, counter = 1000000, objptr = 0;
    char obj[14];
    float point[5];
    while(counter--)
    {
        for(int k = 0; k < dim; k++)
            fscanf(fp, "%f", &point[k]);
        fscanf(fp, "%s", obj);
        j++;
        if(j % 1000 == 0)
        {
            printf("inserting %d\n", j);
        }
        //fwrite (obj , sizeof(char), 13, fpdata);
        insertKey(point, objptr);
        objptr += 13;
    }
}

int calcBeta(int page, int dim)
{
    page -= 4 ; // for leaf pointers
    return page / (2 * dim * sizeof(float) + sizeof(int));
}
int main()
{
    FILE *inputdata = fopen("assgn4_r_data.txt", "r");
    FILE *queryFile = fopen("assgn4_r_querysample.txt", "r");
    FILE *reportFile = fopen("reportfile.csv", "w");
    FILE *outputFile = fopen("outputfile.txt", "w");
    FILE *outdata = fopen("objdata.txt", "w");
    FILE *configFile = fopen("rtree.config", "r");

    int choice = 0, j = 0, pageSize;
    char obj[14];
    float temp[5], start, t, range;
    int objptr = 13000000, k;
    Rectangle query, revisedQuery;
    Point knn;
    vector<Point> ans;
    fscanf(configFile,"%d", &pageSize);
    fscanf(configFile,"%d", &dim);
    maxSize = calcBeta(pageSize, dim);
    minSize = maxSize / 2;
    printf("maxsize, dim is : %d\t%d\n", maxSize, dim);
    //building tree
    BuildTree(inputdata, outdata);
    j = 0;
	while(fscanf(queryFile, "%d", &choice) == 1)
	{
		j++;
		if(j % 500 == 0)
		{
			printf("accessing %d query\n", j);
		}
		switch(choice)
		{
		case 0:
			for(int i = 0; i < dim; i++)
				fscanf(queryFile,"%f", &temp[i]);
            fscanf(queryFile,"%s", obj);
			fwrite (obj , sizeof(char), 13, outdata);
			start = clock();
			insertKey(temp, objptr);
			t = float( clock() - start ) ;
			objptr += 13;
			fprintf(reportFile, "%d,%f\n", choice, t);
			fprintf(outputFile,"%d\t", choice);
			for(int i = 0; i < dim; i++)
				fprintf(outputFile,"%f\t", temp[i]);
			fprintf(outputFile,"%s\n", obj);
			break;
		case 1:
			ans.clear();
			for(int i = 0; i < dim; i++)
				fscanf(queryFile,"%f", &temp[i]);
            start = clock();
			pointQuery(ans, temp);
			t = float( clock() - start ) ;
			fprintf(reportFile, "%d,%f\n", choice, t);
			fprintf(outputFile,"%d\t", choice);
			for(int i = 0; i < dim; i++)
				fprintf(outputFile,"%f\t", temp[i]);
			fprintf(outputFile,"\n");
			if(ans.size() != 0)
			for(int i = 0; i < dim; i++)
				fprintf(outputFile,"%f\t", ans[0].p[i]);
			fprintf(outputFile,"\n");
			break;

		case 2:
			ans.clear();
			for(int i = 0; i < dim; i++)
				fscanf(queryFile,"%f", &temp[i]);
		    fscanf(queryFile,"%f", &range);
			start = clock();
			rangeQuery(ans, temp, range);
			t = float( clock() - start )  ;
			fprintf(reportFile, "%d,%f,%d\n", choice, t, ans.size());
			fprintf(outputFile,"%d\t", choice);
			for(int i = 0; i < dim; i++)
				fprintf(outputFile,"%f\t", temp[i]);
			fprintf(outputFile,"%f\n", range);
			for(int j = 0; j < ans.size(); j++)
				for(int i = 0; i < dim; i++)
					fprintf(outputFile,"%f\t", ans[j].p[i]);
			fprintf(outputFile,"\n");
			break;

		case 3:
			ans.clear();
			for(int i = 0; i < dim; i++)
				fscanf(queryFile,"%f", &knn.p[i]);
			fscanf(queryFile,"%d", &k);
			start = clock();
			kNNQuery(ans, rpt, knn, k);
			t = float( clock() - start ) ;
			fprintf(reportFile, "%d,%f,%d\n", choice, t, ans.size());
			fprintf(outputFile,"%d\t", choice);
			for(int i = 0; i < dim; i++)
				fprintf(outputFile,"%f\t", temp[i]);
			fprintf(outputFile,"%d\n", k);
			for(int j = 0; j < ans.size(); j++)
				for(int i = 0; i < dim; i++)
					fprintf(outputFile,"%f\t", ans[j].p[i]);
			fprintf(outputFile,"\n");
		break;
		case 4:
			ans.clear();
			for(int i = 0; i < 2 * dim; i++)
			{
				if(i / dim == 0)
					fscanf(queryFile,"%f", &query.p1[i % dim]);
				else
					fscanf(queryFile,"%f", &query.p2[i % dim]);
			}
			for(int i = 0; i < 2 * dim; i++)
			{
				if(i / dim == 0)
                    revisedQuery.p1[i%dim] = min(query.p1[i % dim], query.p2[i % dim]);
				else
					revisedQuery.p2[i%dim] = max(query.p1[i % dim], query.p2[i % dim]);
			}
			start = clock();
			windowQuery(ans, rpt, revisedQuery);
			t = float( clock() - start );
			fprintf(reportFile, "%d,%f,%d\n", choice, t, ans.size());
			fprintf(outputFile,"%d\t", choice);
			for(int i = 0; i < 2 * dim; i++)
			{
				if(i / dim == 0)
					fprintf(outputFile,"%f\t", query.p1[i % dim]);
				else
					fprintf(outputFile,"%f\t", query.p2[i % dim]);
			}
			fprintf(outputFile,"\n");
			for(int j = 0; j < ans.size(); j++)
				for(int i = 0; i < dim; i++)
					fprintf(outputFile,"%f\t", ans[j].p[i]);
			fprintf(outputFile,"\n");
			break;
		}
        }
    return 0;
}