//----------------------------------------------------------------------------
// pila.cc: ./pila --benchmark_time_unit=us
//----------------------------------------------------------------------------

#include <benchmark/benchmark.h>
#include <cstdlib>
#include <exception>
#include <functional>
#include <iostream>
#include <memory>
#include <optional>
#include <random>
#include <stack>

//----------------------------------------------------------------------------

const size_t N = 10'000;

//----------------------------------------------------------------------------

std::random_device device;
std::bernoulli_distribution distribution;
std::default_random_engine engine(device());
auto _01 = std::bind(distribution, engine);

//----------------------------------------------------------------------------

namespace pila_c
{
    struct nodo
    {
        int valor;
        nodo *siguiente;
    };

    typedef nodo *pila;

    void crear(pila *p) { *p = NULL; }

    int vacia(pila *p) { return *p == NULL; }
} // namespace pila_c

namespace pila_c_stack1
{
    using namespace pila_c;

    nodo *pop(pila *p)
    {
        nodo *viejo = *p;
        *p = (*p)->siguiente;
        return viejo;
    }

    void destruir(pila *p)
    {
        while (!vacia(p))
            pop(p);
    }

    void push(pila *p, nodo *n)
    {
        n->siguiente = *p;
        *p = n;
    }

    void test(benchmark::State &state)
    {
        pila p = NULL;
        nodo nodos[N];

        for (size_t i = 0; i < N; ++i)
            nodos[i].valor = i;

        for (auto _ : state)
        {
            crear(&p);

            for (size_t i = 0; i < N; ++i)
                if (_01())
                    push(&p, &nodos[i]);
                else if (!vacia(&p))
                    pop(&p);

            destruir(&p);
        }
    }
} // namespace pila_c_stack1

//----------------------------------------------------------------------------

namespace pila_c_stack2
{
    using namespace pila_c_stack1;

    void test(benchmark::State &state)
    {
        pila p = NULL;

        for (auto _ : state)
        {
            nodo nodos[N];

            for (size_t i = 0; i < N; ++i)
                nodos[i].valor = i;

            crear(&p);

            for (size_t i = 0; i < N; ++i)
                if (_01())
                    push(&p, &nodos[i]);
                else if (!vacia(&p))
                    pop(&p);

            destruir(&p);
        }
    }
} // namespace pila_c_stack2

//----------------------------------------------------------------------------

namespace pila_c_heap
{
    using namespace pila_c;

    int pop(pila *p)
    {
        nodo *n = *p;
        int i = (*p)->valor;
        *p = (*p)->siguiente;
        free(n);
        return i;
    }

    void destruir(pila *p)
    {
        while (!vacia(p))
            pila_c_heap::pop(p);
    }

    void push(pila *p, int i)
    {
        nodo *n = (nodo *)malloc(sizeof(nodo));
        assert(n != NULL);
        n->valor = i;
        n->siguiente = *p;
        *p = n;
    }

    void test(benchmark::State &state)
    {
        pila p = NULL;

        for (auto _ : state)
        {
            crear(&p);

            for (size_t i = 0; i < N; ++i)
                if (_01())
                    pila_c_heap::push(&p, i);
                else if (!vacia(&p))
                    pila_c_heap::pop(&p);

            pila_c_heap::destruir(&p);
        }
    }
} // namespace pila_c_heap

//----------------------------------------------------------------------------

namespace pila_cc_stack1
{
    template<class T> class pila {
    public:
        struct nodo
        {
            T valor;
            nodo *siguiente;
        };

        pila() : tope(nullptr) {}

        void push(nodo &nuevo)
        {
            nuevo.siguiente = tope;
            tope = &nuevo;
        }

        nodo &pop()
        {
            nodo *n = tope;
            tope = tope->siguiente;
            return *n;
        }

        bool vacia() { return tope == nullptr; }

    private:
        nodo *tope;
    };

    void test(benchmark::State &state)
    {
        pila<int>::nodo nodos[N];

        for (size_t i = 0; i < N; ++i)
            nodos[i].valor = i;

        for (auto _ : state)
        {
            pila<int> p;

            for (size_t i = 0; i < N; ++i)
                if (_01())
                    p.push(nodos[i]);
                else if (!p.vacia())
                    p.pop();
        }
    }
} // namespace pila_cc_stack1

//----------------------------------------------------------------------------

namespace pila_cc_stack2
{
    using namespace pila_cc_stack1;

    void test(benchmark::State &state)
    {
        for (auto _ : state)
        {
            pila<int>::nodo nodos[N];

            for (size_t i = 0; i < N; ++i)
                nodos[i].valor = i;

            pila<int> p;

            for (size_t i = 0; i < N; ++i)
                if (_01())
                    p.push(nodos[i]);
                else if (!p.vacia())
                    p.pop();
        }
    }
} // namespace pila_cc_stack2

//----------------------------------------------------------------------------

