Деревья типов в C++

Зачитался я тут книгой Александреску «Современное проектирование на С++: Обобщенное программирование и прикладные шаблоны проектирования».


Познакомившись со списками типов и алгоритмами для работы с ними, понял, что списки типов по Александреску совсем никакие не списки, а бинарные деревья типов. После чего я решил закрепить материал и запрограммировать какой-нибудь простой алгоритм на деревьях типов, например, поиск в глубину.

Итак, деревья типов отличаются от списков типов только названием:

template <class T, class U>
struct TypeTree
{
 typedef T Left;
 typedef U Right;
};

Чтобы было понятнее приведу пример:

TypeTree<TypeTree<int, double>, TypeTree<float, TypeTree<char, long> > >

На картинке это буде выглядеть примерно так:

Заодно будем нумеровать узлы так, что если родитель имеет номер n, то левый потомок имеет номер 2*n, а правый --- 2*n + 1. Корневая вершина имеет номер 1.

Теперь об алгоритме поиска типа в дереве типов. Если в дереве типов нет искомого типа, то результатом будет 0, иначе номер искомого типа.

Шаблонный класс DFS в качестве шаблонных параметров принимает дерево типов и искомый тип. Код алгоритма:

template <class TTree, class T> struct DFS;

// Дерево состоит из одной вершины, которая соответствует искомому типу
template <class T>
struct DFS<T, T>
{
 enum { value = 1 };
};

// Дерево состоит из одной вершины, которая не соответствует искомому типу
template <class T, class U>
struct DFS
{
 enum { value = 0 };
};

// Дерево со многими вершинами
template <class Left, class Right, class T>
struct DFS<TypeTree<Left, Right>, T>
{
 // Запускаем алгоритм поиска в глубину для левой и правой веток
 enum { value = DFS_<Left, T, 2>::value + DFS_<Right, T, 3>::value };
};

Класс DFS_ имеет три шаблонных параметра --- два как у класса DFS и целое без знака. Целое число показывает какую вершину мы рассматриваем в данный момент. Код:

template <class TTree, class T, unsigned int i> struct DFS_;

// Листовая вершина с искомым типом
template <class T, unsigned int i>
struct DFS_<T, T, i>
{
 enum { value = i };
};

// Листовая вершина с типом отличным от искомого
template <class U, class T, unsigned int i>
struct DFS_
{
 enum { value = 0 };
};

// Не листовая вершина
template <class Left, class Right, class T, unsigned int i>
struct DFS_<TypeTree<Left, Right>, T, i>
{
 enum { value = DFS_<Left, T, 2*i>::value + DFS_<Right, T, 2*i + 1>::value };
};

Код, написанный ниже, напечатает на экране число 14.

std::cout << DFS<
  TypeTree<TypeTree<int, double>, TypeTree<float, TypeTree<char, long> > >,
  char
 >::value << std::endl;

Вот и все. :)

Из недостатков можно отметить:

1. Будет не очень информативный результат, если в дереве есть два одинаковых типа.
2. Не обрабатывается NullType, который мог бы быть индикатором «сухих листьев» (отсутствующих братьев).