Project 5

The List ADT

Posted: Monday, 11/25/02
Design Document Due: No Design Document
Project Due: Before midnight, Tuesday 12/10/02
NOTE - this due date is two days more than the usual two weeks because of the Thanksgiving holiday. Students are encouraged to submit assignments earlier than 12/10 to have sufficient time to study for finals. The first day of finals (including Mr. Raouf's final) is 12/12/02.
Notes 26 Nov
a const version of operator[] has been added to the specification. The non-const version has not been removed. The reasoning behind all this can be found on the discussion board, or ask a TA or instructor. List.H in F & R's public directory has been changed for this addition.
26 Nov
Two clarifications regarding duplicate data items
  1. remove( ) always removes just one data item, even if there are duplicates. For example, if a list of ints has four 5s in it, then after list.remove(5), the list will have three 5s in it.
  2. unique( ) always leaves one of the duplicates in the list. For example if a list of ints has six 9s in it, then after calling list.unique( ), the list will have one 9.

Objectives

Project Description

One of the fundamental tasks you will be asked to perform in the real world is to design and implement software based on a specification agreed upon with a client (or dictated to you by your boss). In this project you will do exactly that.

You have been awarded a contract by the F & R software company to implement the List ADT as a class template based on the specification you and the head honchos at F & R have agreed upon.

Recall the List ADT presented in class:

You will implement the List ADT according to the interface specified below. On or about Dec. 8th, 2002, someone from F & R will provide you with the test harness (driver) they have written to test your class. In the meantime, you will be writing your code and testing it yourself. You should expect that F & R's driver may create lists of primitive types (ints, strings) or user-defined classes (eg Books, Patrons) to test your class.

The List ADT specification

You and the folks from F & R have agreed upon the following specification and class interface. Because you will eventually be giving F & R your source code, some implementation decisions have also been agreed upon.

Miscellaneous:

  1. The name of the class will be List.
  2. You will provide a class template for the List class.
  3. The name of the implementation file will be List.C
  4. The name of the header file will be List.H
  5. Since the List, List exceptions and the non-member function(s) specified are closely related, all may defined in List.H and implemented in List.C.
  6. You have agreed to a linked list implementation. The choice of single linked list, double linked list, circular linked list, etc. is left to your discretion. An array implementation is not permitted.
  7. The linked list node class must be defined in LLNode.H and implemented in LLNode.C.
  8. All data members and methods of the linked list node class must be private.
  9. The list need not be sorted at all times, but may be sorted if you choose. Note that a sort() method is required.
  10. Duplicate data items ARE allowed.

List class interface

You have agreed to the following interface. The function signatures are etched in wet concrete. They cannot be changed without express written permission of F & R management.

List.H

The interface for the List class is provided in List.H which can be copied from F & R's public directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC202/proj5/List.H

You are responsible for complete documentation of the header file per CMSC 202 coding standards. You are at liberty to decide upon the private data members and private methods. Only operator<< may be a friend of the List class.

Interface Description

This interface description uses T for the template parameter where needed. See List.H for complete, syntactically correct prototypes. Exceptions may only be thrown where indicated below. All methods must handle empty lists properly.
  1. List( ) - the List default constructor that creates an new empty list.
  2. List (const List&) -- the List copy constructor that creates a new list as a deep copy of the list parameter.
  3. ~List( ) -- the List destructor that completely destroys the list.
  4. operator=( const List&) -- the List assignment operator that assigns one existing List object to another.
  5. makeEmpty( ) - removes all data items from the list without destroying the list.
  6. isEmpty( ) -- returns true if the list is empty, false if not empty.
  7. isFull( ) -- returns true if the list is full, false if not full.
  8. size( ) -- returns the number of elements currently stored in the list.
  9. operator[] (int k) -- returns the data item in the kth position. Recall that positions range from 1 to N. If k is invalid for the list, operator[] throws the ListIndex exception.
  10. insert (const T& data) -- inserts data into the list. Returns true if the insertion is successful, false if the insertion fails. For example, an insertion may fail because the list is full. The choice of where to insert data items into the list (front, back, or somewhere else) is left up to you.
  11. remove(const T& data ) -- removes data from the list. Returns true if the remove is successful, false if remove fails. For example, remove() may fail because the list is empty or the data does not exist in the list.
  12. sort ( ) -- rearranges the list in sorted order from smallest data item to largest data item.
  13. reverse( ) -- reverses the order of the data items in the list.
  14. unique( ) -- removes all duplicate data items from the list.
  15. void merge(const List& List1) -- merges List1 into the host list. To merge two lists means to take two lists which are sorted from smallest to largest and combine them into one large sorted list which contains all elements of the original lists.
    For example if the host list = (2, 4, 8, 10) and List1 = (1, 8, 12), then after merge() the host list = (1, 2, 4, 8, 8, 10, 12). If the host list is not sorted from smallest to largest, merge() sorts it. If List1 is not sorted from smallest to largest, merge() throws the ListNotSorted exception.

Other functions

In addition to the List methods described above, the following non-member function must also be supplied. The prototype is completely specified in List.H
  1. operator<< - the list output operator that prints each data item followed by end-of-line (endl).

The LLNode class

Since the type of linked list is up to you, the linked list node class definition is up to you, except that all data and member functions must be private. The List class should be made a friend of the linked list node class. (Note - by making the List class a friend, all List methods are made friends). The linked list node class must be defined in LLNode.H and implemented in LLNode.C.

Exception classes

The agreed upon specification requires these exception classes. These exception classes require no data and no methods. These classes and their trivial implementation may be defined in List.H.

Some Thoughts on Development

Implementing classes from a specification such as this is a common programming task. The best strategy for developing the code is "incremental development". In the incremental development strategy, one small piece of code (method) is written and tested. When the code passes all tests, another small piece of code is written and tested. This incremental process continues until the entire class is complete.

So where do you begin? How about the default constructor? You can't do much until you create a list. Then what? It's hard to do much of anything without being able to insert data. How do you know if the data's really being inserted? What about printing it out? After you have these three fundamental operations working, you can choose which method to implement next.

There seems to be lots of code to write. In reality, almost all the methods/functions are less than 15 lines of code and some are as little as one line of code. You'll find some helpful code in the text too.

One other thought.....think about how to use code you already wrote (ie other List methods) to implement new List methods. If you choose the order which methods are implemented wisely, you can save yourself alot of coding.

Project Make File

You must submit a makefile for this project. The test file provided by F & R will be named Proj5.C. Graders should be able to type "make Proj5" and have the executable compile and link without error.

See the 202 Syllabus for links to more information on make files.

Grading

The grade for this project will be broken down as follows: