CSCI 230 -- Data Structures and Algorithms
Project 1 -- Meows and Mutts

Preliminary Submission Deadline: Friday, January 28 at 11:59:59 pm
Final Submission Deadline: Friday, February 4 at 11:59:59 pm

The Meows and Mutts (M&M) animal clinic and kennel has decided to automate the process of scheduling animals for boarding. They want a new program and they are hiring you to write it for them. Since you have negotiated your contract with M&M so that you retain the rights to the software and since you would like to sell it to other kennels, you need to make your program flexible.

M&M, or any other kennel, will provide you with a list of cages, numbered sequentially starting from 0. Each cage has a weight range of the animals that can fit in it. Once the list of cages is known (assume it will not change), you are ready to start scheduling animals. Only accept reservations for the current calendar year (1-1-2000 to 12-31-2000).

The scheduling must handle several operations.

S

chedule an animal starting at a given date. If there are no cages available, add the animal to the waiting list. If the animal is too big or too small to fit into any of the cages, output an appropriate message and add the animal to neither the waiting list nor the schedule. If the animal is scheduled, output a confirmation message.

C

ancel an animal from the schedule or from the waiting list. If the cancellation is from the schedule, go down the queue of waiting animals, and determine if one can fill in the space in the cage. Try animals in order from the waiting list to fill the time slot. This may result in more than one animal being scheduled (e.g. if Fido had a two week time slot, then Alphie might be able to use the first week, and Buffy the second). Output messages indicating the changes to the schedule. Output an appropriate message if the animal is unknown.

R

evise a reservation if possible. If the revision (change) is possible, make the change and output a message. (Hint: within your program, changing a reservation will involve a temporary cancellation and then a check to see if space is available.) If a change cannot be made, do not add the animal to the waiting list. If a change is made by shortening the animal's scheduled time, check to see if any animals from the waiting list can now be scheduled. Output messages appropriate to the operations performed. (This operation is the most complicated; leave it for last!)

A

nimal status: check the status of an animal. Is it scheduled or on the waiting list? When is it scheduled?

P

rint the schedule of animals for a given day.

Design and Implementation

There are many ways this program could be implemented, many different data structures and algorithms that could be used, and many ways the project description could be extended and made more realistic. It will be interesting to think about these issues during the project and as we explore more sophisticated data structures. For now, however, try to keep it as simple as possible. Use the sequential container classes (lists, vectors, deques, stacks and queues) from the standard (STL) library where needed, and use the STL algorithms whenever you can.

Pay particular attention to the design of your classes. Here is an outline of classes you might have:

• A class that represents the date. It should have a constructor that builds a date from a month and day, less-than and greater-than operators, and an addition operator that adds a number of days. It should also have a function that converts from the month and day to the Julian day--the numbered day of the year (1 to 365). We have provided this class for you in

 

 

Project 1 Auxiliary Files Directory  http://www.rpi.edu/dept/cs/cs230/public/projects/project1/

This directory is also accessible directly on the RCS file system as

             /dept/cs/cs230/public/projects/project1

• A class that represents a cage and keeps a schedule for that cage.
• A class that maintains the entire schedule and contains the cages. It should also maintain lists of scheduled and waiting animals.
• A class that stores and provides information about each animal, including its name, weight, and if/when it is scheduled.

The member functions defined for each of these class objects should support the above outlined scheduling operations. They should do so in such a way that the implementation details (the lists, queues, etc.) are hidden from the outside world. Start your programming task by determining which classes do what operations and then decide on the implementations within each class (some will be simple, others not).

Program synopsis and input format

The program will be run with the command-line

 
    animals cages.txt

(You can set program arguments in Developer Studio using the Project->Settings menu, under the Debug tab.) After reading the cages from cages.txt (or whatever name is provided), the program should interactively query the user for input. All output should be to std::cout or std::cerr.

The format of cages.txt is simple. Each line will give the the minimum and maximum weights (integers) for that cage. The cage numbers will be implicit in the ordering of the input file. The number of cages will be determined by the number of input lines. There will be no mistakes in the file.

The interactive queries will have the following formats. First the user should type one of the characters `S', `C', `R', `A', `P', or `Q' (to quit). Small letters should be allowed as well so the program isn't case sensitive.

• For 'S', the program should request the animal and then request the starting date and duration. The animal will be a name and a weight, such as

 
    Fido 11

