challenge: implement the max function

[Sean Kelly]

Andrei Alexandrescu (See Website For Email) wrote:
> Here's a simple challenge: implement the max function. Requirements:
> 
> a) generic
> b) efficient
> c) preserve lvalueness when possible such that one can write e.g.
> 
> max(arr[0], arr[1]) *= 0.9;

This is the largest stumbling block.  The rest could be handled with 
template code, though it may be a fairly verbose.

> d) should accept two or more arguments
> e) should return the "smartest" type, e.g. max of an unsigned int and 
> unsigned long should return unsigned long
> f) short and easy to understand
> 
> I don't think it's possible to implement the function to the spec in 
> current D, so designs are allowed to invent new features, as long as 
> they define them thoroughly.

Reference return types notwithstanding, I took an initial stab at this a 
few months ago, as outlined in D.learn "max() in phobos?" (11/6/2006) on 
digitalmars.D.learn:

http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=digitalmars.D.learn&artnum=5152

I got distracted and never finished with it, but at the time I was 
experimenting with reducing the template code by using typeof( a + b ) 
as the return type when a and b are concrete values.  However, this 
wouldn't work if a reference type must be returned because of D's 
integer promotion rules (typeof( a + b ) == int where a and b are 
smaller than int).  Some problems with the code:

* It doesn't handle comparison of a UDT and a concrete type.  This could
   be done by adding more template code, but I didn't bother with it at
   the time--I was hoping for something simple and the code is already
   somewhat complex.

* The casts in min/max are required to support UDT comparison because
   the overload resolution mechanism can't handle complex situations.  An
   alternative might be to require the user to explicitly cast one of the
   parameters for min/max, but to me that kind of defeats the point of
   the min/max functions as a macro look-alike.

Most of the template code really belongs in a Traits module, but as it's 
required for the min/max implementation I think it should be counted 
when evaluating complexity :-)

--------------------------------------------------------------------------------

template isSignedIntegerType( T )
{
     const bool isSignedIntegerType = is( T == byte )  ||
                                      is( T == short ) ||
                                      is( T == int )   ||
                                      is( T == long )/+||
                                      is( T == cent )+/;
}

template isUnsignedIntegerType( T )
{
     const bool isUnsignedIntegerType = is( T == ubyte )  ||
                                        is( T == ushort ) ||
                                        is( T == uint )   ||
                                        is( T == ulong )/+||
                                        is( T == ucent )+/;
}

template isIntegerType( T )
{
     const bool isIntegerType = isSignedIntegerType!(T) ||
                                isUnsignedIntegerType!(T);
}

template commonBaseTypeOf( T, U )
{
     static assert( ( is( T == class )     && is( U == class ) ) ||
                    ( is( T == interface ) && is( U == interface ) ),
                    "Supplied types are not siblings." );

     static if( is( T : U ) )
         alias U commonBaseTypeOf;
     else static if( is( U : T ) )
         alias T commonBaseTypeOf;
     else static if( is( T == class ) )
         alias Object commonBaseTypeOf;
     else
         static assert( false, "Interfaces have no generic parent." );
}

template bestCommonTypeOf( T, U )
{
     static if( is( T == class )     || is( U == class ) ||
                is( T == interface ) || is( U == interface ) )
     {
         alias commonBaseTypeOf!( T, U ) bestCommonTypeOf;
     }
     else static if( is( T : U ) && is( U : T ) )
     {
         static if( T.sizeof > U.sizeof )
             alias T bestCommonTypeOf;
         else static if( T.sizeof < U.sizeof )
             alias U bestCommonTypeOf;
         else static if( isUnsignedIntegerType!(T) )
             alias T bestCommonTypeOf;
         else
             alias U bestCommonTypeOf;
     }
     else static if( is( U : T ) )
         alias T bestCommonTypeOf;
     else static if( is( T : U ) )
         alias U bestCommonTypeOf;
     else
         static assert( false, "Unable to find common type." );
}

template min( T, U )
{
     bestCommonTypeOf!(T, U) min( T t, U u )
     {
         alias bestCommonTypeOf!(T, U) rt;
         if( cast(rt) t < cast(rt) u )
             return t;
         return u;
     }
}

