Solved

Need some help with C++ creating an R*-tree

Posted on 2009-07-12
23
831 Views
Last Modified: 2012-05-07
I have this code that generates an R*-tree, but when I create the tree it's always empty, and I need to generate some data to it.

Here is the code for the R*-tree and also the code on how I create the TREE. The problem is when I check the tree is always empty...

here is the source code for all the files just in case you needed.
http://tinyurl.com/la8s2c



Here is the code where I create the tree.
 

// Constructor to create the tree.

RjoinR::RjoinR(char *fileName1, int typeOfTree1, int bufferSize1, int bufferType1, int maxFanout1, int minFanout1, char *fileName2, int typeOfTree2, int bufferSize2, int bufferType2, int maxFanout2, int minFanout2, char *fileResult)

{

	char resultFile[32];

	char statisticsFile[32];
 

	// In order to calculate the maximum number of items inside the Heap

	maxHeapSize = 0;

	numberOfInsertions = 0;

	numberOfDeletions = 0;

	sizeHeapElement = 0;

	itemsUsed = 0;

	itemsNoUsed = 0;

	lastUpperBound = -1.0;

	lastMinMinDist = -1.0;

	maxPQsize = 0;

	numberOfPQInsertions = 0;

	numberOfPQDeletions = 0;

	sizePQElement = 0;

	numberOfDecomposedSubproblems = 0;

	numberOfObjObjDistanceCalculations = 0;

	numberOfMinMinDistRectRectCalculations = 0;

	numberOfMinMaxDistRectRectCalculations = 0;

	numberOfMaxMaxDistRectRectCalculations = 0;

	numberOfMinMinDistRectObjCalculations = 0;

	numberOfMinMaxDistRectObjCalculations = 0;

	numberOfMaxMaxDistRectObjCalculations = 0;

	numberOfSortings = 0;

	totalNumberOfSortedPairs = 0.0;
 

	// R1 = First R*-tree

	R1 = new Rtree(fileName1, typeOfTree1, bufferSize1, bufferType1, maxFanout1, minFanout1);

	if (!R1)

	{

		printf("\nRjoinR::RjoinR => File error 1, creating R1.\n");

		exit(1);

	}

	

	// R2 = Second R*-tree

	R2 = new Rtree(fileName2, typeOfTree2, bufferSize2, bufferType2, maxFanout2, minFanout2);

	if (!R2)

	{

		printf("\nRjoinR::RjoinR => File error 2, creating R2.\n");

		exit(1);

	}
 

	// File of Results

	strcpy(resultFile, fileResult);

	strcat(resultFile, ".cpq");

	if((result = fopen(resultFile, "w+b")) == NULL)

	{

		printf("\nRjoinR::RjoinR => File error 3, craeting result file.\n");

		exit(1);

	}
 

	// File of statistics

	strcpy(statisticsFile, fileResult);

	strcat(statisticsFile, ".stc") ;

	if((statistic = fopen(statisticsFile, "w+t")) == NULL)

	{

		printf("\nRjoinR::RjoinR => File error 4, creating statistics file.\n");

		exit(1);

	}
 

	// ***** 

	// Auxiliary File (TRACE OF THE ALGORITHMS)

	//char auxiliaryFile[32];

	//strcpy(auxiliaryFile, "aaaaa");

	//strcat(auxiliaryFile, ".aaa");

	//if((auxiliaryFile = fopen(auxiliaryFile, "w+b")) == NULL)

	//{

	//	printf("\nRjoinR::RjoinR => File error 5, creating auxiliary file.\n");

	//	exit(1);

	//}

	// ***** 
 

	//R1->traverse_treeBuff();

	//R2->traverse_treeBuff();

	//printf("Height of R1 = %d\n", R1->get_height());

	//printf("Height of R2 = %d\n", R2->get_height());
 

}
 
 

R*-tree code.

*********************************************************
 

#include <stdlib.h>

#include <math.h>

#include <string.h>

#include <time.h>
 

//#include <io.h>

#include <unistd.h>
 

#include "Rstar.hpp"

#include "lrubuff.hpp"

//#include "Two.h"
 

#define MAXDOUBLE 1.7E+308

#define MAXFLOAT 3.4E+38
 

// MINDIST

// Minimum Distance between point and rectangle.

double Rect::MINDIST_Rect_Point(Rect point)

{

	int d;

	double minDist, r;

	double auxMinDist;
 

	auxMinDist = 0.0;

	for(d = 0; (d < dimensionality); d++)		

	{

		if (point.minCoords[d] < minCoords[d])

			r = minCoords[d];

		else

		{

			if (point.minCoords[d] > maxCoords[d])

				r = maxCoords[d];

			else

				r = point.minCoords[d];

		}

		auxMinDist += ((point.minCoords[d] - r) * (point.minCoords[d] - r));

	}
 

	//minDist = auxMinDist;
 

	minDist = sqrt(auxMinDist);

	if (minDist < 0.0)

	{

		printf("\nError: sqrt returns %.6f\n", minDist);

		return minDist;

	}
 

	return minDist;
 

}

//
 

// MAXDIST

// Maximum Distance between point and rectangle.

double Rect::MAXDIST_Rect_Point(Rect point)

{

	int d;

	double maxDist, r;

	double auxMaxDist;
 

	auxMaxDist = 0.0;

	for(d = 0; (d < dimensionality); d++)		

	{

		if (point.minCoords[d] <= ((minCoords[d] + maxCoords[d]) / 2.0))

			r = maxCoords[d];

		else

			r = minCoords[d];

		auxMaxDist += ((point.minCoords[d] - r) * (point.minCoords[d] - r));

	}
 

	//maxDist = auxMaxDist;
 

	maxDist = sqrt(auxMaxDist);

	if (maxDist < 0.0)

	{

		printf("\nError: sqrt returns %.6f\n", maxDist);

		return maxDist;

	}
 

	return maxDist;
 

}

//
 

// MINMAXDIST

// Minimum value of the all the maximum distances between the

// point and points of the each of the d (dimensionality) axes

// respectively.

// MINMAXDIST between point and rectangle.

double Rect::MINMAXDIST_Rect_Point(Rect point)

{

	int k;

	double minMaxDist, rm, rM;

	double auxMinMaxDist;

	double *S;

	double sum;
 

	S = new double[dimensionality];

	if (!(S))

	{

		printf("\nNo enough memory for temporary array of distances.\n");

		return 0.0;

	}
 

	sum = 0;

	for(k = 0; (k < dimensionality); k++)		

	{

		if (point.minCoords[k] >= ((minCoords[k] + maxCoords[k]) / 2.0))

			rM = minCoords[k];

		else

			rM = maxCoords[k];

		sum += ((point.minCoords[k] - rM) * (point.minCoords[k] - rM));

	}
 

	for(k = 0; (k < dimensionality); k++)		

		S[k] = sum;
 

	for(k = 0; (k < dimensionality); k++)		

	{

		if (point.minCoords[k] >= ((minCoords[k] + maxCoords[k]) / 2.0))

			rM = minCoords[k];

		else

			rM = maxCoords[k];

		S[k] -= ((point.minCoords[k] - rM) * (point.minCoords[k] - rM));
 

		if (point.minCoords[k] <= ((minCoords[k] + maxCoords[k]) / 2.0))

			rm = minCoords[k];

		else

			rm = maxCoords[k];

		S[k] += ((point.minCoords[k] - rm) * (point.minCoords[k] - rm));

	}
 

	auxMinMaxDist = MAXDOUBLE;

	for(k = 0; (k < dimensionality); k++)		

	{

		if (S[k] < auxMinMaxDist)

			auxMinMaxDist = S[k];

	}
 

	//minMaxDist = auxMinMaxDist;
 

	minMaxDist = sqrt(auxMinMaxDist);

	if (minMaxDist < 0.0)

	{

		printf("\nError: sqrt returns %.6f\n", minMaxDist);

		return minMaxDist;

	}
 

	delete [] S;
 

	return minMaxDist;
 

}

//
 

// Distance between two points

double Rect::pointDistance(Rect point)

{

	int d;

	double distance, auxDistance;
 

	auxDistance = 0.0;

	for (d = 0; (d < dimensionality); d++)		

		auxDistance += ((minCoords[d] - point.minCoords[d]) * (minCoords[d] - point.minCoords[d]));
 

	//distance = auxDistance;
 

	distance = sqrt(auxDistance);

	if (distance < 0.0)

	{

		printf("\nError: sqrt returns %.6f\n", distance);

		return distance;

	}
 

	return distance;
 

}

//
 

// Distance between two points

void Rect::pointDistance(Rect point, double *distance1, double *distance2)

{

	int d;

	double auxDistance;
 

	auxDistance = 0.0;

	for (d = 0; (d < dimensionality); d++)		

		auxDistance += ((minCoords[d] - point.minCoords[d]) * (minCoords[d] - point.minCoords[d]));
 

	//*distance1 = auxDistance;
 

	*distance1 = sqrt(auxDistance);

	if (*distance1 < 0.0)

	{

		printf("\nError: sqrt returns %.6f\n", *distance1);

		abort();

	}
 

	auxDistance = 0.0;

	for (d = 0; (d < dimensionality); d++)		

		auxDistance += ((maxCoords[d] - point.minCoords[d]) * (maxCoords[d] - point.minCoords[d]));
 

	//*distance2 = auxDistance;
 

	*distance2 = sqrt(auxDistance);

	if (*distance2 < 0.0)

	{

		printf("\nError: sqrt returns %.6f\n", *distance2);

		abort();

	}

}

//
 

double Rect::axisDistance(Rect rect, int axis)

{

	double distance;
 

	distance = 0.0;

	if (maxCoords[axis] < rect.minCoords[axis])

		distance = rect.minCoords[axis] - maxCoords[axis];

	else

	{

		if (rect.maxCoords[axis] < minCoords[axis])

			distance = minCoords[axis] - rect.maxCoords[axis];

		else

			distance = 0.0;

	}
 

	return distance;
 

}
 
 

// MINMINDIST between two rectangles using edges

double Rect::MINMINDIST_Rect_Rect(Rect rect)

{

	int k;

	double minMinDist, l;

	double auxMinMinDist;
 

	auxMinMinDist = 0.0;

	for(k = 0; (k < dimensionality); k++)		

	{

		if (rect.minCoords[k] > maxCoords[k])

			l = rect.minCoords[k] - maxCoords[k];

		else

		{

			if (minCoords[k] > rect.maxCoords[k])

				l = minCoords[k] - rect.maxCoords[k];

			else

				l = 0.0;

		}
 

		auxMinMinDist += (l * l);

	}
 

	//minMinDist = auxMinMinDist;
 

	minMinDist = sqrt(auxMinMinDist);

	if (minMinDist < 0.0)

	{

		printf("\nError: sqrt returns %.6f\n", minMinDist);

		return minMinDist;

	}
 

	return minMinDist;
 

}
 

// MAXMAXDIST between two rectangles.

double Rect::MAXMAXDIST_Rect_Rect(Rect rect)

{

	int k;

	double maxMaxDist, max_d;

	double aux_d1, aux_d2, aux_d3, aux_d4;

	double auxMaxMaxDist;
 

	auxMaxMaxDist = 0.0;

	for (k = 0; (k < dimensionality); k++)		

	{

		aux_d1 = fabs(minCoords[k] - rect.minCoords[k]);

		aux_d2 = fabs(minCoords[k] - rect.maxCoords[k]);

		aux_d3 = fabs(maxCoords[k] - rect.minCoords[k]);

		aux_d4 = fabs(maxCoords[k] - rect.maxCoords[k]);
 

		max_d = -MAXDOUBLE;

		if (aux_d1 > max_d)

			max_d = aux_d1;
 

		if (aux_d2 > max_d)

			max_d = aux_d2;
 

		if (aux_d3 > max_d)

			max_d = aux_d3;
 

		if (aux_d4 > max_d)

			max_d = aux_d4;
 

		auxMaxMaxDist += (max_d * max_d);

	}
 

	//maxMaxDist = auxMaxMaxDist;
 

	maxMaxDist = sqrt(auxMaxMaxDist);

	if (maxMaxDist < 0.0)

	{

		printf("\nError: sqrt returns %.6f\n", maxMaxDist);

		return maxMaxDist;

	}
 

	return maxMaxDist;
 

}

//
 

double Rect::MINMAXDIST_Rect_Rect(Rect rect)

