Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

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

Posted on 2009-07-12
23
Medium Priority
?
873 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
22 Comments
 

Author Comment

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

Expert Comment

by:Infinity08
ID: 24837938
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
ID: 24845450
Infinity08... thanks for your help... that helped... I will post the code here once I finish...
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24854671
Can you post the usrrline.fnl ?
0
 

Author Comment

by:Trexgreen
ID: 24864941
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
ID: 24875056
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
ID: 24875075
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
ID: 24875167
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
ID: 24875441
>>>> 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
ID: 24876281
>> 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
ID: 24876759
>>>> 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
 
LVL 53

Expert Comment

by:Infinity08
ID: 24877356
>> >>>> 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
ID: 24877563
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
ID: 24877601
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
ID: 24877742
>> 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
ID: 24878074
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
ID: 24879790
>>>> 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
ID: 25018970
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
ID: 25020444
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
ID: 25028867
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
ID: 25028884
I added an extra space at the end of the file and that worked :)
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 2000 total points
ID: 25030250
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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
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…

824 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