Find nearest common superclass

[Robert Dodier]

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]

Hi,

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

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]

Hi,



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)!

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.

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!

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;
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]

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!

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;
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;
}

Look good, I think.

But I assume it is only a solution for (1), not for (2). (Typo?

Ciao,
Ingo

 

[Chris Uppal]

Class<?> tc = classes;
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]

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

 

[Piotr Kobzda]

Class<?> tc = classes;
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]

Piotr Kobzda wrote:

[me:]

You right. Unfortunately I can't tell precisely what the result shout
be in such a cases.
Agreed.


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]

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.

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]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Piotr Kobzda schreef:

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
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFEwNK8e+7xMGD3itQRAraBAJ9ipBOLwUR0zbO2I5cnlUOwAzLkOACfb/YE
SCduhGXe4DZqmj0WR4/I+YU=
=Qq1z
-----END PGP SIGNATURE-----

 

[Piotr Kobzda]

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]

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]

Thanks to everyone who replied. I have found this works OK in practice:

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 ());
}

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

 

[hipa]

I recently had the same problem while trying to get the common class of the Java method compiled by Javassist (the common class of design-time available information about return instructions of a method). Here is the complete solution.

private static final Collection<Class<?>> UNDEFINED;
static
{
    List<Class<?>> l = new ArrayList<Class<?>>();
    l.add(Object.class);
    UNDEFINED = Collections.unmodifiableList(l);
}

private static void addAncestors(Collection<Class<?>> ancestors, Class<?> clazz)
{
    if (ancestors.contains(clazz))
    {
        return;
    }

    ancestors.add(clazz);

    for (Class<?> i : clazz.getInterfaces())
    {
        addAncestors(ancestors, i);
    }

    Class<?> sc = clazz.getSuperclass();
    if (sc != null)
    {
        addAncestors(ancestors, sc);
    }
}

private static Collection<Class<?>> getAncestors(Class<?> clazz)
{
    Set<Class<?>> set = new HashSet<Class<?>>();

    addAncestors(set, clazz);

    return set;
}

private static Collection<Class<?>> getNearestCommonSuperclasses(Collection<Class<?>> classes)
{
    Iterator<Class<?>> it = classes.iterator();
    if (!it.hasNext())
    {
        return UNDEFINED;
    }

    // Get possible candidates
    Collection<Class<?>> ancestors = getAncestors(it.next());

    // Remove uncommon ancestors
    while (it.hasNext())
    {
        Class<?> c = it.next();
        ancestors.retainAll(getAncestors(c));

        // java.lang.Object
        if (ancestors.size() == 1)
        {
            return ancestors;
        }
    }

    Set<Class<?>> remove = new HashSet<Class<?>>();

    // Remove the ancestors that have descendants in the list
    for (Class<?> c : ancestors)
    {
        if (remove.contains(c))
        {
            continue;
        }

        Collection<Class<?>> a = getAncestors(c);
        a.remove(c);

        remove.addAll(a);
    }

    ancestors.removeAll(remove);

    // At least java.lang.Object should be here
    return ancestors;
}

The classes graph is not a tree so the common ancestor may be not unique. However the classes graph is a directed acyclyc graph therefore there always exists the lowest common ancestor of a set of the classes. The algorithm used seems to be naive so optimization advices would be appreciated Also primitive types are not supported because in my situation it's an impossible case.