#include <initializer_list>
#include <iostream>
#include <unordered_map>
#include <vector>

struct Node {
    int x, y;
    std::vector<Node *> children;

    Node() : x(0), y(0), children()
    {
    }
    Node(const std::initializer_list<Node *> &nodes)
        : x(0), y(0), children(nodes)
    {
    }
};

void
place(Node *n, int y, int x, std::unordered_map<int, int> &leftFront)
{
    if (x < 0) {
        x = 0;
    }
    if (leftFront.find(y) != leftFront.cend() && x <= leftFront[y]) {
        x = leftFront[y] + 1;
    }

    n->y = y;

    const int nchildren = n->children.size();
    const int width = nchildren + (1 - nchildren%2);
    int childX = x - width/2;
    int i = 0;
    Node *p; // previous child
    for (Node *c : n->children) {
        place(c, y + 1, childX, leftFront);

        childX = c->x;
        if (nchildren%2 == 0) {
            if (i == nchildren/2) {
                x = (c->x + p->x + 1)/2; // or (c->x + p->x)/2 to place root
                                         // closer to previous child
            }
            if (i == nchildren/2 - 1) {
                ++childX;
            }
        } else {
            if (i == nchildren/2) {
                x = childX;
            }
        }
        ++childX;
        ++i;

        p = c;
    }

    n->x = x;
    leftFront[y] = x;
}

void draw(Node *n, std::vector<std::string> &screen)
{
    screen[n->y].resize(n->x + 1, ' ');
    screen[n->y][n->x] = '*';
    for (Node *c : n->children) {
        draw(c, screen);
    }
}

void
doIt(const std::string &title, Node *root)
{
    std::cout << title << ':' << std::endl;

    std::unordered_map<int, int> leftFront;
    place(root, 0, 0, leftFront);

    std::vector<std::string> screen(5); // XXX: hardcoded
    draw(root, screen);

    for (const std::string &l : screen) {
        std::cout << l << std::endl;
    }
}

int
main(void)
{
    {
        Node n40;
        Node n30;
        Node n31 = { &n40 };
        Node n21 = { &n30, &n31 };
        Node n20;
        Node n12 = { &n21 };
        Node n11 = { &n20 };
        Node n10;
        Node n00 = { &n10, &n11, &n12 };
        doIt("original tree", &n00);
    }

    {
        Node n40;
        Node n30;
        Node n31 = { &n40 };
        Node n24 = { &n30, &n31 };
        Node n23;
        Node n22;
        Node n21;
        Node n20;
        Node n12 = { &n24 };
        Node n11 = { &n22, &n23 };
        Node n10 = { &n20, &n21 };
        Node n00 = { &n10, &n11, &n12 };
        doIt("more complicated tree", &n00);
    }

    {
        Node n40;
        Node n30;
        Node n31 = { &n40 };
        Node n24 = { &n30, &n31 };
        Node n23;
        Node n22;
        Node n21;
        Node n20;
        Node n12 = { &n24 };
        Node n11 = { &n22, &n23 };
        Node n10 = { &n20, &n21 };
        Node n00 = { &n10, &n11 };
        doIt("perfect binary tree", &n00);
    }

    return 0;
}