namespace pila_cc_heap
{
    template<class T> class pila {
    public:
        pila() : tope(nullptr) {}

        ~pila()
        {
            while (!vacia())
                pop();
        }

        void push(const T &nuevo) { tope = new nodo{nuevo, tope}; }

        T pop()
        {
            nodo n = *tope;
            delete tope;
            tope = n.siguiente;
            return n.valor;
        }

        bool vacia() { return tope == nullptr; }

    private:
        struct nodo
        {
            T valor;
            nodo *siguiente;
        };

        nodo *tope;
    };

    void test(benchmark::State &state)
    {
        for (auto _ : state)
        {
            pila<int> p;

            for (size_t i = 0; i < N; ++i)
                if (_01())
                    p.push(i);
                else if (!p.vacia())
                    p.pop();
        }
    }
} // namespace pila_cc_heap

//----------------------------------------------------------------------------

namespace pila_unique_ptr
{
    template<class T> class pila {
    public:
        ~pila()
        {
            while (!vacia())
                pop();
        }

        void push(const T &nuevo)
        {
            tope =
                std::move(std::make_unique<nodo>(nodo{nuevo, std::move(tope)}));
        }

        T pop()
        {
            T valor = tope->valor;
            tope = std::move(tope->siguiente);
            return valor;
        }

        bool vacia() { return !tope; }

    private:
        struct nodo
        {
            T valor;
            std::unique_ptr<nodo> siguiente;
        };

        std::unique_ptr<nodo> tope;
    };

    void test(benchmark::State &state)
    {
        for (auto _ : state)
        {
            pila<int> p;

            for (size_t i = 0; i < N; ++i)
                if (_01())
                    p.push(i);
                else if (!p.vacia())
                    p.pop();
        }
    }
} // namespace pila_unique_ptr

//----------------------------------------------------------------------------

namespace pila_exceptions
{
    template<class T> class pila {
    public:
        using empty = std::exception;

        ~pila()
        {
            try
            {
                while (true)
                    pop();
            }
            catch (...)
            {
            }
        }

        void push(const T &nuevo)
        {
            tope =
                std::move(std::make_unique<nodo>(nodo{nuevo, std::move(tope)}));
        }

        T pop()
        {
            if (tope)
            {
                T valor = tope->valor;
                tope = std::move(tope->siguiente);
                return valor;
            }
            throw empty();
        }

    private:
        struct nodo
        {
            T valor;
            std::unique_ptr<nodo> siguiente;
        };

        std::unique_ptr<nodo> tope;
    };

    void test(benchmark::State &state)
    {
        for (auto _ : state)
        {
            pila<int> p;

            for (size_t i = 0; i < N; ++i)
                if (_01())
                    p.push(i);
                else
                {
                    try
                    {
                        p.pop();
                    }
                    catch (const pila<int>::empty &)
                    {
                    };
                }
        }
    }
} // namespace pila_exceptions

//----------------------------------------------------------------------------

namespace pila_optional
{
    template<class T> class pila {
    public:
        ~pila()
        {
            while (pop())
                ;
        }

        void push(const T &nuevo)
        {
            tope =
                std::move(std::make_unique<nodo>(nodo{nuevo, std::move(tope)}));
        }

        std::optional<T> pop()
        {
            if (tope)
            {
                T valor = tope->valor;
                tope = std::move(tope->siguiente);
                return {std::move(valor)};
            } else
            {
                return {};
            }
        }

    private:
        struct nodo
        {
            T valor;
            std::unique_ptr<nodo> siguiente;
        };

        std::unique_ptr<nodo> tope;
    };

    void test(benchmark::State &state)
    {
        for (auto _ : state)
        {
            pila<int> p;

            for (size_t i = 0; i < N; ++i)
                if (_01())
                    p.push(i);
                else
                    p.pop();
        }
    }
} // namespace pila_optional

//----------------------------------------------------------------------------

namespace pila_std_stack
{
    void test(benchmark::State &state)
    {
        for (auto _ : state)
        {
            std::stack<int> s;

            for (size_t i = 0; i < N; ++i)
                if (_01())
                    s.push(i);
                else if (!s.empty())
                    s.pop();
        }
    }
} // namespace pila_std_stack

//----------------------------------------------------------------------------

BENCHMARK(pila_c_stack1::test);
BENCHMARK(pila_c_stack2::test);
BENCHMARK(pila_c_heap::test);
BENCHMARK(pila_cc_stack1::test);
BENCHMARK(pila_cc_stack2::test);
BENCHMARK(pila_cc_heap::test);
BENCHMARK(pila_unique_ptr::test);
BENCHMARK(pila_exceptions::test);
BENCHMARK(pila_optional::test);
BENCHMARK(pila_std_stack::test);

//----------------------------------------------------------------------------

BENCHMARK_MAIN();

//----------------------------------------------------------------------------