// Treap2.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>

#include <stdio.h>
#include <iostream>

using namespace std;


struct Node {
	int key, prior;
	Node* l = 0, *r = 0;
	Node(int _key) { key = _key, prior = rand(); }
	Node(int _key, int _p) { key = _key, prior = _p; }
	friend ostream& operator<<(ostream& stream, Node& N)
	{
		if (N.l != 0)
			stream << *N.l;
		stream << N.key << "; " << N.prior << "\n";
		if (N.r != 0)
			stream << *N.r;
		return stream;
	}
};

Node* root = 0;

Node* merge(Node* l, Node* r) {
	if (!l) return r;
	if (!r) return l;
	if (l->prior > r->prior) {
		l->r = merge(l->r, r);
		return l;
	}
	else {
		r->l = merge(l, r->l);
		return r;
	}
}

typedef pair<Node*, Node*> Pair;

Pair split(Node* p, int x) {
	if (!p) return { 0, 0 };
	if (p->key < x) {
		Pair q = split(p->r, x);
		p->r = q.first;
		return { p, q.second };
	}
	else {
		Pair q = split(p->l, x);
		p->l = q.second;
		return { q.first, p };
	}
}

void insert(int x) {
	if (root == 0)
	{
		root = new Node(x);
		return;
	}
	Pair q = split(root, x);
	Node* t = new Node(x);
	root = merge(q.first, merge(t, q.second));
}

Node* copy(int b = -1)
{
    Node* cur = new Node;
    cur->key = key;
    cur->prior = prior;
    Node* left1;
    Node* right1;
    if (b!=1 && l!=NULL)
        left1 = l->copy();
    else
        left1 = NULL;
    if (b!=0 && r!=NULL)
        right1 = r->copy();
    else
        right1 = NULL;
    cur->l = left1;
    cur->r = right1;
    return cur;
}

class Treap
{
public:
	Node* root;

	//добавить поле, которое можно хранить и поддерживать в узле
	Treap(Node* n = NULL)
	{
		root = n;
	}

	Treap* Merge(Treap* T)
    {
        Treap *copy_this, *copy_T;
        copy_this = new Treap(copy(this));
        copy_T = new Treap(copy(T));
        Treap* res = new Treap();
        res->root = merge(copy_this->root, copy_T->root);
        delete this;
        delete T;
        return res;
    }


    void Split(int x, Node* eq, Treap* left, Treap* right)
    {
        Node* croot <= root;
        Pair p1 = split(croot, x);
        left = new Treap(p1.first);
        right = new Treap(p1.second);
        Node* cur = p1.second;
        while (cur->l)
            cur = cur->l;

        if (cur->key == x)
        {
            eq <= cur;
            delete cur;
        }
        else
            eq = nullptr;
    }


	~Treap()
	{

	}

	friend ostream& operator<<(ostream& stream, Treap& T)
	{
		if(T.root!=NULL)
			stream<<*T.root;
		else
			stream<<"\nEmpty treap!";
		return stream;
	}
};

int main()
{
	Node* N1 = new Node(0, 100);
	root = N1;
	Node* N2 = new Node(10, 50);
	Node* N3 = new Node(20, 25);
	Node* N4 = new Node(30, 55);
	Node* N5 = new Node(40, 10);
	merge(root, N2);
	merge(root, N3);
	merge(root, N4);
	merge(root, N5);

	Pair p = split(root, 30);
	cout << *p.first << "\n\n" << *p.second;
	//insert(1);insert(10);insert(0);insert(-5);insert(3);
	cout << *root;

	return 0;
}


// Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
// Отладка программы: F5 или меню "Отладка" > "Запустить отладку"

// Советы по началу работы
//   1. В окне обозревателя решений можно добавлять файлы и управлять ими.
//   2. В окне Team Explorer можно подключиться к системе управления версиями.
//   3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
//   4. В окне "Список ошибок" можно просматривать ошибки.
//   5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
//   6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.