www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Closest Common Type

reply BCS <ao pathlink.com> writes:
I have a tuple of types, I want a template that evaluates to the most
specialized 
base type of all of them. I'll be using it for classes but for other cases 
it just needs to do something sane (erroring out would do). 

No point in reinventing the wheel so, anyone have such a template laying 
around?
May 16 2008
next sibling parent reply Lutger <lutger.blijdestin gmail.com> writes:
BCS wrote:


 I have a tuple of types, I want a template that evaluates to the most
 specialized base type of all of them. I'll be using it for classes but for
 other cases it just needs to do something sane (erroring out would do).
 
 No point in reinventing the wheel so, anyone have such a template laying
 around?



tango.core.Tuple and std.typetuple have templates called MostDerived and
DerivedToFront, these might be helpful?
May 16 2008
parent reply BCS <ao pathlink.com> writes:
Reply to Lutger,


 BCS wrote:
 

 I have a tuple of types, I want a template that evaluates to the most
 specialized base type of all of them. I'll be using it for classes
 but for other cases it just needs to do something sane (erroring out
 would do).
 
 No point in reinventing the wheel so, anyone have such a template
 laying around?
 



 and DerivedToFront, these might be helpful?



I might be able to use somthing like that as a starting point but what I 
want is this

class A {}
 class B : A {}
 class C : A {}
  class D : C {}
  class E : C {}
class F {}

CCT!(E, D) // == C
CCT!(E, C) // == C
CCT!(E, B) // == A
CCT!(E, A) // == A
CCT!(E, F) // == object
May 16 2008
next sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
BCS wrote:

 Reply to Lutger,
 

 BCS wrote:


 I have a tuple of types, I want a template that evaluates to the most
 specialized base type of all of them. I'll be using it for classes
 but for other cases it just needs to do something sane (erroring out
 would do).

 No point in reinventing the wheel so, anyone have such a template
 laying around?



 and DerivedToFront, these might be helpful?



 I might be able to use somthing like that as a starting point but what I 
 want is this
 
 class A {}
 class B : A {}
 class C : A {}
  class D : C {}
  class E : C {}
 class F {}
 
 CCT!(E, D) // == C
 CCT!(E, C) // == C
 CCT!(E, B) // == A
 CCT!(E, A) // == A
 CCT!(E, F) // == object



That sounds like the kind of thing that you're supposed to be able to 
get from typeof(true?E.init:D.init), but I seem to recall a bug filed by 
  Andrei the other day saying it doesn't work properly for classes.

--bb
May 16 2008
prev sibling parent reply Manfred Nowak <svv1999 hotmail.com> writes:
BCS wrote:


 CCT!(E, D) // == C
 CCT!(E, C) // == C
 CCT!(E, B) // == A
 CCT!(E, A) // == A
 CCT!(E, F) // == object



To give it a name:
it's the lowest common ancestor (LCA) in the derivation tree.

-manfred
May 16 2008
parent reply BCS <ao pathlink.com> writes:
Reply to Manfred,


 BCS wrote:
 

 CCT!(E, D) // == C
 CCT!(E, C) // == C
 CCT!(E, B) // == A
 CCT!(E, A) // == A
 CCT!(E, F) // == object



 it's the lowest common ancestor (LCA) in the derivation tree.
 -manfred
 



or highest common ancestor (HCL), depending on how you draw your trees.

How about, Closest Common Ancestor (CCL)
May 16 2008
parent Manfred Nowak <svv1999 hotmail.com> writes:
BCS wrote:

 depending on how you draw your trees. 



That's also true for 'close'. :-)

-manfred
May 16 2008
prev sibling parent reply BCS <ao pathlink.com> writes:
with a little insight from #D:

template ExtractClass(T...)
{
	static if(T.length > 0)
	{
		static if(is(T[0] P == class)) alias P ExtractClass;
		else      alias ExtractClass!(T[1..$]) ExtractClass;
	}
	else static assert(false);
}

template BaseClass(T)
{
	static if(is(T _ == class) && !is(_ == Object) && is(T BaseT == super))
		alias ExtractClass!(BaseT) BaseClass;
	else static assert(false);
}

template CCT2(T,U)
{
	static if(is(T _ == class) && is(U __ == class))
	{
		static if (is(T : U))      alias U CCT2;
		else static if (is(U : T)) alias T CCT2;
		else  alias CCT2!(BaseClass!(T),U) CCT2;
	}
	else static assert(false);
}

template CCT(T...)
{
	static if(T.length > 1)       alias CCT!(CCT2!(T[0..2]), T[2..$]) CCT;
	else static if(T.length == 1) alias T[0] CCT;
	else static assert(false);
}


class A {}
class B : A {}
class C : A {}
class D : C {}
class E : C {}
class F {}


static assert(is(CCT!(E, D) == C));
static assert(is(CCT!(E, C) == C));
static assert(is(CCT!(E, B) == A));
static assert(is(CCT!(E, A) == A));
static assert(is(CCT!(E, F) == Object));
May 16 2008
next sibling parent BCS <ao pathlink.com> writes:
rename it as you please <G>
May 16 2008
prev sibling parent reply Manfred Nowak <svv1999 hotmail.com> writes:
BCS wrote:


 with a little insight from #D:




Would you please describe your (hopefully) real world case of usage.

I beg for this, because your algorithm has a worst case lower bound for 
the run time of
|   Omega( n * N)
and---if N is fixed---the fastet algorithm has a worst case lower bound 
for the runtime of
|   Omega( n + N);
where n is the number of queries to the derivation tree and N is the 
number of nodes in the derivation tree.

-manfred
May 17 2008
parent BCS <ao pathlink.com> writes:
Reply to Manfred,


 BCS wrote:
 

 with a little insight from #D:
 



 
 Would you please describe your (hopefully) real world case of usage.
 
 I beg for this, because your algorithm has a worst case lower bound
 for
 the run time of
 |   Omega( n * N)
 and---if N is fixed---the fastet algorithm has a worst case lower
 bound
 for the runtime of
 |   Omega( n + N);
 where n is the number of queries to the derivation tree and N is the
 number of nodes in the derivation tree.
 -manfred
 



It's part of my dparse engine. As it is each parse function returns a PObject 
that the user than has to downcast to whatever it should be, I want to have 
the parse function compute the most derived type that it can return based 
on the types returned form the different options.
May 17 2008