#include <assert.h>
#include <stddef.h>
#include <string>

// Option
template<typename T>
struct Option {
    bool tag;
    T value;

    static Option<T> some(T value) {
        return Option {
            .tag = true,
            .value = value,
        };
    }

    static Option<T> none() {
        return Option {
            .tag = false,
        };
    }
};

template<typename T>
T option_unwrap(Option<T> self) {
    assert(self.tag);
    return self.value;
}

// Box
template<typename T>
struct Box {
    T *value;
};

template<typename T>
Box<T> box_new(T value) {
    return Box<T> {
        .value = new T(value),
    };
}

template<typename T>
void box_drop(Box<T> self) {
    delete self.value;
}

template<typename Self>
struct Display {
    void (*fmt)(const Self *self, std::string *f);
};

// iterate on previous program
namespace iota {
    // SimpleIterator
    template<typename T, typename I>
    struct Peekable;

    template<typename Self, typename Item>
    Peekable<Self, Item> peekable_default(Self self);

    template<typename Self, typename Item>
    struct SimpleIterator {
        Option<Item> (*next)(Self *self);
        Peekable<Self, Item> (*peekable)(Self self) = peekable_default<Self, Item>;
    };

    // Peekable
    template<typename T, typename I>
    struct Peekable {
        T iter;
        Option<I> peeked;

        static SimpleIterator<Peekable<T, I>, I> simple_iterator_impl;
    };

    template<typename Self, typename Item>
    Peekable<Self, Item> peekable_default(Self self) {
        return Peekable<Self, Item> {
            .iter = self,
            .peeked = Option<Item>::none(),
        };
    }

    template<typename I, typename T>
    Option<I> peekable_peek(Peekable<T, I> *self) {
        if (!self->peeked.tag) {
            self->peeked = T::simple_iterator_impl.next(&self->iter);
        }
        return self->peeked;
    }

    template<typename I, typename T>
    Option<I> peekable_next(Peekable<T, I> *self) {
        if (self->peeked.tag) {
            const auto tmp = self->peeked;
            self->peeked = Option<I>::none();
            return tmp;
        } else return T::simple_iterator_impl.next(&self->iter);
    }

    template<typename T, typename I>
    SimpleIterator<Peekable<T, I>, I> Peekable<T, I>::simple_iterator_impl = {
        .next = peekable_next,
    };

    // Iota
    struct Iota {
        size_t field0;

        static SimpleIterator<Iota, size_t> simple_iterator_impl;
    };
    
    Iota iota_new() {
        return Iota {
            .field0 = 0,
        };
    }

    Option<size_t> iota_next(Iota *self) {
        const auto prev = self->field0;
        self->field0 = prev + 1;
        return Option<size_t>::some(prev);
    }

    SimpleIterator<Iota, size_t> Iota::simple_iterator_impl = {
        .next = iota_next,
    };
}

namespace peano {
    struct Nat;
    Nat nat_add(Nat self, Nat rhs);

    /// Peano Natural Number
    struct Nat {
        enum {
            Zero,
            Succ,
        } tag;
        Box<Nat> field0;

        static Nat zero() {
            return Nat {
                .tag = Zero,
            };
        }

        static Nat succ(Box<Nat> field0) {
            return Nat {
                .tag = Succ,
                .field0 = field0,
            };
        }

        Nat operator+(Nat rhs) {
            return nat_add(*this, rhs);
        }
    };

    Nat nat_one() {
        return Nat::succ(box_new(Nat::zero()));
    }

    void nat_drop(Nat self) {
        if (self.tag == Nat::Succ) {
            nat_drop(*self.field0.value);
            box_drop(self.field0);
        }
    }

    Nat nat_add(Nat self, Nat rhs) {
        if (self.tag == Nat::Zero) {
            nat_drop(self);
            return rhs;
        } else {
            return Nat::succ(box_new(nat_add(*self.field0.value, rhs)));
        }
    }

    size_t from_nat(Nat value) {
        if (value.tag == Nat::Zero) {
            return 0;
        } else {
            return from_nat(*value.field0.value) + 1;
        }
    }

    Nat into_nat(size_t value) {
        if (value == 0) {
            return Nat::zero();
        } else {
            return Nat::succ(box_new(into_nat(value - 1)));
        }
    }
}

namespace bin_tree {
    template<typename D>
    struct Node;

    template<typename D>
    void node_drop(Node<D> self);
    
    /// Self-Balancing Binary Tree with 0, 1 or 2 children per nodes
    template<typename D>
    struct BinTree {
        enum {
            Leaf,
            Left,
            LeftRight,
        } tag;
        Box<Node<D>> left;
        Box<Node<D>> right;

        static BinTree<D> leaf() {
            return BinTree<D> {
                .tag = Leaf,
            };
        }

        static BinTree<D> left_(Box<Node<D>> left) {
            return BinTree<D> {
                .tag = Left,
                .left = left,
            };
        }

        static BinTree<D> left_right(Box<Node<D>> left, Box<Node<D>> right) {
            return BinTree<D> {
                .tag = LeftRight,
                .left = left,
                .right = right,
            };
        }
    };

    template<typename D>
    void bin_tree_drop(BinTree<D> self) {
        if (self.tag != BinTree<D>::Leaf) {
            node_drop(*self.left.value);
            box_drop(self.left);
        }
        if (self.tag == BinTree<D>::LeftRight) {
            node_drop(*self.right.value);
            box_drop(self.right);
        }
    }