{

	int k;

	double minMaxDist, auxMinMaxDist, max_d, min_d;

	double aux_d1, aux_d2, aux_d3, aux_d4;

	double *S;

	double sum;
 

	S = new double[dimensionality];

	if (!(S))

	{

		printf("\nNo enough memory for temporary array of distances.\n");

		return 0.0;

	}
 

	sum = 0;

	for(k = 0; (k < dimensionality); k++)		

	{

		aux_d1 = fabs(rect.minCoords[k] - minCoords[k]);

		aux_d2 = fabs(rect.minCoords[k] - maxCoords[k]);

		aux_d3 = fabs(rect.maxCoords[k] - minCoords[k]);

		aux_d4 = fabs(rect.maxCoords[k] - maxCoords[k]);
 

		max_d = -MAXDOUBLE;

		if (aux_d1 > max_d)

			max_d = aux_d1;

		if (aux_d2 > max_d)

			max_d = aux_d2;

		if (aux_d3 > max_d)

			max_d = aux_d3;

		if (aux_d4 > max_d)

			max_d = aux_d4;
 

		sum += (max_d * max_d);

	}
 

	for (k = 0; (k < dimensionality); k++)

		S[k] = sum;
 

	for (k = 0; (k < dimensionality); k++)		

	{

		aux_d1 = fabs(rect.minCoords[k] - minCoords[k]);

		aux_d2 = fabs(rect.minCoords[k] - maxCoords[k]);

		aux_d3 = fabs(rect.maxCoords[k] - minCoords[k]);

		aux_d4 = fabs(rect.maxCoords[k] - maxCoords[k]);
 

		max_d = -MAXDOUBLE;

		if (aux_d1 > max_d)

			max_d = aux_d1;

		if (aux_d2 > max_d)

			max_d = aux_d2;

		if (aux_d3 > max_d)

			max_d = aux_d3;

		if (aux_d4 > max_d)

			max_d = aux_d4;
 

		S[k] -= (max_d * max_d);
 

		aux_d1 = fabs(rect.minCoords[k] - minCoords[k]);

		aux_d2 = fabs(rect.minCoords[k] - maxCoords[k]);

		aux_d3 = fabs(rect.maxCoords[k] - minCoords[k]);

		aux_d4 = fabs(rect.maxCoords[k] - maxCoords[k]);
 

		min_d = MAXDOUBLE;

		if (aux_d1 < min_d)

			min_d = aux_d1;

		if (aux_d2 < min_d)

			min_d = aux_d2;

		if (aux_d3 < min_d)

			min_d = aux_d3;

		if (aux_d4 < min_d)

			min_d = aux_d4;
 

		S[k] += (min_d * min_d);

	}
 

	auxMinMaxDist = MAXDOUBLE;

	for (k = 0; (k < dimensionality); k++)		

	{

		if (S[k] < auxMinMaxDist)

			auxMinMaxDist = S[k];

	}
 

	//minMaxDist = auxMinMaxDist;
 

	minMaxDist = sqrt(auxMinMaxDist);

	if (minMaxDist < 0.0)

	{

		printf("\nError: sqrt returns %.6f\n", minMaxDist);

		return minMaxDist;

	}
 

	delete [] S;
 

	return minMaxDist;
 

}
 

// MINMAXDIST between two rectangles using edges in 2D

double Rect::MINMAXDIST_Rect_Rect_2D(Rect rect)

{

	Rect *pointSet1;

	Rect *pointSet2;

	double dist1, dist2, dist3, dist4;

	double maxDist, minimumMaxDist;

	int i, j;
 

	pointSet1 = new Rect[4];	// 4 = 2^2 (2D)

	pointSet2 = new Rect[4];
 

	// Initialization of point set 1

	// Point 0

	pointSet1[0].minCoords[0] = minCoords[0];

	pointSet1[0].maxCoords[0] = minCoords[0];

	pointSet1[0].minCoords[1] = minCoords[1];

	pointSet1[0].maxCoords[1] = minCoords[1];

	// Point 1

	pointSet1[1].minCoords[0] = minCoords[0];

	pointSet1[1].maxCoords[0] = minCoords[0];

	pointSet1[1].minCoords[1] = maxCoords[1];

	pointSet1[1].maxCoords[1] = maxCoords[1];

	// Point 2

	pointSet1[2].minCoords[0] = maxCoords[0];

	pointSet1[2].maxCoords[0] = maxCoords[0];

	pointSet1[2].minCoords[1] = maxCoords[1];

	pointSet1[2].maxCoords[1] = maxCoords[1];

	// Point 3

	pointSet1[3].minCoords[0] = maxCoords[0];

	pointSet1[3].maxCoords[0] = maxCoords[0];

	pointSet1[3].minCoords[1] = minCoords[1];

	pointSet1[3].maxCoords[1] = minCoords[1];
 

	// Initialization of point set 2

	// Point 0

	pointSet2[0].minCoords[0] = rect.minCoords[0];

	pointSet2[0].maxCoords[0] = rect.minCoords[0];

	pointSet2[0].minCoords[1] = rect.minCoords[1];

	pointSet2[0].maxCoords[1] = rect.minCoords[1];

	// Point 1

	pointSet2[1].minCoords[0] = rect.minCoords[0];

	pointSet2[1].maxCoords[0] = rect.minCoords[0];

	pointSet2[1].minCoords[1] = rect.maxCoords[1];

	pointSet2[1].maxCoords[1] = rect.maxCoords[1];

	// Point 2

	pointSet2[2].minCoords[0] = rect.maxCoords[0];

	pointSet2[2].maxCoords[0] = rect.maxCoords[0];

	pointSet2[2].minCoords[1] = rect.maxCoords[1];

	pointSet2[2].maxCoords[1] = rect.maxCoords[1];

	// Point 3

	pointSet2[3].minCoords[0] = rect.maxCoords[0];

	pointSet2[3].maxCoords[0] = rect.maxCoords[0];

	pointSet2[3].minCoords[1] = rect.minCoords[1];

	pointSet2[3].maxCoords[1] = rect.minCoords[1];
 

	minimumMaxDist = MAXDOUBLE;

	for (i = 0; (i < 4); i++)	// 4 = 2^2 (2D)

	{

		for (j = 0; (j < 4); j++)	// 4 = 2^2 (2D)

		{

			dist1 = pointSet1[i].pointDistance(pointSet2[j]);

			dist2 = pointSet1[i].pointDistance(pointSet2[(j + 1) % 4]);

			dist3 = pointSet1[(i + 1) % 4].pointDistance(pointSet2[j]);

			dist4 = pointSet1[(i + 1) % 4].pointDistance(pointSet2[(j + 1) % 4]);
 

			maxDist = -MAXDOUBLE;

			if (dist1 > maxDist)

				maxDist = dist1;

			if (dist2 > maxDist)

				maxDist = dist2;

			if (dist3 > maxDist)

				maxDist = dist3;

			if (dist4 > maxDist)

				maxDist = dist4;
 

			if (maxDist < minimumMaxDist)

				minimumMaxDist = maxDist;
 

		}

	}
 

	delete [] pointSet1;

	delete [] pointSet2;
 

	// *** printf("\nMinimumMaxDist_Edges = %.6f", minimumMaxDist);
 

	return minimumMaxDist;

}
 

// MAXMAXDIST between two rectangles using edges

double Rect::MAXMAXDIST_Rect_Rect_2D(Rect rect)

{

	Rect *pointSet1;

	Rect *pointSet2;

	double dist1, dist2, dist3, dist4;

	double maxDist, maximumMaxDist;

	int i, j;
 

	pointSet1 = new Rect[4];	// 4 = 2^2 (2D)

	pointSet2 = new Rect[4];
 

	// Initialization of point set 1

	// Point 0

	pointSet1[0].minCoords[0] = minCoords[0];

	pointSet1[0].maxCoords[0] = minCoords[0];

	pointSet1[0].minCoords[1] = minCoords[1];

	pointSet1[0].maxCoords[1] = minCoords[1];

	// Point 1

	pointSet1[1].minCoords[0] = minCoords[0];

	pointSet1[1].maxCoords[0] = minCoords[0];

	pointSet1[1].minCoords[1] = maxCoords[1];

	pointSet1[1].maxCoords[1] = maxCoords[1];

	// Point 2

	pointSet1[2].minCoords[0] = maxCoords[0];

	pointSet1[2].maxCoords[0] = maxCoords[0];

	pointSet1[2].minCoords[1] = maxCoords[1];

	pointSet1[2].maxCoords[1] = maxCoords[1];

	// Point 3

	pointSet1[3].minCoords[0] = maxCoords[0];

	pointSet1[3].maxCoords[0] = maxCoords[0];

	pointSet1[3].minCoords[1] = minCoords[1];

	pointSet1[3].maxCoords[1] = minCoords[1];
 

	// Initialization of point set 2

	// Point 0

	pointSet2[0].minCoords[0] = rect.minCoords[0];

	pointSet2[0].maxCoords[0] = rect.minCoords[0];

	pointSet2[0].minCoords[1] = rect.minCoords[1];

	pointSet2[0].maxCoords[1] = rect.minCoords[1];

	// Point 1

	pointSet2[1].minCoords[0] = rect.minCoords[0];

	pointSet2[1].maxCoords[0] = rect.minCoords[0];

	pointSet2[1].minCoords[1] = rect.maxCoords[1];

	pointSet2[1].maxCoords[1] = rect.maxCoords[1];

	// Point 2

	pointSet2[2].minCoords[0] = rect.maxCoords[0];

	pointSet2[2].maxCoords[0] = rect.maxCoords[0];

	pointSet2[2].minCoords[1] = rect.maxCoords[1];

	pointSet2[2].maxCoords[1] = rect.maxCoords[1];

	// Point 3

	pointSet2[3].minCoords[0] = rect.maxCoords[0];

	pointSet2[3].maxCoords[0] = rect.maxCoords[0];

	pointSet2[3].minCoords[1] = rect.minCoords[1];

	pointSet2[3].maxCoords[1] = rect.minCoords[1];
 

	maximumMaxDist = -MAXDOUBLE;

	for (i = 0; (i < 4); i++)	// 4 = 2^2 (2D)

	{

		for (j = 0; (j < 4); j++)	// 4 = 2^2 (2D)

		{

			dist1 = pointSet1[i].pointDistance(pointSet2[j]);

			dist2 = pointSet1[i].pointDistance(pointSet2[(j + 1) % 4]);

			dist3 = pointSet1[(i + 1) % 4].pointDistance(pointSet2[j]);

			dist4 = pointSet1[(i + 1) % 4].pointDistance(pointSet2[(j + 1) % 4]);
 

			maxDist = -MAXDOUBLE;

			if (dist1 > maxDist)

				maxDist = dist1;

			if (dist2 > maxDist)

				maxDist = dist2;

			if (dist3 > maxDist)

				maxDist = dist3;

			if (dist4 > maxDist)

				maxDist = dist4;
 

			if (maxDist > maximumMaxDist)

				maximumMaxDist = maxDist;
 

		}

	}
 

	delete [] pointSet1;

	delete [] pointSet2;
 

	// *** printf("\nMaximumMaxDist_Edges = %.6f", maximumMaxDist);
 

	return maximumMaxDist;

}
 

bool Rect::covers(Rect r)

{ 

	int d;

	bool coverResult = true;
 

	for(d = 0; (d < dimensionality); d++)

	{

		if( (r.minCoords[d] < minCoords[d]) || (r.maxCoords[d] > maxCoords[d]) )

		{

			coverResult = false;

			break;

		}

	}
 

	return coverResult;

}
 

bool Rect::overlaps(Rect r)

{

	bool overlap = true;

	int d;
 

	for(d = 0; ((d < dimensionality) && overlap); d++)

		if( (r.minCoords[d] > maxCoords[d]) || (r.maxCoords[d] < minCoords[d]) )

			overlap = false;
 

	return overlap;

}
 

double Rect::overlapArea(Rect r)

{   

	Rect commRect;

	int i;
 

	if(overlaps(r))

	{

		for(i=0; i<dimensionality; i++)

		{

			if(r.minCoords[i] > minCoords[i])

				commRect.minCoords[i]=r.minCoords[i];

			else

				commRect.minCoords[i]=minCoords[i];

		}

		for(i=0; i<dimensionality; i++)

		{

			if(r.maxCoords[i] < maxCoords[i])

				commRect.maxCoords[i]=r.maxCoords[i];

			else

				commRect.maxCoords[i]=maxCoords[i];

		}

		return commRect.getArea();

	}

	else

		return 0.0;

}
 

// mine

bool Rect::overlapRect(Rect r, Rect *rect)

{

	int i;
 

	if(overlaps(r))

	{

		for(i = 0; (i < dimensionality); i++)

		{

			if(r.minCoords[i] > minCoords[i])

				rect->minCoords[i] = r.minCoords[i];

			else

				rect->minCoords[i] = minCoords[i];

		}

		for(i = 0; (i < dimensionality); i++)

		{

			if(r.maxCoords[i] < maxCoords[i])

				rect->maxCoords[i] = r.maxCoords[i];

			else

				rect->maxCoords[i] = maxCoords[i];

		}

		return true;

	}

	else

		return false;

}

// mine
 

double Rect::proximity(Rect r)

