phone_catalog

#include <utility>
#include <iostream>
#include <c++/4.8.3/queue>

using namespace std;

struct Node {
    string name;
    string phone;
    Node *left_son;
    Node *right_son;

    explicit Node(string n, string p = "Permisson denied") : name(move(n)), phone(std::move(p)), left_son(nullptr),
                                                             right_son(nullptr) {}
};

class SearchTree {
    Node *root;

    Node *create_node(const string &name = "", const string &phone = "");

    Node *search(const string &name, bool last_prev = false);

    void cp(Node *original, Node *copy);

    void turn_left(Node *head);

    void turn_right(Node *head);

    void in_order_print(Node *current_node);

    void post_order_del(Node *current_node);

    bool is_leaf(Node *curr_node);

public:

    SearchTree() : root(nullptr) {}

    ~SearchTree(){
        if(root){
            post_order_del(root);
        }
    }

    void add_contact(const string &name, const string &phone = "");

    void remove_contact(const string &name);

    string search_phone(const string &name);

    void print_list_of_contacts();

    void by_level_print();


};

int main() {
    SearchTree my_tree;
    string command;
    string name;
    string phone;
    string temp;
    bool shortcut = false;
    cout << "add <name> <phone(s)> - to add contact in directory\n" <<
         "search <name> - to find phone(s) by name\n" <<
         "erase <name> - to remove contact from directory\n" <<
         "print - to print list of contacts here\n" <<
         "q - to quit\n";
    while (true) {
        if (! shortcut) {
            cin >> command;
        }
        if (command == "add") {
            cin >> name >> phone;
            temp = my_tree.search_phone(name);
            if (temp != "404") {
                cout
                        << "You already have a contact with that name. Want to add another phone number to this contact? (y/n)"
                        << endl;
                cin >> command;
                while ((command != "y") && (command != "n")) {
                    cout << "Incorrect answer. Try again. y or n?" << endl;
                    cin >> command;
                }
                if (command == "n") {
                    cout << "In this case, please choose another name." << endl;
                    shortcut = true;
                    command = "add";
                    continue;
                } else {
                    cout << "OK" << endl;
                }
            }
            my_tree.add_contact(name, phone);
            shortcut = false;
            cout << "Done" << endl << endl;
            my_tree.by_level_print();
        } else if (command == "search") {
            cin >> name;
            cout << my_tree.search_phone(name) << endl;
        } else if (command == "erase") {
            cin >> name;
            my_tree.remove_contact(name);
            cout << "Done!" << endl << endl;
            my_tree.by_level_print();
        } else if (command == "print") {
            cout << "<name> - <phone number(s)>" << endl;
            my_tree.print_list_of_contacts();
        } else if (command == "q") {
            break;
        } else {
            cout << "Incorrect command, try again. I believe u can~" << endl;
        }
    }
    cout << "Thx 4 using our software :)" << endl;
    return 0;
}

Node *SearchTree::create_node(const string &name, const string &phone) {
    return new Node(name, phone);
}

Node *SearchTree::search(const string &name, bool last_prev) {
    static Node *last_node_prev = nullptr;
    if (last_prev) {
        return last_node_prev;
    }
    Node *curr_node = root;
    while ((curr_node) && (curr_node->name != name)) {
        last_node_prev = curr_node;
        curr_node = name > curr_node->name ? curr_node->right_son : curr_node->left_son;
    }
    return curr_node;
}

void SearchTree::cp(Node *original, Node *copy) {
    copy->name = original->name;
    copy->phone = original->phone;
    copy->left_son = original->left_son;
    copy->right_son = original->right_son;
}

void SearchTree::turn_left(Node *head) {
    cout << "turn left" << endl;
    Node *temp = head->right_son;
    head->right_son = temp->left_son;
    Node *new_head = create_node();
    cp(head, new_head);
    cp(temp, head);
    head->left_son = new_head;
    delete temp;
}

void SearchTree::turn_right(Node *head) {
    cout << "turn right" << endl;
    Node *temp = head->left_son;
    head->left_son = temp->right_son;
    Node *new_head = create_node();
    cp(head, new_head);
    cp(temp, head);
    head->right_son = new_head;
    delete temp;
}

bool SearchTree::is_leaf(Node *curr_node) {
    return (! curr_node->left_son) && (! curr_node->right_son);
}

void SearchTree::add_contact(const string &name, const string &phone) {
    Node *new_node = search(name);
    if (new_node) {
        new_node->phone += ", " + phone;
        return;
    }
    new_node = create_node(name, phone);
    if (root == nullptr) {
        root = new_node;
        return;
    }
    Node *curr_node = root;
    Node *prev_node = curr_node;
    while (curr_node) {
        prev_node = curr_node;
        curr_node = new_node->name > prev_node->name ? prev_node->right_son : prev_node->left_son;
    }
    (prev_node->name < new_node->name ? prev_node->right_son : prev_node->left_son) = new_node;
}

void SearchTree::remove_contact(const string &name) {
    Node *useless_node = search(name);
    Node *prev_node = nullptr;
    bool left = true;

    if (! useless_node) {
        return;
    }
    if (is_leaf(useless_node)) {
        if (root == useless_node) {
            delete root;
            root = nullptr;
            return;
        }
        prev_node = search(name, true);
        left = prev_node->left_son == useless_node;
    }
    while (! is_leaf(useless_node)) {
        if (useless_node->right_son) {
            turn_left(useless_node);
            prev_node = useless_node;
            useless_node = useless_node->left_son;
            left = true;
        } else {
            prev_node = useless_node;
            turn_right(useless_node);
            useless_node = useless_node->right_son;
            left = false;
        }
    }
    delete useless_node;
    if (prev_node) {
        (left ? prev_node->left_son : prev_node->right_son) = nullptr;
    }

}

string SearchTree::search_phone(const string &name) {
    Node *my_node = search(name);
    if (my_node) {
        return my_node->phone;
    } else {
        return "404";
    }

}

void SearchTree::in_order_print(Node *current_node) {
    if (current_node->left_son) {
        in_order_print(current_node->left_son);
    }
    cout << current_node->name << " - " << current_node->phone << endl;
    if (current_node->right_son) {
        in_order_print(current_node->right_son);
    }
}

void SearchTree::print_list_of_contacts() {
    if (root) {
        in_order_print(root);
    }
}

void SearchTree::by_level_print() {
    if(root == nullptr){
        return;
    }
    queue<Node *> *current_level = new queue<Node *>;
    queue<Node *> *next_level = new queue<Node *>;
    current_level->push(root);
    Node *curr_node;
    queue<Node *> *temp;
    while (! current_level->empty()) {
        curr_node = current_level->front();
        current_level->pop();
        cout << curr_node->name << " ";
        if (curr_node->left_son) {
            next_level->push(curr_node->left_son);
        }
        if (curr_node->right_son) {
            next_level->push(curr_node->right_son);
        }
        if (current_level->empty()) {
            temp = next_level;
            next_level = current_level;
            current_level = temp;
            cout << endl;
        }

    }
    cout << endl << endl;
}

void SearchTree::post_order_del(Node *current_node) {
    if (current_node->left_son) {
        post_order_del(current_node->left_son);
    }
    if (current_node->right_son) {
        post_order_del(current_node->right_son);
    }
    delete current_node;
}