/**----------------------------------------------------------*
 *                                                           *
 * problem: drzewo binarne                                   *

 * rozwiazanie: poprawne wykorzystanie sprytnych wskaznikow  *
 *-----------------------------------------------------------*/

#include <memory>
#include <vector>
#include <iostream>

using namespace std;

class Tree {
    struct Node;
    using PNode = std::shared_ptr<Node>;
    using WNode = std::weak_ptr<Node>;
    using UNode = std::unique_ptr<Node>;

    struct Node {
        Node(int v) : value_(v) { cout << "C-tor " << value_ << endl; }
        ~Node() { cout << "D-tor " << value_ << endl; }
        int value_;

        void add(PNode child) {
            if(child->value_ < value_) {
                //modify left sub-tree
                if( left_ )
                    left_->add(child);
                else {
                    left_ = child;
                    left_->parent_ = me_.lock();
                    if(right_) {
                        left_->sibling_ = right_;
                        right_->sibling_ = left_;
                    }
                }
            } else {
                //modify right sub-tree
                if( right_ )
                    right_->add(child);
                else {
                    right_ = child;
                    right_->parent_ = me_.lock();
                    if(left_) {
                        right_->sibling_ = left_;
                        left_->sibling_ = right_;
                    }
                }
            }
        }

        WNode me_; //wskaznik na ten sam wezel

        PNode parent_; //rodzic
        PNode left_; //element nastepny
        PNode right_; //element nasteny
        PNode sibling_; //element sasiedni
    };

public:
    Tree() {}
    ~Tree() {}

    void add(int value) {

        PNode node( new Node(value) );
        node->me_ = node;

        if( head_)
            head_->add(node);
        else
            head_ = node;
    }
private:
    PNode head_;
};


class TreeBetter {
    struct Node;
    using PNode = std::shared_ptr<Node>;
    using WNode = std::weak_ptr<Node>;
    using UNode = std::unique_ptr<Node>;

    struct Node {
        Node(int v) : value_(v) { cout << "C-tor " << value_ << endl; }
        ~Node() { cout << "D-tor " << value_ << endl; }
        int value_;

        void add(PNode child) {
            if(child->value_ < value_) {
                //modify left sub-tree
                if( left_ )
                    left_->add(child);
                else {
                    left_ = child;
                    left_->parent_ = me_;
                    if(right_) {
                        left_->sibling_ = right_;
                        right_->sibling_ = left_;
                    }

                }
            } else {
                //modify right sub-tree
                if( right_ )
                    right_->add(child);
                else {
                    right_ = child;
                    right_->parent_ = me_;
                    if(left_) {
                        right_->sibling_ = left_;
                        left_->sibling_ = right_;
                    }
                }
            }
        }

        WNode me_; //wskaznik na ten sam wezel


        WNode parent_; //rodzic
        PNode left_; //element nastepny
        PNode right_; //element nasteny
        WNode sibling_; //element sasiedni
    };

public:
    TreeBetter() {}
    ~TreeBetter() {}

    void add(int value) {

        PNode node( new Node(value) );
        node->me_ = node;

        if( head_)
            head_->add(node);
        else
            head_ = node;
    }
private:
    PNode head_;
};

/** jezeli zabronione jest istnienie wezla potomnego bez rodzica, to relacja rodzic->dziecko moze byc implemntowana przez unique_ptr, zas relacja dziecko->rodzic nie niesie informacji o wlasnosci */
class TreeEvenBetter {
        Node* parent_; //rodzic
        UNode left_; //element nastepny
        UNode right_; //element nasteny
        Node* sibling_; //element sasiedni
};

int main() {
    {
        Tree t1;
        t1.add(2);
        t1.add(1);
        t1.add(3);
        t1.add(4);
    }
    {
        TreeBetter t2;
        t2.add(12);
        t2.add(11);
        t2.add(13);
        t2.add(14);
    }
    return 0;
}