#include "lab1.h"
#include "lab2.h"
#include "lab3.h"

using namespace std;

/*
void sort(lab1::Queue<int>& q){
    for(int i = 0; i < q.size(); ++i){
        int mn = INT_MAX;
        int first = 0, temp = 0;
        bool swap = true;
        for(int j = 0; j < i; ++j){
            temp = q.front();
            q.pop();
            q.push(temp);
        }
        first = q.front();
        for(int j = i; j < q.size(); ++j){
            temp = q.front();
            mn = min(q.front(), mn);
            q.pop();
            q.push(temp);
        }
        for(int j = 0; j < i; ++j){
            temp = q.front();
            q.pop();
            q.push(temp);
        }
        for(int j = i; j < q.size(); ++j){
            temp = q.front();
            q.pop();
            if(temp == mn && swap) {
                q.push(first);
                swap = false;
            }
            else if(i == j) {
                q.push(mn);
            }
            else
                q.push(temp);
        }
    }
}


int main(){
    srand(time(nullptr));
    lab1::Queue<int> queue(50000);
    for(int i = 0; i < queue.size(); ++i)
        queue.push(rand() % 100000);
    queue.print();
    ::clock_t time = ::clock();
    sort(queue);
    time = ::clock() - time;
    cout << endl;
    queue.print();

    cout << 1000* time / CLOCKS_PER_SEC;
    return 0;
}*/



/*int main(){
    lab2::Graph G(4);
    set<int> visited;
    int cCount;
    cin >> cCount;
    for(int i = 0; i < cCount; ++i){
        char first_v, second_v;
        int weight;
        cin >> first_v >> second_v >> weight;
        G.Add_E(first_v, second_v, weight);
    }
    G.print();


    return 0;
}*/
/*
4
a c 5
b c 11
c b 3
d a 7
 */

void dfs1(lab3::TreeNode* root){
    if(root == nullptr){
        return;
    } else {
        cout << root->val;
        dfs1(root->left);
        dfs1(root->right);
    }
}

void dfs2(lab3::TreeNode* root){
    if(root == nullptr){
        return;
    } else{
        dfs2(root->left);
        cout << root->val;
        dfs2(root->right);
    }
}

bool Compare(int val, lab3::TreeNode* tree){
    if(tree->val == val)
        return true;
    else{
        if(tree != nullptr){
            Compare(val, tree->left);
            Compare(val, tree->right);
        } else {
            return false;
        }
    }
}

int findMinEl(lab3::TreeNode*& root){
    if(root->left == nullptr){
        int val = root->val;
        root = nullptr;
        return val;
    } else {
        findMinEl(root->left);
    }
}

void DeleteNode(lab3::TreeNode *&root){
    if(root == nullptr)
        return;
    else if(root->left == nullptr&& root->right == nullptr){
        root = nullptr;
    } else if(root->left != nullptr&& root->right == nullptr){
        root = root->left;
    } else if(root->left == nullptr&& root->right != nullptr){
        root = root->right;
    } else {
        root->val = findMinEl(root);
    }
}



void multiplie(lab3::TreeNode*& a, lab3::TreeNode* b){
    while (a != nullptr){
        if(Compare(a->val, b)){
            multiplie(a->left, b);
            multiplie(a->right, b);
        } else {
            DeleteNode(a);
        }
    }
}

int main(){
    lab3::TreeNode *root1, *root2;
    vector<int> v1 = {5,8,6,4,2,9}, v2 = {6,4,8,7,1,3};
    for(int i = 0; i < v1.size(); ++i) {
        lab3::Add(root1, v1[i]);
        lab3::Add(root2, v2[i]);
    }
    multiplie(root1, root2);
    dfs1(root1);
}