Martin Chetlen—a professor at Moorpark Community College in Moorpark, CA—contacted me, and we had the following conversation which you might find interesting.
MC: For several years I have used your Walls and Mirrors 5th edition text in my Data Structures class. I am now using the 6th edition. I do have several questions about the text that I would like to get your feedback on.
The text classes (such as the LinkedList class) which use dynamic memory do not overload the assignment operator. This would seem to allow a client of the class to be able to make a copy of an object using a shallow copy which can lead to significant errors. Is there something I am missing here?
FMC: Chapter 4 introduces the concepts of shallow copy and deep copy when it presents LinkedBag. The copy constructor for this class performs a deep copy and does everything that operator= would do. But we do not introduce operator overloading until C++ Interlude 5, which occurs between Chapters 14 and 15. We are trying to control the pace of the introduction of new concepts and keep the focus on the data structures. If your students have a strong C++ background already, you certainly could talk about overloading the assignment operator earlier than the book does.
MC: I understand your approach now. Students who take our DS course must have completed our O-O programming course, therefore they have had operator overloading. In both the pre-requisite course and the DS course, I emphasize the need to have certain member functions when a class uses dynamic memory. Hence the concern about overloading the assignment operator.
The SortedListIsA class methods insert and setEntry that can corrupt the sorted list are overridden. However, returning false or throwing an exception might be an unpleasant surprise to a client. When public inheritance is used, would a better way be to make those methods protected thereby denying the client access to them?
FMC: This is a design issue and another good topic for classroom discussion. The client should be aware of the specifications of a sorted list, as detailed in SortedListInterface, so shouldn't call insert and setEntry. Throwing an exception is a safe way to disable the effect of insert and setEntry. However, as you suggest, making the methods protected or private is another way to prevent the client from using them.
MC: When I was a professional developer, my colleagues and I usually ignored "good citizen" rules, as did our users. Defensive programming became a paramount consideration in order to manage and maintain data integrity on our end. Further, developers tend to like—and take pride in—breaking code. Developers are, as I constantly remind my students, perverse! Thus, another major emphasis point is defensive programming. Holes that are left will be exploited either intentionally or by accident. I will also note that causing a compiler error because of an incorrect access may be a gentler way to inform a developer of a problem than causing an exception, as time-crunched developers (or students) don't always thoroughly peruse specifications. A compiler error will get their attention rather than wait until run-time. Further, it is possible that the part of the code that has the call may not actually get exercised during testing.
FMC: You make good points!
MC: Insofar as protected vs. private is concerned, my approach is whether we wish to use the derived class as a base class or not. Using protected makes it possible to use SortedListIsA as a base class, and so gives derived classes access to the underlying LinkedList class.
FMC: I agree.
MC: As I interpret the Note: and Tip on page 365 , they are stating that the way the class is implemented in the text is not correct. Is that what they imply? If so, why have the SortedListIsA class implemented incorrectly?
FC: Well, SortedListIsA has a "correct" implementation. It works! BUT in this case, it is an "inappropriate" way to go. I feel that you can't teach how to avoid an inappropriate approach without seeing one and analyzing it. Along the way, we show the mechanics of public inheritance. Remember, that inheritance is just detailed in the prior Interlude 4. Public inheritance is often misused and overused; the sorted list provides a good example of how that might happen. However, we will clarify our intent in the next edition. Thank you for pointing this out!
MC: The SortedLinkedListHasA class contains a pointer to ListInterface. I was wondering why this approach was chosen over using LinkedList directly.
FC: By using ListInterface instead of LinkedList or ArrayList, we provide the implementor a choice of how to define the class. You then can talk about efficiency issues in the classroom. Which implementation is better?
MC: I don't see the files for NotFoundException and for the BinaryNode implementation. Are these left as exercises? Is NotFoundException discussed? If so, can you point me to it?
FC: As the book progresses, it provides less code. The complete code, including NotFoundException and BinaryNode, are available to instructors. The implementations of both of these classes are straightforward and a part of one of the programming problems. But providing the code to instructors only, we enable you to control how much of it to give to your students.
MC: In BinaryNode, the set pointer functions return a pointer and are public. Is this dangerous? Was this done to allow the classes that use BinaryNode to access them?
FC: The node is not giving access to data that the client already has (or had) access to—otherwise the pointers (nextPtr, leftChildPtr, rightChildPtr) could not have been set. Remember, a pointer is just another type of data.
The way nodes use pointers is in contrast to the way link-based trees and lists, for example, use them. In a link-based structure, such as a tree, the structure creates the node object using "new" and maintains the pointer to it. The client of the tree should never see a node or a pointer to it.
The client of the node creates—and owns—the node and the pointer to it, just as the client owns the item stored in the node.
Note that the class Node on page 136 does a similar thing.
MC: In the 5th edition of the text, the search tree class used a reference to a pointer in order to return a value as in:
void BinarySearchTree::deleteItem( TreeNode *& treePtr, KeyType searchKey )
The new edition now uses a function return. I am interested as to why this change was made. The 5th edition approach provided the basis for a good discussion about how recursion works.
FC: We had decided to not use reference arguments to return values for public methods, but rather to have the method return the value. We also adhered to that decision, if practical, for private and protected methods. It does mean, however, having to think about recursion differently. Showing your students the other way might be useful, if they are sophisticated enough to not get confused!
MC: Thank you very much for taking the time to answer my questions.