Selected C++ Example #17 //Example #17 // This example code shows the attempt to implement three // different lists (meal lists, airplane lists, and dog lists) // with one implementation of the list code. The general approach // is to use inheritance to weaken the type-checking mechanism // of C++ by making all data types that want to be in a list // inherit from a common base class (in this case the class // ListItem). The common base class captures any necessary // operations that the LinkedList class might need (in this // case, print() and type()). The problem with weak type // checking is that a wrong derived object might end up on // the wrong list. The benefits of mixed list and strong // type checking are captured in the next example, which // reimplements this code with C++ templates. // This example could be extended to include type checking. // The algorithm for doing this is to have each LinkedList // object remember the data type of the first argument inserted. // Once this is recorded all other insertions will check the // type of the object being added to the list with the stored // value. Of course, this algorithm makes it impossible to // have mixed data type lists anywhere in the application. #include <iostream.h> #include <new.h> // ListItem is the class responsible for weakening the type // checking of C++. We make all of our list element classes // inherit from this common base class. The LinkedList will // be of pointers to this base class. Note that all ListItems // must know how to give their type and print themselves. class ListItem { public: virtual void print(ostream& o = cout) = 0; virtual const char* type() = 0; }; // The derived classes Dog, Meal, and Airplane are only // skeleton classes to simplify their implementation. class Dog : public ListItem { public: void bark(); void bite(); void print(ostream&o = cout); const char* type(); }; void Dog::bark() { cout << ''Bow Wow\n''; } void Dog::bite() { cout << ''Ouch!!!\n''; } void Dog::print(ostream& o) { o << ''I am a dog!\n''; } const char* Dog::type() { return(''Dog''); } class Meal : public ListItem { public: void eat(); void print(ostream& o = cout); const char* type(); }; void Meal::eat() { cout << ''Crunch ... Munch ... Crunch ... \n''; } void Meal::print(ostream& o) { o << ''I'm a meal\n''; } const char* Meal::type() { return(''Meal''); } class Airplane : public ListItem { public: void fly(); void print(ostream& o = cout); const char* type(); }; void Airplane::fly() { cout << ''Va-a-a--room!!!\n''; } void Airplane::print(ostream& o) { o << ''I'm an airplane!\n''; } const char* Airplane::type() { return(''Airplane''); } typedef ListItem* DATUM; class LinkedList { struct Node { DATUM data; Node* next; public: Node(DATUM&); }; Node* head; int len; public: LinkedList(); ~LinkedList(); int insert(DATUM&); DATUM remove(); void traverse()const; int length(); }; LinkedList::Node::Node(DATUM& new_data) { data = new_data; next = NULL; } LinkedList::LinkedList() { head = NULL; len = 0; } LinkedList::~LinkedList() { Node* temp; while (head != NULL) { temp = head; head = head->next; delete temp; } } int LinkedList::insert(DATUM& new_item) { Node* temp = head; if (temp == NULL) { head = new Node(new_item); } else { while (temp->next != NULL) { temp = temp->next; } temp->next = new Node(new_item); } return(++len); } // The remove method needs something to return if the list // is empty. We deal with this problem by creating a dummy // DATUM as an internal variable within the remove method. DATUM LinkedList::remove() { Node* temp = head; static DATUM bad_item; DATUM retval; if (temp == NULL) { return(bad_item); } else { retval = head->data; head = head->next; len--; delete temp; return(retval); } } // Notice that the traverse method sends a message to the // data in each node to print itself. This sets up a requirement // that any data type that wants to be in a LinkedList needs // a print method (this constraint is enforced in the base // class ''ListItem''). An even more important consideration is // the fact that the syntax is different if DATUM is a pointer // or nonpointer. Nonpointers would use a dot, and not // an arrow, operator. This problem carries over to templates // as well. It is common to see templates advertise which types // they can, and cannot, handle. void LinkedList::traverse() const { Node* temp = head; cout << ''(\n''; while (temp != NULL) { temp->data->print(); cout << ''\n''; temp = temp->next; } cout << '')\n\n''; } int LinkedList::length() { return(len); } void main() { LinkedList MealList, AirplaneList, DogList; Meal *meal1 = new Meal, *meal2 = new Meal, *meal3 = new Meal; Dog *dog1 = new Dog, *dog2 = new Dog, *dog3 = new Dog; Airplane *air1 = new Airplane, *air2 = new Airplane, *air3 = new Airplane; // At first glance everything seems to work nicely. MealList.insert(meal1); MealList.insert(meal2); MealList.insert(meal3); Meal* aMeal = (Meal*) MealList.remove(); aMeal->eat(); AirplaneList.insert(air1); AirplaneList.insert(air2); AirplaneList.insert(air3); DogList.insert(dog1); DogList.insert(dog2); DogList.insert(dog3); MealList.traverse(); AirplaneList.traverse(); DogList.traverse(); // Until we see some of the nasty side effects of weak type // checking. This code accidentally flies a dog off the // runway at the airport. AirplaneList.insert(dog2); DATUM anItem; while (AirplaneList.length() != 0){ anItem = AirplaneList.remove(); cout << ''My real type is '' << anltem->type() << ''\n''; cout << ''I can fly. . .watch. . . \n''; ((Airplane*) anItem)->fly(); } delete meal1; delete meal2; delete meal3; delete dogl; delete dog2; delete dog3; delete air1; delete air2; delete air3; } |