TypeList и Крестики-нолики

namespace internal { struct Void { }; } // internal  template<typename ...Args> struct TypeList {     typedef internal::Void Head;     typedef internal::Void Tail; };  typedef TypeList<> EmptyTypeList;  template<typename H, typename ...T> struct TypeList<H, T...> {     typedef H Head;     typedef TypeList<T...> Tail; }; 

Типичный TypeList представляет собой «голову»(Head) и «хвост»(Tail), который в свою очередь также является списком типов. Использование:

typedef TypeList<float, double, long double> floating_point_types; 

Раньше, без С++11, это выглядело так:

template <class H, class T> struct typelist {     typedef H head;     typedef T tail; };  typedef typelist<float, typelist<double, long double> > floating_point_types; 

#define TYPELIST_1(T1) typelist<T1, null_typelist> #define TYPELIST_2(T1, T2) typelist<T1, TYPELIST_1(T2) > #define TYPELIST_3(T1, T2, T3) typelist<T1, TYPELIST_2(T2, T3) > ... #define TYPELIST_50... 

Но теперь, благодаря variadic templates, можно избавиться и от макросов, и от ограничения на количество типов в списке.
Собственно говоря интересным является то, как работать со списком типов, как определить операции над ним и что это даёт в конечном итоге(кому интересно более детальное описание и кто ещё не видел Modern C++ Design — советую почитать — не важно, что это 2001 год!).
Итак, как видно, я определил вспомогательный тип internal::Void, который будет работать, как сигнальный флажок и говорить, что список типов пуст(как минимум, для случая, когда пользователь не указал ничего: TypeList<>, или, когда со списка удалено все элементы). Начнём с начала:

IsEmpty

template<typename TL> struct IsEmpty :     std::true_type { };  template<> struct IsEmpty<TypeList<internal::Void, internal::Void>> :     std::true_type { };  template<typename ...Args> struct IsEmpty<TypeList<Args...>> :     std::integral_constant<bool,         std::is_same<typename TypeList<Args...>::Head, internal::Void>::value &&         IsEmpty<typename TypeList<Args...>::Tail>::value> { }; 

Здесь видно почти всё, что нам нужно, для определения других операций. Как видно, сначала мы определяем «костяк»: тип IsEmpty параметризован одним типом. По сути, это «функция», принимающая один аргумент. Поскольку тип TL означает — «любой тип», мы делаем полную специализацию шаблона для случая с пустым списком: TypeList<internal::Void, internal::Void>(можно было бы и просто TypeList<> или, как раз для этого, я определил тип EmptyTypeList) и частичную специализацию, которая работает — «для любого списка типов». Таким образом, наша «функция» определена только для списка типов. В новом стандарте появились такие удобные штуки, как std::integral_constant, которые очень сильно упрощают жизнь: в случае с struct IsEmpty : std::true_type, IsEmpty имеет член класса value, ряд typedef-ов и оператор преобразования в bool.
Как это использовать ?:

typedef TypeList<int> TL1; std::cout << std::boolalpha << IsEmpty<TL1>::value << " " << IsEmpty<EmptyTypeList>() << std::endl; 

Пустой ли список мы имеем определяет следующее выражение:

std::is_same<typename TypeList<Args...>::Head, internal::Void>::value && IsEmpty<typename TypeList<Args...>::Tail>::value 

дословно — «список пуст, если его голова — это вспомогательный тип, обозначающий void И если его хвост также является пустым списком». Как видно, здесь используется рекурсия, которую, как раз и останавливает, полная специализация шаблона для пустого списка.
Дальше:

Contains

template<typename T, typename TL> struct Contains :     std::false_type { };  template<typename ...Args> struct Contains<internal::Void, Args...> :     std::false_type { };  template<typename T, typename ...Args> struct Contains<T, TypeList<Args...>> :     std::integral_constant<bool,         std::is_same<typename TypeList<Args...>::Head, T>::value ||         Contains<T, typename TypeList<Args...>::Tail>::value         > { }; 

Contains определяет есть ли указанный тип T внутри списка типов TL. Использование:

Использование:

typedef TypeList<double, float, float, double, int, char, char, int, char> TL; std::cout << std::boolalpha << Contains<char, TL>::value << " " << Contains<float, TypeList<double>>() << std::endl; 