{

	double min_min, max_min, min_max, max_max;

	double E, D;
 

	if(r.minCoords[0] < minCoords[0])

	{	min_min=r.minCoords[0];

		max_min=minCoords[0];

	}

	else

	{	min_min=minCoords[0];

		max_min=r.minCoords[0];

	}
 

	if(r.maxCoords[0] < maxCoords[0])

	{	min_max=r.maxCoords[0];

		max_max=maxCoords[0];

	}

	else

	{	min_max=maxCoords[0];

		max_max=r.maxCoords[0];

	}
 

	D=min_max - max_min;

	E=max_max - min_min;
 

	return D;

}
 

bool Rect::equal(Rect r)

{

	bool eq = true;

	int d;
 

	for (d = 0; (d < dimensionality); d++)

	{

		if ((minCoords[d] != r.minCoords[d]) || (maxCoords[d] != r.maxCoords[d]))

		{	

			eq = false;

			break;

		}

	}
 

	return eq;

}
 

double Rect::sumCoords()

{

	double sum = 0;

	int d;
 

	for(d = 0; (d < dimensionality); d++)

		sum += maxCoords[d] + minCoords[d];

	return sum;

}
 

Rect Rect::center()

{

	int i;

	Rect centerRect;
 

	for(i = 0; (i < dimensionality); i++)

	{

		centerRect.minCoords[i] = (minCoords[i] + maxCoords[i]) / (float)2.0;

		centerRect.maxCoords[i] = centerRect.minCoords[i];

	}

	return centerRect;

}
 

double Rect::getArea()

{

	double area = 1;

	int d;
 

	for(d = 0; (d < dimensionality); d++)

		area *= maxCoords[d] - minCoords[d];

	return area;

}
 

double Rect::getMargin()

{

	double margin=0;

	int    d;
 

	for(d=0; d<dimensionality; d++)

		margin += maxCoords[d]-minCoords[d];
 

	return margin;

}
 

Rect Rect::enlargeToInclude(Rect r)

{

	int i;

	Rect enlargedRect;
 

	for(i=0; i<dimensionality; i++)

	{	enlargedRect.minCoords[i]=minCoords[i];

		enlargedRect.maxCoords[i]=maxCoords[i];

	}

	for(i=0; i<dimensionality; i++)

	{ if (r.minCoords[i]<enlargedRect.minCoords[i])

			enlargedRect.minCoords[i]=r.minCoords[i];

		if (r.maxCoords[i]>enlargedRect.maxCoords[i])

			enlargedRect.maxCoords[i]=r.maxCoords[i];

	}

	return enlargedRect;

}
 

// mine

double Rect::enlargedArea(Rect r)

{

	int i;

	Rect enlargedRect;
 

	for(i = 0; (i < dimensionality); i++)

	{

		enlargedRect.minCoords[i]=minCoords[i];

		enlargedRect.maxCoords[i]=maxCoords[i];

	}

	for(i = 0; (i < dimensionality); i++)

	{

		if (r.minCoords[i] < enlargedRect.minCoords[i])

			enlargedRect.minCoords[i] = r.minCoords[i];

		if (r.maxCoords[i] > enlargedRect.maxCoords[i])

			enlargedRect.maxCoords[i] = r.maxCoords[i];

	}

	return (double)enlargedRect.getArea();

}

// mine
 

Rect::Rect(float val1, float val2, int mode)

{ 

	int d;
 

	if(mode == DO_NOT_MAKE_POINT)

	{

		for(d=0; d<dimensionality; d++)

		{ 

			minCoords[d]=val1;  /*minVal*/

			maxCoords[d]=val2;  /*maxVal*/

		}

	}

	else

	{

		minCoords[0]=maxCoords[0]=val1;  /*xVal*/

		minCoords[1]=maxCoords[1]=val2;  /*yVal*/

	}

}
 

Rect::Rect(float *minCoord, float *maxCoord)

{ 

	int d;
 

	for(d=0; d<dimensionality; d++)

	{ 

		minCoords[d]=minCoord[d];

		maxCoords[d]=maxCoord[d];

	}

}
 

int Node::whereToInsert(Rect insR, int level, bool *enlarged)

{ 

	double areaOfMinEnlargedMBR=MAXDOUBLE, minEnlargementArea=MAXDOUBLE;

	double area, enlargementArea;

	Rect   enlargedRect, minEnlargedRect;

	int    insPos=0, i, j;

	double minOverlapEnlargement=MAXDOUBLE;

	double overlap, enlargedRectOverlap, *overlapEnlargement;
 

	overlapEnlargement = (double *) malloc((numOfEntries)*sizeof(double));

	

	for(i=0; i<numOfEntries; i++)

		overlapEnlargement[i]=0;
 

	/*if child pointers point to leaves*/

	if(level==1)

	{

		for(i=0; i<numOfEntries; i++)

		{

			enlargedRect=entries[i].r.enlargeToInclude(insR);

			overlap=enlargedRectOverlap=0;

			for(j=0; j<numOfEntries; j++)

			{

				if(j!=i)

				{	

					overlap+=entries[i].r.overlapArea(entries[j].r);

					enlargedRectOverlap+=enlargedRect.overlapArea(entries[j].r);

				}

			}

			overlapEnlargement[i]=enlargedRectOverlap-overlap;

			if(overlapEnlargement[i] < minOverlapEnlargement)

				minOverlapEnlargement=overlapEnlargement[i];

		}

	}

	else

		minOverlapEnlargement=0; /*reset ties to examine all entries*/

	

	/*Either upper level or ties occured*/

	for(i=0; i<numOfEntries; i++)

	{ 

		if(overlapEnlargement[i] == minOverlapEnlargement)

		{

			area=entries[i].r.getArea();

			enlargedRect=entries[i].r.enlargeToInclude(insR);

			enlargementArea=enlargedRect.getArea()-area;

			if( (enlargementArea<minEnlargementArea) ||

					(enlargementArea==minEnlargementArea && area<areaOfMinEnlargedMBR) )

			{ minEnlargedRect=enlargedRect;

				minEnlargementArea=enlargementArea;

				areaOfMinEnlargedMBR=area;

				insPos=i;

			}

		}

	}
 

	if( !entries[insPos].r.covers(insR) )

	{	

		entries[insPos].r=minEnlargedRect;

		*enlarged=true;

	}

	else

		*enlarged=false;
 

	if(overlapEnlargement)

		free(overlapEnlargement);
 

	return insPos;

}
 

bool Node::existInNode(Rect r, int *atPos)

{ 

	bool e=false;

	int  i;
 

	for(i=0; (i<numOfEntries); i++)

		if(r.equal(entries[i].r))

		{	

			if (atPos)

				*atPos=i;

			e=true;

			break;

		}

	return e;

}
 

void Node::getMBR(Rect *MBR)

{

	int i, d;
 

	for(d=0; d<dimensionality; d++)

	{

		MBR->minCoords[d]= (float)MAXFLOAT;

		MBR->maxCoords[d]=-(float)MAXFLOAT;

	}
 

	for(i=0; i<numOfEntries; i++)

		for(d=0; d<dimensionality; d++)

		{

			if(entries[i].r.minCoords[d] < MBR->minCoords[d])

				MBR->minCoords[d]=entries[i].r.minCoords[d];

			if(entries[i].r.maxCoords[d] > MBR->maxCoords[d])

				MBR->maxCoords[d]=entries[i].r.maxCoords[d];

		}

}
 

void Node::getMBRsOfDistributions(int k, Rect *g1MBR, Rect *g2MBR)

{
 

	int i, d;
 

	for(d=0; d<dimensionality; d++)

	{

		g1MBR->minCoords[d] = g2MBR->minCoords[d] =  (float)MAXFLOAT;

		g1MBR->maxCoords[d] = g2MBR->maxCoords[d] = -(float)MAXFLOAT;

	}
 

	for(i=0; i<k; i++)

		for(d=0; d<dimensionality; d++)

		{

			if(entries[i].r.minCoords[d] < g1MBR->minCoords[d])

				g1MBR->minCoords[d]=entries[i].r.minCoords[d];

			if(entries[i].r.maxCoords[d] > g1MBR->maxCoords[d])

				g1MBR->maxCoords[d]=entries[i].r.maxCoords[d];

		}
 

	for(i=k; i<numOfEntries; i++)

		for(d=0; d<dimensionality; d++)

		{

			if(entries[i].r.minCoords[d] < g2MBR->minCoords[d])

				g2MBR->minCoords[d]=entries[i].r.minCoords[d];

			if(entries[i].r.maxCoords[d] > g2MBR->maxCoords[d])

				g2MBR->maxCoords[d]=entries[i].r.maxCoords[d];

		}

}
 

void Node::insert(NodeEntry newEntry, int atPos)

{ int i;
 

	for(i=numOfEntries; i>atPos; i--)

		entries[i]=entries[i-1];

	entries[atPos]=newEntry;

	numOfEntries++;

}
 

void Node::remove(int fromPos)

{

	int i;

	

	for(i=fromPos; i<numOfEntries-1; i++)

		entries[i]=entries[i+1];

	

	numOfEntries--;

}
 

void Node::copy(Node n)

{

	int i;
 

	numOfEntries=n.numOfEntries;

	leafNode=n.leafNode;

	for (i = 0; (i < numOfEntries); i++)

		entries[i] = n.entries[i];    

}
 

void Node::copyNode(Node *src)

{

	memcpy(&numOfEntries, &(src->numOfEntries), sizeof(int));

	memcpy(&leafNode, &(src->leafNode), sizeof(bool));

	memcpy(entries, src->entries, (sizeof(NodeEntry) * maxNumOfEntries));

}
 

int Node::sizeNode()

{

	return (int)(sizeof(int) + sizeof(bool) + (sizeof(NodeEntry) * maxNumOfEntries));

}
 

void Node::copyNodeToString(char *page)

{

	memcpy(page, &numOfEntries, sizeof(int));

	memcpy(page + sizeof(int), &leafNode, sizeof(bool));

	memcpy(page + (sizeof(int) + sizeof(bool)), entries, (sizeof(NodeEntry) * maxNumOfEntries));

}
 

void Node::copyStringToNode(char *page)

{

	memcpy(&numOfEntries, page, sizeof(int));

	memcpy(&leafNode, page + sizeof(int), sizeof(bool));

	memcpy(entries, page + (sizeof(int) + sizeof(bool)), (sizeof(NodeEntry) * maxNumOfEntries));

}
 

// QuickSort over the NODE.

void Node::quickSortIncreasingDimension(int dimension)

{

	quickSortIncreasingDimension(0, (numOfEntries - 1), dimension);

}

// QuickSort over the NODE.
 

// QuickSort over the NODE.

void Node::quickSortIncreasingDimension(int begin, int end, int dimension)

{

	int i, j;

	double pivot;

	NodeEntry tempEntry;
 

	if (end <= begin)

		return;

	i = begin;

	j = end;

	pivot = entries[(begin + end) / 2].r.minCoords[dimension];

	do

	{

		while ((entries[i].r.minCoords[dimension] < pivot) && (i < end))

			i++;

		while ((pivot < entries[j].r.minCoords[dimension]) && (begin < j))

			j--;

		if (i <= j)

		{

			// Exchange the values 'i' and 'j' in 'entries'

			tempEntry = entries[i];

			entries[i] = entries[j];

			entries[j] = tempEntry;
 

			i++;

			j--;

		}

	} while (i <= j);
 

	if (begin < j)

		quickSortIncreasingDimension(begin, j, dimension);	// Recursive Call
 

	if (i < end)

		quickSortIncreasingDimension(i, end, dimension);		// Recursive Call

}

// QuickSort over the NODE.
 

// QuickSort over the NODE.

void Node::quickSortDecreasingDimension(int dimension)

{

	quickSortDecreasingDimension(0, (numOfEntries - 1), dimension);

}

// QuickSort over the NODE.
 

// QuickSort over the NODE.

void Node::quickSortDecreasingDimension(int begin, int end, int dimension)

{

	int i, j;

	double pivot;

	NodeEntry tempEntry;
 

	if (end <= begin)

		return;

	i = begin;

	j = end;

	pivot = entries[(begin + end) / 2].r.minCoords[dimension];

	do

	{

		while ((entries[i].r.minCoords[dimension] > pivot) && (i < end))

			i++;

		while ((pivot > entries[j].r.minCoords[dimension]) && (begin < j))

			j--;

		if (i <= j)

		{

			// Exchange the values 'i' and 'j' in 'entries'

			tempEntry = entries[i];

			entries[i] = entries[j];

			entries[j] = tempEntry;
 

			i++;

			j--;

		}

	} while (i <= j);
 

	if (begin < j)

		quickSortDecreasingDimension(begin, j, dimension);	// Recursive Call
 

	if (i < end)

		quickSortDecreasingDimension(i, end, dimension);		// Recursive Call

}

// QuickSort over the NODE.
 

// QuickSort over an array with doubles

void Node::quickSort(double *array, NodeEntry *auxEntries, int begin, int end)

