Posted: Monday 2/18/02
Design Document Due Date: design2.txt is due before midnight, Sunday 2/24/02
Project Due Date: Before midnight, Sunday 3/3/02

Objectives

• To become familiar with C++ class syntax and coding standards
• To reinforce the concepts of abstraction, encapsulation, and information hiding
• To reinforce the abstractions of pointers and linked lists
• To further practice the use of make files

Project Description

We are going to assume that we are using an operating system where the request for dynamic memory from the heap is quite costly; i.e., a call to new is time consuming. Therefore, we would like to make such requests as infrequently as possible. This can be done by requesting a "chunk" of memory all at once rather than small pieces of memory frequently.

This method will certainly reduce the frequency of calls to new, but we must now have a method for managing the memory "chunk." We must in effect manage our own heap.

We will manage our heap by storing it as a heap object. That is, we will define a heap class where the heap is an array. Each element of the heap will be a structure that can store a single character (the data field) and an integer (the pointer field). Here is the Heap class definition that we will use:

Given the above Heap class definition, a client program can manipulate a linked list of characters. It can do so by asking the heap for the index of the next free cell (a call to newCell). It can also return a node to the heap (a call to freeCell). The contents of a specific list node can be manipulated via the setData and setNext member functions. More detailed documentation for each of the member functions can be found in the actual class header file that is provided for you (see "Further Specification" below).

Note the constant NULLCELL. This constant is used to indicate a null pointer. For example, if the heap has no more free cells, freeListPtr should be set to NULLCELL. Likewise, the last node in the heap's linked list of free cells should contain a "next" pointer whose value is NULLCELL.

Also notice the resize utility function. Your newCell function should request another "chunk" of memory from the system when your heap is full. That is, it should resize array theHeap by some constant number of elements. This way, function newCell returns NULLCELL only when the system heap is out of memory. For example, if the current heap size is 12 and the heap is full, a request for another heap cell should increase the size of the heap by, say, 5. The request for a heap cell can then be fulfilled, with a resulting heap size of 17 and 4 free heap cells remaining.

Further Specification

1. You will be provided with the class definition for the Heap class and a test driver (main function). Note that the test driver may not be the one that is used by the graders, so test the code that you write thoroughly. You can find the completely documented Heap class definition and test driver in my pub directory: /afs/umbc.edu/users/s/m/smitchel/pub/CMSC202/p2/heap.H /afs/umbc.edu/users/s/m/smitchel/pub/CMSC202/p2/proj2.C You will be writing the code for the following:
   • The three non-member functions that are called from main( ). They are:
     • CreateList - Creates a linked list of characters
     • PrintList - Prints the linked list of characters
     • FreeList - Frees the linked list of characters

     Be careful to pass their parameters correctly (by value, reference, or const reference). You may choose to have subfunctions that are called by these three functions, but you are not required to.

   • All of the member functions for class Heap.

     Note that you may not change the Heap class definition in any way. This is the exact file that the graders will use to compile and test your program.

2. Your resize member function must use a resize size of 5 elements. Make this a constant in your Heap class implementation (heap.C) file.

3. Your program should accept two command line arguments. The first argument is the file containing the characters to be read and inserted into the linked list. The second argument is the initial heap size. For example, an invocation of Proj2 chars.dat 7 read from the input file chars.dat and gives the heap an initial size of 7 elements.

Assumptions

• The test driver used by the graders will not call any functions other than CreateList, PrintList, FreeList and the Heap class member functions. In other words, the only capabilities that the test driver will have will be to create a list, print the list, and deallocate the list. For example, it will not attempt to insert a node into the list.

• The user will enter an initial heap size of at least one at the command line.

• The format of an input file is simply a succession of any printable non-whitespace characters.

Sample Runs

Here are some sample runs using a data file called chars.dat that contains the following characters:

Error Handling

Your program, and ALL programs in this class, must handle the following errors:

• Correct number of command line arguments
• All files were successfully opened
• Any input data files are not empty
• Any dynamic storage was successfully allocated

Other Notes

Your program, and ALL programs in this class, should always follow these rules:

• Don't open a data file, whether input or output, until it is needed.
• Close all data files, whether input or output, as soon as they are not needed anymore.
• Do not use the #define preprocessor directive. Use the const statement instead.
• Use dynamic allocation for all arrays (including strings). The only exception is when you are using a temporary string to read a data item in from a file or the keyboard.
• Deallocate any dynamic storage as soon as it is no longer needed.
• Protect all header files with the #ifndef and #endif preprocessor directives.

Project Make File

You are required to submit a make file with this project. The grader should simply need to type "make" and your project should compile and link to an executable called Proj2. The grader should also have the ability to do a "make clean" and "make cleanest."

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

Grading

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

• 70% - Correctness
  • The program behaves the same way that the sample does and the code meets ALL of the project specification.

• 10% - Design
  • Your design was submitted on time.
  • You have made a reasonable attempt at pseudocoding all of the Heap class member functions. (See the specification for design2.txt.

• 20% - CMSC 202 Coding Standards and Documentation
  • Your code follows the CMSC 202 Coding Standards
  • Your program is neatly and well-documented

Project Submission

• heap.C - contains the implementations for the Heap class member functions
• listmanip.C - contains the implementations for CreateList, PrintList, and FreeList, and any functions called by these functions
• listmanip.H - contains the prototypes for the functions in listmanip.C
• Makefile (or makefile) - the make file that builds the Proj2 executable

Submit as follows:

You can check to see what files you have submitted by typing

More complete documentation for submit and related commands can be found here.

Remember -- if you make any change to your program, no matter how insignificant it may seem, you should recompile and retest your program before submitting it. Even the smallest typo can cause compiler errors and a reduction in your grade.