Снова же: «если голова списка это наш тип T, то T есть внутри списка, а иначе — посмотреть, есть ли T в хвосте списка».
Частичная специализация — мере предосторожности — а вдруг кто-то воспользуется нашим типом internal::Void?

Length

template<typename TL> struct Length :     std::integral_constant<unsigned int, 0> { };  template<typename ...Args> struct Length<TypeList<Args...>> :     std::integral_constant<unsigned int,         IsEmpty<TypeList<Args...>>::value             ? 0             : 1 + Length<typename TypeList<Args...>::Tail>::value> { }; 

Если список пуст — длина нулевая, а иначе — это единица(потому что присутствует «голова»(Head)) + длина хвоста:

typedef TypeList<double, float, float, double, int, char, char, int, char> TL; std::cout << Length<TL>::value << " " << Length<EmptyTypeList>() << std::endl; 

TypeAt

template<unsigned int N, typename TL> struct TypeAt {     typedef internal::Void type; }; 

— возвращает тип по индексу, почти, как массив. Реализация — первый заход(меняем тип N на int):

//template<int N, typename ...Args> //struct TypeAt<N, TypeList<Args...>> //{     //    typedef typename std::conditional<N == 0, //        typename TypeList<Args...>::Head, //        typename TypeAt<N - 1, typename TypeList<Args...>::Tail>::type>::type type; //}; 

— всё будет прекрасно работать, но! — хотелось бы быть предупреждённым, если указан слишком большой индекс. Можно бы было выкрутиться и с текущей реализацией, но здесь нужно учитывать то, что шаблон должен быть корректно инстанцирован для случая N=-1. Поэтому идём другим путём:

template<typename ...Args> struct TypeAt<0, TypeList<Args...>> {     typedef typename TypeList<Args...>::Head type; };  template<unsigned int N, typename ...Args> struct TypeAt<N, TypeList<Args...>> {     static_assert(N < Length<TypeList<Args...>>::value, "N is too big");          typedef typename TypeAt<N - 1, typename TypeList<Args...>::Tail>::type type; }; 

— голова имеет нулевой индекс, а для других случаев — будем одновременно уменьшать индекс на единицу и «съедать» кусочек хвоста(передвигаемся слева на право), пока не сможем отнять — индекс нулевой, а текущая голова и есть нужный нам тип! Использование:

typedef TypeList<char, short> TL2; static_assert(std::is_same<TypeAt<1, TL2>::type, short>::value, "Something wrong!"); 

Вывод списка

// Пустой список std::ostream& operator<<(std::ostream& ostr, EmptyTypeList) { 	ostr << "{}"; 	return ostr; }  template<typename TL> void PrintTypeListHelper(TL, std::ostream& ostr) { }  template<typename T> void PrintTypeListHead(T, std::ostream& ostr) { 	ostr << typeid(T).name(); }  template<typename ...Args> void PrintTypeListHead(TypeList<Args...> tl, std::ostream& ostr) { 	ostr << tl; }  template<typename Head, typename ...Args> void PrintTypeListHelper(TypeList<Head, Args...>, std::ostream& ostr) { 	PrintTypeListHead(Head(), ostr); 	if(!IsEmpty<TypeList<Args...>>::value) 	{ 		ostr << ' '; 		PrintTypeListHelper<Args...>(TypeList<Args...>(), ostr); 	} }  template<typename ...Args> std::ostream& operator<<(std::ostream& ostr, TypeList<Args...> tl) { 	ostr << '{'; 	PrintTypeListHelper(tl, ostr); 	ostr << '}'; 	return ostr; } 

Эти функции помогают аккуратно вывести обычные списки типов и вложенные, например:

typedef TypeList<double, float, float, double, int, char, char, int, char> TL; std::cout << TL() << std::endl;  typedef TypeList<TL2, double, TL2> TL10; std::cout << TL10() << std::endl; 

{double float float double int char char int char}
{{char short} double {char short}}

