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

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)
// ********************************************************************

Select allOpen in new window