Выкладываю очень древний код. Написано сразу по прочтению первой половины книги "Modern C++ Design". Код не выдерживает никакой критики(как с точки зрения оптимальности(например поддерживаются списки одинаковых ключей), так и красоты), но может кому покажется интересным. Дорабатывать смысла не имело и не имеет, поэтому критика не рекомендуется. На вопрос "зачем" тоже ответить не смогу.
Пример использования в самом конце.
//
// Построение сбалансированного бинарного дерева поиска в compile time
// и фабрики классов на его базе.
//
// Для компиляции потребуется Loki !
//
// public domain
//
#include <vector>
#include <iostream>
#include "Typelist.h"
using namespace Loki;
//
// Loki-style enable_if :))
//
template <bool B, class T = void>
struct EnableIf_C {
typedef T Result;
};
template <class T>
struct EnableIf_C<false, T> {};
template <class Cond, class T = void>
struct EnableIf : public EnableIf_C<Cond::Result, T> {};
template <class T, class Special = void> struct ExtractKey;
template <int Value,class Special>
struct ExtractKey<Int2Type<Value>,Special >
{
enum
{
KEY = Value
};
};
template <int Value,class Tail,class Special>
struct ExtractKey<Typelist<Int2Type<Value>, Tail>,Special >
{
enum
{
KEY = Value
};
};
template <class T,class Special> struct ExtractKey
{
enum
{
KEY = -1
};
};
template <class T> struct ExtractType;
template <class Type,class Tail> struct ExtractType<Typelist<Type,Tail> >
{
typedef Type Result;
};
template <class T> struct ExtractType
{
typedef T Result;
};
template <class T, int mx = -1> struct KeyMax;
template <int mx, class Head, class Tail> struct KeyMax<Typelist<Head,Tail>, mx>
{
enum
{
MAX = KeyMax<Tail, (ExtractKey<Head>::KEY > mx) ? ExtractKey<Head>::KEY : mx >::MAX
};
};
template <int mx> struct KeyMax<NullType,mx>
{
enum
{
MAX = mx
};
};
template <class T, int mn = 0xFFFFFF> struct KeyMin;
template <int mn, class Head, class Tail> struct KeyMin<Typelist<Head,Tail>, mn>
{
enum
{
MIN = KeyMin<Tail, (ExtractKey<Head>::KEY < mn) ? ExtractKey<Head>::KEY : mn >::MIN
};
};
template <int mn> struct KeyMin<NullType,mn>
{
enum
{
MIN = mn
};
};
template <class T, int mx, int mn, int med = mn> struct KeyMed;
template <int mx, int mn, int md, class Head, class Tail> struct KeyMed<Typelist<Head,Tail>, mx, mn, md>
{
#define ABS(x) (x<0 ? -x : x)
#define D(x) ABS((mn+(mx-mn)/2-x))
enum
{
Value = KeyMed<Tail,mx,mn,D(ExtractKey<Head>::KEY) < D(md) ? ExtractKey<Head>::KEY : md>::Value
};
#undef D
#undef ABS
};
template <int mx, int mn, int md> struct KeyMed<NullType,mx,mn,md>
{
enum
{
Value = md
};
};
template <int ki,int k> struct KeyLesser
{
enum
{
Result = ki < k
};
};
template <int ki,int k> struct KeyGreater
{
enum
{
Result = ki > k
};
};
template <int ki,int k> struct KeyEqual
{
enum
{
Result = ki == k
};
};
template <bool Cond, class Key> struct FilterKey;
template <class Key> struct FilterKey<true,Key>
{
typedef Typelist<Key,NullType> Result;
};
template <bool Cond, class Key> struct FilterKey
{
typedef NullType Result;
};
template <int K,template <int,int> class C,class TList> struct KeyQuery;
template <int K,template <int,int> class C,class Head,class Tail> struct KeyQuery<K,C,Typelist<Head,Tail> >
{
typedef typename FilterKey<C<ExtractKey<Head>::KEY,K>::Result,Head>::Result C0;
typedef typename TL::Append<C0,typename KeyQuery<K,C,Tail>::Result>::Result Result;
};
template <int K,template<int,int> class C> struct KeyQuery<K,C,NullType>
{
typedef NullType Result;
};
//
// собственно "дерево"
//
template <class Mid,class Left,class Right> struct BST;
template <class Mid,class Left,class Right> struct BST
{
enum
{
LSUB_H = Left::HEIGHT + 1,
RSUB_H = Right::HEIGHT + 1,
HEIGHT = LSUB_H > RSUB_H ? LSUB_H : RSUB_H,
KEY = ExtractKey<Mid>::KEY
};
typedef typename ExtractType<Mid>::Result Value;
typedef Left L;
typedef Right R;
};
template <> struct BST<NullType,NullType,NullType>
{
enum
{
LSUB_H = 0,
RSUB_H = 0,
HEIGHT = 0
};
};
typedef BST<NullType,NullType,NullType> BST_Null;
template <class TList> struct MakeTree;
template <> struct MakeTree<NullType>
{
typedef BST_Null Result;
};
template <class TList> struct MakeTree
{
enum
{
MED = KeyMed<TList,KeyMax<TList>::MAX,KeyMin<TList>::MIN>::Value
};
typedef BST<typename KeyQuery<MED,KeyEqual,TList>::Result,
typename MakeTree<typename KeyQuery<MED,KeyLesser,TList>::Result>::Result,
typename MakeTree<typename KeyQuery<MED,KeyGreater,TList>::Result>::Result > Result;
};
//
// фабрика классов, работает как генератор кода поиска по дереву
// т.е. поиск происходит в ран-тайме, т.к. конкретный id становится известен только в ран-тайме
//
template <class T,class TTree> struct ObjectFactory;
template <class T,class Mid, class Left, class Right>
struct ObjectFactory<T,BST<Mid, Left, Right> >
{
typedef typename ExtractType<Mid>::Result Type;
enum
{
ID = ExtractKey<Mid>::KEY
};
static inline T* Create(int typeID)
{
if (typeID==ID) return new Type();
if (typeID<ID) return ObjectFactory<T,Left>::Create(typeID);
if (typeID>ID) return ObjectFactory<T,Right>::Create(typeID);
return NULL;
}
};
template <class T>
struct ObjectFactory<T,BST_Null >
{
static inline T *Create(int)
{
return NULL;
}
};
//
// Пример использования
//
struct Object { };
//
// Специальные экстракторы ключей для объектов, наследуемых от Object
//
template <class T,class Tail>
struct ExtractKey<Typelist<T, Tail>,typename EnableIf_C<Conversion<T,Object>::exists >::Result >
{
enum
{
KEY = T::ID
};
};
template <class T>
struct ExtractKey<T,typename EnableIf_C<Conversion<T,Object>::exists >::Result >
{
enum
{
KEY = T::ID
};
};
struct Object1 : Object
{
Object1() { std::cout<<"Object1::ctor"<<std::endl; };
const static int ID = 1;
};
struct Object2 : Object
{
Object2() { std::cout<<"Object2::ctor"<<std::endl; };
const static int ID = 2;
};
struct Object3 : Object
{
Object3() { std::cout<<"Object3::ctor"<<std::endl; };
const static int ID = 3;
};
struct Object4 : Object
{
Object4() { std::cout<<"Object4::ctor"<<std::endl; };
const static int ID = 4;
};
struct Object5 : Object
{
Object5() { std::cout<<"Object5::ctor"<<std::endl; };
const static int ID = 5;
};
struct Object6 : Object
{
Object6() { std::cout<<"Object6::ctor"<<std::endl; };
const static int ID = 6;
};
typedef TYPELIST_6(Object1,Object2,Object3,Object4,Object5,Object6) object_list;
typedef MakeTree<object_list>::Result object_tree;
template <class Tree> inline Object* CreateObject(int typeID)
{
return ObjectFactory<Object,Tree>::Create(typeID);
};
int main()
{
std::cout<<"object_list:\n"<<std::endl;
std::cout<<typeid(object_list).name()<<std::endl;
std::cout<<"\nobject_tree:\n"<<std::endl;
std::cout<<typeid(object_tree).name()<<std::endl;
std::vector<Object*> objs;
for(int id = Object1::ID; id <= Object6::ID; ++id) objs.push_back(CreateObject<object_tree>(id));
for(std::vector<Object*>::iterator it = objs.begin(); it != objs.end(); ++it)
delete *it;
}
