digitalmars.D.learn - Closest Common Type
- BCS (5/5) May 16 2008 I have a tuple of types, I want a template that evaluates to the most sp...
- Lutger (3/9) May 16 2008 tango.core.Tuple and std.typetuple have templates called MostDerived and
- BCS (14/26) May 16 2008 I might be able to use somthing like that as a starting point but what I...
- Bill Baxter (5/36) May 16 2008 That sounds like the kind of thing that you're supposed to be able to
- Manfred Nowak (4/9) May 16 2008 To give it a name:
- BCS (3/14) May 16 2008 or highest common ancestor (HCL), depending on how you draw your trees.
- Manfred Nowak (3/4) May 16 2008 That's also true for 'close'. :-)
- BCS (43/43) May 16 2008 with a little insight from #D:
-
BCS
(1/1)
May 16 2008
rename it as you please
- Manfred Nowak (12/13) May 17 2008 [...]
- BCS (5/25) May 17 2008 It's part of my dparse engine. As it is each parse function returns a PO...
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
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
Reply to Lutger,BCS wrote: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) // == objectI 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
BCS wrote:Reply to Lutger,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. --bbBCS wrote: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) // == objectI 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
BCS wrote:CCT!(E, D) // == C CCT!(E, C) // == C CCT!(E, B) // == A CCT!(E, A) // == A CCT!(E, F) // == objectTo give it a name: it's the lowest common ancestor (LCA) in the derivation tree. -manfred
May 16 2008
Reply to Manfred,BCS wrote:or highest common ancestor (HCL), depending on how you draw your trees. How about, Closest Common Ancestor (CCL)CCT!(E, D) // == C CCT!(E, C) // == C CCT!(E, B) // == A CCT!(E, A) // == A CCT!(E, F) // == objectTo give it a name: it's the lowest common ancestor (LCA) in the derivation tree. -manfred
May 16 2008
BCS wrote:depending on how you draw your trees.That's also true for 'close'. :-) -manfred
May 16 2008
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
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
Reply to Manfred,BCS wrote: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.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