[boost] Re: Metaprogramming: map.

From: David Abrahams (dave_at_[hidden])
Date: 2003-10-01 09:27:56

David Abrahams <dave_at_[hidden]> writes:

> I did some research on maps and sets for the upcoming MPL book and
> discovered an approach which essentially provides O(1) lookup, though
> I don't think we have an implementation in the MPL just yet.
> Unfortunately, I no longer have the prototype.  I'm sure Aleksey has a
> copy.

Aleksey kindly dug this up for me; hope it helps.

// Copyright 2003 David Abrahams

#include "boost/mpl/apply.hpp"
#include "boost/mpl/void.hpp"
#include "boost/mpl/bool.hpp"
#include "boost/static_assert.hpp"

using namespace boost::mpl;

#  if __ICL || _MSC_VER && _MSC_VER <= 1300
#   define VC67 1 // Believe it or not, even Intel5,6,7 wants this hack
#  endif 

typedef char (&no)[2];
template <class T> struct id { id(); typedef T type; };

struct set_base
{
};

#  if VC67
template <class X>
no operator%(set_base, X);

template <class T, class B = set_base>
struct set_node : B
{
    friend char operator%(set_node, id<T>);
};

template <class T, class S>
struct member
{
    enum { value = sizeof(S()%id<T>()) == 1 };
};

# else

template <class X>
no check(set_base, X);

template <class T, class B = set_base>
struct set_node : B
{
    friend char check(set_node, id<T>);
};

template <class T, class S>
struct member
{
    static bool const value = sizeof(check(S(),id<T>())) == 1;
};
# endif

typedef set_node<int, set_node<long, set_node<short> > > s;

BOOST_STATIC_ASSERT(( member<int,s>::value ));
BOOST_STATIC_ASSERT(( member<long,s>::value ));
BOOST_STATIC_ASSERT(( member<short,s>::value ));
BOOST_STATIC_ASSERT(( !member<char,s>::value ));
                 
//----------

#  if VC67
struct map_base
{
    enum { index = 1 };
};

template <class X>
char operator%(map_base, X);

template <class K, class V, class B = map_base>
struct map_node : B
{
    enum { index = B::index + 1 };
    typedef char (&index_t)[index];
    friend index_t operator%(map_node, id<K>);
    friend id<V> operator*(map_node, id<index_t>);
};

template <class T, class M>
struct index
{
    enum { value = sizeof(M()%id<T>()) - 1 };
};
#  else
struct map_base
{
    static unsigned const index = 1;
};

template <class X>
char find(map_base, X);

template <class K, class V, class B = map_base>
struct map_node : B
{
    static unsigned const index = B::index + 1;
    typedef char (&index_t)[index];
    friend index_t find(map_node, id<K>);
    friend id<V> at_(map_node, id<index_t>);
};

template <class T, class M>
struct index
{
    static unsigned const value = sizeof(find(M(), id<T>())) - 1;
};
#  endif

typedef map_node<int, int*, map_node<long, long*, map_node<short, short*> > > m;

# if !__BORLANDC__ // no idea why, but Bcc 5.5.1 barfs here.
BOOST_STATIC_ASSERT(( index<int,m>::value == 3 ));
BOOST_STATIC_ASSERT(( index<long,m>::value == 2 ));
BOOST_STATIC_ASSERT(( index<short,m>::value == 1 ));
BOOST_STATIC_ASSERT(( index<char,m>::value == 0 ));
BOOST_STATIC_ASSERT(( index<char*,m>::value == 0 ));
BOOST_STATIC_ASSERT(( index<char*,m>::value == 0 ));
BOOST_STATIC_ASSERT(( index<char**,m>::value == 0 ));
# endif

// ------

# if VC67
template <class T>
int fassert_same(id<T>,id<T>);
template <class X, class Y> struct assert_same
{
    static id<X> a;
    static id<Y> b;
    enum { x = sizeof(fassert_same(a, b)) };
};
# else
template <class, class> struct assert_same;
template <class T> struct assert_same<T,T> {};
# endif

#  ifdef __MWERKS__
template <class M, class K>
struct at
{
    typedef char (&ix)[index<K,M>::value + 1];
    typedef __typeof__(at_(M(), id<ix>())) id_;
    typedef typename id_::type type;
};

assert_same<at<m,int>::type,int*> c1;
assert_same<at<m,long>::type,long*> c2;
assert_same<at<m,short>::type,short*> c3;
#  endif

// -------------

template <unsigned = 0>
struct unused_;

typedef char (&n1)[1];
typedef char (&n2)[2];
typedef char (&n3)[3];
typedef char (&n4)[4];
typedef char (&n5)[5];

# if !__BORLANDC__ // no idea why, but Bcc 5.5.1 barfs here.
template <
    class K1 = unused_<0>, class V1 = unused_<>
  , class K2 = unused_<1>, class V2 = unused_<>
  , class K3 = unused_<2>, class V3 = unused_<>
  , class K4 = unused_<3>, class V4 = unused_<>
>
struct vmap
{
    typedef V1 v1;
    typedef V2 v2;
    typedef V3 v3;
    typedef V4 v4;
    friend n1 operator%(vmap,id<K1>);
    friend n2 operator%(vmap,id<K2>);
    friend n3 operator%(vmap,id<K3>);
    friend n4 operator%(vmap,id<K4>);
};

template <unsigned N>
struct at_impl;

template <>
struct at_impl<1>
{
    template <class VM>
    struct apply
    {
        typedef typename VM::v1 type;
    };
};

template <>
struct at_impl<2>
{
    template <class VM>
    struct apply
    {
        typedef typename VM::v2 type;
    };
};

template <>
struct at_impl<3>
{
    template <class VM>
    struct apply
    {
        typedef typename VM::v3 type;
    };
};

template <>
struct at_impl<4>
{
    template <class VM>
    struct apply
    {
        typedef typename VM::v4 type;
    };
};

template <class VM, class K>
struct vat
{
    enum { index = sizeof(VM()%id<K>()) };
    typedef at_impl<index> outer;
    typedef typename outer::template apply<VM>::type type;
};

typedef vmap<int*, int, long*, long, short*, short, char, char*> vm;

assert_same<vat<vm,int*>::type, int> d1;
assert_same<vat<vm,long*>::type, long> d2;
assert_same<vat<vm,short*>::type, short> d3;
assert_same<vat<vm,char>::type, char*> d4;
# endif

int main()
{
    return 0;
}

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com