#

##
In Review

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.

    0:   // **************************************************
    1:   //
    2:   // Title:     Week 3 in Review
    3:   //
    4:   // File:      Week3
    5:   //
    6:   // Description:   Provide a template-based linked list
    7:   //                demonstration program with exception handling
    8:   //
    9:   // Classes:    PART - holds part numbers and potentially other
    10:   //                      information about parts. This will be the
    11:   //                      example class for the list to hold
    12:   //                      Note use of operator<< to print the
    13:   //                      information about a part based on its
    14:   //                      runtime type.
    15:   //
    16:   //               Node - acts as a node in a List
    17:   //
    18:   //               List - template-based list which provides the
    19:   //                      mechanisms for a linked list
    20:   //
    21:   //
    22:   // Author:    Jesse Liberty (jl)
    23:   //
    24:   // Developed:   Pentium 200 Pro. 128MB RAM MVC 5.0
    25:   //
    26:   // Target:    Platform independent
    27:   //
    28:   // Rev History:  9/94 - First release (jl)
    29:   //               4/97 - Updated (jl)
    30:   // **************************************************
    31:
    32:   #include <iostream.h>
    33:
    34:   // exception classes
    35:   class Exception {};
    36:   class OutOfMemory :   public Exception{};
    37:   class NullNode :    public Exception{};
    38:   class EmptyList :   public Exception {};
    39:   class BoundsError :   public Exception {};
    40:
    41:
    42:   // **************** Part ************
    43:   // Abstract base class of parts
    44:   class Part
    45:   {
    46:   public:
    47:    Part():itsObjectNumber(1) {}
    48:    Part(int ObjectNumber):itsObjectNumber(ObjectNumber){}
    49:    virtual ~Part(){};
    50:    int GetObjectNumber() const { return itsObjectNumber; }
    51:    virtual void Display() const =0;  // must be overridden
    52:
    53:   private:
    54:    int itsObjectNumber;
    55:   };
    56:
    57:   // implementation of pure virtual function so that
    58:   // derived classes can chain up
    59:   void Part::Display() const
    60:   {
    61:     cout << "\nPart Number: " << itsObjectNumber << endl;
    62:   }
    63:
    64:   // this one operator<< will be called for all part objects.
    65:   // It need not be a friend as it does not access private data
    66:   // It calls Display() which uses the required polymorphism
    67:   // We'd like to be able to override this based on the real type
    68:   // of thePart, but C++ does not support contravariance
    69:   ostream& operator<<( ostream& theStream,Part& thePart)
    70:   {
    71:    thePart.Display();  // virtual contravariance!
    72:    return theStream;
    73:   }
    74:
    75:   // **************** Car Part ************
    76:   class CarPart : public Part
    77:   {
    78:   public:
    79:    CarPart():itsModelYear(94){}
    80:    CarPart(int year, int partNumber);
    81:    int GetModelYear() const { return itsModelYear; }
    82:    virtual void Display() const;
    83:   private:
    84:    int itsModelYear;
    85:   };
    86:
    87:   CarPart::CarPart(int year, int partNumber):
    88:    itsModelYear(year),
    89:    Part(partNumber)
    90:   {}
    91:
    92:   void CarPart::Display() const
    93:   {
    94:       Part::Display();
    95:       cout << "Model Year: " << itsModelYear << endl;
    96:   }
    97:
    98:   // **************** AirPlane Part ************
    99:   class AirPlanePart : public Part
    100:   {
    101:   public:
    102:    AirPlanePart():itsEngineNumber(1){};
    103:    AirPlanePart(int EngineNumber, int PartNumber);
    104:    virtual void Display() const;
    105:    int GetEngineNumber()const { return itsEngineNumber; }
    106:   private:
    107:    int itsEngineNumber;
    108:   };
    109:
    110:   AirPlanePart::AirPlanePart(int EngineNumber, int PartNumber):
    111:    itsEngineNumber(EngineNumber),
    112:    Part(PartNumber)
    113:   {}
    114:
    115:   void AirPlanePart::Display() const
    116:   {
    117:    Part::Display();
    118:    cout << "Engine No.: " << itsEngineNumber << endl;
    119:   }
    120:
    121:   // forward declaration of class List
    122:   template <class T>
    123:   class List;
    124:
    125:   // ****************  Node ************
    126:   // Generic node, can be added to a list
    127:   // ************************************
    128:
    129:   template <class T>
    130:   class Node
    131:   {
    132:   public:
    133:    friend class List<T>;
    134:    Node (T*);
    135:    ~Node();
    136:    void SetNext(Node * node) { itsNext = node; }
    137:    Node * GetNext() const;
    138:    T * GetObject() const;
    139:   private:
    140:    T* itsObject;
    141:    Node * itsNext;
    142:   };
    143:
    144:   // Node Implementations...
    145:
    146:   template <class T>
    147:   Node<T>::Node(T* pOjbect):
    148:   itsObject(pOjbect),
    149:   itsNext(0)
    150:   {}
    151:
    152:   template <class T>
    153:   Node<T>::~Node()
    154:   {
    155:    delete itsObject;
    156:    itsObject = 0;
    157:    delete itsNext;
    158:    itsNext = 0;
    159:   }
    160:
    161:   // Returns NULL if no next Node
    162:   template <class T>
    163:   Node<T> * Node<T>::GetNext() const
    164:   {
    165:       return itsNext;
    166:   }
    167:
    168:   template <class T>
    169:   T * Node<T>::GetObject() const
    170:   {
    171:    if (itsObject)
    172:       return itsObject;
    173:    else
    174:       throw NullNode();
    175:   }
    176:
    177:   // ****************  List ************
    178:   // Generic list template
    179:   // Works with any numbered object
    180:   // ***********************************
    181:   template <class T>
    182:   class List
    183:   {
    184:   public:
    185:    List();
    186:    ~List();
    187:
    188:    T*        Find(int & position, int ObjectNumber)  const;
    189:    T*      GetFirst() const;
    190:    void      Insert(T *);
    191:    T*      operator[](int) const;
    192:    int      GetCount() const { return itsCount; }
    193:   private:
    194:    Node<T> * pHead;
    195:    int      itsCount;
    196:   };
    197:
    198:   // Implementations for Lists...
    199:   template <class T>
    200:   List<T>::List():
    201:    pHead(0),
    202:    itsCount(0)
    203:    {}
    204:
    205:   template <class T>
    206:   List<T>::~List()
    207:   {
    208:    delete pHead;
    209:   }
    210:
    211:   template <class T>
    212:   T*   List<T>::GetFirst() const
    213:   {
    214:    if (pHead)
    215:       return pHead->itsObject;
    216:    else
    217:       throw EmptyList();
    218:   }
    219:
    220:   template <class T>
    221:   T *  List<T>::operator[](int offSet) const
    222:   {
    223:    Node<T>* pNode = pHead;
    224:
    225:    if (!pHead)
    226:       throw EmptyList();
    227:
    228:    if (offSet > itsCount)
    229:       throw BoundsError();
    230:
    231:    for (int i=0;i<offSet; i++)
    232:       pNode = pNode->itsNext;
    233:
    234:   return   pNode->itsObject;
    235:   }
    236:
    237:   // find a given object in list based on its unique number (id)
    238:   template <class T>
    239:   T*   List<T>::Find(int & position, int ObjectNumber)  const
    240:   {
    241:    Node<T> * pNode = 0;
    242:    for (pNode = pHead, position = 0;
    243:          pNode!=NULL;
    244:          pNode = pNode->itsNext, position++)
    245:    {
    246:       if (pNode->itsObject->GetObjectNumber() == ObjectNumber)
    247:          break;
    248:    }
    249:    if (pNode == NULL)
    250:       return NULL;
    251:    else
    252:       return pNode->itsObject;
    253:   }
    254:
    255:   // insert if the number of the object is unique
    256:   template <class T>
    257:   void List<T>::Insert(T* pObject)
    258:   {
    259:    Node<T> * pNode = new Node<T>(pObject);
    260:    Node<T> * pCurrent = pHead;
    261:    Node<T> * pNext = 0;
    262:
    263:    int New =  pObject->GetObjectNumber();
    264:    int Next = 0;
    265:    itsCount++;
    266:
    267:    if (!pHead)
    268:    {
    269:       pHead = pNode;
    270:       return;
    271:    }
    272:
    273:    // if this one is smaller than head
    274:    // this one is the new head
    275:    if (pHead->itsObject->GetObjectNumber() > New)
    276:    {
    277:       pNode->itsNext = pHead;
    278:       pHead = pNode;
    279:       return;
    280:    }
    281:
    282:    for (;;)
    283:    {
    284:       // if there is no next, append this new one
    285:       if (!pCurrent->itsNext)
    286:       {
    287:          pCurrent->itsNext = pNode;
    288:          return;
    289:       }
    290:
    291:       // if this goes after this one and before the next
    292:       // then insert it here, otherwise get the next
    293:       pNext = pCurrent->itsNext;
    294:       Next = pNext->itsObject->GetObjectNumber();
    295:       if (Next > New)
    296:       {
    297:          pCurrent->itsNext = pNode;
    298:          pNode->itsNext = pNext;
    299:          return;
    300:       }
    301:       pCurrent = pNext;
    302:    }
    303:   }
    304:
    305:
    306:   int main()
    307:   {
    308:    List<Part> theList;
    309:    int choice;
    310:    int ObjectNumber;
    311:    int value;
    312:    Part * pPart;
    313:    while (1)
    314:    {
    315:       cout << "(0)Quit (1)Car (2)Plane: ";
    316:       cin >> choice;
    317:
    318:       if (!choice)
    319:          break;
    320:
    321:       cout << "New PartNumber?: ";
    322:       cin >>  ObjectNumber;
    323:
    324:       if (choice == 1)
    325:       {
    326:          cout << "Model Year?: ";
    327:          cin >> value;
    328:          try
    329:          {
    330:             pPart = new CarPart(value,ObjectNumber);
    331:          }
    332:          catch (OutOfMemory)
    333:          {
    334:             cout << "Not enough memory; Exiting..." << endl;
    335:             return 1;
    336:          }
    337:       }
    338:       else
    339:       {
    340:          cout << "Engine Number?: ";
    341:          cin >> value;
    342:          try
    343:          {
    344:             pPart = new AirPlanePart(value,ObjectNumber);
    345:          }
    346:          catch (OutOfMemory)
    347:          {
    348:             cout << "Not enough memory; Exiting..." << endl;
    349:             return 1;
    350:          }
    351:       }
    352:       try
    353:       {
    354:          theList.Insert(pPart);
    355:       }
    356:       catch (NullNode)
    357:       {
    358:          cout << "The list is broken, and the node is null!" << endl;
    359:          return 1;
    360:       }
    361:       catch (EmptyList)
    362:       {
    363:          cout << "The list is empty!" << endl;
    364:          return 1;
    365:       }
    366:    }
    367:    try
    368:    {
    369:       for (int i = 0; i < theList.GetCount(); i++ )
    370:          cout << *(theList[i]);
    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:       catch (BoundsError)
    383:       {
    384:          cout << "Tried to read beyond the end of the list!" << endl;
    385:          return 1;
    386:       }
    387:   return 0;
    388: }

    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 listing modifies the program provided in Week 2 to add templates, `ostream` processing, and exception handling. The output is identical.
On lines 35-39, 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 44, 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 69-73. 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<<` that 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 129-142, `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 `Node`, and there is no object, this is considered an exception, and the exception is thrown on line 174.

On lines 181-197, 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 306-388, 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.