Tree lib

//
// Created by Sailein on 27.05.2018.
//

#ifndef IAMGROOT_GROOTTREE_H
#define IAMGROOT_GROOTTREE_H

#include <iostream>
#include <string>
#include <sstream>
#include <cmath>

using namespace std;

struct Complex //стуктура комплексных чисел
{
    double re, im;
    Complex (double re = 0.0, double im = 0.0) : re(re), im(im) {} // constructor
    Complex (const Complex& other)
    {
        *this = other;
    }
    Complex operator+(const Complex& other) const // & - ссылка - чтобы не копировать
    {
        return Complex(re + other.re, im + other.im);
    }
    Complex operator*(const Complex& other) const
    {
        return Complex((re * other.re - im * other.im), (re * other.im + other.re * im));
    }
    Complex operator*(double scalar) const
    {
        return Complex(re * scalar, im * scalar);
    }
    const Complex& operator=(const Complex& other)
    {
        this->re = other.re;
        this->im = other.im;
        return *this;
    }
    double modulus () const
    {
        return sqrt(pow(re, 2.0) + pow(im, 2.0));
    }
    bool operator!= (const Complex& other) const
    {
        return (this->re != other.re) && (this->im != other.im);
    }
    bool operator== (const Complex& other) const
    {
        return (this->re == other.re) && (this->im == other.im);
    }
    bool operator<(double num) const
    {
        return modulus() < num;
    }
    bool operator>(double num) const
    {
        return modulus() > num;
    }
};

ostream& operator<<(ostream& os, const Complex& number)
{
    return os << number.re << " + " << number.im << "i ";
}

istream& operator>>(istream& is, Complex& number)
{
    return is >> number.re >> number.im;
}

template <typename T>
class Tree; // объявление класса Дерево

template <typename T>
struct Operation // дефолтная операция для обхода (ничего не делаем) - все что наследуется используем в траверсе
{
    virtual void operator()(const T& element) {}
};

template <typename T>
struct CloneOperation: public Operation<T> // операция клонирования деревьев
{
    Tree<T>& result;
    CloneOperation(Tree<T>& reciever) : result(reciever) {}
    virtual void operator()(const T& element)
    {
        result.insert(element);
    }
};

template <typename T>
struct StringPrintOperation: public Operation<T> // операция вывода элементов в строку
{
    string result;
    virtual void operator()(const T& element)
    {
        result += to_string(element) + ",";
    }
};

template <typename T, typename F>
struct MapOperation: public Operation<T> // операция мап - применение функции
{
    Tree<F> result;
    F (*func) (const T& element);
    MapOperation( F (*func) (const T& element)) : func(func) {}
    virtual void operator()(const T& element)
    {
        result.insert(func(element));
    }
};

template <typename T>
struct WhereOperation: public Operation<T> // операция мап - применение функции
{
    Tree<T> result;
    bool (*func) (const T& element);
    WhereOperation( bool (*func) (const T& element)) : func(func) {}
    virtual void operator()(const T& element)
    {
        result.insert(func(element));
    }
};

