#include <iostream>
#include <math.h>
#include <string>
#include <vector>
using namespace std;



template <typename T>
struct treenode {
    T data;
    int kids;
    treenode *leftkid;
    treenode *rightkid;


};

template <typename T>
class tree {
    treenode<T> *root;

    void destroytree(treenode<T> *node) {
        if (node != nullptr) {
            destroytree(node->leftkid);
            destroytree(node->rightkid);
            delete node;
        }
    }

    void postorder_print(treenode<T> *node) {
        if (node != nullptr) {
            cout << node->data << endl;
            postorder_print(node->leftkid);
            postorder_print(node->rightkid);
        }
    }

    int get_value_of_function (treenode<void*> *node) {
        return ((int(*)(int))(node->data))(5);
    }

    void print_value_of_function (treenode<void*> *node) {
        if (node != nullptr) {
            cout << get_value_of_function(node) << endl;;
            print_value_of_function(node->leftkid);
            print_value_of_function(node->rightkid);
        }
    }


    // 1. map
    void map (treenode<T> *node, T value) {
        if (node != nullptr) {
            node->data = value;
            map (node->leftkid, value);
            map (node->rightkid, value);
        }
    }

    bool check (treenode<string> *node) {
        if ((node->data).length() < 5) return true;
        else return false;
    }

    bool check (treenode<void*> *node) {
        if (get_value_of_function(node) < 10) return true;
        else return false;
    }

    // 2. where
    void where (treenode<T> *node, tree<T> *new_tree) { // УКАЗАТЕЛЬ  на новое дерево
        if (node != nullptr) {
            if (check(node)) {
                T key = node->data;
                new_tree->insert(key);
            }
            where (node->leftkid, new_tree);
            where (node->rightkid, new_tree);
        }
    }


    // 3. слияние
    void merge_trees (treenode<T> *node_of_1st_tree, tree<T> second_tree) {
        // к дереву second_tree прибавляем все элементы дерева для к-ого вызвана ф-ия
        if (node_of_1st_tree != nullptr) {
            second_tree->insert(node_of_1st_tree->data);
            merge_trees(node_of_1st_tree->leftkid, second_tree);
            merge_trees(node_of_1st_tree->rightkid, second_tree);
        }
    }

    // 4. извлечение поддерева по заданному элементу
    void subtree_extraction (treenode<T> *node, T value, tree<T> *res_tree, vector<treenode<T>*> *store) {
        if (node != nullptr) {
            if(node->data == value) {
                store->push_back(node);
                return;
            }
            else {
                subtree_extraction(node->leftkid, value, res_tree, store);
                subtree_extraction(node->rightkid, value, res_tree, store);

            }
        // берем первое совпадение элемента в соответствии с обходом
        if (!store->empty()) res_tree->root = store->at(0);
        }
    }


    // 5. поиск элемента на вхождение
    bool does_value_contain (treenode<T> *node, T value, bool* check) {
        if (node != nullptr) {
            if (node->data == value) {
                *check = true;
            }
            else {
                does_value_contain(node->leftkid, value, check);
                does_value_contain(node->rightkid, value, check);
            }
        }
        if (*check == true) return true;
        else return false;
    }

    bool does_subtree_contain (treenode<T> *node, tree<T> *new_tree, vector<bool> *store) {

    }



////////////////////////////////////////////////////////////

public:
    tree() {
        root = nullptr;
    }

    ~tree() {
        destroytree(root);
    }

    void insert(T data);

    void postorder_print() {
        postorder_print(root);
    }
    void map (T value) {
        map (root, value);
    }
    void print_value_of_function () {
        print_value_of_function (root);
    }
    void where (tree<T> *new_tree) {
        where (root, new_tree);
    }
    void merge_trees (tree<T> *second_tree) { //
        merge_trees(root, second_tree);
    }
    void subtree_extraction (T value, tree<T> *res_tree) {
        vector<treenode<T>*> *store = new vector<treenode<T>*>;
        subtree_extraction(root, value, res_tree, store);
        delete store;
    }
    bool does_value_contain (T value) {
        bool* check = new bool;
        return does_value_contain(root, value, check);
    }

};



