#include <iostream>
#include <string>

#include <boost/timer.hpp>

#include <origin/utility/typestr.hpp>

// #include <origin/trees/nary_tree.hpp>
#include <origin/trees/nary_tree/node.hpp>
#include <origin/trees/preorder.hpp>

// NOTE: find() outperforms anchors for N == 2, 3 in release mode.

using std::cout;
using std::cin;
using namespace origin;
using namespace origin::trees;

int nodes = 0;

// Construct two nodes for the given root and recurse. If this function is
// called as build(x, n), and x has arity a, then this will construct a
// tree with the number of nodes given by the geometric series:
// sum(0, n, pow(i, a))
// where i is the loop variable.
template <typename Node>
void build(Node* root, int n) {
    if(n == 0) return;
    for(std::size_t i = 0; i < root->arity(); ++i) {
        Node* p = new Node(nodes + 1 + i);
        root->attach_child(p, i);
    }
    nodes += root->arity();
    for(std::size_t i = 0; i < root->arity(); ++i) {
        build(root->child(i), n - 1);
    }
}

template <typename Node>
void destroy(Node* node) {
    if(node->is_leaf()) {
        return;
    }
    for(std::size_t i = 0; i < node->arity(); ++i) {
        delete node->child(i);
    }
}

template <typename Node>
void test() {
    Node n;

    nodes = 1;
    build(&n, 10);
    cout << "Built: " << nodes << "\n";

    int x = 0;
    boost::timer t;
//     std::clock_t start = std::clock();
    preorder_iterator<Node> i(&n), end;
    for(; i != end; ++i) {
        ++x;
//         cout << *i << "\n";
    }
//     std::clock_t finish = std::clock();
//     cout << "cycles: " << (finish - start) << "\n";
    cout << "time esapled? " << t.elapsed() << "\n";
    destroy(&n);
}

int main()
{
    using namespace nary_tree_;
    int const N = 5;
    typedef nary_tree_::node<int, N> BasicNode;
    typedef nary_tree_::node<int, N, anchored_link> AnchoredNode;

    test<BasicNode>();
    cout << "********************\n";
    test<AnchoredNode>();

    return 0;
}