    template<typename D>
    struct Node {
        D data;
        BinTree<D> shape;

        static Display<Node<D>> display_impl;
    };

    template<typename D>
    void node_fmt(const Node<D> *self, std::string *f) {
        *f += std::to_string(self->data);
        *f += ":";
        if (self->shape.tag == BinTree<D>::Leaf) *f += "()";
        else if (self->shape.tag == BinTree<D>::Left) {
            *f += "( ";
            node_fmt(self->shape.left.value, f);
            *f += " )";
        } else if (self->shape.tag == BinTree<D>::LeftRight) {
            *f += "( ";
            node_fmt(self->shape.left.value, f);
            *f += ", ";
            node_fmt(self->shape.right.value, f);
            *f += " )";
        }
    }

    template<typename D>
    Display<Node<D>> Node<D>::display_impl = {
        .fmt = node_fmt<D>,
    };

    template<typename D>
    Node<D> node_root(D data) {
        return Node<D> {
            .data = data,
            .shape = BinTree<D>::leaf(),
        };
    }

    template<typename D>
    void node_drop(Node<D> self) {
        bin_tree_drop(self.shape);
    }

    template<typename D, typename N>
    N node_weight(const Node<D> *self) {
        using namespace peano;

        auto subtree = Nat::zero();
        if (self->shape.tag != BinTree<D>::Leaf) subtree = into_nat(node_weight<D, N>(self->shape.left.value));
        if (self->shape.tag == BinTree<D>::LeftRight) subtree = subtree + into_nat(node_weight<D, N>(self->shape.right.value));
        const auto nat = /*this node*/nat_one() + subtree;
        return from_nat(nat);
    }

    template<typename D>
    Node<D> node_add(Node<D> self, Node<D> rhs) {
        const auto data = self.data;
        const auto shape = self.shape;

        BinTree<D> new_shape;
        if (shape.tag == BinTree<D>::Leaf) new_shape = BinTree<D>::left_(box_new(rhs));
        else if (shape.tag == BinTree<D>::Left) {
            new_shape = BinTree<D>::left_right(shape.left, box_new(rhs));
        } else if (shape.tag == BinTree<D>::LeftRight && node_weight<D, size_t>(shape.left.value) < node_weight<D, size_t>(shape.right.value)) {
            new_shape = BinTree<D>::left_right(box_new(node_add(*shape.left.value, rhs)), shape.right);
        } else if (shape.tag == BinTree<D>::LeftRight) {
            new_shape = BinTree<D>::left_right(shape.left, box_new(node_add(*shape.right.value, rhs)));
        }

        return Node<D> {
            .data = data,
            .shape = new_shape,
        };
    }
}

#include <iostream>
int main() {
    {
        auto iota = iota::iota_new();
        assert(option_unwrap(iota::iota_next(&iota)) == 0);
        assert(option_unwrap(iota::iota_next(&iota)) == 1);
        assert(option_unwrap(iota::iota_next(&iota)) == 2);
        assert(option_unwrap(iota::iota_next(&iota)) == 3);
    
        auto peekable_iota = iota::Iota::simple_iterator_impl.peekable(iota);
        assert(option_unwrap(iota::peekable_peek(&peekable_iota)) == 4);
        assert(option_unwrap(iota::peekable_peek(&peekable_iota)) == 4);
        assert(option_unwrap(iota::peekable_peek(&peekable_iota)) == 4);

        assert(option_unwrap(iota::peekable_next(&peekable_iota)) == 4);
        assert(option_unwrap(iota::peekable_next(&peekable_iota)) == 5);
        assert(option_unwrap(iota::peekable_next(&peekable_iota)) == 6);
    }

    auto iota = iota::iota_new();
    auto b = bin_tree::node_root(option_unwrap(iota::iota_next(&iota)));
    for (size_t i = 0; i < 100; i++) {
        const auto new_ = bin_tree::node_root(option_unwrap(iota::iota_next(&iota)));
        b = bin_tree::node_add(b, new_);
    }

    std::string f;
    bin_tree::Node<size_t>::display_impl.fmt(&b, &f);
    // std::cout << f;
    assert(f == "0:( 1:( 4:( 10:( 22:( 46:( 94:() ), 62:( 78:() ) ), 30:( 38:( 86:() ), 54:( 70:() ) ) ), 14:( 18:( 42:( 90:() ), 58:( 74:() ) ), 26:( 34:( 82:() ), 50:( 66:(), 98:() ) ) ) ), 6:( 8:( 20:( 44:( 92:() ), 60:( 76:() ) ), 28:( 36:( 84:() ), 52:( 68:(), 100:() ) ) ), 12:( 16:( 40:( 88:() ), 56:( 72:() ) ), 24:( 32:( 80:() ), 48:( 64:(), 96:() ) ) ) ) ), 2:( 3:( 9:( 21:( 45:( 93:() ), 61:( 77:() ) ), 29:( 37:( 85:() ), 53:( 69:() ) ) ), 13:( 17:( 41:( 89:() ), 57:( 73:() ) ), 25:( 33:( 81:() ), 49:( 65:(), 97:() ) ) ) ), 5:( 7:( 19:( 43:( 91:() ), 59:( 75:() ) ), 27:( 35:( 83:() ), 51:( 67:(), 99:() ) ) ), 11:( 15:( 39:( 87:() ), 55:( 71:() ) ), 23:( 31:( 79:() ), 47:( 63:(), 95:() ) ) ) ) ) )");

    bin_tree::node_drop(b);
    return 0;
}