Java Forum / General / July 2006
Find nearest common superclass
Robert Dodier - 20 Jul 2006 23:58 GMT Hello,
Given a collection of classes, how can I find their nearest common superclass?
It seems like it would be simple enough -- maybe something which iterates over a pair-wise comparison such as this:
static Class commonSuperclass (Class c1, Class c2) { if (c1.isAssignableFrom (c2)) return c1;
if (c2.isAssignableFrom (c1)) return c2;
return commonSuperclass (c1.getSuperclass (), c2.getSuperclass ()); }
But it seems likely there are pitfalls which would affect a naive implementation. So I'm hoping this is a wheel which doesn't need reinvention today. Any info is appreciated.
Robert Dodier
Ingo R. Homann - 21 Jul 2006 08:04 GMT Hi,
> Hello, > [quoted text clipped - 14 lines] > > But it seems likely there are pitfalls I see two pitfalls:
(1) Consider D extends C which B extends A extends Object and Z extends B extends Object. The common superclass of Z and D is C, but it will not be found (because their hierarchies have a different depth)!
(2) I do not know if you need this, but the common super*type* could also be an interface implemented by both classes. You do not consider this.
A solution for (1) would be to write a method that returns a Set of tupels of (superclass,depth) and to find the superclass with the lowest depth within the list of common superclasses (pseudocode):
void commonSuperclasses(Class c1, Class c2, int depth, Set<Tupel<Class,int>> superclasses) { if (c1.isAssignableFrom (c2)) { superclasses.add(new Tupel(c1,depth)); return; } if (c2.isAssignableFrom (c1)) { superclasses.add(new Tupel(c2,depth)); return; } commonSuperclasses(c1.getSuperClass(),c2,depth+1,superclass); commonSuperclasses(c1,c2.getSuperClass(),depth+1,superclass); }
Finding the Class with the lowest depth and correctly avoiding NPE's when class Object is reached, is left to the reader! :-)
Note that I would think that such a method existed somewhere in java.lang.reflect...
Ciao, Ingo
Piotr Kobzda - 21 Jul 2006 08:36 GMT > Hi, > [quoted text clipped - 22 lines] > B extends Object. The common superclass of Z and D is C, but it will > not be found (because their hierarchies have a different depth)! class D extends C {}; class C extends B {}; class B extends A {}; class A {}; class Z extends B {}; // B extends Object indirectly
Common superclass for Z and D is B, not C.
Of course, Robert's algorithm will not find that.
> (2) I do not know if you need this, but the common super*type* could > also be an interface implemented by both classes. You do not consider this. [quoted text clipped - 19 lines] > Finding the Class with the lowest depth and correctly avoiding NPE's > when class Object is reached, is left to the reader! :-) IMHO better solution for (2) would be:
public static Class commonSuperclass(Class... classes) { Class<?> rc = null; for(int i = 0; i < classes.length; ++i) { Class<?> tc = classes[i]; if (tc == null || tc.isInterface()) continue; // or (better) throw an exception if (rc == null) { rc = tc; } else { while (! rc.isAssignableFrom(tc)) rc = rc.getSuperclass(); } if (rc == Object.class) break; } return rc; }
piotr
Ingo R. Homann - 21 Jul 2006 08:45 GMT Hi,
> Common superclass for Z and D is B, not C. Of course. Sorry, that was a simple typo!
>> Finding the Class with the lowest depth and correctly avoiding NPE's >> when class Object is reached, is left to the reader! :-) [quoted text clipped - 18 lines] > return rc; > } Look good, I think.
But I assume it is only a solution for (1), not for (2). (Typo? :-)
Ciao, Ingo
Piotr Kobzda - 21 Jul 2006 11:01 GMT > Look good, I think. > > But I assume it is only a solution for (1), not for (2). (Typo? :-) Typo of course :)
For (2) the solution is not as simple as provided one, it would be something like this:
public static Set<Class> commonSupertypes(Class... classes) { Set<Class> rs = new HashSet<Class>(); // callect all types of each class for(Class clazz : classes) { for(Class c = clazz; c != null; c = c.getSuperclass()) { rs.add(c); collectInterfacesOf(c, rs); } } // remove uncommon types from rs for(Iterator<Class> it = rs.iterator(); it.hasNext(); ) { Class<?> rc = it.next(); for(Class clazz : classes) { if (! rc.isAssignableFrom(clazz)) { it.remove(); break; } } } // remove redundant types from rs for(Iterator<Class> it = rs.iterator(); it.hasNext(); ) { Class<?> tc = it.next(); for(Class rc : rs) { if (tc != rc && tc.isAssignableFrom(rc)) { it.remove(); break; } } } return rs; }
private static void collectInterfacesOf(Class c, Set<Class> rs) { for(Class i : c.getInterfaces()) { rs.add(i); collectInterfacesOf(i, rs); } }
piotr
Chris Uppal - 21 Jul 2006 09:57 GMT > Class<?> tc = classes[i]; > if (tc == null || tc.isInterface()) > continue; // or (better) throw an exception I think array classes, and the Class objects corresponding to the primitive types, will also require special attention.
And let's not even mention generics ;-)
-- chris
Piotr Kobzda - 21 Jul 2006 11:17 GMT >> Class<?> tc = classes[i]; >> if (tc == null || tc.isInterface()) >> continue; // or (better) throw an exception > > I think array classes, and the Class objects corresponding to the primitive > types, will also require special attention. You right. Unfortunately I can't tell precisely what the result shout be in such a cases.
> And let's not even mention generics ;-) A few generics mentioned are only to avoid compiler warnings during prototyping. In final solution probably forgetting about generics or using Class<?> instead of unparameterized Class would be enough.
piotr
Chris Uppal - 21 Jul 2006 12:33 GMT [me:]
> > I think array classes, and the Class objects corresponding to the > > primitive types, will also require special attention. > > You right. Unfortunately I can't tell precisely what the result shout > be in such a cases. Agreed.
> > And let's not even mention generics ;-) > > A few generics mentioned are only to avoid compiler warnings during > prototyping. In final solution probably forgetting about generics or > using Class<?> instead of unparameterized Class would be enough. I agree with that too, but that might not be what the OP wanted.
FWIW, I'll append my attempt at this. Largely untested....
-- chris
====== LeastCommonSuperclass.java ========= public class LeastCommonSuperclass { // We implement the following rules: // LCS of null and any type is null. // LCS of interface and any class is the interface if the class implements // it, or Object otherwise. // LCS of interface and any other interface is whichever interface // extends (including indirectly) the other one, or Object if // neither does. // LCS of primitive type and any distinct type is null. // LCS of array type and any distinct class is Object.
public static Class<?> of(Class<?>... classes) { Class<?> retval = classes[0]; // exception if size == 0 for (Class<?> cl : classes) retval = of(retval, cl); return retval; }
public static Class<?> of(Class<?> class1, Class<?> class2) { if (class1 == class2) return class1; if (class1 == null || class2 == null) return null; if (!class1.isArray() && class1.isAssignableFrom(class2)) return class1; if (!class2.isArray() && class2.isAssignableFrom(class1)) return class2; if (class1.isInterface() || class2.isInterface()) return Object.class; return of(class1.getSuperclass(), class2.getSuperclass()); } } ===========================================
Piotr Kobzda - 21 Jul 2006 14:52 GMT > FWIW, I'll append my attempt at this. Largely untested.... After rethinking it, I have extended my attempt:
public static Class<?> commonSuperclass(Class<?>... classes) { for(Class<?> tc : classes) if (tc == null) throw new NullPointerException(); Class<?> rc = null; for(Class<?> tc : classes) { if (tc.isInterface() || tc.isPrimitive()) return null; // no superclasses if (rc == null) { rc = tc; } else { while (! rc.isAssignableFrom(tc)) rc = rc.getSuperclass(); } } return rc; }
It seems to be similar to your approach in most assumptions except the one for the interfaces.
Interfaces have no superclasses (getSuperclass() returns null), so when a single Class object (representing interface) has no superclass, all input classes can not have common superclass either.
piotr
Piotr Kobzda - 21 Jul 2006 13:58 GMT >> I see two pitfalls: >> [quoted text clipped - 11 lines] > > Of course, Robert's algorithm will not find that. Not true. Robert's algorithm will do that too. This is in fact the same algorithm Chris and me implemented in our attempts. The only difference is that Robert and Chris have it implemented recursively, my implementation is iterative approach.
The all difficulties holds here in special cases which Chris has pointed out before, and tried to resolve later in his implementation.
piotr
Hendrik Maryns - 21 Jul 2006 14:12 GMT Piotr Kobzda schreef:
>>> I see two pitfalls: >>> [quoted text clipped - 13 lines] > > Not true. Not true (logic’s double negation). Robert’s algorithm does not have a check whether one of the two arguments is a superclass of the other.
> Robert's algorithm will do that too. It will, if that check is added.
H. - -- Hendrik Maryns
================== http://aouw.org Ask smart questions, get good answers: http://www.catb.org/~esr/faqs/smart-questions.html
Piotr Kobzda - 21 Jul 2006 15:02 GMT > Robert’s algorithm does not have a > check whether one of the two arguments is a superclass of the other. Not true. Robert's algorithm check all of this things:
// check if a first argument is a superclass of a second one if (c1.isAssignableFrom (c2)) return c1; // check if a second argument is a superclass of a first one if (c2.isAssignableFrom (c1)) return c2;
piotr
Robert Dodier - 21 Jul 2006 17:31 GMT Thanks to everyone who replied. I have found this works OK in practice:
> static Class commonSuperclass (Class c1, Class c2) > { [quoted text clipped - 4 lines] > return commonSuperclass (c1.getSuperclass (), c2.getSuperclass ()); > } Interfaces and array types aren't recognized by this, but in those cases I can't see that there is any workable answer ... e.g. given interfaces X and Y and classes A and B which both implement X and Y, there isn't a unique common supertype. Likewise in array types, a superclass/subclass relation among classes C and D doesn't imply any relationship between arrays of C and arrays of D.
For the time being it is OK for me just to work with ordinary classes, so although it is an interesting question I'll just let it go for now.
best, Robert Dodier
Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
|
|