Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 24.06.2014 | нет комментариев
Захотелось, наконец-то(!), испробовать 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_typeIsEmpty имеет член класса 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;
};

— возвращает тип по индексу, примерно, как массив. Реализация — 1-й заход(меняем тип 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, так как добавляемый список типов «разложился» на ко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> 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

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

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB