// file  Tree23.h  
// частичный пример 2-3 дерева 
// с использованием наследования
   
#pragma once

#include <iostream>
using namespace std;                  


//  2-3 дерево
//  чвстичная реализация

template <class T>
class Tree23
{
    struct TreeNode {
        T value;
        TreeNode *first, *second;
        TreeNode(const T& x, TreeNode* p1, TreeNode *p2) { value = x; first = p1, second = p2; }
        virtual TreeNode * Add(T &x, TreeNode *&q2); 
        virtual void Print(ostream &os) const;
        virtual ~TreeNode() {} 
    }; 
        
    struct TreeNode3 : public TreeNode {
        T value2;
        TreeNode *third;
        TreeNode3(const T& x1, const T& x2, TreeNode* p1, TreeNode *p2, TreeNode *p3) 
           : TreeNode(x1, p1, p2) { value2 = x2; third = p3; }
        TreeNode * Add(T &x, TreeNode *&q2); 
        void Print(ostream &os) const;
        ~TreeNode3() {}    
    };

    TreeNode * root;

    // вспомогательная функция для сокращения кода
    inline static void Replace(TreeNode *&p, TreeNode *&q) { if (p != q) { delete p; p = q; } }

public:
    Tree23() { root = nullptr; }
    void Add(const T &x);
    ~Tree23() { /* надо реализовать */ }

    template<class P>
    friend ostream & operator<<(ostream &os, const Tree23<P> &t);
};

template <class T>
ostream & operator<<(ostream &os, const Tree23<T> &t)
{
    os << "The tree:\n";
    if (t.root) t.root->Print(os);
    os << "end\n";
    return os;
}

template <class T>
void Tree23<T>::TreeNode::Print(ostream &os) const
{
    os << this << " : " <<value  << " -> " << first << " " << second <<endl;
    if (first) {
        first->Print(os);
        second->Print(os);
    }
}

template <class T>
void Tree23<T>::TreeNode3::Print(ostream &os) const
{
    os << this << " : " << TreeNode::value << " " << value2 << " -> ";
    os << TreeNode::first << " " << TreeNode::second <<  " " << third <<endl;
    if (TreeNode::first) {
        TreeNode::first->Print(os);
        TreeNode::second->Print(os);
        third->Print(os);
    }
}

// добавление значения x в текущую вершину 2-3 дерева.
// Eсли x уже есть в дереве, то не делает ничего.
// Если добавилось без расщепления, то возращает указатель на 
// корень получившегося поддерева и q2 = 0.
// Если на данном уровне произошло расщепление, 
// то возвращает указатель на левое поддерево, 
// правое поддерево передается через параметр q2,
// вытолкнутое значение - через параметр x.


template <class T>
typename Tree23<T>::TreeNode * Tree23<T>::TreeNode::Add( T &x, TreeNode *&q2)
{
    // 2-вершина либо остается собой, либо преобразуется в 3-вершину
    TreeNode3 *q0;
    TreeNode *q1 = nullptr;
    q2 = nullptr;    
    
    if (x < value) {
        if (first) {   // добавляем в поддерево
            q1 = first->Add(x, q2);
            if (q2 == nullptr) {  // расщепления поддерева не было 
                Tree23<T>::Replace(first, q1);
                return this; 
            }
        } 
        // тут надо добавлять x в данную вершину
        // т.е. переходить к 3-вершине
        q0 = new TreeNode3(x, value, q1, q2, second);
        q2 = nullptr;
        return q0;
    } else if (x > value ) {   // аналогично справа
        if (second) {   // добавляем в поддерево
            q1 = second->Add(x, q2);
            if (q2 == nullptr) {  // расщепления поддерева не было 
                Replace(second, q1);
                return this; 
            }
        } 
        // тут надо добавлять x в данную вершину
        q0 = new TreeNode3(value, x, first, q1, q2);
        q2 = nullptr;
        return q0;
    } else {  // значение x уже есть в дереве
        return this;
    }
} 

template <class T>
typename Tree23<T>::TreeNode * Tree23<T>::TreeNode3::Add( T &x, TreeNode *&q2)
{
    // 3-вершина либо остается собой, либо расщепляется на две 2-вершины
    TreeNode *q01, *q02, *q1 = nullptr;
    q2 = nullptr;    

    if (x < TreeNode::value) {
        if (TreeNode::first) {   // добавляем в поддерево
            q1 = TreeNode::first->Add(x, q2);
            if (q2 == nullptr) {  // расщепления поддерева не было 
                Tree23<T>::Replace(TreeNode::first, q1);
                return this; 
            }
        } 
        // тут надо расщеплять данную вершину
        q01 = new TreeNode(x, q1, q2);
        q02 = new TreeNode(value2, TreeNode::second, third);
        x = TreeNode::value;
        q2 = q02;
        return q01;
    } else if (x == TreeNode::value ) {  // значение есть в value
        return this;
    } else if (x < value2 ) {
        if (TreeNode::second) {   // добавляем в поддерево
            q1 = TreeNode::second->Add(x, q2);
            if (q2 == nullptr) {  // расщепления поддерева не было 
                Tree23<T>::Replace(TreeNode::second, q1);
                return this; 
            }
        } 
        // тут надо расщеплять данную вершину
        q01 = new TreeNode(TreeNode::value, TreeNode::first, q1);
        q02 = new TreeNode(value2, q2, third);
        q2 = q02;
        return q01;
    } else if (x == value2 ) {  // значение есть в value2
        return this;
    } else {
        if (third) {   // добавляем в поддерево
            q1 = third->Add(x, q2);
            if (q2 == nullptr) {  // расщепления поддерева не было 
                Tree23<T>::Replace(third, q1);
                return this; 
            }
        } 
        // тут надо расщеплять данную вершину
        q01 = new TreeNode(TreeNode::value, TreeNode::first, TreeNode::second);
        q02 = new TreeNode(x, q1, q2);
        x = value2;
        q2 = q02;
        return q01;
    }
}


template <class T>
void Tree23<T>::Add(const T&x)
{
    TreeNode  *q1 = nullptr, *q2 = nullptr;
    T xx = x;
    if (root) {
        q1 = root->Add(xx, q2);
        if (q2 == nullptr) {
            Tree23<T>::Replace(root,q1);
            return;
        } 
    }
    delete root;
    root = new TreeNode(xx, q1, q2);
}