template <typename T>
class Tree // Я ЕСТЬ ГРУТ
{
private:
    class Node // элемент древа - право лево назад  и данные
    {
    private:
        T m_data;
        Node* m_left;
        Node* m_right;
        Node* m_parent;
    public:
        Node (const T& data, Node* parent = nullptr, Node* left = nullptr, Node* right = nullptr) // конструктор
                : m_data(data), m_parent(parent), m_left(left), m_right(right) {};
        const T& data() const // все сеттеры и геттеры
        {
            return m_data;
        }
        void setData(const T& data)
        {
            m_data = data;
        }
        Node* parent()  const
        {
            return m_parent;
        }
        Node* left() const
        {
            return m_left;
        }
        Node* right() const
        {
            return m_right;
        }
        void setLeft(Node* left)
        {
            m_left = left;
        }
        void setRight(Node* right)
        {
            m_right = right;
        }
        void setParent(Node* parent)
        {
            m_parent = parent;
        }
    };
    Node* m_root = nullptr;
    size_t m_size = 0;
public:
    Tree<T>() {} // конструктор по умолчанию
    Tree<T>(string row)
    {
        insertFromString(row); // конструктор древа из строки
    }
    Tree<T>(const char* row)
    {
        insertFromString(row); // конструктор древа из строки еще 1
    }
    Tree<T> (const Tree<T>& other) // конструктор копирования
    {
        *this = other;
    }
    void insert (const T& element) // ввод элемента - самое важное
    {
        if (root() == nullptr)
        {
            setRoot(new Node(element));
            return;
        }
        Node* cur = root(); // cur - current временная переменная
        while (element != cur->data())
        {
            if (element > cur->data())
            {
                if (cur->right() == nullptr)
                {
                    cur->setRight(new Node(element, cur));
                    return;
                }
                cur = cur->right();
            }
            else if (element < cur->data())
            {
                if (cur->left() == nullptr)
                {
                    cur->setLeft(new Node(element, cur));
                    return;
                }
                cur = cur->left();
            }
        }
    }
    void traverse (Operation<T>& operation, string type = "kpl") const // обход - публик версия - регистронезависим
    {
        traverse(root(), operation, type);
    }
    bool containsElement (const T& element) const // есть ли вхождение элемента? (!)
    {
        return search(element) != nullptr;
    }
    Tree<T> extract (const T& element) const // извлечение поддерева по элементу (!)
    {
        Tree<T> result;
        CloneOperation<T> clone(result);
        Node* subRoot = search(element);
        traverse(subRoot, clone); //обход с копированием
        return clone.result;
    }
    string toString (string traverseType) const // извлечение в строку (!)
    {
        StringPrintOperation<T> row;
        traverse(root(), row, traverseType);
        return row.result.substr(0, row.result.size()-1); //убираем последнюю запятую. и если элеменетов нет то пишем пустую строку
    }
    void insertFromString (string row) // чтениче из строки и построение дерева (!)
    {
        for (size_t i = 0; i < row.size();) //проверить < or <= наш цикл идет от запятой до запятой
        {
            size_t j = row.find(',', i + 1);
            T tmp;
            istringstream stream (row.substr(i, j));
            stream >> tmp;
            insert(tmp);
            if (j == string::npos)  return;
            i = j + 1;
        }
    }
    const Tree<T>& operator=(const Tree<T>& other)
    {
        CloneOperation<T> clone(*this);
        other.traverse(clone); //обход с копированием
        return *this;
    }
    friend Tree<T> operator+(const Tree<T>& tree1, const Tree<T>& tree2) //слияние (!)
    {
        Tree<T> result;
        CloneOperation<T> clone(result);
        tree1.traverse(clone);
        tree2.traverse(clone);
        return clone.result;
    }
    template <typename F>
    Tree<F> map (F (*func) (const T& element)) const // map (!) - используем лямбда функции
    {
        MapOperation<T, F> mapOp(func);
        traverse(mapOp);
        return mapOp.result;
    }
    Tree<T> where (bool (*func) (const T& element)) const // where (!)
    {
        WhereOperation<T> whereOp(func);
        traverse(whereOp);
        return whereOp.result;
    }
protected:// так как они используют Node* - а это внутренне устройство дерева, мы его защитим
    Node* root() const
    {
        return m_root;
    }
    void setRoot (Node* root)
    {
        m_root = root;
    }
    // Обходы: * КЛП * КПЛ * ЛПК * ЛКП * ПЛК * ПКЛ; К – корень Л – лево (левое поддерево) П – право (правое поддерево)
    void traverse (Node* node, Operation<T>& operation, string type = "kpl") const //обход
    {
        if (node == nullptr) return;
        for (int i = 0; i < 3; ++i)
        {
            if ((type[i] == 'K') || (type[i] == 'k'))
            {
                operation(node->data()); // "K"
            }
            else if ((type[i] == 'P') || (type[i] == 'p'))
            {
                traverse(node->right(), operation, type); // "P"
            }
            else if ((type[i] == 'L') || (type[i] == 'l'))
            {
                traverse(node->left(), operation, type); // "L"
            }
        }
    }
    Node* search (const T& element) const // поиск элемента - это как insert , но ток без изменений
    {
        if (root() == nullptr) return nullptr;
        Node* cur = root();
        while (element != cur->data())
        {
            if (element > cur->data())
            {
                if (cur->right() == nullptr)
                {
                    return nullptr;
                }
                cur = cur->right();
            }
            else if (element < cur->data())
            {
                if (cur->left() == nullptr)
                {
                    return nullptr;
                }
                cur = cur->left();
            }
        }
        return cur;
    }
};
#endif //IAMGROOT_GROOTTREE_H