#pragma once
#include <optional>

namespace cartesian {
using Key = float;
using Value = int;
using Priority = int;

struct Node;

struct Tree {
    Node* root = nullptr;

    bool empty() const {
        return root == nullptr;
        // return !root;
    }

    void insert(Key x, Value v, Priority y);

    std::optional<Value> find(Key x);

    std::optional<Value> remove(Key x);

    std::pair<Tree, Tree> split(Key x, bool upper = false);

    static Tree merge(Tree l, Tree r);
};

struct Node {
    Key x;
    Value v;
    Priority y;
    Tree l, r;
};

std::pair<Tree, Tree> Tree::split(Key x, bool upper) {
    if (empty())
        return {{},{}};
        // return {};
    bool root_is_right;
    if (upper)
        root_is_right = (root->x > x);
    else
        root_is_right = (root->x >= x);
    if (root_is_right) {
        //std::pair<Tree, Tree> split_result =
        //        root->l.split(x);
        auto [l, r] = root->l.split(x);
        root->l = r;
        return {l, *this};
    } else {
        auto [l, r] = root->r.split(x);
        root->r = l;
        return {*this, r};
    }
}

Tree Tree::merge(Tree l, Tree r) {
    if (l.empty())
        return r;
    if (r.empty())
        return l;
    if (l.root->y < r.root->y) {
        r.root->l = merge(l, r.root->l);
        return r;
    } else {
        l.root->r = merge(l.root->r, r);
        return l;
    }
}

void insert(Key x, Value v, Priority y);

std::optional<Value> Tree::find(Key x) {
    auto [l, r] = split(x);
    auto [rl, rr] = r.split(x, true);
    std::optional<Value> ans;
    if (!rl.empty())
        ans = rl.root->v;
    *this = merge(l, merge(rl, rr));
    return ans;
}

std::optional<Value> Tree::remove(Key x) {
    auto [l, r] = split(x);
    auto [rl, rr] = r.split(x, true);
    std::optional<Value> ans;
    if (!rl.empty()) {
        ans = rl.root->v;
        delete rl.root;
    }
    *this = merge(l, rr); // TODO: пропал rl?????
    return ans;
}

void Tree::insert(Key x, Value v, Priority y) {
    remove(x);
    auto [l, r] = split(x);
    // новое дерево c
    Node* node_ptr = new Node{
        .x = x,
        .v = v,
        .y = y,
        .l = {},
        .r = {},
    };
    Tree c{.root = node_ptr};
    *this = merge(l, merge(c, r));
}
}