Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / July 2006

Tip: Looking for answers? Try searching our database.

Find nearest common superclass

Thread view: 
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 Magazines

Get 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 ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.