524 MULTIPLE INHERITANCE $15.1 Multiple COMPARABLE NUMERIC structure inheritance INTEGER REAL DOUBLE Windows are trees and rectangles Assume a window system that allows nesting windows to an arbitrary depth: Windows and subwindows In the corresponding class WINDOW,we will find features of two general kinds: Some deal with a window as a member of a hierarchical structure:list of subwindows,parent window,number of subwindows,add or remove a subwindow. Others cover its properties as a graphical object occupying a graphical area:height, width,x position,y position,display,hide,translate
524 MULTIPLE INHERITANCE §15.1 Windows are trees and rectangles Assume a window system that allows nesting windows to an arbitrary depth: In the corresponding class WINDOW, we will find features of two general kinds: • Some deal with a window as a member of a hierarchical structure: list of subwindows, parent window, number of subwindows, add or remove a subwindow. • Others cover its properties as a graphical object occupying a graphical area: height, width, x position, y position, display, hide, translate. INTEGER COMPARABLE NUMERIC REAL DOUBLE Multiple structure inheritance Windows and subwindows
$15.1 EXAMPLES OF MULTIPLE INHERITANCE 525 It is possible to write the class as a single piece,with all these features mixed together.But this would be bad design.To keep the structure manageable we should separate the two aspects,treating class WINDOW as the combination of two abstractions: Hierarchical structures,which should be covered by a class TREE. Rectangular screen objects,covered by a class RECTANGLE. In practice we may need more specific class names(describing some particular category of trees,and a graphical rather than purely geometrical notion of rectangle),but the ones above will be convenient for this discussion.WINDOW will appear as: class WINDOW inherit TREE [WINDOW] RECTANGLE feature ..Specific window features... end Note that class TREE will be generic,so we need to specify an actual generic parameter,here WINDOW itself.The recursive nature of this definition reflects the recursion in the situation modeled:a window is a tree of windows. This example will,later on in the discussion,help us understand the need for a feature renaming mechanism associated with inheritance. A further refinement might follow from the observation that some windows are purely text windows.Although we might represent this property by introducing a class TEXT WINDOW as a client of STR/NG with an attribute text:STRING we may prefer to consider that each text window is also a string.In this case we will use multiple inheritance from WINDOW and STR/NG.(If all windows of interest are text windows,we might directly use triple inheritance from TREE,RECTANGLE and STRING,although even in that case it is probably better to work in two successive stages. See“WOULD YOU The general question of how to choose between heir and client relations,as in the RATHER BUY OR INHERIT?”,24.2 case of TEXT WINDOW,is discussed in detail in the chapter on inheritance methodology. page 812. Trees are lists and list elements Class TREE itself provides a striking example of multiple inheritance. A tree is a hierarchical structure made of nodes,each containing some information. Common definitions tend to be of the form "A tree is either empty or contains an object called the root,together with(recursively)a list of trees,called the children of the root", complemented by a definition of node,such as"An empty tree has no nodes;the nodes of a non-empty tree comprise its root and (recursively)the nodes of its children".Although useful,and reflective of the recursiveness inherent in the notion of tree,these definitions fail to capture its essential simplicity
§15.1 EXAMPLES OF MULTIPLE INHERITANCE 525 It is possible to write the class as a single piece, with all these features mixed together. But this would be bad design. To keep the structure manageable we should separate the two aspects, treating class WINDOW as the combination of two abstractions: • Hierarchical structures, which should be covered by a class TREE. • Rectangular screen objects, covered by a class RECTANGLE. In practice we may need more specific class names (describing some particular category of trees, and a graphical rather than purely geometrical notion of rectangle), but the ones above will be convenient for this discussion. WINDOW will appear as: class WINDOW inherit TREE [WINDOW] RECTANGLE feature … Specific window features … end Note that class TREE will be generic, so we need to specify an actual generic parameter, here WINDOW itself. The recursive nature of this definition reflects the recursion in the situation modeled: a window is a tree of windows. This example will, later on in the discussion, help us understand the need for a feature renaming mechanism associated with inheritance. A further refinement might follow from the observation that some windows are purely text windows. Although we might represent this property by introducing a class TEXT_WINDOW as a client of STRING with an attribute text: STRING we may prefer to consider that each text window is also a string. In this case we will use multiple inheritance from WINDOW and STRING. (If all windows of interest are text windows, we might directly use triple inheritance from TREE, RECTANGLE and STRING, although even in that case it is probably better to work in two successive stages.) The general question of how to choose between heir and client relations, as in the case of TEXT_WINDOW, is discussed in detail in the chapter on inheritance methodology. Trees are lists and list elements Class TREE itself provides a striking example of multiple inheritance. A tree is a hierarchical structure made of nodes, each containing some information. Common definitions tend to be of the form “A tree is either empty or contains an object called the root, together with (recursively) a list of trees, called the children of the root”, complemented by a definition of node, such as “An empty tree has no nodes; the nodes of a non-empty tree comprise its root and (recursively) the nodes of its children”. Although useful, and reflective of the recursiveness inherent in the notion of tree, these definitions fail to capture its essential simplicity. See “WOULD YOU RATHER BUY OR INHERIT?”, 24.2, page 812
526 MULTIPLE INHERITANCE $15.1 To get a different perspective,observe that there is no significant distinction between the notion of tree and that ofnode,as we may identify a node with the subtree of which it is the root.This suggests aiming for a class TREE [G]that describes both trees and nodes. The formal generic parameter G represents the type of information attached to every node; the tree below,for example,is an instance of TREE [INTEGER]. 89 A tree of integers 235 30 0 5 1000 Now consider a notion of L/S7,with a class that has been sketched in earlier chapters.A general implementation (linked,for example)will need an auxiliary class CELL to describe the individual elements of a list. LIST (CELL) These notions suggest a simple definition of trees:a tree (or tree node)is a list,the list of its children;but it is also a potential list element,as it can be made into a subtree of another tree. Definition:tree A tree is a list that is also a list element. Although this definition would need some refinement to achieve full mathematical rigor,it directly yields a class definition: deferred class TREE [G]inherit LIST G] CELL [G] feature end From L/ST come the features to find out the number of children (counr),add a child, remove a child and so on. From CELL come the features having to do with a node's siblings and parents:next sibling,add a sibling,reattach to a different parent node
526 MULTIPLE INHERITANCE §15.1 To get a different perspective, observe that there is no significant distinction between the notion of tree and that of node, as we may identify a node with the subtree of which it is the root. This suggests aiming for a class TREE [G] that describes both trees and nodes. The formal generic parameter G represents the type of information attached to every node; the tree below, for example, is an instance of TREE [INTEGER]. Now consider a notion of LIST, with a class that has been sketched in earlier chapters. A general implementation (linked, for example) will need an auxiliary class CELL to describe the individual elements of a list. These notions suggest a simple definition of trees: a tree (or tree node) is a list, the list of its children; but it is also a potential list element, as it can be made into a subtree of another tree. Although this definition would need some refinement to achieve full mathematical rigor, it directly yields a class definition: deferred class TREE [G] inherit LIST [G] CELL [G] feature … end From LIST come the features to find out the number of children (count), add a child, remove a child and so on. From CELL come the features having to do with a node’s siblings and parents: next sibling, add a sibling, reattach to a different parent node. Definition: tree A tree is a list that is also a list element. A tree of integers 89 235 –2 30 –1 0 5 1000 (CELL) LIST
$15.1 EXAMPLES OF MULTIPLE INHERITANCE 527 This example is typical of the reusability benefits of multiple inheritance.Writing specific features for subtree insertion or removal would needlessly replicate the work done for lists.Writing specific features for sibling and parent operations would needlessly replicate the work done for list elements.Only a facelift is needed in each case. In addition you will have to take care,in the feature clause,of the specific features of trees and of the little mutual compromises which,as in any marriage,are necessary to ensure that life together is harmonious and prolific.In a class TREE derived from these ideas,which has been used in many different applications(from graphics to structural editing),these specific features fit on little more than a page;for the most part,the class is simply engendered as the legitimate fruit of the union between lists and list elements. This process is exactly that used in mathematics to combine theories:a topological vector space,for example,is a vector space that also is a topological space;here too,some connecting axioms need to be added to finish up the merger. Composite figures The following example is more than an example;it is a design pattern useful in many different contexts. Consider an inheritance structure containing classes for various graphical figures, such as the one used in the preceding chapter to introduce some of the fundamental concepts of inheritance FIGURE,OPEN FIGURE,POLYGON,RECTANGLE, ELL/PSE and so on.So far,as you may have noted,that structure used single inheritance Assume that we have included in this hierarchy all the basic figure patterns that we need.That is not enough yet:many figures are not basic.Of course we could build any graphical illustration from elementary shapes,but that is not a convenient way to work; instead,we will want to build ourselves alibrary of figures,some basic,some constructed from the basic ones.For example,from basic segment and circle figures Elementary figures we may assemble a composite figure,representing a wheel A composite figure which someone may in turn use as a predefined pattern to draw,say,a bicycle;and so on
§15.1 EXAMPLES OF MULTIPLE INHERITANCE 527 This example is typical of the reusability benefits of multiple inheritance. Writing specific features for subtree insertion or removal would needlessly replicate the work done for lists. Writing specific features for sibling and parent operations would needlessly replicate the work done for list elements. Only a facelift is needed in each case. In addition you will have to take care, in the feature clause, of the specific features of trees and of the little mutual compromises which, as in any marriage, are necessary to ensure that life together is harmonious and prolific. In a class TREE derived from these ideas, which has been used in many different applications (from graphics to structural editing), these specific features fit on little more than a page; for the most part, the class is simply engendered as the legitimate fruit of the union between lists and list elements. This process is exactly that used in mathematics to combine theories: a topological vector space, for example, is a vector space that also is a topological space; here too, some connecting axioms need to be added to finish up the merger. Composite figures The following example is more than an example; it is a design pattern useful in many different contexts. Consider an inheritance structure containing classes for various graphical figures, such as the one used in the preceding chapter to introduce some of the fundamental concepts of inheritance — FIGURE, OPEN_FIGURE, POLYGON, RECTANGLE, ELLIPSE and so on. So far, as you may have noted, that structure used single inheritance. Assume that we have included in this hierarchy all the basic figure patterns that we need. That is not enough yet: many figures are not basic. Of course we could build any graphical illustration from elementary shapes, but that is not a convenient way to work; instead, we will want to build ourselves a library of figures, some basic, some constructed from the basic ones. For example, from basic segment and circle figures we may assemble a composite figure, representing a wheel which someone may in turn use as a predefined pattern to draw, say, a bicycle; and so on. Elementary figures A composite figure
528 MULTIPLE INHERITANCE $15.1 We need a general mechanism for adding a new figure type which will be built from previously defined ones but,once defined,will be on a par with them.Computer drawing tools provide a Group command for this purpose. Let us call the corresponding notion COMPOSITE FIGURE.A composite figure is clearly a figure;so COMPOSITE FIGURE should inherit from F/GURE,achieving the goal of treating composite figures"on a par"with basic ones.A composite figure is also a list of figures-its constituents;each of them may be basic or itself composite.Hence the use of multiple inheritance: A composite extent* display* FIGURE LINKED LIST figure is a barycenter* rotate* figure and a list of figures COMPOSITE OPEN CLOSED FIGURE perimeter* FIGURE FIGURE SEGMENT POLYLINE perinteter POLYGON ELLIPSE TRIANGLE diagonal OUADRANGLE CIRCLE perimeter perimeter BASIC sidel,side2 RECTANGLE FIGURES (see previous chapter) perimeter SQUARE To get an effective class for COMPOSITE F/GURE we choose an implementation of lists;LINKED L/ST is just one possibility.The class declaration will look like this:
528 MULTIPLE INHERITANCE §15.1 We need a general mechanism for adding a new figure type which will be built from previously defined ones but, once defined, will be on a par with them. Computer drawing tools provide a Group command for this purpose. Let us call the corresponding notion COMPOSITE_FIGURE. A composite figure is clearly a figure; so COMPOSITE_FIGURE should inherit from FIGURE, achieving the goal of treating composite figures “on a par” with basic ones. A composite figure is also a list of figures — its constituents; each of them may be basic or itself composite. Hence the use of multiple inheritance: To get an effective class for COMPOSITE_FIGURE we choose an implementation of lists; LINKED_LIST is just one possibility. The class declaration will look like this: A composite figure is a figure and a list of figures OPEN_ FIGURE SEGMENT POLYLINE POLYGON ELLIPSE QUADRANGLE TRIANGLE CIRCLE display* rotate* extent* … barycenter* perimeter* perimeter+ diagonal SQUARE perimeter++ perimeter++ perimeter+ CLOSED_ FIGURE FIGURE RECTANGLE perimeter++ side1, side2 ∗ ∗ ∗ COMPOSITE_ FIGURE LINKED_LIST BASIC FIGURES (see previous chapter)