Header.h

#ifndef HEADER_H
#define HEADER_H

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <stddef.h>
#include <cstring>
#include <string>
#include <list>
#include <map>
#include <iterator>

#define LEAF 20
#define NODE 10
#define OBJECT 30
#define XAXIS 100
#define YAXIS 200
#define MAX 80
#define MIN 90

using namespace std;

struct MBR {
	int x1, y1; // Êîîðäèíàòû âåðõíåé ëåâîé òî÷êè
	int x2, y2; // Êîîðäèíàòû íèæíåé ïðàâîé òî÷êè
};

struct Node {
	MBR covering; // ïîêðûòèå âåðøèíû
	Node** childs; // ìàññèâ ïîòîìêîâ
	Node* parent; // ðîäèòåëü
	int type; // òèï âåðøèíû - ëèñò, óçåë èëè îáúåêò - LEAF NODE OBJECT 
	int objCount; // ÷èñëî ïîòîìêîâ
	int data; // äàííûå (äëÿ îáúåêòà)
};

class OperationsWithObjects {
public:
	Node* ChooseNodeWithMinMBR(Node* curNode, Node* newNode); // íàõîæäåíèå ïîòîìêà ñ ìèíèìàëüíûì óâåëè÷åíèåì MBR ïðè äîáàâëåíèè íîâîé âåðøèíû
	long Area(MBR mbr); // íàõîæäåíèå ïëîùàäè
	int FindMaxBottomBorder(Node** nodes, int nodesCount, int axis); // ïîèñê ìàêñèìàëüíî óäàëåííîãî ýëåìåíòà ïî îñè
	void CalculateMBR(Node* node); // îáíîâëåíèå MBR âåðøèíû
	bool IsIntersect(MBR mbr1, MBR mbr2); // ïðîâåðêà íà ïåðåñå÷åíèå äâóõ MBR
	bool IsFullyContains(MBR container, MBR content); // ïðîâåðêà íà ïîëíîå âõîæäåíèå îäíîé MBR â äðóãóþ
	bool IsEqual(MBR mbr1, MBR mbr2); // ïðîâåðêà íà ðàâåíñòâî äâóõ MBR
};

class Rtree:OperationsWithObjects {
public:
	Rtree();
	~Rtree();
	void InsertObject(Node* neObject); // âñòàâêà îáúåêòà â äåðåâî (èíòåðôåéñ)
	bool DeleteObject(MBR covering, int data); // óäàëåíèå îáúåêòà
	void SearchByArea(MBR area, list<Node*>* res); // ïîèñê ïî ïëîùàäè (èíòåðôåéñ)
	Node* SearchObject(MBR covering, int data); // ïîèñê îáúåêòà (èíòåðôåéñ)
	Node* FindExtremumByArea(int borderType); // ïîèñê ìàêñèìàëüíîãî/ìèíèìàëüíîãî ïî ïëîùàäè îáúåêòà (èíòåðôåéñ)
	void PrintRtree(ofstream &outputStream); // âûâîä ñòðóêòóðû äåðåâà (èíòåðôåéñ)

	int m; // ìèíèìàëüíîå ÷èñëî ïîòîìêîâ ó âåðøèíû
	int M; // ìàêñèìàëüíîå ÷èñëî ïîòîìêîâ ó âåðøèíû

private:
	Node* root;
	Node* curExtremum;

	void MemFree(Node* nodeToDelete); // îñâîáîæäåíèå ïàìÿòè

	void InsertNode(Node* neObject, int level);
	void _PrintRtree(Node* curNode, int level, ofstream &outputStream);
	Node* _FindExtremumByArea(Node* curNode, int borderType);
	Node* _SearchObject(Node* curNode, MBR covering, int data);
	void _SearchByArea(Node* curNode, MBR area, list<Node*>* res);

	Node* ChooseNode(Node* newObject, int level); // ïîèñê óçëà äëÿ âñòàâêè
	void CorrectTree(Node* leaf, Node* splitLeaf); // ïðîöåäóðà êîððåêòèðîâêè äåðåâà
	Node* SplitNode(Node* curNode, Node* newNode); // ïðîöåäóðà äåëåíèÿ óçëà
	int TreeLevel(); // îïðåäåëåíèå òåêóùåé âûñîòû äåðåâà
};

#endif HEADER_H