with the name ending with a whitespace and the weight being an integer. The starting date and duration will be described by 3 integers: a month, a day, and a number of days.
• For `C', a cancellation, the program should just request the animal name (which must match exactly the name in the schedule).
• For `R', a revision, the program should request the animal name and the new starting date and duration.
• For `P', the program should request the starting date (month and day) and the number of days to print the schedule.

Sample input and output are provided in

Project 1 Auxiliary Files Directory  http://www.rpi.edu/dept/cs/cs230/public/projects/project1/

This directory is also accessible directly on the RCS file system as

             /dept/cs/cs230/public/projects/project1

Notes and assumptions

• Each animal may be in the schedule or on the waiting list only once. Therefore, your program should check to see if an input animal is already scheduled or waiting; if so, do not permit a new scheduling operation. If the animal is canceled it may be rescheduled, however.
• An animal occupies a cage all day for each day it is scheduled. Therefore, if it is scheduled for 7 days starting on 8/3 it will occupy the cage for 8/3, 8/4, 8/5, 8/6, 8/7, 8/8, 8/9. (Note that it does not occupy the cage for 8/10!)
• The month and day values that your program reads will be correct and will not go past the end of the year, even at the end of an animal's scheduled stay.
• Be sure to use the string class from the standard library instead of char* for the animal names. It will simplify life considerably. If you haven't used string before, look in a recent reference book on C++.

Implementation environment

You should use the Visual Studio environment and you must submit a makefile. Visual Studio will create one for you but you must explicity tell it to make it available (under the Project menu, select Export Makefile).

Submission dates and guidelines

A preliminary submission is required (see the beginning of the project description for the Preliminary Submission Deadline): each student must submit a brief outline of the design of the classes for the project. Submission should be via email to the TA for your section. This outline should indicate the class declarations, member function declaration (but not implementation) and member variables. It must also include a drawing (done with a text editor) of your classes and their interrelationships. Students not submitting an outline or submitting an obviously thoughtless one by the indicated date will have a 10 point penalty taken from the project grade. During final implementation of the project, students should feel free to revise the design.

The Final Submission Deadline is given at the beginning of the project description. Projects submitted after the deadline will not be accepted for credit. If you do not submit a project before the deadline, you will lose all credit and there will be no opportunity to make up the lost credit.

This project will require a number of files, so submission will require some extra steps. Make sure that every file that you submit has your name, section meeting time, and instructor name in a comment at the top.

Copy your files to RCS: Copy all of the files that you will submit to RCS. This will include a readme file, a makefile and any file with a .cpp suffix or a .h suffix, but not, I repeat not files with a .exe, .dsp, .dsw .ncb or .opt suffix. Your submission must include a text file called readme.txt This file must include your name, section meeting time, and instructor name. In addition, it must include a list of all the inplementation files and any special instructions that the TA will need to know in order to run your program.

Example:

Snoop Doggie Dog
Section 8: Thursday, 6 PM
Eric Breimer 

cage.h
cage.cpp
animal.h
animal.cpp
schedule.h
schedule.cpp
main.cpp

To run the program type
animals cages.txt

Create a tar file: Login to a Unix system and do the following: Create a tar file. Tar is an acronym for Tape Archive. To create a tar file, use the tar command with two flags c (for create) and f (for file), followed by the file name of the tar file (it should have a .tar suffix) followed by the names of all of the files that you want to send. For example the following command:
tar cf temp.tar myfile.h myfile.cpp readme.txt
creates a tar file called temp.tar which contains three files, myfile.h, myfile.cpp and readme.txt.

You will need to check to make sure that the tar file is correct. The best way to do this is to copy the tar file to another directory and run the following command: tar xf temp.tar
After running this command, the files myfile,cpp, myfile.h and myfile.rc will be in the new directory. Here are the unix commands to do this:

mkdir newdir
cp temp.tar newdir/temp.tar
cd newdir
tar xf temp.tar

The first line creates a new directory called newdir, the second copies the tar file to the new directory, the third line makes newdir the current directory, and the fourth line extracts the files.

Copy the tar file: The submission directory is /dept/cs/cs230/project1/. In the submission directory are sub-directories for each section. Copy your tar file to the proper sub-directory. For example, if you are in section 8, copy your tar file to /dept/cs/cs230/project1/section8. The name of your tar file must be login.tar, where login is your RCS login. For example, if your login name is snoopd, your tar file must have the name snoopd.tar. If you want to update your submission, the name of your tar file must be login-2.tar. Keep incrementing the number every time you want to update your file. Therefor, the name of your third update should be login-3.tar and your fourth update should be login-4.tar.

Use the unix copy command cp to copy your submission. For example:

cp temp.tar /dept/cs/cs230/project1/section8/snoopd.tar

Please, make sure you copy your tar file into the subdirectory for your section and verify that the name of your tar file is your RCS login. You will not recieve credit for your submission unless you follow the submission guidelines.

Check list:

• Make sure the name of your tar file matches your RCS user id.
• Make sure you submit to the proper section.
• Make sure your tar file includes all .h and .cpp files.
• Verify that all your files text format before using tar.

Grading criteria

• 30% Code and Design: You must write code that attemps to implement all the classes and functions needed for the project. The code does not have to be correct but a valid attempt at implementing all the components is necessary.
• 15% Coding Guidelines: You must follow the coding guidelines. You can not receive credit for coding guidelines unless you've attempted to implement all the classes and functions needed for the project.
• 10% Compilation: Your code must compile. You can not receive credit for compilation unless you've attempted to implement all the classes and functions needed for the project
• 20% Correctness (Scheduling and Printing): Your code must sucessfully schedule animals. In order to demonstrate the correctness, the schedule function and print schedule function must work.
• 5% Cancel: Your cancel function must work correctly. You can not receive credit for the cancel function unless your schedule and print functions are correctly working.
• 5% Revise: The revise function must work. You can not receive credit for the revise function unless your schedule and print functions are correctly working.
• 5% Animal Status: The animal status function must work. You can not receive credit for the animal status function unless your schedule and print functions are correctly working.
• 10% Preliminary submission:

Academic integrity

Students may discuss the program design, especially the design of the classes. Implementation of class member functions and the main program must be done individually. Sharing of code is expressly forbidden and will be detected by code comparison tools. Projects from all 8 sections will be graded together by the TAs.

1/13/2000