#include <iostream>

#include <origin/trees/tree.hpp>
#include <origin/trees/preorder.hpp>
#include <origin/trees/postorder.hpp>

using namespace std;
using namespace origin;
using namespace origin::trees;

typedef pair<int, int> Link;
static Link links[] = {
    {0, 1}, {0, 2},
    {1, 3}, {1, 4},
    {2, 5},
    {4, 6}, {4, 7},
    {5, 8}
};
static size_t const nlinks = sizeof(links) / sizeof(Link);

int main() {
    typedef tree_::node<int> Node;

    // Initialize some nodes.
    Node nodes[10];
    for(size_t i = 0; i < 10; ++i) {
        nodes[i].put(i);
    }

    // Construct the tree above.
    for(Link* p = links; p != links + nlinks; ++p) {
        nodes[p->first].append_child(&nodes[p->second]);
    }

    {
        typedef preorder_iterator<Node> Preorder;
        Preorder end;
        cout << "fwd pre: ";
        for(Preorder i(&nodes[1]); i != end; ++i) {
            cout << *i << " ";
        }
        cout << "\n";
        cout << "rev pre: ";
        for(Preorder i(&nodes[1], &nodes[7]); i != end; --i) {
            cout << *i << " ";
        }
        cout << "\n";
    }

    {
        typedef postorder_iterator<Node> Iter;
        Iter end;
        cout << "fwd post: ";
        for(Iter i(&nodes[1]); i != end; ++i) {
            cout << *i << " ";
        }
        cout << "\n";
        cout << "rev post: ";
        for(Iter i(&nodes[1], &nodes[7]); i != end; --i) {
            cout << *i << " ";
        }
        cout << "\n";
    }
}