\documentclass{article}
\usepackage{hyperlatex}
\newcommand{\hlink}[3]{\xlink{#1}{#2}{#3}\texonly{\footnote{#2}}}
\newcommand{\tild}{\~{}}
\input{techexp}
\texonly{\textheight 9in}
\texonly{\topmargin -0.5in}
\texonly{\oddsidemargin 0.0in}
\texonly{\textwidth 6.5in}
\newcommand{\HlxIcons}{}

\htmltitle{CSCI 230 --- Data Structures and Algorithms --- Project 1}
\htmladdress{~}
\htmlattributes{BODY}{BGCOLOR="#ffffe6"}
\setcounter{htmlautomenu}{2}
\htmlonly{\setcounter{secnumdepth}{0}}
\setcounter{htmldepth}{0}

\title{CSCI 230 --- Data Structures and Algorithms\\
       Project 1 --- Meows and Mutts}

\author{~}
\begin{document} \maketitle

\subsection*{Preliminary Submission Deadline: Friday, January 28 at \mbox{11:59:59~pm}\\
Final Submission Deadline: Friday, February 4 at \mbox{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.
\begin{description}
\item[{\bf 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.

\item[{\bf 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.

\item[{\bf 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!)

\item[{\bf A}] nimal status: check the status of an animal.  Is it scheduled
or on the waiting list?  When is it scheduled?

\item[{\bf P}] rint the schedule of animals for a given day.
\end{description}

\subsection*{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:
\begin{itemize}

\item  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
\begin{center}
\hlink{Project 1 Auxiliary Files Directory}{http://www.rpi.edu/dept/cs/cs230/public/projects/project1/}{}
\end{center}
This directory is also accessible directly on the RCS file system
as\begin{verbatim}
             /dept/cs/cs230/public/projects/project1
\end{verbatim}

\item  A class that represents a cage and keeps a schedule for that
cage.

\item  A class that maintains the entire schedule and contains the
cages.  It should also maintain lists of scheduled and waiting
animals.

\item  A class that stores and provides information about each animal,
including its name, weight, and if/when it is scheduled.

\end{itemize}
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).


\subsection*{Program synopsis and input format}

The program will be run with the command-line
\begin{verbatim} 
    animals cages.txt
\end{verbatim}
(You can set program arguments in Developer Studio using the
Project{\tt ->}Settings menu, under the Debug tab.)  After reading the cages
from {\tt cages.txt} (or whatever name is provided), the program
should interactively query the user for input.  All output should be
to {\tt std::cout} or {\tt std::cerr}.

The format of {\tt 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.
\begin{itemize}

\item  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
\begin{verbatim} 
    Fido 11
\end{verbatim}
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.
\item  For `C', a cancellation, the program should just request the
animal name (which must match exactly the name in the schedule).
\item  For `R', a revision, the program should request the animal name
and the new starting date and duration.
\item  For `P', the program should request the starting date (month and
day) and the number of days to print the schedule.
\end{itemize}
Sample input and output are provided in 
\begin{center}
\hlink{Project 1 Auxiliary Files Directory}{http://www.rpi.edu/dept/cs/cs230/public/projects/project1/}{}
\end{center}
This directory is also accessible directly on the RCS file system
as\begin{verbatim}
             /dept/cs/cs230/public/projects/project1
\end{verbatim}

\subsection*{Notes and assumptions}


\begin{itemize}

 \item  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.
\item  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!)
 
 \item  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.

 \item  Be sure to use the {\tt string} class from the standard
library instead of {\tt char*} for the animal names.  It will
simplify life considerably.  If you haven't used {\tt string}
before, look in a recent reference book on C++.

\end{itemize}

\subsection*{Implementation environment}

You should use the Visual Studio environment and 
you {\bf 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).


\subsection*{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 (in part based on the feedback).

The Final Submission Deadline is given at the beginning of the project
description.  Projects submitted after the deadline will
\emph{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.

{\bf 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 {\tt .cpp} suffix or a {\tt .h}
suffix, but {\em not}, I repeat {\em not} files with a 
{\tt .exe}, {\tt .dsp}, {\tt .dsw} {\tt .ncb} or {\tt .opt}
suffix. Your submission must include a text file called {\tt readme.txt}
This file must include your name, section meeting time, 
and instructor name.  In addition, it {\bf 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:
\begin{verbatim}
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
\end{verbatim}


{\bf Create a tar file:} Login to a Unix system and do the following:
Create a {\tt tar} file. Tar is an acronym for Tape Archive.
To create a tar file, use the tar command with two flags {\tt c}
(for create) and {\tt f} (for file), followed by the file name of
the tar file (it should have a {\tt .tar} suffix) followed by
the names of all of the files that you want to send.  For example
the following command:\\
\verb+   tar cf temp.tar myfile.h myfile.cpp readme.txt+\\
creates a tar file called {\tt temp.tar} which contains
three files, {\tt myfile.h, myfile.cpp} and {\tt 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:
\verb+ tar xf temp.tar+\\
After running this command, the files {\tt myfile,cpp, myfile.h}
and {\tt myfile.rc} will be in the new directory. 
Here are the unix commands to do this:
\begin{verbatim}
mkdir newdir
cp temp.tar newdir/temp.tar
cd newdir
tar xf temp.tar
\end{verbatim}
The first line creates a new directory called {\tt newdir}, the
second copies the tar file to the new directory, the third line
makes {\tt newdir} the current directory, and the fourth line
extracts the files.


{\bf Copy the tar file:} The submission directory is {\tt /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 
{\tt /dept/cs/cs230/project1/section8}.
The name of your tar file must be {\em login}{\tt.tar},
where {\em login} is your RCS login.  For example,
if your login name is {\tt snoopd}, your tar file must 
have the name {\tt snoopd.tar}.  If you want to update your
submission, the name of your tar file must be
{\em login}{\tt-2.tar}.  Keep incrementing the number every time
you want to update your file.  Therefor, the name of your 
third update should be {\em login}{\tt-3.tar} and your fourth
update should be {\em login}{\tt-4.tar}.

Use the unix copy command {\tt cp} to copy your submission.  For
example:

\verb+cp temp.tar /dept/cs/cs230/project1/section8/snoopd.tar+

{\bf 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. 
{\bf You will not recieve credit for your submission unless
you follow the submission guidelines.}

{\bf Check list:}
\begin{itemize}
\item  Make sure the name of your tar file matches your RCS user id.
\item  Make sure you submit to the proper section.
\item  Make sure your tar file includes all .h and .cpp files.
\item  Verify that all your files text format before using tar.
\end{itemize}


\subsection*{Grading criteria}

\begin{itemize}
\item 30\% {\bf 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.
\item 15\% {\bf 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.
\item 10\% {\bf 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
\item 20\% {\bf 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.  
\item 5\% {\bf 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.
\item 5\% {\bf Revise:} The revise function must work. You can not receive credit for the revise function
unless your schedule and print functions are correctly working.
\item 5\% {\bf 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.
\item 10\% {\bf Preliminary submission:}
\end{itemize}


\subsection*{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.

\end{document}
