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

Захотелось, наконец-то(!), попробовать variadic templates, так как до сих пор привязан к 10й студии, где ничего этого нету. А чтобы долго не думать, где же можно бесполезно использовать variadic templates, пришла идея попробовать, как будет выглядеть Typelist. Для тех, кто ещё не знает, что это такое, я постараюсь объяснять по ходу дела, а тем, кому это скучно — может сразу пролистать вниз — попробуем написать подобие крестиков-ноликов с использованием Typelist.

Итак, TypeList:

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, это выглядело так:

Старый TypeList

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

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

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

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!");

Вывод списка

operator<<

// Пустой список
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

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, которая будет удалять со второго списка типов все те, которые есть в первом. Но! В таком случае ее нельзя использовать для списков, которые содержат другие списки:

RemoveAll v2

//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

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

Позиция типа в списке

struct Constants { typedef std::integral_constant<unsigned int, UINT_MAX/*std::numeric_limits<unsigned int>::max()*/> npos; }; namespace internal { template<typename T, unsigned int IndexFrom, typename TL> struct FindHelper : std::integral_constant<unsigned int, 0> { }; template<typename T, unsigned int IndexFrom> struct FindHelper<T, IndexFrom, EmptyTypeList> : std::integral_constant<unsigned int, 0> { }; template<typename T, unsigned int IndexFrom, typename ...Args> struct FindHelper<T, IndexFrom, TypeList<Args...>> : std::integral_constant<unsigned int, std::is_same<typename TypeList<Args...>::Head, T>::value ? IndexFrom : IndexFrom + 1 + FindHelper<T, IndexFrom, typename TypeList<Args...>::Tail>::value> { }; } // internal template<typename T, typename TL> struct Find { }; template<typename T> struct Find<T, EmptyTypeList> : Constants::npos { }; template<typename ...Args> struct Find<internal::Void, TypeList<Args...>> : Constants::npos { }; template<typename T, typename ...Args> struct Find<T, TypeList<Args...>> : std::integral_constant<unsigned int, Contains<T, TypeList<Args...>>::value ? internal::FindHelper<T, 0, TypeList<Args...>>::value : Constants::npos::value> { };

Несколько вещей:

— 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

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

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

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}
}

И, когда COLUMNS = 4:

{
{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:

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 делает на практике(это хорошо видно, когда количество столбиков и рядочков неодинаково):

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

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

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.