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!