{

	int i, j;

	double pivot;

	double auxValue;

	NodeEntry auxEntry;
 

	if (end <= begin)

		return;

	i = begin;

	j = end;

	pivot = array[(begin + end) / 2];

	do

	{

		while ((array[i] < pivot) && (i < end))

			i++;

		while ((pivot < array[j]) && (begin < j))

			j--;

		if (i <= j)

		{

			// Exchange the values 'i' and 'j' in 'array'

			auxValue = array[i];

			array[i] = array[j];

			array[j] = auxValue;

			auxEntry = auxEntries[i];

			auxEntries[i] = auxEntries[j];

			auxEntries[j] = auxEntry;
 

			i++;

			j--;

		}

	} while (i <= j);
 

	if (begin < j)

		quickSort(array, auxEntries, begin, j);	// Recursive Call
 

	if (i < end)

		quickSort(array, auxEntries, i, end);		// Recursive Call

}

// QuickSort over an array with doubles
 

void Node::sort(int dimensionType, int cornerType)

{

	double    *sorting = (double *) malloc((numOfEntries)*sizeof(double));

	Rect	  MBR;

	double	  centerOfMBR[dimensionality], centerOfRect[dimensionality];

	double	  euclidDist;

	int		  i, d;
 

	if(cornerType==2)

	{

		getMBR(&MBR);

		for(d=0; d<dimensionality; d++)

			centerOfMBR[d]=MBR.maxCoords[d]/2+MBR.minCoords[d]/2;

	}
 

	for(i=0; i<numOfEntries; i++)

	{

		if(cornerType==0)

			sorting[i]=entries[i].r.minCoords[dimensionType];

		else if(cornerType==1)

			sorting[i]=entries[i].r.maxCoords[dimensionType];

		else

		{	euclidDist=0;

			for(d=0; d<dimensionality; d++)

				centerOfRect[d]=entries[i].r.maxCoords[d]/2+entries[i].r.minCoords[d]/2;

			for(d=0; d<dimensionality; d++)

				euclidDist+=(centerOfRect[d]-centerOfMBR[d])*(centerOfRect[d]-centerOfMBR[d]);

			sorting[i]=euclidDist;

		}

	}
 

	// QuickSort

	quickSort(sorting, entries, 0, (numOfEntries - 1));
 
 

	// Improved Bubble Sort

	//NodeEntry dummy;

	//double temp;

	//int j;

	//bool	  intrchange=true;

	//i=1;

	//while ((i <= numOfEntries - 1) && intrchange )

	//{

	//	intrchange=false;

	//	for(j = 0; (j < numOfEntries - i); j++)

	//	{

	//		if(sorting[j] > sorting[j+1])

	//		{

	//			intrchange=true;

	//			// swap distances

	//			temp=sorting[j];

	//			sorting[j]=sorting[j+1];

	//			sorting[j+1]=temp;

	//			// swap entries

	//			dummy=entries[j];

	//			entries[j]=entries[j+1];

	//			entries[j+1]=dummy;

	//		}

	//	}

	//	i++;

	//}

	

	if(sorting)

		free(sorting);

}
 

void Node::split(NodeEntry newEntry, Rect *adjustMBR, NodeEntry *propNodeEntry, int m, LRUBufferMng *buffer)

{ 

	int    M=numOfEntries;

	Node   *overflowNode=new Node(M+1);

	Node   *newNode=new Node(M);

	Rect   g1MBR, g2MBR;

	double areaValue, minAreaValue=MAXDOUBLE;

	double overlapValue, minOverlapValue=MAXDOUBLE;

	int    i, k;

	double S, minS=MAXDOUBLE;

	int	   d, splitAxis, splitIndex;

	int	   cornerType, cornerTypeIndex;
 

	/*form overflow node*/

	overflowNode->numOfEntries=numOfEntries;

	overflowNode->leafNode=leafNode;

	for(i=0; i<numOfEntries; i++)

		overflowNode->entries[i]=entries[i];
 

	overflowNode->append(newEntry);
 
 

	/*choose split axis*/

	for(d=0; d<dimensionality; d++)

	{

		S=0;

		for(cornerType=0; cornerType<=1; cornerType++)

		{

			overflowNode->sort(d, cornerType);

			for(k=1; k<=maxNumOfEntries-2*m+2; k++)

			{

				overflowNode->getMBRsOfDistributions(m-1+k, &g1MBR, &g2MBR);

				S += g1MBR.getMargin()+g2MBR.getMargin();

			}

		}

		if(S < minS)

		{

			minS=S;

			splitAxis=d;

		}

	}
 

	/*choose split index*/

	for(cornerType=0; cornerType<=1; cornerType++)

	{

		overflowNode->sort(splitAxis, cornerType);

		for(k=1; k<=maxNumOfEntries-2*m+2; k++)

		{

			overflowNode->getMBRsOfDistributions(m-1+k, &g1MBR, &g2MBR);

			overlapValue=g1MBR.overlapArea(g2MBR);

			areaValue=g1MBR.getArea()+g2MBR.getArea();

			if( (overlapValue<minOverlapValue) || 

				(overlapValue==minOverlapValue && areaValue<minAreaValue) )

			{

				minOverlapValue=overlapValue;

				splitIndex=k;

				cornerTypeIndex=cornerType;

				minAreaValue=areaValue;

			}

		}

	}
 
 

	/*fill the two pages (...in a bad way, indeed...)*/

	overflowNode->sort(splitAxis, cornerTypeIndex);

	overflowNode->getMBRsOfDistributions(m-1+splitIndex, &g1MBR, &g2MBR);
 

	for(i=0; i<m-1+splitIndex; i++)

		entries[i]=overflowNode->entries[i];

	numOfEntries=m-1+splitIndex;
 

	for(i=m-1+splitIndex; i<M+1; i++)

		newNode->entries[i-(m-1+splitIndex)]=overflowNode->entries[i];

	newNode->numOfEntries=M+1-(m-1+splitIndex);
 

	newNode->leafNode=leafNode;
 

	*adjustMBR=g1MBR;

	propNodeEntry->r=g2MBR;

	propNodeEntry->p=newNode->writeNode(buffer);

	delete overflowNode;

	delete newNode;

}
 

void Node::reInsertion(NodeEntry newEntry, int currLevel, Rect *adjustMBR, reInsNodeList *reInsL)

{

	int    M=numOfEntries;

	Node   *overflowNode=new Node(M+1);

	int	   p=(int)((double)maxNumOfEntries * 0.35);

	int	   i;
 
 

	/*form overflow node*/

	overflowNode->numOfEntries=numOfEntries;

	overflowNode->leafNode=leafNode;

	for(i=0; i<numOfEntries; i++)

		overflowNode->entries[i]=entries[i];
 

	overflowNode->append(newEntry);

	

	/*get p of sorted entries*/

	overflowNode->sort(2, 2);
 

	for(i=M+1-p; i<M+1; i++)

		reInsL->insert(overflowNode->entries[i], currLevel);
 

	for(i=0; i<M+1-p; i++)

		entries[i]=overflowNode->entries[i];
 

	numOfEntries = M+1-p;

	getMBR(adjustMBR);
 

	delete overflowNode;

}
 
 

void Node::readNode(LRUBufferMng *buffer, Addr a)

{

	//long nodeSize = sizeof(int) + sizeof(bool) + sizeof(NodeEntry) * maxNumOfEntries;

	

	//fseek(f, (nodeSize * (long)a) + sizeof(rtreeHeader), SEEK_SET);

	//fread(&numOfEntries, sizeof(int), 1, f);

	//fread(&leafNode, sizeof(bool), 1, f);

	//fread(entries, sizeof(NodeEntry), numOfEntries, f);
 

	long nodeSize;

	long int start;

	unsigned int len;

	int numRead;
 

	nodeSize = sizeof(int) + sizeof(bool) + (sizeof(NodeEntry) * maxNumOfEntries);

	

	char *page = new char[nodeSize];

	start = (nodeSize * (long)a) + (long)sizeof(rtreeHeader);

	len = nodeSize;

	numRead = buffer->read(page, start, len);

	if (numRead != (int)len)

		printf("\n **** ERROR in Node::readNode *****\n");

	memcpy(&numOfEntries, page, sizeof(int));

	memcpy(&leafNode, page + sizeof(int), sizeof(bool));

	memcpy(entries, page + (sizeof(int) + sizeof(bool)), (sizeof(NodeEntry) * maxNumOfEntries));
 

	delete [] page;
 

}
 

void Node::writeNode(LRUBufferMng *buffer, Addr a)

{

	//long nodeSize = sizeof(int) + sizeof(bool) + sizeof(NodeEntry) * maxNumOfEntries;
 

	//fseek(f, a*nodeSize+sizeof(rtreeHeader), SEEK_SET);

	//fwrite(&numOfEntries, sizeof(int), 1, f);

	//fwrite(&leafNode, sizeof(bool), 1, f);

	//fwrite(entries, sizeof(NodeEntry), numOfEntries, f);
 

	long nodeSize;

	long int start;

	unsigned int len;

	int numWritten;
 

	nodeSize = sizeof(int) + sizeof(bool) + (sizeof(NodeEntry) * maxNumOfEntries);

	

	char *page = new char[nodeSize];

	memcpy(page, &numOfEntries, sizeof(int));

	memcpy(page + sizeof(int), &leafNode, sizeof(bool));

	memcpy(page + (sizeof(int) + sizeof(bool)), entries, (sizeof(NodeEntry) * maxNumOfEntries));

	start = (nodeSize * (long)a) + (long)sizeof(rtreeHeader);

	len = nodeSize;

	numWritten = buffer->write(page, start, len);

	if (numWritten != (int)len)

		printf("\n **** ERROR in Node::writeNode (1) *****\n");
 

	delete [] page;
 

}
 

Addr Node::writeNode(LRUBufferMng *buffer)

{

	long nodeSize;

	long absAddr;

	Addr relAddr;

	FILE *f;

	long int start;

	unsigned int len;

	long int fileSize;

	int numPut;
 

	nodeSize = sizeof(int) + sizeof(bool) + (sizeof(NodeEntry) * maxNumOfEntries);

	f = buffer->get_fd();
 

	// Write the page at the end of the file

	fseek(f, 0L, SEEK_END);

	absAddr = ftell(f);

	fileSize = absAddr;

	absAddr -= sizeof(rtreeHeader);

	relAddr = (Addr)(absAddr / nodeSize);

	

	fwrite(&numOfEntries, sizeof(int), 1, f);

	fwrite(&leafNode, sizeof(bool), 1, f);

	fwrite(entries, sizeof(NodeEntry), maxNumOfEntries, f);
 

	// Put the page in the buffer

	char *page = new char[nodeSize];

	memcpy(page, &numOfEntries, sizeof(int));

	memcpy(page + sizeof(int), &leafNode, sizeof(bool));

	memcpy(page + (sizeof(int) + sizeof(bool)), entries, (sizeof(NodeEntry) * maxNumOfEntries));

	start = fileSize;

	len = nodeSize;

	numPut = buffer->put(page, start, len);

	if (numPut != (int)len)

		printf("\n **** ERROR in Node::writeNode (2) *****\n");
 

	delete [] page;

	

	return relAddr;
 

}
 

Node::Node(int maxNumberOfEntries)

{

	numOfEntries=0;

	maxNumOfEntries=maxNumberOfEntries;

	leafNode=true;

	entries=(NodeEntry *) malloc(maxNumOfEntries * sizeof(NodeEntry));

	if(entries==NULL)

	{

		printf("\nMalloc error");

		abort();

	}

}
 

Node::~Node()

{ if(entries)

		free(entries);

}
 

void reInsNodeList::insert(NodeEntry nodeE, int level)

{

	reInsNodeListEntry *listE=new reInsNodeListEntry(nodeE, level);

	reInsNodeListEntry *curr=first, *prev=first;

	if(!first)

	{

		first=listE;

	}

	else

	{

		while(curr!=NULL)

		{

			if(curr->level > level)

			{

				prev=curr;

				curr=curr->next;

			}

			else

				break;

		}

		listE->next=prev->next;

		prev->next=listE;

	}

}
 

bool reInsNodeList::getNext(NodeEntry *nodeE, int *level)

{

	reInsNodeListEntry *curr=first;
 

	if(first)

	{

		first->ne.copy(nodeE);

		*level=first->level;

		first=first->next;

		delete curr;

		return true;

	}

	else

		return false;
 

}
 

void Rtree::createRoot(NodeEntry newEntry, Rect *adjOldRootMBR)

{

	Node *newRoot=new Node(M);
 

	if(adjOldRootMBR!=NULL)

	{ newRoot->leafNode=false;

		newRoot->append(NodeEntry(*adjOldRootMBR, rootNodeAddr));

	}

	newRoot->append(newEntry);

	rootNodeAddr=newRoot->writeNode(externalBuffer);
 

	// *** printf("\nRoot : %d", rootNodeAddr);

	

	numOfNodes++;

	height++;

	delete newRoot;

}
 
 

void Rtree::insert(Rect insR, Addr pointer, int atLevel)

