/**----------------------------------------------------------*
 * ZAD3                                                      *
 *                                                           *
 * 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 PWNode = std::weak_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();
                }
            } else {
                //modify right sub-tree
                if( right_ )
                    right_->add(child);
                else {
                    right_ = child;
                    right_->parent_ = me_.lock();
                }
            }
        }

        PWNode me_; //wskaznik na ten sam wezel

        PNode parent_; //rodzic
        PNode left_; //element nastepny
        PNode right_;
    };

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 PWNode = std::weak_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_;
                }
            } else {
                //modify right sub-tree
                if( right_ )
                    right_->add(child);
                else {
                    right_ = child;
                    right_->parent_ = me_;
                }
            }
        }

        PWNode me_; //wskaznik na ten sam wezel

        PWNode parent_; //rodzic
        PNode left_; //element nastepny
        PNode right_;
    };

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_;
};


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