#include <typeinfo>
#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>

#include <assert.h>
#include <time.h>
#include <stdio.h>


struct	A
{
	virtual int	MemberFn()	{ return 0;}
	virtual	~A()	{}
};

struct	AB	: A		{};
struct	AC	: A		{};
struct	AD	: A		{};
struct	ACD	: AC	{};
struct	ABE	: AB	{};



template< class T, int N>
struct	array
/* Simple fixed-size STL-style container. */
{
	inline explicit array( unsigned int i)					{ assert( i==N); i=i;	}
	inline explicit array()									{}
	inline T&		operator [] ( unsigned int i)			{ return this->m_items[i];	}
	inline const T&	operator [] ( unsigned int i)	const	{ return this->m_items[i];	}
	inline unsigned int	size()						const	{ return N;	}
	private:
		T	m_items[N];
};

template< class T, int N>
bool	operator < ( const array< T, N>& lhs, const array< T, N>& rhs)
{
	for ( unsigned int i=0; i<N; ++i)
	{
		if ( lhs[i] < rhs[i])	return true;
	}
	return false;
}


template< class Key, class Value>
struct	vmap
/* Simple associative map, for use with key types that look
like arrays with operator[] - see the static cmp() function.
Underlying implementation is a sorted std::vector. */
{
	typedef	Key									key_type;
	typedef Value								mapped_type;
	typedef std::pair< key_type, mapped_type>	value_type;

	vmap()	: m_cached( -1)	{}

	static inline int	cmp( const Key& lhs, const Key& rhs)
	/* Better than operator< or std::less,
	because equality doesn't require 2 comparisons (???). */
	{
		unsigned int	n = lhs.size();
		assert( n==rhs.size());
		for ( unsigned int i=0; i<n; ++i)
		{
			if ( lhs[i] != rhs[i])	return lhs[i]-rhs[i];
		}
		return 0;
	}

	static bool	Compare( const value_type& lhs, const value_type& rhs)
	{
		return ( cmp( lhs.first, rhs.first) < 0) ? true : false;
	}

	inline mapped_type&	operator [] ( const key_type& key)
	{
		if ( m_cached!=-1)
		{
			if ( 0==cmp( key, m_items[m_cached].first))
				return m_items[m_cached].second;
		}

		unsigned int	min = 0;
		unsigned int	max = m_items.size();

		for(;;)
		{
			if ( min==max)
			{
				m_items.push_back( std::make_pair( key, mapped_type()));
				std::sort( m_items.begin(), m_items.end(), Compare);
				assert( 0==cmp( m_items[ min].first,key));
				return m_items[min].second;
			}
			
			unsigned int	i = (min+max)/2;

			int	diff = cmp( key, m_items[i].first);

			if ( diff<0)	max = i;
			else if ( diff>0)	min = i+1;
			else
			{
				m_cached = i;
				return m_items[i].second;
			}
		}
	}
	private:
		std::vector< value_type>	m_items;	// this is always sorted.
		int							m_cached;
};




int	Fn1( virtual A& a);
//void	Fn2( virtual A& a1, virtual A& a2);


int	Fn1_( static  A&)	{ return 0;	}

int	Fn1_( static AB&)	{ return 0;	}
int	Fn1_( static AC&)	{ return 0;	}
int	Fn1_( static AD&)	{ return 0;	}
int	Fn1_( static ACD&)	{ return 0;	}
int	Fn1_( static ABE&)	{ return 0;	}

int	Fn2_( A&, A&)	{ return 0;	}



int	Fn1_cmm_implcall1_2_3_A3_AB( A&)
{
	return 0;
}
int	Blank( A& a)
{
	//Fn1_cmm_implcall_cmm_param_cmm_classA_cmm_classAB( a);
	static const std::type_info*	cache = &typeid( AB);
	if ( &typeid( a) == cache)	return Fn1_cmm_implcall1_2_3_A3_AB( a);
	return 0;
}