{

	NodeEntry insE(insR, pointer);

	NodeEntry reInsEntry;

	int       level, i;

	bool	 *newReInsAtLevel=NULL;
 

	if(rootNodeAddr==null_addr)

		createRoot(insE);

	else

	{	NodeEntry propNodeEntry;

		Rect adjustMBR;
 

		reInsertionAtLevel=new bool[height];

		for(i=0; i<height; i++)

			reInsertionAtLevel[i]=false;
 

		reInsList.insert(insE, atLevel);

		while( reInsList.getNext(&reInsEntry, &level) )

		{

			if(insert(reInsEntry, rootNodeAddr, &adjustMBR, &propNodeEntry, height-1, level)==SPLIT)

			{	

				createRoot(propNodeEntry, &adjustMBR);

				newReInsAtLevel=new bool[height]; /* old height + 1*/

				for(i=1; i<height; i++)

					newReInsAtLevel[i]=reInsertionAtLevel[i-1];

				newReInsAtLevel[0]=false;

				delete [] reInsertionAtLevel;

				reInsertionAtLevel=newReInsAtLevel;

			}

		}

		if(reInsertionAtLevel)

			delete [] reInsertionAtLevel;

	}

}
 

int Rtree::insert(NodeEntry insE, Addr nodeAddr, Rect *adjustMBR, NodeEntry *propNodeEntry, int currLevel, int atLevel)

{

	Node *node=new Node(M);

	int  insPos;

	bool enlarged=false;

	int  insStatus;

	bool notWrite=false;
 

	node->readNode(externalBuffer, nodeAddr);
 

	if(currLevel > atLevel)

	{

		insPos=node->whereToInsert(insE.r, currLevel, &enlarged);

		insStatus=insert(insE, node->entries[insPos].p, adjustMBR, propNodeEntry, currLevel-1, atLevel);

	}

	else

	{	insPos=0;

		propNodeEntry->r=insE.r;

		propNodeEntry->p=insE.p;

		*adjustMBR=node->entries[0].r;

		insStatus=SPLIT;

	}
 

	if(insStatus != SPLIT)

	{	

		if(insStatus == ADJASTMENT)

		{

			node->entries[insPos].r=*adjustMBR;

			node->getMBR(adjustMBR);

			insStatus=ADJASTMENT;

		}

		else if(!enlarged)

		{

			notWrite=true;

			insStatus=NO_ACTION;

		}

	}

	else

	{ 

		node->entries[insPos].r=*adjustMBR;

		if(!node->full())

		{ node->append(*propNodeEntry);

			insStatus=NO_ACTION;

		}

		else

		{	

			if((!reInsertionAtLevel[currLevel]) && (currLevel != height-1))

			{

				node->reInsertion(*propNodeEntry, currLevel, adjustMBR, &reInsList);

				reInsertionAtLevel[currLevel]=true;

				insStatus=ADJASTMENT;

			}

			else

			{

				node->split(*propNodeEntry, adjustMBR, propNodeEntry, m, externalBuffer);

				insStatus=SPLIT;

				numOfNodes++;
 

				// *** printf("\n%d", numOfNodes);
 

			}

		}

	}

	if(!notWrite)

		node->writeNode(externalBuffer, nodeAddr);
 

	delete node;

	return insStatus;

}
 

void Rtree::erase(Rect delR)

{

	Rect      adjustMBR;

	NodeEntry reInsEntry;

	int       level;
 

	erase(delR, rootNodeAddr, &adjustMBR, height-1);

	while( reInsList.getNext(&reInsEntry, &level) )

		insert(reInsEntry.r, reInsEntry.p, level);

}
 

int Rtree::erase(Rect delR, Addr nodeAddr, Rect *adjustMBR, int currLevel)

{

	Node *node=new Node(M);

	int delPos;

	bool enlarged=false;

	int  eraseResult;

	bool notWrite=false;
 

	node->readNode(externalBuffer, nodeAddr);
 

	if(!node->leafNode)

	{	eraseResult=NO_ACTION;

		for(delPos=0; delPos<node->numOfEntries; delPos++)

			if(node->entries[delPos].r.covers(delR))

			{	

				eraseResult=erase(delR, node->entries[delPos].p, adjustMBR, currLevel-1);

				if(eraseResult!=NO_ACTION)

					break;

			}

	}

	else

	{	if(node->existInNode(delR, &delPos))

			eraseResult=ELIMINATION;

		else

			eraseResult=NO_ACTION;

	}
 

	if(eraseResult != ELIMINATION)

	{	if(eraseResult == NO_ACTION)

		{	

			notWrite=true;

			eraseResult=NO_ACTION;

		}

		else

		{	

			node->entries[delPos].r=*adjustMBR;

			node->getMBR(adjustMBR);

			eraseResult=ADJASTMENT;

		}

	}

	else

	{	

		if(currLevel < height-1)

		{

			if(!node->halfFull(m))

			{	

				node->remove(delPos);

				node->getMBR(adjustMBR);

				eraseResult=ADJASTMENT;

			}

			else

			{	

				int i;
 

				node->remove(delPos);

				/*collect resinsertion elements*/

				for(i=0; i<node->numOfEntries; i++)

					reInsList.insert(node->entries[i], currLevel);

				/*notWrite=? depending on stack*/

				numOfNodes--;

				eraseResult=ELIMINATION;

			}

		}

		/*node is the root*/

		else

		{

			node->remove(delPos);

			if(node->leafNode)

			{	

				/*1 before deletion, 0 after*/

				if(node->numOfEntries == 0)

				{

					rootNodeAddr=null_addr;

					height--;

				}
 

			}

			else

			{

				/*2 before deletion, 1 after*/

				if(node->numOfEntries == 1)

				{

					rootNodeAddr=node->entries[0].p;

					height--;

				}

			}

			eraseResult=NO_ACTION;

		}

	}

	if(!notWrite)

		node->writeNode(externalBuffer, nodeAddr);
 

	delete node;

	return eraseResult;

}
 

bool Rtree::search(Rect R)

{

	bool result;
 

	if(rootNodeAddr==null_addr)

		result=false;

	else

		result=search(R, rootNodeAddr);

	return result;

}
 

// mine

void Rtree::traverse_tree()

{

	if(rootNodeAddr != null_addr)

	{

		printf("\nHeight = %d\n\n",height);

		traverse_tree(rootNodeAddr, 0);

	}

}

// mine
 

int Rtree::rangeSearch(Rect R)

{ 

	static int disk_accesses=0;
 

	fprintf(result, "\n(%.2f, %.2f), (%.2f, %.2f) => ", R.minCoords[0], R.minCoords[1], R.maxCoords[0], R.maxCoords[1]);
 

	if(rootNodeAddr==null_addr)

		return 0;
 

	rangeSearch(R, rootNodeAddr, &disk_accesses);
 

	return  disk_accesses;

}
 

// mine

int Rtree::rangeSearch(Rect R, Addr nodeAddr)

{

	static int disk_accesses = 0;
 

	fprintf(result, "\n(%.2f, %.2f), (%.2f, %.2f) => ", R.minCoords[0], R.minCoords[1], R.maxCoords[0], R.maxCoords[1]);
 

	if(nodeAddr==null_addr)

		return 0;
 

	rangeSearch(R, nodeAddr, &disk_accesses);
 

	return  disk_accesses;

}

// mine
 

bool Rtree::search(Rect R, Addr nodeAddr)

{

	bool found=false;

	Node *node=new Node(M);

	int i;
 

	node->readNode(externalBuffer, nodeAddr);
 

	if(!node->leafNode)

	{ for(i=0; (i<node->numOfEntries) && !found; i++)

			if(node->entries[i].r.covers(R))

			{

				found=search(R, node->entries[i].p);

				if(found)

					break;

			}

	}

	else

		found=node->existInNode(R);

	delete node;

	return found;

}
 

// mine

void Rtree::traverse_tree(Addr nodeAddr, int margin)

{

	Node *node = new Node(M);

	Addr aux_addr;

	int i, j;

	double aux_min, aux_max;
 

	node->readNode(externalBuffer, nodeAddr);
 

	if (!(node->leafNode))

	{

		// node

		for (i = 0; (i < margin); i++)

			fprintf(result, "  ");

		fprintf(result, "(%d)[", margin);

		for (i = 0; (i < (node->numOfEntries)); i++)

		{

			if (i < ((node->numOfEntries) - 1))

			{

				for(j=0; j<dimensionality; j++)

				{ 

					aux_min = node->entries[i].r.minCoords[j];

					aux_max = node->entries[i].r.maxCoords[j];

					fprintf(result, "(%.2f, %.2f)-", aux_min, aux_max);

				}

				fprintf(result, "<R%d>; ", node->entries[i].r.id); // identifier				

			}

			else

			{				

				for(j=0; j<dimensionality; j++)

				{ 

					aux_min = node->entries[i].r.minCoords[j];

					aux_max = node->entries[i].r.maxCoords[j];

					fprintf(result, "(%.2f, %.2f)-", aux_min, aux_max);

				}

				fprintf(result, "<R%d>]", node->entries[i].r.id);	// identifier				

			}

		}

		fprintf(result, "\n");
 

		// All entries of the node -> recursive calls

		for (i = 0; (i < (node->numOfEntries)); i++)

		{

			aux_addr = node->entries[i].p;

			if (aux_addr != null_addr)

				traverse_tree(aux_addr, margin + 1);	// RECURSIVE CALL

		}
 

	}

	else

	{

		// node

		for (i = 0; (i < margin); i++)

			fprintf(result, "  ");

		fprintf(result, "(%d)[", margin);

		for (i = 0; (i < (node->numOfEntries)); i++)

		{

			if (i < ((node->numOfEntries) - 1))

			{				

				for(j=0; j<dimensionality; j++)

				{ 

					aux_min = node->entries[i].r.minCoords[j];

					aux_max = node->entries[i].r.maxCoords[j];

					fprintf(result, "(%.2f, %.2f)-", aux_min, aux_max);

				}

				fprintf(result, "<R%d>; ", node->entries[i].r.id); // identifier				

			}

			else

			{				

				for(j=0; j<dimensionality; j++)

				{ 

					aux_min = node->entries[i].r.minCoords[j];

					aux_max = node->entries[i].r.maxCoords[j];

					fprintf(result, "(%.2f, %.2f)-", aux_min, aux_max);

				}

				fprintf(result, "<R%d>]", node->entries[i].r.id);	// identifier				

			}

		}

		fprintf(result, "\n");

		

	}
 

	delete node;
 

}

// mine
 

void Rtree::rangeSearch(Rect R, Addr nodeAddr, int *disk_accesses)

{

	Node *node=new Node(M);

	int i;
 

	node->readNode(externalBuffer, nodeAddr);
 

	(*disk_accesses)++;

	if(!node->leafNode)

	{ for(i=0; i<node->numOfEntries; i++)

			if(R.overlaps(node->entries[i].r))

				rangeSearch(R, node->entries[i].p, disk_accesses);

	}

	else

		for(i=0; i<node->numOfEntries; i++)

			if(R.overlaps(node->entries[i].r))

				fprintf(result, "%d\n", node->entries[i].r.id);

	delete node;

}
 

long Rtree::writeHeader()

{

	rtreeHeader h;

	FILE *f;
 

	f = externalBuffer->get_fd();
 

	h.rootAddress = rootNodeAddr;

	h.maxNodes = M;

	h.minNodes = m;

	// mine

	h.height = height;

	h.numOfNodes = numOfNodes;

	h.typeOfTree = typeOfTree;

	// mine

	rewind(f);

	fwrite(&h, sizeof(rtreeHeader), 1, f);

	return sizeof(rtreeHeader);

}
 

long Rtree::readHeader()

{

	rtreeHeader h;

	FILE *f;
 

	f = externalBuffer->get_fd();
 

	rewind(f);

	fread(&h, sizeof(rtreeHeader), 1, f);
 

	rootNodeAddr = h.rootAddress;

	M = h.maxNodes;

	m = h.minNodes;

	// mine

	height = h.height;

	numOfNodes = h.numOfNodes;

	typeOfTree = h.typeOfTree;

	// mine

	return sizeof(rtreeHeader);

}
 

int Rtree::fileOpen(char *fileName)

{

	char fn[20];

	int openCond;

	FILE *rtreeFile;
 

	strcpy(fn, fileName);

	strcat(fn, ".r") ;

	if (access(fn, 0))

	{

		if((rtreeFile = fopen(fn, "w+b")) == NULL)

		{

			printf("\n File error 4");

			openCond=FILE_ERROR;

		}

		else

		{

			openCond=FILE_CREATE;

		}

	}

	else

	{

		if((rtreeFile = fopen(fn, "r+b")) == NULL)

		{

			printf("\n File error 5");

			openCond=FILE_ERROR;

		}

		else

			openCond=FILE_OPEN;

	}
 

	// EXTERNAL BUFFER

	externalBuffer->open(rtreeFile);

	// EXTERNAL BUFFER
 

	return openCond;
 

}
 

void Rtree::createTree(char *fileName, int type)