Append и Add

 template<typename TOrTL2, typename TL> struct Append { };  template<typename T, typename ...Args> struct Append<T, TypeList<Args...>> {     typedef TypeList<Args..., T> type; };  template<typename ...Args1, typename ...Args2> struct Append<TypeList<Args1...>, TypeList<Args2...>> {     typedef TypeList<Args2..., Args1...> type; };  template<typename T, typename TL> struct Add { };  template<typename T, typename ...Args> struct Add<T, TypeList<Args...>> { 	typedef TypeList<Args..., T> type; }; 

При использовании Append со списком типов в первом аргументе происходит «разложение» на составные. Т.е.:

typedef TypeList<int> TL1; typedef TypeList<char, short> TL2;  std::cout << TL1() << ", " << TL2() << std::endl; std::cout << Add<TL2, TL1>::type() << ", " << Append<TL2, TL1>::type() << std::endl; 

{int}, {char short}
{int {char short}}, {int char short}
В первом случае длина результата — 2, тогда как во втором — 3, так как добавляемый список типов «разложился» на компоненты.

RemoveAll

template<typename TOrTL2, typename TL> struct RemoveAll { };  template<typename T, typename ...Args> struct RemoveAll<T, TypeList<Args...>> { private:     typedef typename RemoveAll<T, typename TypeList<Args...>::Tail>::type Removed;     typedef typename TypeList<Args...>::Head Head;      public:     typedef typename std::conditional<         std::is_same<Head, T>::value,         Removed,         typename Append<Removed, TypeList<Head>>::type         >::type type; };  template<typename T, typename Head> struct RemoveAll<T, TypeList<Head>> {     typedef typename std::conditional<         std::is_same<Head, T>::value,         EmptyTypeList,         TypeList<Head>>::type type; };  template<typename T> struct RemoveAll<T, EmptyTypeList> {     typedef EmptyTypeList type; }; 

Удаление делается так:

• С пустого списка мы ничего не можем удалить
• Если у нас список с одним элементом(только голова) — то вернуть пустой список, если тип головы совпадает с заданным или ничего не изменять в противном случае
• Для всех остальных случаев — удалить элементы с хвоста и если тип головы не совпадает с заданным типом — добавить её до результата удаления

Важно то, что, поскольку при удалении с хвоста мы сгрупировали результат в другой список типов, при объединении, используется Append, который «раскручивает» назад сгруппированный список типов.
Использование:

typedef TypeList<double, float, float, double, int, char, char, int, char> TL; std::cout << TL() << std::endl; std::cout << RemoveAll<char, TL>::type() << std::endl; 

{double float float double int char char int char}
{double float float double int int}

Можно написать ещё одну версию RemoveAll, которая будет удалять со второго списка типов все те, которые есть в первом. Но! В таком случае ее нельзя использовать для списков, которые содержат другие списки:

//template<typename Head2, typename ...Args1> //struct RemoveAll<TypeList<Head2>, TypeList<Args1...>> //{ //    typedef typename RemoveAll<Head2, TypeList<Args1...>>::type type; //}; // //template<typename ...Args1> //struct RemoveAll<EmptyTypeList, TypeList<Args1...>> //{ //    typedef TypeList<Args1...> type; //}; // //template<typename ...Args2, typename ...Args1> //struct RemoveAll<TypeList<Args2...>, TypeList<Args1...>> //{ //private: //    typedef TypeList<Args2...> TL2; //    typedef TypeList<Args1...> TL1; //     //    typedef typename RemoveAll<typename TL2::Tail, TL1>::type Removed; //    typedef typename TL2::Head Head2; //     //public: //    typedef typename std::conditional< //        Contains<Head2, Removed>::value, //        typename RemoveAll<Head2, Removed>::type, //        TL1 //        >::type type;     //}; 

Пример:

typedef TypeList<double, float, float, double, int, char, char, int, char> TL; typedef TypeList<char, double> TL2; std::cout << TL() << std::endl; std::cout << RemoveAll<TL2, TL>::type() << std::endl; 

{double float float double int char char int char}
{float float int int}

RemoveDuplicates

template<typename TL> struct RemoveDuplicates { };  template<> struct RemoveDuplicates<EmptyTypeList> {     typedef EmptyTypeList type; };  template<typename ...Args> struct RemoveDuplicates<TypeList<Args...>> { private:     typedef TypeList<Args...> TL;     typedef typename RemoveAll<typename TL::Head, typename TL::Tail>::type HeadRemovedFromTail;     typedef typename RemoveDuplicates<HeadRemovedFromTail>::type TailWithoutDuplicates; public:     typedef typename Append<TailWithoutDuplicates, TypeList<typename TL::Head>>::type type; }; 

