1188 GENERICITY VERSUS INHERITANCE $B.7 B.7 BIBLIOGRAPHICAL NOTES The material for this chapter originated with an article at the first OOPSLA conference [M 1986].The Trellis language [Schaffert 1986]also offered the combination of multiple inheritance with constrained and unconstrained genericity EXERCISES E-B.1 Artificial anchors The artificial anchor anchor is declared as an attribute of class MATRIX and thus entails a small run-time space overhead in instances of the class.Is it possible to avoid this overhead by declaring anchor as a"once function",whose body may be empty since it will never need to be evaluated?(Hint:consider type rules.) E-B.2 Binary trees and binary search trees Write a generic "binary tree"class BINARY TREE;a binary tree (or binary node)has some root information and two optional subtrees,left and right.Then consider the notion of"binary search tree"where a new element is inserted on the left of a given node if its information field is less than or equal to the information of that node,and to the right otherwise;this assumes that there is a total order relation on"informations".Write a class BINARY SEARCH TREE implementing this notion,as a descendant of BINARY TREE. Make the class as general as possible,and its use by a client,for an arbitrary type of "informations"with their specific order relation,as easy as possible. E-B.3 More usable matrices Add to the last version obtained for class MATRIX two functions,one for access and one for modification,which in contrast to item and put will allow clients to manipulate a matrix of type MATRIXY [G]in terms of elements of type G rather than RING_ELEMENT [G]. E-B.4 Full queue implementations Expand the queue example by defining a deferred class OUEUE,completing the class of this chapter(now called ARRAYED OUEUE,inheriting from OUEUE and ARRAY,and with proper postconditions),and adding a class LINKED_OUEUE for the linked list implementation (based on inheritance from LINKED LIST and OUEUE).1188 GENERICITY VERSUS INHERITANCE §B.7 B.7 BIBLIOGRAPHICAL NOTES The material for this chapter originated with an article at the first OOPSLA conference [M 1986]. The Trellis language [Schaffert 1986] also offered the combination of multiple inheritance with constrained and unconstrained genericity. EXERCISES E-B.1 Artificial anchors The artificial anchor anchor is declared as an attribute of class MATRIX and thus entails a small run-time space overhead in instances of the class. Is it possible to avoid this overhead by declaring anchor as a “once function”, whose body may be empty since it will never need to be evaluated? (Hint: consider type rules.) E-B.2 Binary trees and binary search trees Write a generic “binary tree” class BINARY_TREE; a binary tree (or binary node) has some root information and two optional subtrees, left and right. Then consider the notion of “binary search tree” where a new element is inserted on the left of a given node if its information field is less than or equal to the information of that node, and to the right otherwise; this assumes that there is a total order relation on “informations”. Write a class BINARY_SEARCH_TREE implementing this notion, as a descendant of BINARY_TREE. Make the class as general as possible, and its use by a client, for an arbitrary type of “informations” with their specific order relation, as easy as possible. E-B.3 More usable matrices Add to the last version obtained for class MATRIX two functions, one for access and one for modification, which in contrast to item and put will allow clients to manipulate a matrix of type MATRIX [G] in terms of elements of type G rather than RING_ELEMENT [G]. E-B.4 Full queue implementations Expand the queue example by defining a deferred class QUEUE, completing the class of this chapter (now called ARRAYED_QUEUE, inheriting from QUEUE and ARRAY, and with proper postconditions), and adding a class LINKED_QUEUE for the linked list implementation (based on inheritance from LINKED_LIST and QUEUE)