{

	FILE *fnl;

	char fnlFileName[20];

	float x, y;

	float x_min, y_min, x_max, y_max;

	float min_Coord[max_dimensionality];

	float max_Coord[max_dimensionality];

	int identifier, inclin, counter;
 

	// 'type' (typeOfTree) means

	// 0 = A single point for each entry in the R*-tree leaves

	// 1 = Two points for each entry in the R*-tree leaves

	// 2 = An MBR for each entry in the R*-tree leaves

	// 3 = A Line-Segment (MBR + inclination) for each entry in the R*-tree leaves
 

	if ((type < 0) || (type > 3))

	{

		printf("\nFile error 1. The type of the creation R*-tree is wrong\n");

		return;

	}
 

	strcpy(fnlFileName, fileName);

	if((fnl = fopen(strcat(fnlFileName, ".fnl"), "rt")) == NULL)

	{

		printf("\n File error 2");

		abort();

	}
 

	switch (type)

	{

		case 0:		// 0 = A single point for each entry in the R*-tree leaf nodes

			for(;;)

			{

				if(fscanf(fnl, "%f : %f : %d\n", &x, &y, &identifier) == EOF)

					break;

				Rect insPoint(x, y, MAKE_POINT);

				insPoint.id = identifier;

				insPoint.inclination = true;

				insert(insPoint);

			}

			break;

		case 1:		// 1 = Two points for each entry in the R*-tree leaf nodes

			counter = 0;

			for(;;)

			{

				if (fscanf(fnl, "%f : %f : %d\n", &x, &y, &identifier) == EOF)

					break;

				else

					counter++;

				

				if (fscanf(fnl, "%f : %f : %d\n", &x_max, &y_max, &identifier) == EOF)

				{

					counter++;

					Rect insOnePoint(x, y, MAKE_POINT);

					insOnePoint.inclination = true;

					insOnePoint.id = counter / 2;

					insert(insOnePoint);

				}

				else

				{

					counter++;

					min_Coord[0] = (float)x;

					min_Coord[1] = (float)y;

					max_Coord[0] = (float)x_max;

					max_Coord[1] = (float)y_max;

					Rect insTwoPoints(min_Coord, max_Coord);

					insTwoPoints.inclination = true;

					insTwoPoints.id = counter / 2;

					insert(insTwoPoints);

				}

			}

			break;

		case 2:		// 2 = An MBR for each entry in the R*-tree leaf nodes

			for(;;)

			{

				if(fscanf(fnl, "%f : %f : %f : %f : %d\n", &x_min, &y_min, &x_max, &y_max, &identifier) == EOF)

					break;

				min_Coord[0] = (float)x_min;

				min_Coord[1] = (float)y_min;

				max_Coord[0] = (float)x_max;

				max_Coord[1] = (float)y_max;

				if (x_max < x_min)

				{

					printf("\nERROR. x_max < x_min (Violate MBR condition)");

					abort();

				}

				if (y_max < y_min)

				{

					printf("\nERROR. y_max < y_min (Violate MBR condition)");

					abort();

				}

				Rect insMBR(min_Coord, max_Coord);

				insMBR.inclination = true;

				insMBR.id = identifier;

				insert(insMBR);

			}

			break;

		case 3:		// 3 = A Line-Segment (MBR + inclination) for each entry in the R*-tree leaf nodes

			for(;;)

			{

				if(fscanf(fnl, "%f : %f : %f : %f : %d : %d\n", &x_min, &y_min, &x_max, &y_max, &inclin, &identifier) == EOF)

					break;

				min_Coord[0] = (float)x_min;

				min_Coord[1] = (float)y_min;

				max_Coord[0] = (float)x_max;

				max_Coord[1] = (float)y_max;

				if (x_max < x_min)

				{

					printf("\nERROR. x_max < x_min (Violate MBR condition)");

					abort();

				}

				if (y_max < y_min)

				{

					printf("\nERROR. y_max < y_min (Violate MBR condition)");

					abort();

				}

				Rect insSegment(min_Coord, max_Coord);

				if (inclin == 1)

					insSegment.inclination = true;

				else

					insSegment.inclination = false;

				insSegment.id = identifier;

				insert(insSegment);

			}

			break;

	}
 

	fclose(fnl);
 

}
 

void Rtree::checkErase(int numOfDeletions)

{ 

	FILE *fnl;

	float  x, y, c;

	char fnlFileName[20];

	int i;
 

	strcpy(fnlFileName, "lb");

	if((fnl=fopen(strcat(fnlFileName, ".fnl"), "rt")) == NULL)

	{

		printf("\n File error 2");

		abort();

	}
 

	printf("Deletions:\n");

	for(i=0; i<numOfDeletions; i++)

	{ 

		 printf("%d\n", i);
 

		 //r=(((float)rand())/RAND_MAX)*53000.0;

		 //rewind(fnl);

		 //for(j=0; j<r-1; j++)

		 

		 fscanf(fnl, "%f : %f : %f\n", &x, &y, &c);

			

		 Rect delR(x, y, MAKE_POINT);

		 erase(delR);

	}

	fclose(fnl);

}
 

// mine

void Rtree::checkErase(char *fileName)

{

	FILE *fnl;

	char fnlFileName[20];

	int i;

	float  x_min, y_min, x_max, y_max;

	float min_Coord[max_dimensionality];

	float max_Coord[max_dimensionality];

	int c;
 

	strcpy(fnlFileName, fileName);

	if((fnl=fopen(strcat(fnlFileName, ".fnl"), "rt")) == NULL)

	{

		printf("\n File error 2");

		abort();

	}
 

	i = 0;

	printf("Deletions:\n");

	for(;;)

	{ 

		if(fscanf(fnl, "%f : %f : %f : %f : %d\n", &x_min, &y_min, &x_max, &y_max, &c) == EOF)

			break;

		min_Coord[0] = (float)x_min; min_Coord[1] = (float)y_min;

		max_Coord[0] = (float)x_max; max_Coord[1] = (float)y_max;

		Rect delR(min_Coord, max_Coord);

		erase(delR);

		printf("%d\n", i);

		i++;

	}
 

	fclose(fnl);

}

// mine
 

void Rtree::checkTree(Addr a, Rect fatherMBR, int level, int maxLevel, long *zn)

{ 

	Node *node=new Node(M);

  int i;

  int minP;

	Rect MBR;
 

	node->readNode(externalBuffer, a);
 

	node->getMBR(&MBR);

	if(!MBR.equal(fatherMBR)) 

	{

		if(a!=rootNodeAddr)

			printf("\nNew Error");

	}

	*zn -= a;

	if(node->numOfEntries < m || node->numOfEntries > M)

	{ 

		if(a != rootNodeAddr)

		{

			printf("\nError 1");

    }

	}
 

	if(maxLevel<level)

		maxLevel=level;
 

	if( (node->leafNode) && (level>maxLevel) )

	{ 

		printf("\nError 2");

	}
 

	node->leafNode ? (minP=-1) : (minP=0);  

	for(i=0; i<node->numOfEntries; i++)

	{ 

		//if(node->entries[i].p<minP || node->entries[i].p>=numOfNodes)

		//	printf("\nError 3"); 

		

		if(!fatherMBR.covers(node->entries[i].r))

		{ 

			printf("\nError 4");

    }

		if(!node->leafNode)

			checkTree(node->entries[i].p, node->entries[i].r, level+1, maxLevel, zn);

	}
 

	delete node;

}    
 

// mine

void Rtree::checkTree()

{

	float minVal = -(float)MAXFLOAT;

	float maxVal = (float)MAXFLOAT;

	Rect totalSpace(minVal, maxVal);

	long zn = ((long)numOfNodes) * ((long)numOfNodes-1) / 2;

	checkTree(rootNodeAddr, totalSpace, 0, 0, &zn);

	if(zn!=0)

	{ 

		printf("\nZero error");

	}

}

// mine
 

Rtree::Rtree(char *fileName, int typeTree, int bufferSize, int bufferType, int maxFanout, int minFanout)

{

	int openCondition;

	numOfNodes = 0;

	height = 0;
 

	// EXTERNAL BUFFER

	externalBuffer = new LRUBufferMng(NULL, bufferSize, bufferType);

	// EXTERNAL BUFFER
 

	openCondition = fileOpen(fileName);

	if(openCondition == FILE_ERROR)

		abort();

	else if(openCondition == FILE_CREATE)

		{ 

			rootNodeAddr = null_addr;

			M = maxFanout;

			if(minFanout != -1)

				m = minFanout;

			else

				m = (int)((double)M*0.4);

			typeOfTree = typeTree;
 

			headerSize = writeHeader();

			createTree(fileName, typeTree);

		}

		else	// FILE_OPEN

		{

			headerSize = readHeader();

		}
 

	// ***** 

	// FILE of RESULT (structure of R*-tree)

	//char resultFile[32];

	//strcpy(resultFile, fileName);

	//strcat(resultFile, ".rst") ;

	//if((result=fopen(resultFile, "w+b")) == NULL)

	//	printf("\n File error 4");

	// ***** 
 

	// in another public function, no in the constructor

	//double minVal = -MAXDOUBLE, maxVal= MAXDOUBLE;

	//Rect totalSpace(minVal, maxVal);

	//long zn=((long)numOfNodes)*((long)numOfNodes-1)/2;

	//checkTree(rootNodeAddr, totalSpace, 0, 0, &zn);

	//if(zn!=0)

	//	printf("\nZero error");

	// in another public function, no in the constructor
 

	// mine

	// Check Erase

	//checkErase(fileName);

	// mine

	

	//height=3;

	//numOfNodes=928;

	//checkErase(47000);

	//checkTree(rootNodeAddr, totalSpace, 0, 0, &zn);
 

}
 

Rtree::~Rtree()

{

	// Always write the header of the file => FILE_CREATE or not.

	// For this reason always update the file .r

	// This operation always updates the header.

	headerSize = writeHeader();
 

	externalBuffer->close();

	delete externalBuffer;
 

	// ***** fclose(result);
 

}
 

// mine (GLOBAL BUFFER)

void Rtree::readNodeBuff(Node *currentNode, Addr address)

{

	currentNode->readNode(externalBuffer, address);

}

// mine (GLOBAL BUFFER)
 

// mine Statistics

void Rtree::statistics(Addr nodeAddr)

{

	int i;
 

	Node *node = new Node(M);

	node->readNode(externalBuffer, nodeAddr);
 

	if (!node->leafNode)

	{

		numberOfNonLeafNodes++;

		for (i = 0; (i < (node->numOfEntries)); i++)

		{

			numberOfNonLeafElements++;

			statistics(node->entries[i].p);

		}

	}

	else

	{

		numberOfLeafNodes++;

		for (i = 0; (i < (node->numOfEntries)); i++)

		{

			numberOfLeafElements++;

			if (node->entries[i].r.id > maximumIdentifier)

				maximumIdentifier = node->entries[i].r.id;

		}

	}
 

	delete node;

}

// mine Statistics
 

// mine Statistics

void Rtree::statistics(FILE *statisticsFile)

{

	int sizeOfPage;

	char row[4096];
 

	if (rootNodeAddr != null_addr)

	{
 

		numberOfNonLeafNodes = 0;

		numberOfLeafNodes = 0;

		numberOfNonLeafElements = 0;

		numberOfLeafElements = 0;

		maximumIdentifier = -2147483647;

		statistics(rootNodeAddr);
 

		row[0] = '\0';

		strcpy(row, "<<< R*-tree >>>\n");

		fprintf(statisticsFile, "%s", row);
 

		row[0] = '\0';

		sprintf(row, "Type of Tree (0, 1, 2, 3) = %d\n", typeOfTree);

		fprintf(statisticsFile, "%s", row);
 

		row[0] = '\0';

		sprintf(row, "Height = %d\n", height);

		fprintf(statisticsFile, "%s", row);
 

		row[0] = '\0';

		sprintf(row, "Number of Non-Leaf Nodes = %d\n", numberOfNonLeafNodes);

		fprintf(statisticsFile, "%s", row);
 

		row[0] = '\0';

		sprintf(row, "Number of Leaf Nodes = %d\n", numberOfLeafNodes);

		fprintf(statisticsFile, "%s", row);
 

		row[0] = '\0';

		sprintf(row, "Number of Non-Leaf Elements = %ld\n", numberOfNonLeafElements);

		fprintf(statisticsFile, "%s", row);
 

		row[0] = '\0';

		sprintf(row, "Number of Leaf Elements = %ld\n", numberOfLeafElements);

		fprintf(statisticsFile, "%s", row);
 

		row[0] = '\0';

		sprintf(row, "Max Fanout (M) = %d, Min Fanout (m) = %d\n", M, m);

		fprintf(statisticsFile, "%s", row);
 

		sizeOfPage = sizeof(int) + sizeof(bool) + (sizeof(NodeEntry) * M);
 

		row[0] = '\0';

		sprintf(row, "Size of Page (Node) = %d Bytes\n", sizeOfPage);

		fprintf(statisticsFile, "%s", row);
 

		row[0] = '\0';

		sprintf(row, "Size of LRU-Buffer = %d Bytes (%d Pages)\n", (externalBuffer->get_sizeOfLRUBuffer() + (sizeOfPage * externalBuffer->get_noPages())), externalBuffer->get_noPages());

		fprintf(statisticsFile, "%s", row);

	}

}