Функция, которая удаляет дубликаты:

• С пустого списка мы ничего не можем удалить
• Удаляем такие же элементы, как и голова из хвоста
• Рекурсивно вызываем функцию для хвоста
• Объединяем голову с результатом

Пример:

typedef TypeList<double, float, float, double, int, char, char, int, char> TL; std::cout << TL() << std::endl; std::cout << RemoveDuplicates<TL>::type() << std::endl; 

{double float float double int char char int char}
{double float int char}

Find

Несколько вещей:
— Constants — для констант. В нашем случае только для константы, которая говорит о том, что элемент не найден(constexp не поддерживается в моей студии, поэтому UINT_MAX)
— internal::FindHelper — собственно говоря, «штука», которая ищет тип в списке, который точно(!) этот тип содержит(дополнительный параметр IndexFrom — начальное значение отсчёта, совсем не нужная вещь:) — рассчитана на случай, когда нужно будет задавать с какой позиции начинать поиск)

Снова же — ничего замысловатого — если указанный тип и тип головы списка совпадает — тогда индекс — нулевой, а иначе — переместится вправо на 1цу и сделать то же самое для хвоста списка.
Пример:

typedef TypeList<double, float, float, double, int, char, char, int, char> TL; std::cout << std::boolalpha << std::is_same<TypeAt<Find<double, TL>::value, TL>::type, double>() << std::endl; 

Slice

namespace internal { template<unsigned int IndexBegin, unsigned int IndexEnd, typename TL> struct SliceHelper { };  template<unsigned int IndexBegin, unsigned int IndexEnd> struct SliceHelper<IndexBegin, IndexEnd, EmptyTypeList> {     typedef EmptyTypeList type; };  template<unsigned int IndexBegin, typename ...Args> struct SliceHelper<IndexBegin, IndexBegin, TypeList<Args...>> {     typedef TypeList<typename TypeAt<IndexBegin, TypeList<Args...>>::type> type; };  template<unsigned int IndexBegin, unsigned int IndexEnd, typename ...Args> struct SliceHelper<IndexBegin, IndexEnd, TypeList<Args...>> { private:     static_assert(IndexEnd >= IndexBegin, "Invalid range");     typedef TypeList<Args...> TL; public:     typedef typename Add<         typename TypeAt<IndexEnd, TL>::type,         typename SliceHelper<IndexBegin, IndexEnd - 1, TL>::type         >::type type; };  } // internal  template<unsigned int IndexBegin, unsigned int IndexAfterEnd, typename TL> struct Slice { };  template<unsigned int IndexBegin, unsigned int IndexEnd, typename ...Args> struct Slice<IndexBegin, IndexEnd, TypeList<Args...>> {     typedef typename internal::SliceHelper<IndexBegin, IndexEnd, TypeList<Args...>>::type type; };  template<unsigned int Index, typename TL> struct CutTo { };  template<unsigned int Index, typename ...Args> struct CutTo<Index, TypeList<Args...>> {     typedef typename Slice<0, Index, TypeList<Args...>>::type type; };  template<unsigned int Index, typename TL> struct CutFrom { };  template<unsigned int Index, typename ...Args> struct CutFrom<Index, TypeList<Args...>> { private:     typedef TypeList<Args...> TL; public:     typedef typename Slice<Index, Length<TL>::value - 1, TL>::type type; }; 

«Вырезает» указанную часть списка:

• С пустого списка мы ничего не можем взять
• Когда указанные начало(IndexBegin) и конец(IndexEnd) совпадают, то это аналогично операции TypeAt<IndexBegin>
• Начиная с конца указанного диапазона, взять элемент и добавить к результату рекурсивного вызова(в котором конец указанного диапазона уменьшается на 1цу)

Пример:

typedef TypeList<double, float, float, double, int, char, char, int, char> TL; std::cout << TL() << std::endl; std::cout << Slice<2, 6, TL>::type() << std::endl; std::cout << CutTo<2, TL>::type() << std::endl; std::cout << CutFrom<8, TL>::type() << std::endl; 

