The Week in Review program for Week 2 brings together many of the skills you've acquired over the past fortnight and produces a powerful program.
This demonstration of linked lists utilizes virtual functions, pure virtual functions, function overriding, polymorphism, public inheritance, function overloading, forever loops, pointers, references, and more.
The goal of this program is to create a linked list. The nodes on the list are designed to hold parts, as might be used in a factory. While this is not the final form of this program, it does make a good demonstration of a fairly advanced data structure. The code list is 300 lines. Try to analyze the code on your own before reading the analysis that follows the output.
1: // **************************************************
2: //
3: // Title: Week 2 in review
4: //
5: // File: Week2
6: //
7: // Description: Provide a linked list demonstration program
8: //
9: // Classes: PART - holds part numbers and potentially other
10: // information about parts
11: //
12: // PartNode - acts as a node in a PartsList
13: //
14: // PartsList - provides the mechanisms for a linked list of parts
15: //
16: // Author: Jesse Liberty (jl)
17: //
18: // Developed: 486/66 32mb RAM MVC 1.5
19: //
20: // Target: Platform independent
21: //
22: // Rev History: 9/94 - First release (jl)
23: //
24: // **************************************************
25:
26: #include <iostream.h>
27:
28: typedef unsigned long ULONG;
29: typedef unsigned short USHORT;
30:
31:
32: // **************** Part ************
33:
34: // Abstract base class of parts
35: class Part
36: {
37: public:
38: Part():itsPartNumber(1) {}
39: Part(ULONG PartNumber):itsPartNumber(PartNumber){}
40: virtual ~Part(){};
41: ULONG GetPartNumber() const { return itsPartNumber; }
42: virtual void Display() const =0; // must be overridden
43: private:
44: ULONG itsPartNumber;
45: };
46:
47: // implementation of pure virtual function so that
48: // derived classes can chain up
49: void Part::Display() const
50: {
51: cout << "\nPart Number: " << itsPartNumber << endl;
52: }
53:
54: // **************** Car Part ************
55:
56: class CarPart : public Part
57: {
58: public:
59: CarPart():itsModelYear(94){}
60: CarPart(USHORT year, ULONG partNumber);
61: virtual void Display() const { Part::Display(); cout << "Model Year: " << ÂitsModelYear << endl; }
62: private:
63: USHORT itsModelYear;
64: };
65:
66: CarPart::CarPart(USHORT year, ULONG partNumber):
67: itsModelYear(year),
68: Part(partNumber)
69: {}
70:
71:
72: // **************** AirPlane Part ************
73:
74: class AirPlanePart : public Part
75: {
76: public:
77: AirPlanePart():itsEngineNumber(1){};
78: AirPlanePart(USHORT EngineNumber, ULONG PartNumber);
79: virtual void Display() const{ Part::Display(); cout << "Engine No.: " << ÂitsEngineNumber << endl; }
80: private:
81: USHORT itsEngineNumber;
82: };
83:
84: AirPlanePart::AirPlanePart(USHORT EngineNumber, ULONG PartNumber):
85: itsEngineNumber(EngineNumber),
86: Part(PartNumber)
87: {}
88:
89: // **************** Part Node ************
90: class PartNode
91: {
92: public:
93: PartNode (Part*);
94: ~PartNode();
95: void SetNext(PartNode * node) { itsNext = node; }
96: PartNode * GetNext() const;
97: Part * GetPart() const;
98: private:
99: Part *itsPart;
100: PartNode * itsNext;
101: };
102:
103: // PartNode Implementations...
104:
105: PartNode::PartNode(Part* pPart):
106: itsPart(pPart),
107: itsNext(0)
108: {}
109:
110: PartNode::~PartNode()
111: {
112: delete itsPart;
113: itsPart = 0;
114: delete itsNext;
115: itsNext = 0;
116: }
117:
118: // Returns NULL if no next PartNode
119: PartNode * PartNode::GetNext() const
120: {
121: return itsNext;
122: }
123:
124: Part * PartNode::GetPart() const
125: {
126: if (itsPart)
127: return itsPart;
128: else
129: return NULL; //error
130: }
131:
132: // **************** Part List ************
133: class PartsList
134: {
135: public:
136: PartsList();
137: ~PartsList();
138: // needs copy constructor and operator equals!
139: Part* Find(ULONG & position, ULONG PartNumber) const;
140: ULONG GetCount() const { return itsCount; }
141: Part* GetFirst() const;
142: static PartsList& GetGlobalPartsList() { return GlobalPartsList; }
143: void Insert(Part *);
144: void Iterate(void (Part::*f)()const) const;
145: Part* operator[](ULONG) const;
146: private:
147: PartNode * pHead;
148: ULONG itsCount;
149: static PartsList GlobalPartsList;
150: };
151:
152: PartsList PartsList::GlobalPartsList;
153:
154: // Implementations for Lists...
155:
156: PartsList::PartsList():
157: pHead(0),
158: itsCount(0)
159: {}
160:
161: PartsList::~PartsList()
162: {
163: delete pHead;
164: }
165:
166: Part* PartsList::GetFirst() const
167: {
168: if (pHead)
169: return pHead->GetPart();
170: else
171: return NULL; // error catch here
172: }
173:
174: Part * PartsList::operator[](ULONG offSet) const
175: {
176: PartNode* pNode = pHead;
177:
178: if (!pHead)
179: return NULL; // error catch here
180:
181: if (offSet > itsCount)
182: return NULL; // error
183:
184: for (ULONG i=0;i<offSet; i++)
185: pNode = pNode->GetNext();
186:
187: return pNode->GetPart();
188: }
189:
190: Part* PartsList::Find(ULONG & position, ULONG PartNumber) const
191: {
192: PartNode * pNode = 0;
193: for (pNode = pHead, position = 0;
194: pNode!=NULL;
195: pNode = pNode->GetNext(), position++)
196: {
197: if (pNode->GetPart()->GetPartNumber() == PartNumber)
198: break;
199: }
200: if (pNode == NULL)
201: return NULL;
202: else
203: return pNode->GetPart();
204: }
205:
206: void PartsList::Iterate(void (Part::*func)()const) const
207: {
208: if (!pHead)
209: return;
210: PartNode* pNode = pHead;
211: do
212: (pNode->GetPart()->*func)();
213: while (pNode = pNode->GetNext());
214: }
215:
216: void PartsList::Insert(Part* pPart)
217: {
218: PartNode * pNode = new PartNode(pPart);
219: PartNode * pCurrent = pHead;
220: PartNode * pNext = 0;
221:
222: ULONG New = pPart->GetPartNumber();
223: ULONG Next = 0;
224: itsCount++;
225:
226: if (!pHead)
227: {
228: pHead = pNode;
229: return;
230: }
231:
232: // if this one is smaller than head
233: // this one is the new head
234: if (pHead->GetPart()->GetPartNumber() > New)
235: {
236: pNode->SetNext(pHead);
237: pHead = pNode;
238: return;
239: }
240:
241: for (;;)
242: {
243: // if there is no next, append this new one
244: if (!pCurrent->GetNext())
245: {
246: pCurrent->SetNext(pNode);
247: return;
248: }
249:
250: // if this goes after this one and before the next
251: // then insert it here, otherwise get the next
252: pNext = pCurrent->GetNext();
253: Next = pNext->GetPart()->GetPartNumber();
254: if (Next > New)
255: {
256: pCurrent->SetNext(pNode);
257: pNode->SetNext(pNext);
258: return;
259: }
260: pCurrent = pNext;
261: }
262: }
263:
264: void main()
265: {
266: PartsList pl = PartsList::GetGlobalPartsList();
267: Part * pPart = 0;
268: ULONG PartNumber;
269: USHORT value;
270: ULONG choice;
271:
272: while (1)
273: {
274: cout << "(0)Quit (1)Car (2)Plane: ";
275: cin >> choice;
276:
277: if (!choice)
278: break;
279:
280: cout << "New PartNumber?: ";
281: cin >> PartNumber;
282:
283: if (choice == 1)
284: {
285: cout << "Model Year?: ";
286: cin >> value;
287: pPart = new CarPart(value,PartNumber);
288: }
289: else
290: {
291: cout << "Engine Number?: ";
292: cin >> value;
293: pPart = new AirPlanePart(value,PartNumber);
294: }
295:
296: pl.Insert(pPart);
297: }
298: void (Part::*pFunc)()const = Part::Display;
299: pl.Iterate(pFunc);
300: }
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 2 in Review provides a linked list implementation for Part objects. A linked list is a dynamic data structure, that is it is like an array but it is sized to fit as objects are added and deleted.
This particular linked list is designed to hold objects of class Part, where Part is an abstract data type serving as a base class to any objects with a part number. In this example, Part has been subclassed into CarPart and AirplanePart.
Class Part is declared on lines 3443, and consists of a part number and some accessors. Presumably this class could be fleshed out to hold other important information about the parts such as what components they are used in, how many are in stock, and so forth. Part is an abstract data type, enforced by the pure virtual function Display().
Note that Display() does have an implementation, on lines 5052. It is the designers intention that derived classes will be forced to create their own Display() method, but may chain up to this method as well.
Two simple derived classes, CarPart and AirPlanePart are provided on lines 5669 and 7487, respectively. Each provides an overridden Display() method, which does in fact chain up to the base class Display() method.
The class PartNode serves as the interface between the Part class and the PartList class. It contains a pointer to a part and a pointer to the next node in the list. Its only methods are to get and set the next node in the list and to return the Part to which it points.
The intelligence of the list is, appropriately, in the class PartsList, whose declaration is on lines 133150. The PartsList keeps a pointer to the first element in the list (pHead) and uses that to access all other methods by walking the list. Walking the list means asking each node in the list for the next node, until you reach a node whose next pointer is NULL.
This is only a partial implementation, a fully developed list would provide either greater access to its first and last nodes, or would provide an iterator object, which allowed clients to easily walk the list.
The PartsList nonetheless provides a number of interesting methods, which are listed in alphabetical order. This is often a good idea, as it makes finding the functions easier.
Find() takes a PartNumber and a ULONG. If the part corresponding to the PartNumber is found, it returns a pointer to the Part and fills the ULONG with the position of that part in the list. If the PartNumber is not found, it returns NULL and the position is meaningless.
GetCount() returns the number of elements in the list. PartsList keeps this number as a member variable, itsCount, though it could of course compute this number by walking the list.
GetFirst() returns a pointer to the first Part in the list, or returns NULL if the list is empty.
GetGlobalPartsList() returns a reference to the static member variable GlobalPartsList. This is a static instance of this class; every program with a PartsList also has one GlobalPartsList, though of course it is free to make other PartsLists as well. A full implementation of this idea would modify the constructor of Part to ensure that every part is created on the GlobalPartsList.
Insert takes a pointer to a Part, creates a PartNode for it and adds it to the list, ordered by PartNumber.
Iterate takes a pointer to a member function of Part, which takes no parameters, returns void and is const. It calls that function for every Part object in the list. In the example program this is called on Display(), which is a virtual function, so the appropriate Display() method will be called based on the run-time type of the Part object called.
Operator[] allows direct access to the Part at the offset provided. Rudimentary bounds checking is provided, if the list is NULL or if the offset requested is greater than the size of the list, NULL is returned as an error condition.
Note that in a real program these comments on the functions would be written into the class declaration.
The driver program is on lines 264300. A pointer to PartsList is declared on line 266 and initialized with the GlobalPartsList. Note that the GlobalPartsList itself is initialized on line 152. This is necessary as the declaration of a static member variable does not define it; definition must be done outside the declaration of the class.
On lines 272294 the user is repeatedly prompted to choose whether to enter a car part or an airplane part. Depending on the choice the right value is requested and the appropriate part is created. Once created the part is inserted into the list on line 296.
The implementation for the Insert() method of PartsList is on lines 216262. When the first part number is entered, 2837, a CarPart with that part number and the model year 90 is created and passed in to LinkedList::Insert().
On line 218 a new PartNode is created with that part, and the variable New is initialized with the part number. The PartsList's itsCount member variable is incremented on line 224.
On line 226 the test that pHead is NULL will evaluate true. Since this is the first node, it is true that the PartsList's pHead pointer has zero. Thus on line 228 pHead is set to point to the new node and this function returns.
The user is prompted to enter a second part, and this time an AirPlane part with part number 378 and engine number 4938 is entered. Once again PartsList::Insert() is called, and once again pNode is initialized with the new node. The static member variable itsCount is incremented to 2, and pHead is tested. Since pHead was assigned last time, it is no longer null and the test fails.
On line 234 the part number held by pHead, 2837, is compared against the current part number, 378. Since the new one is smaller than the one held by pHead, the new one must become the new head pointer, and the test on line 234 is true.
On line 236 the new node is set to point to the node currently pointed to by pHead. Note that this does not point the new node to pHead itself, but rather to the node that pHead was pointing to! On line 237 pHead is set to point to the new node.
The third time through the loop, the user enters the part number 4499 for a Car with model year 94. The counter is incremented and the number this time is not less than the number pointed to by pHead, so the for loop which begins on line 241 is entered.
The value pointed to by pHead is 378. The value pointed to by the second node is 2837. The current value is 4499. The pointer pCurrent points to the same node as pHead and so it does have a next value, it points to the second node, and so the test on line 244 fails.
The pointer pCurrent is set to point to the next node and the loop repeats. This time the test on line 145 succeeds, there is no next item, so the current node is told to point to the new node on line 246 and the insert is finished.
The fourth time through the part number 3000 is entered. This proceeds just like the previous, but this time when the current node is pointing to 2837 and the next node has 4499, the test on line 254 returns TRUE and the new node is inserted into position.
When the user finally presses 0 the test on line 277 evaluates true and the while(1) loop breaks. On line 298 the member function Display() is assigned to the pointer to member function pFunc. In a real program this would be assigned dynamically, based on the user's choice of method.
The pointer to member function is passed to the PartsList Iterate() method. On line 208 the Iterate() method ensures that the list is not empty. Then on lines 211213 each Part on the list is called using the pointer to member function. This calls the appropriate Display() method for the Part, as shown in the output.
Go to: Table of Contents | Next Page