// mine Statistics
 

// mine. Number of MBRs on the Leaves

int Rtree::numberOfMBRsOnLeaves(int *maximumIdentif, int *noNonLeafElements)

{

	if (rootNodeAddr != null_addr)

	{

		numberOfNonLeafElements = 0;

		numberOfLeafElements = 0;

		maximumIdentifier = -2147483647;

		statistics(rootNodeAddr);

		*maximumIdentif =	maximumIdentifier;

		*noNonLeafElements = numberOfNonLeafElements;

		return numberOfLeafElements;

	}

	else

	{

		*noNonLeafElements = 0;

		*maximumIdentif =	0;

		return 0;

	}

}

// mine. Number of MBRs on the Leaves
 

// mine. Load all MBRs on Leaves in the Array of Rectangles

void Rtree::loadMBRsOnLeavesInArray(Addr nodeAddr, Rect **leafNodesArray)

{

	Node *node = new Node(M);

	int i;
 

	node->readNode(externalBuffer, nodeAddr);
 

	if (!node->leafNode)

	{

		for (i = 0; (i < (node->numOfEntries)); i++)

			loadMBRsOnLeavesInArray(node->entries[i].p, leafNodesArray);

	}

	else

	{

		for (i = 0; (i < (node->numOfEntries)); i++)

		{

			*leafNodesArray[numberOfLeafElements] = node->entries[i].r;

			numberOfLeafElements++;

		}

	}
 

	delete node;

}

// mine. Load all MBRs on Leaves in the Array of Rectangles
 

// mine. Load all MBRs on Leaves in the Array of Rectangles

void Rtree::loadMBRsOnLeavesInArray(Rect **leafNodesArray)

{

	if (rootNodeAddr != null_addr)

	{

		numberOfLeafElements = 0;

		loadMBRsOnLeavesInArray(rootNodeAddr, leafNodesArray);

	}

}

// mine. Load all MBRs on Leaves in the Array of Rectangles
 

// Load all MBRs, Non-Leaf and Leaf Nodes in two Arrays of Rectangles

void Rtree::loadMBRsInArrays(Addr nodeAddr, int currLevel, RectAndLevel **nonLeafNodesArray, Rect **leafNodesArray)

{

	Node *node = new Node(M);

	int i;
 

	node->readNode(externalBuffer, nodeAddr);
 

	if (!node->leafNode)

	{

		for (i = 0; (i < (node->numOfEntries)); i++)

		{

			(*nonLeafNodesArray[numberOfNonLeafElements]).rect = node->entries[i].r;

			(*nonLeafNodesArray[numberOfNonLeafElements]).level = currLevel;

			numberOfNonLeafElements++;

			loadMBRsInArrays(node->entries[i].p, currLevel - 1, nonLeafNodesArray, leafNodesArray);

		}

	}

	else

	{

		for (i = 0; (i < (node->numOfEntries)); i++)

		{

			*leafNodesArray[numberOfLeafElements] = node->entries[i].r;

			numberOfLeafElements++;

		}

	}
 

	delete node;

}

// Load all MBRs, Non-Leaf and Leaf Nodes in two Arrays of Rectangles
 

// Load all MBRs, Non-Leaf and Leaf Nodes in two Arrays of Rectangles

void Rtree::loadMBRsInArrays(RectAndLevel **nonLeafNodesArray, Rect **leafNodesArray)

{

	if (rootNodeAddr != null_addr)

	{

		numberOfNonLeafElements = 0;

		numberOfLeafElements = 0;

		loadMBRsInArrays(rootNodeAddr, height - 1, nonLeafNodesArray, leafNodesArray);

	}

}

// Load all MBRs, Non-Leaf and Leaf Nodes in two Arrays of Rectangles
 

// ********************************************************************

// Pairs of 2D Objects (points, MBRs or Line-Segments included in MBRs)

// ********************************************************************

bool ObjectObject::ISZERO(double x)

{

	double epsilon;
 

	epsilon = 0.00001;

	if (fabs(x) < epsilon)

		return true;

	else

		return false;

}
 

bool ObjectObject::AB_ISPOINT()

{

	return (bool)((A[0] == B[0]) && (A[1] == B[1]));

}
 

bool ObjectObject::CD_ISPOINT()

{

	return (bool)((C[0] == D[0]) && (C[1] == D[1]));

}
 

double ObjectObject::Area2(float *a, float *b, float *c)

{

	return (double)((((double)b[0] - (double)a[0]) * ((double)c[1] - (double)a[1])) - (((double)c[0] - (double)a[0]) * ((double)b[1] - (double)a[1])));

}
 

bool ObjectObject::Collinear(float *a, float *b, float *c)

{

	if (ISZERO(Area2(a, b, c)))

		return true;

	else

		return false;

}
 

double ObjectObject::Minimum(double v1, double v2, double v3, double v4)

{

	double minimum;
 

	minimum = v1;

	if (v2 < minimum)

		minimum = v2;

	if (v3 < minimum)

		minimum = v3;

	if (v4 < minimum)

		minimum = v4;

	

	return (double)minimum;

}
 

double ObjectObject::Maximum(double v1, double v2, double v3, double v4)

{

	double maximum;
 

	maximum = v1;

	if (v2 > maximum)

		maximum = v2;

	if (v3 > maximum)

		maximum = v3;

	if (v4 > maximum)

		maximum = v4;

	

	return (double)maximum;

}
 

double ObjectObject::PointPoint_Distance(float *a, float *b)

{

	return (double)(sqrt((((double)a[0] - (double)b[0]) * ((double)a[0] - (double)b[0])) + (((double)a[1] - (double)b[1]) * ((double)a[1] - (double)b[1]))));

	//return (double) (((double)a[0] - (double)b[0]) * ((double)a[0] - (double)b[0])) + (((double)a[1] - (double)b[1]) * ((double)a[1] - (double)b[1]));

}
 

bool ObjectObject::BetweenSegment(float *a, float *b, float *c)

{

	bool aux_0, aux_1;
 

	if (a[0] != b[0]) 

		aux_0 = (((a[0] <= c[0]) && (c[0] <= b[0])) || ((a[0] >= c[0]) && (c[0] >= b[0])));

	else

		aux_0 = (a[0] == c[0]);

		

	if (a[1] != b[1]) 		

		aux_1 = (((a[1] <= c[1]) && (c[1] <= b[1])) || ((a[1] >= c[1]) && (c[1] >= b[1])));

	else

		aux_1 = (a[1] == c[1]);
 

	return (bool)(aux_0 && aux_1);

}
 

bool ObjectObject::Intersection(float *a, float *b, float *c, float *d)

{

	double P, Q, R, S;

	double num, denom;

	float Point[2];
 

	P = (double)(b[0] - a[0]);

	Q = (double)(b[1] - a[1]);

	R = (double)(d[0] - c[0]);

	S = (double)(d[1] - c[1]);
 

	denom = (S * P) - (R * Q);

	if (ISZERO(denom))

	{

		if (Collinear(a, b, c))

		{

			if ((BetweenSegment(a, b, c)) || (BetweenSegment(a, b, d)) || (BetweenSegment(c, d, a)) || (BetweenSegment(c, d, b)))

				return true;

			else

				return false;

		}

		else

			return false;

	}

	else

	{

		num = ((double)a[1] * R * P) - ((double)c[1] * R * P) + ((double)c[0] * S * P) - ((double)a[0] * Q * R);

		Point[0] = (float)(num / denom);

		num = ((double)a[1] * S * P) - ((double)a[0] * Q * S) - ((double)c[1] * Q * R) + ((double)c[0] * S * Q);

		Point[1] = (float)(num / denom);
 

		if ((BetweenSegment(a, b, Point)) && (BetweenSegment(c, d, Point)))

			return true;

		else

			return false;

	}

}
 

void ObjectObject::LineLine_Distance(float *a, float *b, float *c, double *dist)

{

	double P, Q, R, S;

	double num, denom;

	float Point[2];
 

	P = (double)(b[0] - a[0]);

	Q = (double)(b[1] - a[1]);

	R = (double)(b[1] - a[1]);

	S = (double)(a[0] - b[0]);
 

	denom = (S * P) - (R * Q);

	if (ISZERO(denom))

		*dist = MAXDOUBLE;

	else

	{

		num = ((double)a[1] * R * P) - ((double)c[1] * R * P) + ((double)c[0] * S * P) - ((double)a[0] * Q * R);

		Point[0] = (float)(num / denom);

		num = ((double)a[1] * S * P) - ((double)a[0] * Q * S) - ((double)c[1] * Q * R) + ((double)c[0] * S * Q);

		Point[1] = (float)(num / denom);

		

		if (BetweenSegment(a, b, Point))

			*dist = PointPoint_Distance(Point, c);

		else

			*dist = MAXDOUBLE;

	}

}
 

void ObjectObject::SegmentSegment_Distance()

{

	double dist1, dist2, dist3, dist4;

	int c;
 

	if (dimensionality != 2)

	{

		distance = MAXDOUBLE;

		printf("\nERROR. The dimensionality is different to 2\n");		

		return;

	}
 

	if (Intersection(A, B, C, D))

	{

		distance = 0.0;

		return;

	}
 

	c = 0;

	LineLine_Distance(A, B, C, &dist1);

	if (dist1 == MAXDOUBLE)

		c++;

	LineLine_Distance(A, B, D, &dist2);

	if (dist2 == MAXDOUBLE)

		c++;

	LineLine_Distance(C, D, A, &dist3);

	if (dist3 == MAXDOUBLE)

		c++;

	LineLine_Distance(C, D, B, &dist4);

	if (dist4 == MAXDOUBLE)

		c++;
 

	if (c == 4)

	{

		dist1 = PointPoint_Distance(A, C);

		dist2 = PointPoint_Distance(A, D);

		dist3 = PointPoint_Distance(B, C);

		dist4 = PointPoint_Distance(B, D);

	}
 

	distance = Minimum(dist1, dist2, dist3, dist4);

}
 

void ObjectObject::calculateMinimumDistance()

{

	float aux_A[2];

	float aux_C[2];

	double aux_distance, dist1, dist2;
 

	if ((AB_ISPOINT()) && (CD_ISPOINT()))

	{

		aux_A[0] = A[0];

		aux_A[1] = B[1];

		aux_C[0] = C[0];

		aux_C[1] = D[1];

		distance = PointPoint_Distance(aux_A, aux_C);

	}
 

	if ((AB_ISPOINT()) && (!(CD_ISPOINT())))

	{

		aux_A[0] = A[0];

		aux_A[1] = B[1];

		LineLine_Distance(C, D, aux_A, &aux_distance);

		if (aux_distance == MAXDOUBLE)

		{

			dist1 = PointPoint_Distance(C, aux_A);

			dist2 = PointPoint_Distance(D, aux_A);

			distance = dist1;

			if (dist2 < distance)

				distance = dist2;

		}

		else

			distance = aux_distance;

	}
 

	if ((!(AB_ISPOINT())) && (CD_ISPOINT()))

	{

		aux_C[0] = C[0];

		aux_C[1] = D[1];

		LineLine_Distance(A, B, aux_C, &aux_distance);

		if (aux_distance == MAXDOUBLE)

		{

			dist1 = PointPoint_Distance(A, aux_C);

			dist2 = PointPoint_Distance(B, aux_C);

			distance = dist1;

			if (dist2 < distance)

				distance = dist2;

		}

		else

			distance = aux_distance;

	}
 

	if ((!(AB_ISPOINT())) && (!(CD_ISPOINT())))

		SegmentSegment_Distance();

}
 

void ObjectObject::calculateMaximumDistance()

{

	double dist1, dist2, dist3, dist4;

	float aux_A[2];

	float aux_C[2];
 

	if ((AB_ISPOINT()) && (CD_ISPOINT()))

	{

		aux_A[0] = A[0];

		aux_A[1] = B[1];

		aux_C[0] = C[0];

		aux_C[1] = D[1];

		distance = PointPoint_Distance(aux_A, aux_C);

	}
 

	if ((AB_ISPOINT()) && (!(CD_ISPOINT())))

	{

		aux_A[0] = A[0];

		aux_A[1] = B[1];

		dist1 = PointPoint_Distance(C, aux_A);

		dist2 = PointPoint_Distance(D, aux_A);

		distance = dist1;

		if (dist2 > distance)

			distance = dist2;

	}
 

	if ((!(AB_ISPOINT())) && (CD_ISPOINT()))

	{

		aux_C[0] = C[0];

		aux_C[1] = D[1];

		dist1 = PointPoint_Distance(A, aux_C);

		dist2 = PointPoint_Distance(B, aux_C);

		distance = dist1;

		if (dist2 > distance)

			distance = dist2;

	}
 

	if ((!(AB_ISPOINT())) && (!(CD_ISPOINT())))

	{

		dist1 = PointPoint_Distance(A, C);

		dist2 = PointPoint_Distance(A, D);

		dist3 = PointPoint_Distance(B, C);

		dist4 = PointPoint_Distance(B, D);
 

		distance = Maximum(dist1, dist2, dist3, dist4);

	}

}
 