{double float float double int char char int char}
{float double int char char}
{double float float}
{char}

Replace

template<unsigned int Index, typename NewValue, typename TL> struct Replace { };  template<typename NewValue, typename ...Args> struct Replace<0, NewValue, TypeList<Args...>> {     typedef typename Append<typename TypeList<Args...>::Tail, TypeList<NewValue>>::type type; };  template<unsigned int Index, typename NewValue, typename ...Args> struct Replace<Index, NewValue, TypeList<Args...>> { private:     typedef TypeList<Args...> TL;     typedef std::integral_constant<bool, Index == Length<TL>::value - 1> AtEndWorkAround;  public:     typedef typename std::conditional<         AtEndWorkAround::value,         typename internal::ReplaceEnd<NewValue, TL>::type,         typename internal::ReplaceMiddle<AtEndWorkAround::value, Index, NewValue, TL>::type         >::type type; }; 

Заменяет тип в указанной позиции(Index) на другой(NewValue):

• Замена первого элемента:
  
  • Это Head
  • Cоздать с NewValue список типов к которому добавить «хвост»(т.е. всё кроме первого элемента — «головы»)

• Замена последнего элемента:
  
  • Последний элемент имеет индекс Index - 1
  • «Вырезать» список от начала и до последнего элемента, не включая его(т.е. до Index - 2)
  • К результату добавить NewValue

• Остальные случаи:
  
  • Взять список от 0 до Index - 1 — Begin
  • Взять список от Index + 1 до конца — End
  • Объеденить три части: Begin + NewValue + End

Пример:

typedef TypeList<int, char, float> TLR; std::cout << TLR() << std::endl; std::cout << Replace<0, double, TLR>::type() << std::endl; 

{int char float}
{double char float}

ReplaceType

namespace internal { template<bool NotFoundWorkaround, typename OldValue, typename NewValue, typename TL> struct ReplaceTypeHelper {     typedef EmptyTypeList type; };  template<typename OldValue, typename NewValue, typename ...Args> struct ReplaceTypeHelper<false, OldValue, NewValue, TypeList<Args...>> { private:     typedef TypeList<Args...> TL; public:     typedef typename Replace<Find<OldValue, TL>::value, NewValue, TL>::type type; };  } // internal  // Will replace first founded @OldValue template<typename OldValue, typename NewValue, typename TL> struct ReplaceType { };  template<typename OldValue, typename NewValue, typename ...Args> struct ReplaceType<OldValue, NewValue, TypeList<Args...>> { private:     typedef TypeList<Args...> TL;     typedef std::integral_constant<bool,         Find<OldValue, TL>::value == Constants::npos::value         > NotFound; public:     typedef typename std::conditional<         NotFound::value,         TL,         typename internal::ReplaceTypeHelper<             NotFound::value,             OldValue,             NewValue,             TL             >::type         >::type type; }; 

Аналогично Replace, только сначала нужно найти позицию(Find)

Пример:

typedef TypeList<int, char, float> TLR; std::cout << TLR() << std::endl; std::cout << ReplaceType<char, double, TLR>::type() << std::endl; 

{int char float}
{int double float}

Крестики-нолики

Создадим поле, обычно 3х3:

// Empty field struct E { };  struct O { };  struct X { };  enum { ROWS = 3, COLUMNS = 3 };  // RepeatT создаёт список типов, // который состоит из N элементов типа T typedef RepeatT<E, COLUMNS>::type Row; typedef RepeatT<Row, ROWS>::type Field; 

Т.е. поле — это список рядков(Важно *), а рядок — это список ячеек.
Получается, что-то такое:

std::cout << Field() << std::endl;  { {struct E struct E struct E} {struct E struct E struct E} {struct E struct E struct E} } 

{ {struct E struct E struct E struct E} {struct E struct E struct E struct E} {struct E struct E struct E struct E} } 

Определим функции для изменения состояния:

template<unsigned int R, unsigned int C, typename F> struct FigureAt { private:     typedef typename TypeAt<R, F>::type CurrentRow; public:     typedef typename TypeAt<C, CurrentRow>::type type; };  template<unsigned int R, unsigned int C, typename NewFigure, typename F> struct ReplaceAt { private:     typedef typename TypeAt<R, F>::type OldRow;     typedef typename Replace<C, NewFigure, OldRow>::type NewRow; public:     typedef typename Replace<R, NewRow, F>::type type; }; 