int	main( int argc, char** argv)
{
    try
    {
        if ( argc!=2)
        {
            std::cerr << "expecting one parameter\n";
            return 1;
        }

        fprintf( stderr, "%-25s", argv[1]);

        /* using fprintf instead of iostreams, because gcc 2.95 has
        limited support for std manipulators. */

	    A&	ab	= *new AB;
	    A&	ac	= *new AC;
	    A&	ad	= *new AD;
	    A&	acd	= *new ACD;
	    A&	abe	= *new ABE;

	    (void)	ab;
	    (void)	ac;
	    (void)	ad;
	    (void)	acd;
	    (void)	abe;

	    double t_virtmethod, t_virtfn, t_method;

	    int	its = 2*1000*1000;

        // fill up cmm's internal dispatch caches a bit:
        Fn1( ab);
        Fn1( ac);
        Fn1( ad);
        Fn1( acd);
        Fn1( abe);

	    {
		    clock_t	t=clock();
		    for ( int i=0; i<its; ++i)
		    {
			    ab.MemberFn();
                ac.MemberFn();
                ad.MemberFn();
                acd.MemberFn();
                abe.MemberFn();
		    }
		    t = clock() - t;
		    t_virtmethod = 1.0*t/CLOCKS_PER_SEC/its;
            fprintf( stderr, "Virtual member fn: %8.2g. ", 1.0*t/CLOCKS_PER_SEC/its);
		    //std::cerr << "Virtual member fn: " << (1.0*t/CLOCKS_PER_SEC/its) << ". ";
	    }

	    {
		    clock_t	t=clock();
		    for ( int i=0; i<its; ++i)
		    {
			    Fn1( ab);
                Fn1( ac);
                Fn1( ad);
                Fn1( acd);
                Fn1( abe);
		    }
		    t = clock() - t;
		    t_virtfn = 1.0*t/CLOCKS_PER_SEC/its;
            fprintf( stderr, "Multimethod: %8.2g. ", 1.0*t/CLOCKS_PER_SEC/its);
		    //std::cerr << "Multimethod:       " << (1.0*t/CLOCKS_PER_SEC/its) << ". ";
	    }

        /* the following tests the speed of using cached impl pointers. only supported
        for cmm -s, not cmm -c/l.*/
        #if 0
	    {
		    clock_t	t=clock();

            typedef int	(*fnptr)( A& a);

            fnptr   fn_ab = Fn1_cmm_getimpl( ab);
            fnptr   fn_ac = Fn1_cmm_getimpl( ac);
            fnptr   fn_ad = Fn1_cmm_getimpl( ad);
            fnptr   fn_acd = Fn1_cmm_getimpl( acd);
            fnptr   fn_abe = Fn1_cmm_getimpl( abe);

		    for ( int i=0; i<its; ++i)
		    {
			    fn_ab( ab);
                fn_ac( ac);
                fn_ad( ad);
                fn_acd( acd);
                fn_abe( abe);
		    }
		    t = clock() - t;
		    t_virtfn = 1.0*t/CLOCKS_PER_SEC/its;
            fprintf( stderr, "cached ptrs: %8.2g. ", 1.0*t/CLOCKS_PER_SEC/its);
		    //std::cerr << "cached ptrs: " << std::width( 12) << (1.0*t/CLOCKS_PER_SEC/its) << ". ";
	    }
        #endif

	    if ( 0)
	    {
		    clock_t	t=clock();
		    for ( int i=0; i<its; ++i)
		    {
			    ab.A::MemberFn();
		    }
		    t = clock() - t;
		    t_method = 1.0*t/CLOCKS_PER_SEC/its;
            fprintf( stderr, "Directfn: %8.2g. ", 1.0*t/CLOCKS_PER_SEC/its);
		    //std::cerr << "Directfn: " << std::width( 12) << (1.0*t/CLOCKS_PER_SEC/its) << ". ";
	    }
	    {
		    clock_t	t=clock();
		    for ( int i=0; i<its; ++i)
		    {
			    Blank( ab);
			    Blank( ac);
			    Blank( ad);
			    Blank( acd);
			    Blank( abe);
		    }
		    t = clock() - t;
		    t_method = 1.0*t/CLOCKS_PER_SEC/its;
            fprintf( stderr, "Blank: %8.2g. ", 1.0*t/CLOCKS_PER_SEC/its);
		    //std::cerr << "Blank: " << std::width( 12) << (1.0*t/CLOCKS_PER_SEC/its) << ". ";
	    }
	    std::cerr << "Slow-down multimethod/virtual method fn=" << t_virtfn/t_virtmethod << "\n";

	    return 0;
    }
    catch( std::exception& e)
    {
        std::cerr << "error: "<< e.what() << "\n";
        return 0;   // get ambiguous dispatch with cmm -c/-l.
    }
    return 1;
}