#include "dsw.h"

#include <iostream>
#include <queue>

int main()
{
    auto one = std::make_unique<node<int>>(1);
    auto two = std::make_unique<node<int>>(2);
    auto thr = std::make_unique<node<int>>(3);
    auto fur = std::make_unique<node<int>>(4);
    auto fiv = std::make_unique<node<int>>(5);
    auto six = std::make_unique<node<int>>(6);
    auto sev = std::make_unique<node<int>>(7);
    auto egt = std::make_unique<node<int>>(8);

    /**      4
     *      / \
     *     /   \
     *    3     8
     *   /     /
     *  1     7
     *   \   /
     *    2 5
     *       \
     *        6
     */

    one->right = two.get();
    thr->left  = one.get();
    fur->left  = thr.get();
    fur->right = egt.get();
    egt->left  = sev.get();
    sev->left  = fiv.get();
    fiv->right = six.get();

    auto root = fur.get();
    rebalance(root);

    std::queue<decltype(root)> q;
    q.push(root);
    auto depth = 0;
    while (!q.empty()) {
        auto s = q.size();
        std::cout << "Depth [" << depth++ << "]: ";
        while (s--) {
            auto x = q.front();
            q.pop();
            std::cout << x->val << " ";
            if (x->left)  q.push(x->left);
            if (x->right) q.push(x->right);
        }
        std::cout << std::endl;
    }
}