The following program brings together many of the advanced techniques you've learned during the past three weeks of hard work. Week 3 in Review provides a template-based linked list with exception handling. Examine it in detail; if you understand it fully, you are a C++ programmer.
Warning: If your compiler does not support templates, or if your compiler does not support try and catch, you will not be able to compile or run this listing.
Listing R3.1. Week 3 in Review listing.
1: // **************************************************
2: //
3: // Title: Week 3 in review
4: //
5: // File: Week3
6: //
7: // Description: Provide a template-based linked list
8: // demonstration program with exception handling
9: //
10: // Classes: PART - holds part numbers and potentially other
11: // information about parts. This will be the
12: // example class for the list to hold
13: // Note use of operator<< to print the
14: // information about a part based on its
15: // run time type.
16: //
17: // Node - acts as a node in a List
18: //
19: // List - template based list which provides the
20: // mechanisms for a linked list
21: //
22: //
23: // Author: Jesse Liberty (jl)
24: //
25: // Developed: 486/66 32mb RAM MVC 1.5
26: //
27: // Target: Platform independent
28: //
29: // Rev History: 9/94 - First release (jl)
30: // **************************************************
31:
32: #include <iostream.h>
33:
34: typedef unsigned long ULONG;
35: typedef unsigned short USHORT;
36:
37: // exception classes
38: class Exception {};
39: class OutOfMemory : public Exception{};
40: class NullNode : public Exception{};
41: class EmptyList : public Exception {};
42: class BoundsError : public Exception {};
43:
44:
45: // **************** Part ************
46: // Abstract base class of parts
47: class Part
48: {
49: public:
50: Part():itsObjectNumber(1) {}
51: Part(ULONG ObjectNumber):itsObjectNumber(ObjectNumber){}
52: virtual ~Part(){};
53: ULONG GetObjectNumber() const { return itsObjectNumber; }
54: virtual void Display() const =0; // must be overridden
55:
56: private:
57: ULONG itsObjectNumber;
58: };
59:
60: // implementation of pure virtual function so that
61: // derived classes can chain up
62: void Part::Display() const
63: {
64: cout << "\nPart Number: " << itsObjectNumber << endl;
65: }
66:
67: // this one operator<< will be called for all part objects.
68: // It need not be a friend as it does not access private data
69: // It calls Display() which uses the required polymorphism
70: // We'd like to be able to override this based on the real type
71: // of thePart, but C++ does not support contravariance
72: ostream& operator<<( ostream& theStream,Part& thePart)
73: {
74: thePart.Display(); // virtual contravariance!
75: return theStream;
76: }
77:
78: // **************** Car Part ************
79: class CarPart : public Part
80: {
81: public:
82: CarPart():itsModelYear(94){}
83: CarPart(USHORT year, ULONG partNumber);
84: USHORT GetModelYear() const { return itsModelYear; }
85: virtual void Display() const;
86: private:
87: USHORT itsModelYear;
88: };
89:
90: CarPart::CarPart(USHORT year, ULONG partNumber):
91: itsModelYear(year),
92: Part(partNumber)
93: {}
94:
95: void CarPart::Display() const;
96: {
97: Part::Display();
98: cout << "Model Year: " << itsModelYear << endl;
99: }
100:
101: // **************** AirPlane Part ************
102: class AirPlanePart : public Part
103: {
104: public:
105: AirPlanePart():itsEngineNumber(1){};
106: AirPlanePart(USHORT EngineNumber, ULONG PartNumber);
107: virtual void Display() const;
108: USHORT GetEngineNumber()const { return itsEngineNumber; }
109: private:
110: USHORT itsEngineNumber;
111: };
112:
113: AirPlanePart::AirPlanePart(USHORT EngineNumber, ULONG PartNumber):
114: itsEngineNumber(EngineNumber),
115: Part(PartNumber)
116: {}
117:
118: void AirPlanePart::Display() const
119: {
120: Part::Display();
121: cout << "Engine No.: " << itsEngineNumber << endl;
122: }
123:
124: // forward declaration of class List
125: template <class T>
126: class List;
127:
128: // **************** Node ************
129: // Generic node, can be added to a list
130: // ************************************
131:
132: template <class T>
133: class Node
134: {
135: public:
136: friend class List<T>;
137: Node (T*);
138: ~Node();
139: void SetNext(Node * node) { itsNext = node; }
140: Node * GetNext() const;
141: T * GetObject() const;
142: private:
143: T* itsObject;
144: Node * itsNext;
145: };
146:
147: // Node Implementations...
148:
149: template <class T>
150: Node<T>::Node(T* pOjbect):
151: itsObject(pOjbect),
152: itsNext(0)
153: {}
154:
155: template <class T>
156: Node<T>::~Node()
157: {
158: delete itsObject;
159: itsObject = 0;
160: delete itsNext;
161: itsNext = 0;
162: }
163:
164: // Returns NULL if no next Node
165: template <class T>
166: Node<T> * Node<T>::GetNext() const
167: {
168: return itsNext;
169: }
170:
171: template <class T>
172: T * Node<T>::GetObject() const
173: {
174: if (itsObject)
175: return itsObject;
176: else
177: throw NullNode();
178: }
179:
180: // **************** List ************
181: // Generic list template
182: // Works with any numbered object
183: // ***********************************
184: template <class T>
185: class List
186: {
187: public:
188: List();
189: ~List();
190:
191: void Iterate(void (T::*f)()const) const;
192: T* Find(ULONG & position, ULONG ObjectNumber) const;
193: T* GetFirst() const;
194: void Insert(T *);
195: T* operator[](ULONG) const;
196: ULONG GetCount() const { return itsCount; }
197: private:
198: Node<T> * pHead;
199: ULONG itsCount;
200: };
201:
202: // Implementations for Lists...
203: template <class T>
204: List<T>::List():
205: pHead(0),
206: itsCount(0)
207: {}
208:
209: template <class T>
210: List<T>::~List()
211: {
212: delete pHead;
213: }
214:
215: template <class T>
216: T* List<T>::GetFirst() const
217: {
218: if (pHead)
219: return pHead->itsObject;
220: else
221: throw EmptyList();
222: }
223:
224: template <class T>
225: T * List<T>::operator[](ULONG offSet) const
226: {
227: Node<T>* pNode = pHead;
228:
229: if (!pHead)
230: throw EmptyList();
231:
232: if (offSet > itsCount)
233: throw BoundsError();
234:
235: for (ULONG i=0;i<offSet; i++)
236: pNode = pNode->itsNext;
237:
238: return pNode->itsObject;
239: }
240:
241: // find a given object in list based on its unique number (id)
242: template <class T>
243: T* List<T>::Find(ULONG & position, ULONG ObjectNumber) const
244: {
245: Node<T> * pNode = 0;
246: for (pNode = pHead, position = 0;
247: pNode!=NULL;
248: pNode = pNode->itsNext, position++)
249: {
250: if (pNode->itsObject->GetObjectNumber() == ObjectNumber)
251: break;
252: }
253: if (pNode == NULL)
254: return NULL;
255: else
256: return pNode->itsObject;
257: }
258:
259: // call function for every object in list
260: template <class T>
261: void List<T>::Iterate(void (T::*func)()const) const
262: {
263: if (!pHead)
264: return;
265: Node<T>* pNode = pHead;
266: do
267: (pNode->itsObject->*func)();
268: while (pNode = pNode->itsNext);
269: }
270:
271: // insert if the number of the object is unique
272: template <class T>
273: void List<T>::Insert(T* pObject)
274: {
275: Node<T> * pNode = new Node<T>(pObject);
276: Node<T> * pCurrent = pHead;
277: Node<T> * pNext = 0;
278:
279: ULONG New = pObject->GetObjectNumber();
280: ULONG Next = 0;
281: itsCount++;
282:
283: if (!pHead)
284: {
285: pHead = pNode;
286: return;
287: }
288:
289: // if this one is smaller than head
290: // this one is the new head
291: if (pHead->itsObject->GetObjectNumber() > New)
292: {
293: pNode->itsNext = pHead;
294: pHead = pNode;
295: return;
296: }
297:
298: for (;;)
299: {
300: // if there is no next, append this new one
301: if (!pCurrent->itsNext)
302: {
303: pCurrent->itsNext = pNode;
304: return;
305: }
306:
307: // if this goes after this one and before the next
308: // then insert it here, otherwise get the next
309: pNext = pCurrent->itsNext;
310: Next = pNext->itsObject->GetObjectNumber();
311: if (Next > New)
312: {
313: pCurrent->itsNext = pNode;
314: pNode->itsNext = pNext;
315: return;
316: }
317: pCurrent = pNext;
318: }
319: }
320:
321:
322: int main()
323: {
324: List<Part> theList;
325: int choice;
326: ULONG ObjectNumber;
327: USHORT value;
328: Part * pPart;
329: while (1)
330: {
331: cout << "(0)Quit (1)Car (2)Plane: ";
332: cin >> choice;
333:
334: if (!choice)
335: break;
336:
337: cout << "New PartNumber?: ";
338: cin >> ObjectNumber;
339:
340: if (choice == 1)
341: {
342: cout << "Model Year?: ";
343: cin >> value;
344: try
345: {
346: pPart = new CarPart(value,ObjectNumber);
347: }
348: catch (OutOfMemory)
349: {
350: cout << "Not enough memory; Exiting..." << endl;
351: return 1;
352: }
353: }
354: else
355: {
356: cout << "Engine Number?: ";
357: cin >> value;
358: try
359: {
360: pPart = new AirPlanePart(value,ObjectNumber);
361: }
362: catch (OutOfMemory)
363: {
364: cout << "Not enough memory; Exiting..." << endl;
365: return 1;
366: }
367: }
368: try
369: {
370: theList.Insert(pPart);
371: }
372: catch (NullNode)
373: {
374: cout << "The list is broken, and the node is null!" << endl;
375: return 1;
376: }
377: catch (EmptyList)
378: {
379: cout << "The list is empty!" << endl;
380: return 1;
381: }
382: }
383: try
384: {
385: for (int i = 0; i < theList.GetCount(); i++ )
386: cout << *(theList[i]);
387: }
388: catch (NullNode)
389: {
390: cout << "The list is broken, and the node is null!" << endl;
391: return 1;
392: }
393: catch (EmptyList)
394: {
395: cout << "The list is empty!" << endl;
396: return 1;
397: }
398: catch (BoundsError)
399: {
400: cout << "Tried to read beyond the end of the list!" << endl;
401: return 1;
402: }
403: return 0;
404: }
Output:
(0)Quit (1)Car (2)Plane: 1
New PartNumber?: 2837
Model Year? 90
(0)Quit (1)Car (2)Plane: 2
New PartNumber?: 378
Engine Number?: 4938
(0)Quit (1)Car (2)Plane: 1
New PartNumber?: 4499
Model Year? 94
(0)Quit (1)Car (2)Plane: 1
New PartNumber?: 3000
Model Year? 93
(0)Quit (1)Car (2)Plane: 0
Part Number: 378
Engine No. 4938
Part Number: 2837
Model Year: 90
Part Number: 3000
Model Year: 93
Part Number 4499
Model Year: 94
Analysis:
The Week 3 in Review modifies the program provided in Week 2 to add templates, ostream processing and exception handling. The output is identical.
On lines 3742 a number of exception classes are declared. In the somewhat primitive exception handling provided by this program, no data or methods are required of these exceptions; they serve as flags to the catch statements, which print out a very simple warning and then exit. A more robust program might pass these exceptions by reference and then extract context or other data from the exception objects in an attempt to recover from the problem.
On line 45 the abstract base class Part is declared exactly as it was in Week 2. The only interesting change here is in the non-class member operator<<() which is declared on lines 7276. Note that this is neither a member of Part nor a friend of part, it simply takes a Part reference as one of its arguments.
You might want to have operator<< take a CarPart and an AirPlanePart in the hopes that the correct operator<< would be called based on whether a car part or an airplane part is passed. Since the program passes a pointer to a part, however, and not a pointer to a car part or an airplane part, C++ would have to call the right function based on the real type of one of the arguments to the function. This is called contravariance and is not supported in C++.
There are only two ways to achieve polymorphism in C++: function polymorphism and virtual functions. Function polymorphism won't work here because in every case you are matching the same signature: the one taking a reference to a Part.
Virtual functions won't work here because operator<< is not a member function of Part. You can't make operator<< a member function of Part because you want to invoke
cout << thePart
and that means that the actual call would be to cout.operator<<(Part&) and cout does not have a version of operator<< which takes a part reference!
To get around this limitation, the Week 3 program uses just one operator<<, taking a reference to a Part. This then calls Display(), which is a virtual member function and thus the right version is called.
On lines 132145, Node is defined as a template. It serves the same function as Node did in the Week 2 review program, but this version of Node is not tied to a Part object. It can, in fact, be the node for any type of object.
Note that if you try to get the object from the Node and there is no object this is considered an exception, and the exception is thrown on line 177.
On lines 180200 a generic List class template is defined. This list class can hold nodes of any objects that have unique identification numbers, and it keeps them sorted in ascending order. Each of the list functions checks for exceptional circumstances and throws the appropriate exceptions as required.
On lines 322404 the driver program creates a list of two types of Part objects, and then prints out the values of the objects in the list by using the standard streams mechanism.
Go to: Table of Contents | Next Page