template max( T, U )
{
     bestCommonTypeOf!(T, U) max( T t, U u )
     {
         alias bestCommonTypeOf!(T, U) rt;
         if( cast(rt) t > cast(rt) u )
             return t;
         return u;
     }
}

void main()
{
     class B
     {
         this( int v )
         {
             value = v;
         }

         int opCmp( B rhs )
         {
             return value - rhs.value;
         }

         int opCmp( Object rhs )
         {
             return opCmp( cast(B) rhs );
         }

         private int value;
     }

     class C : B
     {
         this( int v )
         {
             super( v );
         }
     }

     class D : B
     {
         this( int v )
         {
             super( v );
         }
     }

     static assert( is( bestCommonTypeOf!( int, uint ) == uint ) );
     static assert( is( bestCommonTypeOf!( uint, int ) == uint ) );

     static assert( is( bestCommonTypeOf!( long, uint ) == long ) );
     static assert( is( bestCommonTypeOf!( uint, long ) == long ) );

     static assert( is( bestCommonTypeOf!( char, byte ) == byte ) );
     static assert( is( bestCommonTypeOf!( byte, char ) == char ) );


     static assert( is( bestCommonTypeOf!( byte, long ) == long ) );
     static assert( is( bestCommonTypeOf!( long, byte ) == long ) );
     static assert( is( bestCommonTypeOf!( long, float ) == float ) );
     static assert( is( bestCommonTypeOf!( float, long ) == float ) );
     static assert( is( bestCommonTypeOf!( float, real ) == real ) );
     static assert( is( bestCommonTypeOf!( cfloat, creal ) == creal ) );
     static assert( is( bestCommonTypeOf!( creal, cfloat ) == creal ) );

     static assert( is( bestCommonTypeOf!( B, C ) == B ) );
     static assert( is( bestCommonTypeOf!( C, B ) == B ) );
     static assert( is( bestCommonTypeOf!( C, D ) == Object ) );
     static assert( is( bestCommonTypeOf!( D, C ) == Object ) );

     int     ismall = 1, ibig = 2;
     byte    bsmall = 1, bbig = 2;
     float   fsmall = 1, fbig = 2;
     double  dsmall = 1, dbig = 2;

     assert( max( ibig, ismall )==ibig );
     assert( max( ismall, ibig )==ibig);
     assert( min( ibig, ismall )==ismall );
     assert( min( ismall, ibig )==ismall );

     assert( max( fbig, fsmall )==fbig );
     assert( max( fsmall, fbig )==fbig );
     assert( min( fbig, fsmall )==fsmall );
     assert( min( fsmall, fbig )==fsmall );

     assert( min( dsmall, fbig )==dsmall );
     assert( max( dsmall, fbig )==fbig );
     assert( min( dbig, fsmall )==fsmall );
     assert( max( dbig, fsmall )==dbig );

     assert( is( typeof( min( dsmall, fbig ) ) == double ) );
     assert( is( typeof( max( dsmall, fbig ) ) == double ) );
     assert( is( typeof( min( dbig, fsmall ) ) == double ) );
     assert( is( typeof( max( dbig, fsmall ) ) == double ) );

     assert( is( typeof( min( bsmall, ibig ) ) == int ) );
     assert( is( typeof( max( bsmall, ibig ) ) == int ) );
     assert( is( typeof( min( bbig, ismall ) ) == int ) );
     assert( is( typeof( max( bbig, ismall ) ) == int ) );

     B b = new B( 1 );
     C c = new C( 2 );
     D d = new D( 3 );

     assert( min( b, c ) == b );
     assert( max( b, c ) == c );
     assert( min( c, d ) == c );
     assert( max( c, d ) == d );

     assert( b < cast(B) c );
     assert( cast(B) c > b );

/*
     char  a;
     byte b;
     struct S {} struct T {}

     static assert( is( typeof( a + b ) == char ) );
     auto c = a + b;

     static assert( is( typeof( ubyte.init + ushort.init ) == bool ) );
*/
}