Mais um blog inútil.

Ora viva!

Desde a minha última submissão, tem havido vasto progresso no estado da arte da Arvorezinha. Foi lançado um novo standard, e tem havido um renovado interesse em criar arvorezinhas cada vez mais obscuras e intricadas.

Isto traz-nos a este post. Um dos problemas fundamentais com as arvorezinhas anteriores em templates de C++ era que cada caracter era impresso de cada vez. Era muito mais interessante se pudéssemos gerar a string completa da arvorezinha durante a compilação, após o qual imprimir seria apenas uma questão de enviar a string para a função adequada (printf, cout, etc). Uma das novidades no novo standard de C++, oficializado o ano passado, são os variadic templates. Estes são uma versão em templates das funções com número de argumentos variável, como já existiam em C(++) e no pré-processador de C, que nos permite "construir" uma string caracter a caracter, e despejá-la numa initializer list quando acabamos.

Para simplificar a apresentação, desacoplei a lógica da arvorezinha da lógica que constrói a string, para ser mais fácil compreender a implementação. Também incluí uma versão não variádica opcional, caso não estejam satisfeitos.

#include <cstdio>

struct NullType {};
 
template<size_t N>
struct Arvorezinha2
{
    static const size_t NC = 2*N * (N + N/2);

    template<bool B, size_t L, size_t C> struct Pedaco;

    template<size_t L, size_t C>
    struct Pedaco<true, L, C> // Arvore
    {

        template<bool B, typename D>
        struct Ramo
        {
            static const char value = ' ';
        };              

        template<typename D>
        struct Ramo<true, D>
        {
            static const char value = '*';
        };

        static const size_t len = N*2 - 1;
        static const size_t beg = N-(L+1);
        static const size_t end = 2*(L+1)-1;
        static const char value = Ramo<C >= beg && C < beg + end, NullType>::value;
    };

    template<size_t L, size_t C>
    struct Pedaco<false, L, C> // Tronco
    {
        template<bool B, typename D>
        struct Lenha
        {
            static const char value = ' ';
        };

        template<typename D>
        struct Lenha<true,D>
        {
            static const char value = '#';
        };

        static const size_t len = N*2 - 1;
        static const size_t beg = len/4 - N%2 + 1;
        static const size_t end = len/2 - !(N%2);
        static const char value = Lenha<C >= beg && C <= beg + end, NullType>::value;
    };

    template<size_t L>
    struct Pedaco<true, L, 2*N-1>
    {
        static const char value = '\n';
    };

    template<size_t L>
    struct Pedaco<false, L, 2*N-1>
    {
        static const char value = '\n';
    };


    template<size_t X>
    struct Arvorezinha
    {
        static const size_t L = X / (2*N);
        static const size_t C = X % (2*N);
        static const char value = Pedaco<L < N, L, C>::value;
    };

    template<size_t I>
    struct AT
    {
        static const char value = Arvorezinha<I>::value;
    };    
};

template<template<size_t> class T, size_t N, bool V/*ariadic*/ = true>
struct Desenhar
{
    template<char... Str>
    static inline const char (&str())[sizeof...(Str)+1]
    {
        static const char value[sizeof...(Str)+1] = {Str..., 0};
        return value;
    }

    template<size_t I, typename D, char...Str>
    struct StringBuilder
    {
        static inline const char *toStr()
        {
            return StringBuilder<I+1, D, Str..., T<N>::template AT<I>::value>::toStr();
        }
    };

    template<typename D, char...Str>
    struct StringBuilder<T<N>::NC, D, Str...>
    {
        static inline const char *toStr()
        {
            return str<Str...>();
        }
    };

    static inline const char *toString()
    {
        return StringBuilder<0,NullType>::toStr();
    }

    static inline void desenhar()
    {
        puts(toString());
    }

};

template<template<size_t> class T, size_t N>
struct Desenhar<T, N, false>
{
    template<size_t i, typename D/*ummy*/>
    struct Rec
    {
        static inline void desenhar()
        {
            Rec<i-1,D>::desenhar();
            putchar(T<N>::template AT<i>::value);
        }
    };
 
    template<typename D>
    struct Rec<0,D>
    {
        static inline void desenhar()
        {
            putchar(T<N>::template AT<0>::value);
        }
    };
 
    static inline void desenhar()
    {
        Rec<T<N>::NC-1, NullType>::desenhar();
    }
};

int main(int argc, char **argv)
{
    Desenhar<Arvorezinha2, 5/*, true*/>::desenhar();
    return 0;
}

O resultado da compilação é essencialmente óptimo: o programa resume-me a carregar o endereço de uma string, e chamar a função puts:

0000000000400430 <main>:
  400430:	48 83 ec 08          	sub    $0x8,%rsp
  400434:	bf 40 06 40 00       	mov    $0x400640,%edi
  400439:	e8 d2 ff ff ff       	callq  400410 <puts@plt>
  40043e:	31 c0                	xor    %eax,%eax
  400440:	48 83 c4 08          	add    $0x8,%rsp
  400444:	c3                   	retq   
  400445:	90                   	nop
  400446:	90                   	nop
  400447:	90                   	nop

Bem haja!