template <typename T>
void tree<T>:: insert(T data) {
    if (root == nullptr) {
        root = new treenode<T>;
        root->leftkid = nullptr;
        root->rightkid = nullptr;
        root->data = data;
        root->kids = 0;
    }
    else {
        treenode<T> *curr = root;
        int n(0), side(0), levelsize(0), range(0), number=root->kids+2;

        while (pow(2, n) <= number) {
            levelsize = pow(2, n);
            n++;
        }
        range = levelsize;

        while (range != 1) {
            if (number < (levelsize + range / 2)) {
                curr->kids++;
                if (range != 2) {
                    curr = curr->leftkid;
                    range = range / 2;
                }
                else {
                    side = 0;
                    break;
                }
            }
            else {
                curr->kids++;
                if (range != 2) {
                    curr = curr->rightkid;
                    range = range / 2;
                    levelsize += range;
                }
                else {
                    side = 1;
                    break;
                }
            }
        }

        treenode<T> *newnode = new treenode<T>;
        newnode->kids = 0;
        newnode->leftkid = nullptr;
        newnode->rightkid = nullptr;
        newnode->data = data;

        if (side == 0) {
            curr->leftkid = newnode;
        }
        else {
            curr->rightkid = newnode;
        }


    }
}

int f1 (int x) {
    return x + x;
}

int f2 (int x) {
    return pow(x, 3);
}

int f3 (int x) {
    return x + 1;
}

int main() {

    void *ptr[] = {(void*)f1, (void*)f2, (void*)f3};



    tree<string> char_tree;
    string s1 = "winter";
    string s2 = "spring";
    string s3 = "s";
    string s4 = "au";

    char_tree.insert(s1);
    char_tree.insert(s2);
    char_tree.insert(s3);
    char_tree.insert(s4);
    char_tree.insert(s1);
    char_tree.insert(s2);
    char_tree.insert(s3);
    char_tree.insert(s4);
    char_tree.insert(s2);
    char_tree.insert(s2);
    char_tree.insert(s2);
    char_tree.insert(s2);


    /*char_tree.insert(s1);
    char_tree.insert(s3);
    char_tree.insert(s4);
    char_tree.insert(s1);
    char_tree.insert(s3);
    char_tree.insert(s4); */
    string add = "mephi";

    if (char_tree.does_value_contain(s3)) cout << "s3 yes" << endl;
    else cout << "no" << endl;
    if (char_tree.does_value_contain(s1)) cout << "s1 yes" << endl;
    else cout << "no" << endl;
    if (char_tree.does_value_contain(s2)) cout << "s2 yes" << endl;
    else cout << "no" << endl;
    if (char_tree.does_value_contain(s4)) cout << "s4 yes" << endl;
    else cout << "no" << endl;
    if (char_tree.does_value_contain(add)) cout << "yes" << endl;
    else cout << "mephi no" << endl;

    /*tree<string> *new_tree = new tree<string>;

    //vector<treenode<string> *> store;
    char_tree.subtree_extraction(s2, new_tree);
    new_tree->postorder_print();*/


    /*string add = "mephi";
    string add2 = "mephi2";
    string add3 = "mephi3";
    string add4 = "mephi4";

    tree<string> *new_tree = new tree<string>;
    new_tree->insert(add);
    new_tree->insert(add2);
    new_tree->insert(add3);
    new_tree->insert(add4);

    char_tree.merge_trees(new_tree);
    new_tree->postorder_print();

    //char_tree.map(add);
    //char_tree.postorder_print();

    tree<string> *new_tree = new tree<string>;
    char_tree.where(new_tree);
    new_tree->postorder_print();


    tree<void*> function_tree;
    function_tree.insert(ptr[0]);
    function_tree.insert(ptr[1]);
    function_tree.insert(ptr[2]);

    //function_tree.postorder_print();
    //function_tree.print_value_of_function();

    //function_tree.map(ptr[1]);

    //function_tree.postorder_print();
    //function_tree.print_value_of_function();

    tree<void*> *new_tree2 = new tree<void*>;

    function_tree.subtree_extraction(ptr[0], new_tree2);
    //function_tree.where(new_tree2);
    new_tree2->postorder_print();
    new_tree2->print_value_of_function(); */













}