void ObjectObject::setData(float *MIN_1, float *MAX_1, bool flag1, float *MIN_2, float *MAX_2, bool flag2)

{

	if (flag1)

	{

		A[0] = MIN_1[0]; A[1] = MIN_1[1];

		B[0] = MAX_1[0]; B[1] = MAX_1[1];

	}

	else

	{

		A[0] = MIN_1[0]; A[1] = MAX_1[1];

		B[0] = MAX_1[0]; B[1] = MIN_1[1];

	}
 

	if (flag2)

	{

		C[0] = MIN_2[0]; C[1] = MIN_2[1];

		D[0] = MAX_2[0]; D[1] = MAX_2[1];

	}

	else

	{

		C[0] = MIN_2[0]; C[1] = MAX_2[1];

		D[0] = MAX_2[0]; D[1] = MIN_2[1];

	}
 

	distance = MAXDOUBLE;

}
 

void ObjectObject::setData(Rect MBR_1, Rect MBR_2)

{

	setData(MBR_1.minCoords, MBR_1.maxCoords, MBR_1.inclination, MBR_2.minCoords, MBR_2.maxCoords, MBR_2.inclination);

}
 
 

ObjectObject::ObjectObject(float *MIN_1, float *MAX_1, bool flag1, float *MIN_2, float *MAX_2, bool flag2)

{

	if (dimensionality != 2)

	{

		distance = MAXDOUBLE;

		printf("\nERROR. The dimensionality is different to 2\n");		

		return;

	}
 

	if (flag1)

	{

		A[0] = MIN_1[0]; A[1] = MIN_1[1];

		B[0] = MAX_1[0]; B[1] = MAX_1[1];

	}

	else

	{

		A[0] = MIN_1[0]; A[1] = MAX_1[1];

		B[0] = MAX_1[0]; B[1] = MIN_1[1];

	}
 

	if (flag2)

	{

		C[0] = MIN_2[0]; C[1] = MIN_2[1];

		D[0] = MAX_2[0]; D[1] = MAX_2[1];

	}

	else

	{

		C[0] = MIN_2[0]; C[1] = MAX_2[1];

		D[0] = MAX_2[0]; D[1] = MIN_2[1];

	}
 

	distance = MAXDOUBLE;

}
 

ObjectObject::ObjectObject(Rect MBR_1, Rect MBR_2)

{

	ObjectObject(MBR_1.minCoords, MBR_1.maxCoords, MBR_1.inclination, MBR_2.minCoords, MBR_2.maxCoords, MBR_2.inclination);

}

// ********************************************************************

// Pairs of 2D Objects (points, MBRs or Line-Segments included in MBRs)

// ********************************************************************

Open in new window

0
Comment
Question by:Trexgreen
  • 12
  • 6
  • 4
23 Comments
 

Author Comment

by:Trexgreen
Comment Utility
when I do the printf("Height of R1 = %d\n", R1->get_height()); it's always 0
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
That's a lot of code, so I haven't looked at it all.

But, I notice that in the RjoinR and Rtree constructors, you have a lot of commented code. I assume that's of no consequence to the problem you are having ?

I assume furthermore, that the parameters you pass to the RjoinR constructor are all valid ?

Then, in the Rtree constructor, I notice there are 3 options. Either :

* the fileOpen failed, and then the code is aborted
* the file is created, in which case the header is added to it, and then you try to read the tree data from the file (that was just created)
* the file is opened succesfully, in which case only the header is read from it, not the actual data

Was the createTree() call supposed to be added to the FILE_OPEN case instead ? Or am I missing something ?

It would be interesting to see the output you get when you run the code, and also to know in which of the 3 above cases it ends up.
0
 

Author Comment

by:Trexgreen
Comment Utility
Infinity08... thanks for your help... that helped... I will post the code here once I finish...
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
Can you post the usrrline.fnl ?
0
 

Author Comment

by:Trexgreen
Comment Utility
I will... I haven't had time to work on this.. hope on the weekend I will be able to do.
0
 

Author Comment

by:Trexgreen
Comment Utility
Infinity08, that was what I had in mind...

But when I add the createTree() to the file open it gives me a code dump error... :(

The values in the RjoinR is correct, and the value passing to the constructor is correct too.
0
 

Author Comment

by:Trexgreen
Comment Utility
itsmeandnobodyelse:
The file right now has zero value, because I'm having some problem creating the index...so when I look in the R*-tree it has zero value.
0
 

Author Comment

by:Trexgreen
Comment Utility
I traced the error to this section here in the Rstar.cpp file.

This block of code is called for the first time when there is no file in the folder.

I get the follwoing error msg.

File error 2 Abort (core dumped)
	strcpy(fnlFileName, fileName);

	if((fnl = fopen(strcat(fnlFileName, ".fnl"), "rt")) == NULL)

	{

		printf("\n File error 2");

		abort();

	}

Open in new window

0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> File error 2 Abort (core dumped)

Hmmm. If you would output 'errno' from errno.h you more surely would know that it is file error 2 (file not found).

In the moment you only can say that the file open failed for any reason.

And the fnlFileName ist the name which was passed in main as r1TreeFileName.

Here it should get its value from

          case 5:
             strcpy(r1TreeFileName, item);
      break;
      
So far so good. But if you look at the definition of fnlFileName you see

>>>> char fnlFileName[20];

That means the r1TreeFileName must not be longer than 15 characters or the strcat would write out of boundaries.

In any case you must increase that, e. g. to

   char fnlFileName[MAX_PATH];

where MAX_PATH normally is 512 bytes.

Note, I aborted at the same statement because the usrrline.fnl was missing at all.


0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> This block of code is called for the first time when there is no file in the folder.

Then the abort is expected behavior, right ? ie. it's not a problem - it's how you wrote the code ;)
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> it's how you wrote the code ;)

Not really. The program expects a parameter file to be passed as first argument. I used the KCPQExample.txt which was part of the zipped folder you provided with above link. With parameter 5 of any line of that file which look like  

8 K2000123 1 0 USrrline 3 0 0 204 -1 USrdline 3 0 0 204 -1 777 777 0 0 0 0 0

we have 'USrrline' what was passed first from main to RjoinR::RjoinR and then to Rtree::createTree where the fnlFileName therefore was concatenated from "USrrline" and ".fnl". Though the result has a length less than 20 (fortunately) the problem is that the file doesn't exist in that you provided. And if you got the problem yourself as well, it seems the file doesn't exist at your system either?

 
0
How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> >>>> it's how you wrote the code ;)
>>
>> Not really.

The code is written to abort when the file doesn't exist ... So, that's what happens. When the file doesn't exist, the code aborts.
0
 

Author Comment

by:Trexgreen
Comment Utility
Infinity08:
The first time you run the program if you don't have the file, it will create the file for you and generate all the data, you can see that on the Rtree::fileOpen
int Rtree::fileOpen(char *fileName)

{

	char fn[20];

	int openCond;

	FILE *rtreeFile;

 

	strcpy(fn, fileName);

	strcat(fn, ".r") ;

	if (access(fn, 0))

	{

		if((rtreeFile = fopen(fn, "w+b")) == NULL)

		{

			printf("\n File error 4");

			openCond=FILE_ERROR;

		}

		else

		{

			openCond=FILE_CREATE;

		}

	}

	else

	{

		if((rtreeFile = fopen(fn, "r+b")) == NULL)

		{

			printf("\n File error 5");

			openCond=FILE_ERROR;

		}

		else

			openCond=FILE_OPEN;

	}

 

	// EXTERNAL BUFFER

	externalBuffer->open(rtreeFile);

	// EXTERNAL BUFFER

 

	return openCond;

 

}

Open in new window

0
 

Author Comment

by:Trexgreen
Comment Utility
itsmeandnobodyelse:

Yes, you need to pass the KCPQExample.txt to run the program, and that has some parameters to create the R*-tree, and one of the parameters is the files name.

>>8 K2000123 1 0 USrrline 3 0 0 204 -1 USrdline 3 0 0 204 -1 777 777 0 0 0 0 0

I will double check here to see if all the files is in the folder, and in the zip file.
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> The first time you run the program if you don't have the file, it will create the file for you and generate all the data, you can see that on the Rtree::fileOpen

What I see is that the fileOpen works on the file with .r extension.
But the error occurs when trying to open the file with .fnl extension.

So, as I said : if the file doesn't exist, then it's normal that the code aborts when you try to open it, because that's how you've written the code.

What am I missing ?
0
 

Author Comment

by:Trexgreen
Comment Utility
Infinity08,
>>So, as I said : if the file doesn't exist, then it's normal that the code aborts when you try to open it, because that's how you've written the code.

Sorry you were correct. If you don't have the .fnl file it will abort, but the .fnl file is just a copy of the fileName. I can see the problem now, since I'm renaming the USrrline to have the .r extension it actually there is no fileName since fileName = USrrline

I will make some changes for it to look in the USrrline.r file later tonight and let you know how it goes.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> I will make some changes for it to look in the USrrline.r file later tonight and let you know how it goes.
If you make changes anyhow, please increase the char sizes for filenames. It makes no sense to have a size of 128 in the main and a size of 20 in the functions which were opening or creating the files.

I also would recommend not to abort in case of *normal* errors like missing files. Print out a meaningful error message with names and error code retrieved from errno. Then return with FALSE or -1 from the function the error occured and check that return value in the calling function.
0
 

Author Comment

by:Trexgreen
Comment Utility
Sorry for the delay getting back... but I got busy at work and could not work on this anymore... now I'm working on it again.

There is a file missing and that is the.FNL file that setup the R-tree.

Does anyone know hot generate thisfile? I try to contact the author of the code but I got no answer from him.

The file need to have the folloing information according to the Rtree::createTree  around line 2182
if(fscanf(fnl, "%f : %f : %f : %f : %d : %d\n", &x_min, &y_min, &x_max, &y_max, &inclin, &identifier) == EOF)

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
Just check the Rtree::createTree method, and you'll see that there are 4 different file formats depending on the type :

>>       // 'type' (typeOfTree) means
>>       // 0 = A single point for each entry in the R*-tree leaves
>>       // 1 = Two points for each entry in the R*-tree leaves
>>       // 2 = An MBR for each entry in the R*-tree leaves
>>       // 3 = A Line-Segment (MBR + inclination) for each entry in the R*-tree leaves

Then check the switch cases that follow for the exact format. For example, for type 0, each point will be on one line :

        0.123 : 0.456 : 7

with 0.123 the x coordinate, 0.456 the y coordinate, and 7 the identifier for the point.

Similarly, you can easily find out the file format for the other 3 types.
0
 

Author Comment

by:Trexgreen
Comment Utility
I create the file and it accpeted, but i goes in an endless loop, is there something that I can add to the file to make sure it's the end of the file?

Here is what I have in the file.

USrdline.fnl
0.123:0.456:2.345:3.456:0:1
0.321:0.654:5.345:6.456:0:2
0.333:0.122:3.345:5.456:0:3

this is where it goes in the endless loop.
case 3:		// 3 = A Line-Segment (MBR + inclination) for each entry in the R*-tree leaf nodes

			for(;;)

			{

				if(fscanf(fnl, "%f : %f : %f : %f : %d : %d\n", &x_min, &y_min, &x_max, &y_max, &inclin, &identifier) == EOF)

					break;

				min_Coord[0] = (float)x_min;

				min_Coord[1] = (float)y_min;

				max_Coord[0] = (float)x_max;

				max_Coord[1] = (float)y_max;

				if (x_max < x_min)

				{

					printf("\nERROR. x_max < x_min (Violate MBR condition)");

					abort();

				}

				if (y_max < y_min)

				{

					printf("\nERROR. y_max < y_min (Violate MBR condition)");

					abort();

				}

				Rect insSegment(min_Coord, max_Coord);

				if (inclin == 1)

					insSegment.inclination = true;

				else

					insSegment.inclination = false;

				insSegment.id = identifier;

				insert(insSegment);

			}

			break;

	}

Open in new window

0
 

Author Comment

by:Trexgreen
Comment Utility
I added an extra space at the end of the file and that worked :)
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 500 total points
Comment Utility
Instead of relying on fscanf returning EOF, check its return value more extensively. fscanf returns the number of items read correctly. In this case, you're trying to read 6 items. If fscanf returns a value different from 6, it means it failed to read a line.

Or even better : don't use fscanf for your input. Use fgets to read the input one line at a time into a string buffer. Then parse that buffer to get the data you need out of it. Doing this will make your code more robust, and you won't have to worry about these little error cases, since the stream will remain in a consistent state.
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now