Например:

typedef ReplaceAt<1, 1, X, Field>::type Field2; typedef ReplaceAt<2, 1, X, Field2>::type Field3;  { {struct E struct E struct E struct E} {struct E struct X struct E struct E} {struct E struct X struct E struct E} }  

Поле есть, выставлять значения мы умеем — нужно как-то определять есть ли победитель?
Для начала — простой случай: победил тот, кто выстроил или ряд, или столбик(по диагонали не будем считать сейчас). Т.е. на входе у насть есть масив рядочков(столбиков) и если среди них присутствует хотя бы один, полность выстроенный одним знаком(крестиком, ноликом) рядочек(столбик), то этот знак победил!
Итак:

template<typename Figure, typename Field> struct IsWin {     // Определяем рядок или столбик победителя     typedef typename RepeatT<Figure, COLUMNS>::type WinRow;     typedef typename RepeatT<Figure, ROWS>::type WinColumn;      // Если есть хотя бы один рядок или столбик победителя     static const bool value = Contains<WinRow, Field>::value ||     // Field - это список рядков, ReconfigureField -     // превращает список рядков в список столбиков         Contains<WinColumn, typename ReconfigureField<Field>::type>::value; }; 

Взглянем на ReconfigureField:

namespace internal { template<unsigned int C, unsigned int R, typename CurrentColumnType, typename F> struct ColumnTypeHelper {     typedef typename Add<         typename FigureAt<R, C, F>::type,         typename ColumnTypeHelper<C, R - 1, CurrentColumnType, F>::type         >::type type; };  template<unsigned int C, typename CurrentColumnType, typename F> struct ColumnTypeHelper<C, 0, CurrentColumnType, F> {     typedef typename Add<typename FigureAt<0, C, F>::type, CurrentColumnType>::type type; };  } // internal  template<unsigned int C, typename F> struct ColumnType {     typedef typename internal::ColumnTypeHelper<C, ROWS - 1, EmptyTypeList, F>::type type; };  namespace internal { template<unsigned int C, typename NewF, typename F> struct ReconfigureFieldHelper {     typedef typename Add<         typename ColumnType<C, F>::type,         typename ReconfigureFieldHelper<C - 1, NewF, F>::type         >::type type; };  template<typename NewF, typename F> struct ReconfigureFieldHelper<0, NewF, F> {     typedef typename Add<         typename ColumnType<0, F>::type,         NewF         >::type type; }; } // internal  template<typename F> struct ReconfigureField {     typedef typename internal::ReconfigureFieldHelper<         COLUMNS - 1, EmptyTypeList, F>::type type; }; 

Что ReconfigureField делает на практике(это хорошо видно, когда количество столбиков и рядочков неодинаково):

typedef ReplaceAt<1, 1, X, Field>::type Field2; typedef ReplaceAt<2, 1, X, Field2>::type Field3;  std::cout << Field3() << std::endl; std::cout << ReconfigureField<Field3>::type() << std::endl;  { {struct E struct E struct E struct E} {struct E struct X struct E struct E} {struct E struct X struct E struct E} }  { {struct E struct E struct E} {struct E struct X struct X} {struct E struct E struct E} {struct E struct E struct E} }  

Т.е. 1 столбик становится 1 рядком, 2й столбик — 2м и т.д. — это всё, что нужно, чтобы найти столбик победителя на поле, что мы и делаем:

Contains<WinColumn, typename ReconfigureField<Field>::type>::value 

Можно ещё поизвращаться, но я устал. В конце-концов:

typedef ReplaceAt<1, 1, X, Field>::type Field2; typedef ReplaceAt<2, 1, X, Field2>::type Field3; typedef ReplaceAt<0, 1, X, Field3>::type Field4;  std::cout << std::boolalpha << IsWin<X, Field2>::value << std::endl; std::cout << std::boolalpha << IsWin<X, Field3>::value << std::endl; std::cout << std::boolalpha << IsWin<X, Field4>::value << std::endl;  // Вывод false false true 

Спасибо за внимание!