Puzzling OO design problem

[Kay Schluehr]

Hi George,

it's a nice little puzzle and it is more fun to solve it if one is not
a student anymore :)

Filling the gaps in the lattice is somehow necessary but it is not
necessary to create all the classes.

Ansatz:

We can consider two matrices: one is filled with nodes ( class names )
the other is filled with arrows between the nodes representing the
inheritance relationships.

In symbolic notatation:

        | A  B  C |
Nodes = | D  0  F |
        | G  H  I |

         | 0   l    l  |
Arrows = | u   0   u*l |
         | u  u*l  u*l |


Remarks:
1 ) if a node or an arrow is empty a 0 is inserted into the matrix.

2 ) u is for uppermost, l is for leftmost. A multiplication between
    arrows should read as a logical AND: u*l ~ upper AND left.

With this interpretation the above matrizes contains the same
information than the lattice:

A <- B <- C
^    ^    ^
|    |    |
D <- 0 <- F
^    ^    ^
|    |    |
G <- H <- I

Now we need an algorithm to create all the classes from the matrix
information using multiple inheritance when needed:


# arrows symbolized as primes. Only u and l are used in the impl.
# d and r are somewhat more complicated to implement

l = 2
r = 3
u = 5
d = 7

class ClassGridError(Exception):pass

class ClassGrid(object):
    def __init__(self):
       self.class_names = []  # rows of the class-name matrix
       self.arrows      = []  # rows of the arrow matrix
       self.classes     = {}  # store the resulting classes

    def add_names(self,names):
        self.class_names.append(names)

    def add_arrow(self,arrow):
        self.arrows.append(arrow)

    def __repr__(self):
        if self.classes:
            return self.classes.__repr__()
        return object.__repr__(self)

    def create_classes(self):
        for i,class_row in enumerate(self.class_names):
            for j,cls_name in enumerate(class_row):
                if cls_name == 0:
                    continue
                arrow = self.arrows[i][j]
                if arrow == 0:
                   self.classes[cls_name] = type(cls_name,(),{})
                else:
                   bases = []
                   name  = 0
                   if arrow%u == 0:   # search uppermost
                      k = i-1
                      while k>=0:
                         name = self.class_names[k][j]
                         if name:
                            break
                         k-=1
                      if not name:
                         raise ClassGridError,"Wrong arrow matrix"
                      bases.append(self.classes[name])
                   if arrow%l == 0:  # search leftmost
                      k = j-1
                      while k>=0:
                         name = self.class_names[i][k]
                         if name:
                            break
                         k-=1
                      if not name:
                         raise ClassGridError,"Wrong arrow matrix"
                      bases.append(self.classes[name])
                   self.classes[cls_name] =
type(cls_name,tuple(bases),{})

cg = ClassGrid()

cg.add_names(("A","B","C"))
cg.add_names(("D", 0, "F"))
cg.add_names(("G","H","I"))

cg.add_arrow(( 0,  l,   l ))
cg.add_arrow(( u,  0,  u*l))
cg.add_arrow(( u, u*l, u*l))

cg.create_classes()

Now You can checkout Your solution:

>>> cg.classes["A"].__subclasses__()
[<class '__main__.B'>, <class '__main__.D'>]

>>> cg.classes["B"].__subclasses__()
[<class '__main__.C'>, <class '__main__.H'>]

>>> cg.classes["C"].__subclasses__()
[<class '__main__.F'>]

>>> cg.classes["D"].__subclasses__()
[<class '__main__.F'>, <class '__main__.G'>]

>>> cg.classes["F"].__subclasses__()
[<class '__main__.I'>]

>>> cg.classes["G"].__subclasses__()
[<class '__main__.H'>]

>>> cg.classes["H"].__subclasses__()
[<class '__main__.I'>]

>>> cg.classes["I"].__subclasses__()
[]

Ciao,
Kay