Еще немного про деревья типов в C++

В продолжении заметки о деревьях типов реализуем обратный алгоритм (поиск типа по номеру в дереве).



Для начала опишу вспомогательные структуры, которые потребуются позже:

// Тип Null, обозначающий пустой ответ
class NullType;

// Проверка типа на равенство NullType
template <class T>
struct isNull
{
 enum { value = false };
};

template <>
struct isNull<NullType>
{
 enum { value = true };
};

// структура Select, описанная у Александреску
template<bool flag, class T, class U>
struct Select
{
 typedef T Result;
};

template<class T, class U>
struct Select<false, T, U>
{
 typedef U Result;
};

Алгоритм поиска типа по его номеру в дереве aDFS будет выдавать подходящий тип, если вершина с искомым номером есть в дереве, иначе NullType. Вот его реализация:

template <class TTree, unsigned int n, unsigned int i> struct aDFS_;

// Лист с подходящим номером
template <class T, unsigned int n>
struct aDFS_<T, n, n>
{
 typedef T Result;
};

// Лист с  неподходящим номером
template <class T, unsigned int n, unsigned int i>
struct aDFS_
{
 typedef NullType Result;
};

// Развилка с подходящим номером
template <class Left, class Right, unsigned int n>
struct aDFS_<TypeTree<Left, Right>, n, n>
{
 typedef TypeTree<Left, Right> Result;
};

// Развилка с неподходящим номером
template <class Left, class Right, unsigned int n, unsigned int i>
struct aDFS_<TypeTree<Left, Right>, n, i>
{
 private:
  typedef typename aDFS_<Left, n, 2*i>::Result Res1;
  typedef typename aDFS_<Right, n, 2*i + 1>::Result Res2;
 public:
  typedef typename Select<isNull<Res2>::value, Res1, Res2>::Result Result;
};

// TTree - дерево типов, n - номер искомой вершины
template <class TTree, unsigned int n>
struct aDFS
{
 typedef typename aDFS_<TTree, n, 1>::Result Result;
};

И наш любимый пример будет выглядеть так:

typedef
    TypeTree<TypeTree<int, double>, TypeTree<float, TypeTree<char, long> > >
    TestTree;

std::cout << isNull<aDFS<TestTree, 14>::Result>::value << std::endl;
std::cout << isNull<aDFS<TestTree, 144>::Result>::value << std::endl;

В консоли будет напечатаны 1 и 0.