#include <iostream>
//#include "stdafx.h"
//#include <ifstream>
//#include <ofstream>
#include <fstream>
// 1 - black
// 0 - red
// leaf_add - добавление вершины
// left_rotate - левый поворт
// right_rotate - правый поворот
// tree_insert_fixup - балансировка дерева
// сруктура для промежутка
using namespace std;
struct space {
int low,high;
};
class leaf {
public:
int color;
space i;
int max;
leaf *father, *left, *right;
leaf( int k, int z);
//~leaf()
int maxim(int max, int leftMax, int rightMax);
};
leaf::leaf(int k, int z) {
right = NULL;
left = NULL;
father = NULL;
i.low = k;
i.high = z;
color = 0;
max = i.high;
}
int leaf::maxim (int max, int leftMax, int rightMax){
if (max < leftMax) {
if (leftMax < rightMax) return rightMax;
else return leftMax;
}
else { if (max < rightMax) return rightMax;
else return max;
}
}
class tree {
public:
leaf *root;
leaf *null;
tree();
~tree();
void treeInsert(leaf *y);
void treeInsertFixup(leaf *z);
void tempo(leaf *c);
void leftRotate(leaf *a);
void rightRotate(leaf *b);
void treePrint (leaf *x, ofstream *outflow, int level);
void treePrintAnswer (ofstream *outflow, int *numArray, int N);
int intervalSearch (space a, char c);
void treeDeleteFixup(leaf *j);
void treeDelete(leaf *i);
void transplant(leaf *o,leaf *p);
leaf *minimum (leaf *k);
leaf *maximum (leaf *m);
void treeBuild (char *fileName, char *fileNameOut);
int pointSearch(int x, char c);
void maxFix (leaf *x);
void treePaint(char *fileName);
};
tree::tree() {
leaf *o = new leaf(0,0);
o->color = 1;
null = o;
root = o;
}
tree::~tree() {
// deleaf(a);
};
void tree::leftRotate (leaf *x){
leaf *y = x->right;
x->right = y->left;
if (y->left != null)
y->left->father = x;
y->father = x->father;
if (x->father == null)
root = y;
else {
if (x == x->father->left)
x->father->left = y;
else x->father->right = y;
}
y->left = x;
x->father = y;
x->max = x->maxim(x->i.high, x->right->max,x->left->max);
}
void tree::rightRotate (leaf *x){
leaf *y = x->left;
x->left = y->right;
if (y->right != null)
y->right->father = x;
y->father = x->father;
if (x->father == null)
root = y;
else {
if (x == x->father->right)
x->father->right = y;
else x->father->left = y;
}
y->right = x;
x->father = y;
x->max = x->maxim(x->i.high, x->right->max,x->left->max);
}
void tree::treeInsertFixup (leaf *z){
leaf *temp;
while (z->father->color == 0) {
if (z->father == z->father->father->left) {
temp = z->father->father->right;
if (temp->color == 0) {
z->father->color = 1;
temp->color = 1;
z->father->father->color = 0;
z = z->father->father;
}
else {
if (z == z->father->right) {
z = z->father;
leftRotate(z);
}
else {
z->father->color = 1;
z->father->father->color = 0;
rightRotate(z->father->father);
}
}
}
else {
temp = z->father->father->left;
if (temp->color == 0) {
z->father->color = 1;
temp->color = 1;
z->father->father->color = 0;
z = z->father->father;
}
else {
if (z == z->father->left) {
z = z->father;
rightRotate(z);
}
else {
z->father->color = 1;
z->father->father->color = 0;
leftRotate(z->father->father);
}
}
}
}
root->color = 1;
}
void tree::treeInsert (leaf *y) {
leaf *temp = root;
leaf *g = null;
while (temp != null) {
g = temp;
if (temp->i.low < y->i.low) {
temp->max = temp->maxim(temp->max, temp->left->max, y->max);
temp = temp->right;
}
else {
temp->max = temp->maxim(temp->max, temp->right->max, y->max);
temp = temp->left;
}
}
if (g == null) {
root = y;
y->father = null;
y->left = null;
y->right = null;
}
else { if (g->i.low < y->i.low) {
g->right = y;
y->father = g;
y->left = null;
y->right = null;
}
else {
g->left = y;
y->father = g;
y->left = null;
y->right = null;
}
}
treeInsertFixup(y);
// maxFix(y);
}
void tree::treePrint (leaf *x, ofstream *outflow, int level) {
if (x!=null) {
treePrint(x->right, outflow, level + 1);
for (int i = 0; i < level; i++) *outflow << "\t\t";
*outflow << "L:" <<level<<";C:"<< x->color << ";"<< "(" << x->i.low << "-" << x->i.high << ")" << ";" << "max:" << x->max << ";" << "\n\n";
treePrint(x->left, outflow, level + 1);
}
}
//void tree::treePrintAnswer (ofstream *outflow, int *numArray, int N){
// if (N == 0) *outflow << "There nothing to search.\n";
// else{
// for ( int i = 0; i < N; i++) {
// space a;
// a.low = *(numArray + N); a.high = *(numArray + N);
// if (intervalSearch(a) == null) *outflow << "Your point doesn't exist in this tree\n";
// else *outflow << "Your element is here:" << intervalSearch(a)->i.low <<"-"<< intervalSearch(a)->i.high << "\n";
// }}
//}
void treePaint2 (leaf *a, leaf *c, ofstream *b){
if (a->color == 1) {
*b << "node [color = \"black\"]; \n";
*b << "\""<< a->i.low << "-" << a->i.high << "\n" << a->max <<"\"" << "[shape=\"circle\", style=\"filled\",fillcolor=\"black\",fontcolor=\"white\"];\n";
*b <<"\""<< a->father->i.low << "-" << a->father->i.high << "\n" << a->father->max << "\"" << "->" << "\"" << a->i.low << "-" << a->i.high <<"\n"<< a->max << "\";\n";
}
else {
*b << "node [color = \"red\"]; \n";
*b << "\""<< a->i.low << "-" << a->i.high << "\n" << a->max <<"\"" << "[shape=\"circle\", style=\"filled\",fillcolor=\"red\",fontcolor=\"white\"];\n";
*b <<"\""<< a->father->i.low << "-" << a->father->i.high << "\n" << a->father->max << "\""<<"->"<<"\""<< a->i.low << "-" << a->i.high << "\n" << a->max << "\";\n";
}
if (a->left != c) treePaint2(a->left,c,b);
if (a->right != c) treePaint2(a->right,c,b);
}
void tree::treePaint (char *fileName){
ofstream z(fileName);
// if (z.is_open()) cout << "\nYour file is open and begun to work" << endl;
// else cout << "XYI, a ne risovanie";
z << "digraph G { \n";
treePaint2(root, null, &z);
z << "}";
z.close();
}
int overlap (space *x, space *y){
if ((x->low <= y->low) && (x->high >= y->high) )
return 1;
else return 0;
}
int overlapPoint (int x, space *y){
if ((x >= y->low) && (x <= y->high)) return 1;
else return 0;
}
int tree::pointSearch (int x, char c) {
leaf *a = root;
while ((a != null) && (!overlapPoint(x, &(a->i)))) {
if ((a->left != null) && (x <= a->left->max)) a = a->left;
else if ((a->right != null) && (x <= a->right->max)) a = a->right;
else {cout << "No point in axis " << c <<"."<< endl;
return 0;}
}
if (a != null) {
cout << "Axis " << c << ":" << a->i.low << "-" << a->i.high <<"."<< endl;
return 1;
}
else {
return 0;
}
}
void treePointSearch(tree *xT, tree *yT) {
int x1,x2,y1,y2;
char c,a,b;
cout << "q - quit, s - search" << endl;
scanf("%c%c",&a,&c);
switch (c) {
case 'q':
cout << "end.";
case 's':
cout << "Please put coordinate of your object in format 'x1-x2,y1-y2'" << endl;
scanf("%d%*c%d%*c%d%*c%d", &x1, &x2, &y1, &y2);
space x,y;
x.low = x1; x.high = x2;
y.low = y1; y.high = y2;
if (xT->intervalSearch(x,'X') && yT->intervalSearch(y,'Y')) {
cout << "The Object is in the field." << endl;
}
else {
cout << "The Object is not present in the field." << endl;
}
cout << "Do you want try one more? y/n"<< endl;
scanf("%c%c", &a, &c);
if (c == 'y') treePointSearch(xT, yT);
}
}
int tree::intervalSearch (space a, char c){
leaf *x = root;
while (!overlap (&(x->i),&a) && (x != null)) {
if ((x->left != null) && (x->left->max >= a.high)) x = x->left;
else {
if ((x->right != null) && (x->right->max >= a.high)) x = x->right;
else {
cout << "No obj in axis " << c << endl;
return 0;
}
}
}
cout << "Axis " << c << ":" << x->i.low << "-" << x->i.high << endl;
return 1;
}
void tree::transplant (leaf *x, leaf *y){
if (x->father == null) root = y;
else {
if (x == x->father->left) x->father->left = y;
else x->father->right = y;
}
y->father = x->father;
}
leaf *tree::minimum (leaf *a){
while (a->left != null) a = a->left;
return a;
}
leaf *tree::maximum (leaf *a){
while (a->right != null) a = a->right;
return a;
}
void tree::treeDeleteFixup(leaf *x){
leaf *w;
while ((x != root) && (x->color == 1)){
if (x == x->father->left){
w = x->father->right;
if (w->color == 0) {
w->color = 1;
x->father->color = 0;
leftRotate(x->father);
w = x->father->right;
}
if ((w->left->color == 1) && (w->right->color == 1)){
w->color = 0;
x = x->father;
}
else {
if (w->right->color == 1){
w->left->color = 1;
w->color = 0;
rightRotate(w);
w = x->father->right;
}
w->color = x->father->color;
x->father->color = 1;
w->right->color = 1;
leftRotate(x->father);
x = root;
}
}
else {
w = x->father->left;
if (w->color == 0) {
w->color = 1;
x->father->color = 0;
rightRotate(x->father);
w = x->father->left;
}
if ((w->right->color == 1) && (w->left->color == 1)){
w->color = 0;
x = x->father;
}
else {
if (w->left->color == 1){
w->right->color = 1;
w->color = 0;
leftRotate(w);
w = x->father->left;
}
w->color = x->father->color;
x->father->color = 1;
w->left->color = 1;
rightRotate(x->father);
x = root;
}
}
}
x->color = 1;
}
void tree::treeDelete (leaf *z){
leaf *y = z;
leaf *x;
int yOriginalColor = y->color;
if (z->left == null){
x = z->right;
transplant (z,z->right);
}
else {
if (z->right == null) {
x = z->left;
transplant (z,z->left);
}
else {
y = minimum(z->right);
yOriginalColor = y->color;
x = y->right;
if (y->father == z) x->father = y;
else {
transplant(y, y->right);
y->right = z->right;
y->right->father = y;
}
transplant(z, y);
y->left = z->left;
y->left->father = y;
y->color = z->color;
}
}
if (yOriginalColor == 1) treeDeleteFixup(x);
}
void tree::treeBuild (char *fileName, char *fileNameOut) {
ifstream inflow(fileName);
//if (inflow) cout << endl << "Your file is open and begun to work" << endl;
//else cout << endl << "Your file doesn't found" << endl;
char string[10];
int *numSearch = new int[5];
int count = 0;
while (!inflow.eof()) {
inflow >> string;
char *high = new char[3];
char *low = new char[3];
int i = 0;
while (string[i] != '\0') {
if (string[i] == '-') {
for (int j = 0; j < i; j++)
low[j] = string[j];
low[2] = '\0';
int k = 0;
while (string[++i] != '\0') {
high[k++] = string[i];
}
}
i++;
}
leaf *a = new leaf(atoi(low), atoi(high));
treeInsert(a);
}
ofstream a(fileNameOut);
treePrint(root, &a, 0); // закинули дерево в выходной документ
// treePrintAnswer(&a, numSearch, count);
}
int main (int argc, char *argv[]) {
tree Tx,Ty;
Tx.treeBuild(argv[1],argv[2]); //построение дерева по файлу
Ty.treeBuild(argv[3],argv[4]);
treePointSearch(&Tx,&Ty);
Tx.treePaint(argv[5]); //Нарисовали в .dot
Ty.treePaint(argv[6]);
return 0;
}