Largest shared superclass
Is there an easy way to get the "largest shared superclass" in a list of objects? For example, if
class A(object): pass
class B(A): pass
class C(A): pass
class D(B, C): pass
class E(C): pass
class F(D, E): pass
and
b = B()
d = D()
e = E()
then
gcs(b, e) is A
gcs(d, e) is C
gcs(e, e) is E
source to share
Based on Martijn's idea, but using a simpler approach, given that time complexity won't be an issue here (thanks to @veedrac for his inputs):
def gcs(*instances):
classes = [type(x).mro() for x in instances]
for x in classes[0]:
if all(x in mro for mro in classes):
return x
print gcs(b, e)
print gcs(d, e)
print gcs(e, e)
Output:
<class '__main__.A'>
<class '__main__.C'>
<class '__main__.E'>
A small variation of the above code using sets:
def gcs(*instances):
mros = (type(ins).mro() for ins in instances)
mro = next(mros)
common = set(mro).intersection(*mros)
return next((x for x in mro if x in common), None)
source to share
This is essentially a simplified problem with a long and generic subsequence; compare the MRO sequences and return the type with the smallest sum of their indices:
def gcs(a, b):
"""Find the common base class between two classes or instances"""
try:
a, b = a.mro(), b.mro()
except AttributeError:
a, b = type(a).mro(), type(b).mro()
a_idx, b_idx = {t: i for i, t in enumerate(a)}, {t: i for i, t in enumerate(b)}
try:
return min(a_idx.viewkeys() & b_idx.viewkeys(),
key=lambda t: a_idx[t] + b_idx[t])
except ValueError:
return None
This is an O (M + N) algorithm, where M and N are the MRO sizes of both objects. The function can handle both classes and instances.
Demo with your sample objects:
>>> gcs(e, b)
<class '__main__.A'>
>>> gcs(e, d)
<class '__main__.C'>
>>> gcs(e, e)
<class '__main__.E'>
source to share
I think one problem is that you can have more than one largest common superclass - take a class inheritance structure like
AB ---> A
\ /
x
/ \
BA ---> B
In this case, both A
and B
are legitimate answers to gca([AB, BA])
.
After facing this in my own code, I realized that I needed to revisit the question:
Find the minimum set of common databases shared by the specified list of classes; defined as all classes that 1) are the parent class of everything in the original list and 2) do not have NO subclasses, which are also included in the returned list.
This last requirement takes care of getting only the "closest" class, but handles the case when there are multiple such values.
The following code implements the following:
def minimal_common_bases(classes):
# pull first class, and start with it bases
gen = iter(classes)
cls = next(gen, None)
if cls is None:
return set()
common = set(cls.__mro__)
# find set of ALL ancestor classes,
# by intersecting MROs of all specified classes
for cls in gen:
common.intersection_update(cls.__mro__)
# remove any bases which have at least one subclass also in the set,
# as they aren't part of "minimal" set of common ancestors.
result = common.copy()
for cls in common:
if cls in result:
result.difference_update(cls.__mro__[1:])
# return set
return result
- NOTE. In the py2 section, you need to use
inspect.getmro(cls)
insteadcls.__mro__
.
source to share