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