CMSC-341 Spring 2003
Project 2
Assigned |
Feb 9th, 2003 |
|
Due |
Sunday Feb 23, 2003 by 11:59PM |
|
Updates |
Feb 11, 2003
In keeping with our definition of List, you
may assume that there will be no duplicate BUY transactions
It seem's my keyboard was stuck when typing this project
description.... the correct name for the data structure is Deque,
not Dequeue.
|
The List ADT is a fundamental building block for other ADTs such as the
stack and queue. The text describes singly-linked lists and provides an
implementation. In this project you will use the author's list code
(modified by you) to implement the Deque (pronounced "deck") ADT
and then use the Deque in a small application.
Using one ADT to implement another is an important programming
concept known as "layering". The user of the deque doesn't know
there's a LinkedList underneath. The deque's methods are implemented
using the LinkedList methods.
Deque is derived from "double ended queue". It's similar to
a queue, but allows equeuing and dequeing from both ends.
These operations are referred to as "InsertAtFront", "InsertAtBack",
"RemoveFromFront" and "RemoveFromBack". In the C++ STL, stacks
and queues are implemented using a deque.
Pictorially, a deque looks like this.
Description
When you get older and richer, you will probably consider buying
and eventually selling shares of stock in some company. This project
will give you a little insight into this process.
When a share of a common stock of some company is sold, the
profit (or, sometimes, loss) is the difference between the share's
selling price and the share's purchace price. This calculation is easy
to understand for a single purchase and single sale.
When we buy shares of stock over a long period of time and then
decide to sell some (but not all) of them, we must identify the shares
actually being sold. The accepted method for identification is to
assume that the shares being sold are the ones that were bought first
(the ones we've owned the longest).
For example, suppose we buy 100 shares at $10 per share
on day 1; 200 shares at $25 per share on day 2; and 200 shares at $30 per share
on day 3.
Sometime later, we sell 100 shares for $35 each.
Applying the "sell the oldest ones first" principle
means that the 100 shares we sold were the 100 which were bought
on day 1 and our profit on the sale is 100 * (35 - 10) = $2500.
Sometime later we sell 300 shares at $27 per share. These 300
shares consist of the 200 shares bought on day 2 and 100
of the 200 shares bought on day 3. So our profit is
200 * (27 - 25) + 100 * (27 - 30) = $400 - $300 = $100. The 100
shares bought on day 3 will be the first ones sold the next
time we sell shares.
Because shares are sold in the same order they are purchased,
this application can be supported by a FIFO ADT such as a deque.
Class Descriptions
Definition of the Deque
The Deque ADT supports the following set of standard operations.
These operations must be implemented even if you find that not
all of them are required for this project. If necessary, you should
also implement the default constructor, copy constructor, assignment
operator and destructor.
The return types and "const"ness are left to you as is the
deque error handling implementation.
- InsertAtFront( const T& item); -- inserts the item
as the first item in the deque.
- InsertAtBack( const T& item); -- inserts the item
as the last item in the deque.
- RemoveFromFont( void ); -- removes the first item
in the deque.
- RemoveFromBack( void ); -- removes the last item
in the deque.
- IsEmpty( void ) -- indicates whether or not the deque is empty
Your Deque will use a modified version of the author's Linked List
code to actually store the data in the Deque. The author's code
(LinkedList.H and LinkedList.C)
should be copied from Mr. Frey's public directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341.
This code has been modified for g++ v3.2.1 and has been successfully
compiled and tested on linux.
Your modifications must be limited to the following. No other changes
to the Linked List code are permitted.
- The addition of a tail pointer (and associated code changes)
for easier access to the back of the list.
- The addition of one new public method that constructs a ListItr
to the last item in the Linked List.
Note that the Deque may not be a friend of any class or function and no
class or function may be a friend of the Deque.
A transaction class
Your program will read "BUY" and "SELL" transactions from a command
file. The BUY transactions will be stored in the deque. SELL
transactions will be processed as they occur.
You must design and implement the transaction class as you see fit
based on the project requirements. Keep your design simple -- very
few methods or data elements are required. It is not necessary to
implement the default constructor, copy constructor, assigment operator
and destructor if the compiler's default implementation is sufficient.
Project 2 will be invoked with a command line that consists of a single
argument -- the name of the transaction file to read.
As
usual, you should check the validity of all command line arguments.
The Data File
The data file will contain BUY and SELL transactions.
Each transaction will consist of
- The transaction type -- either BUY or SELL
- An integer number of shares of stock
Note:Your application may assume that sufficient
shares have previously been bought for each SELL transaction.
- A floating point price per share (no leading $)
There will be one transaction per line. The file may
contain blank lines. The transaction file used to produce the
sample output is named "txfile" ("tx" is a common industry
abbreviation for "transaction") and may be found in Mr. Frey's
public directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj2
Its contents are listed here
BUY 100 2.00
BUY 400 3.00
SELL 150 5.50
SELL 150 0.50
BUY 300 1.50
BUY 120 5.25
Sample Output
This sample output was produced by
processing the "txfile" in Mr. Frey's public directory which
is shown above.
Although your output does not have to match exactly, it
must meet the following requirements.
- Each transaction must be listed in the order in
which it occurred.
- The profit or loss must be reported for
each SELL transaction. The amount of a loss must
be enclosed in parentheses (a standard accounting practice).
- The total profit of all sales must be reported
- All dollar amounts must be reported with exactly
two decimal places and preceded with a dollar sign ($).
- A list of all shares bought but never sold must
be reported in the order in which the purchases occurred.
linux3[15]% Proj2 txfile
Bought 100 shares at $2.00
Bought 400 shares at $3.00
Sold 150 shares at $5.50 for profit of $475.00
Sold 150 shares at $0.50 for profit of $(375.00)
Bought 300 shares at $1.50
Bought 120 shares at $5.25
Total Profit: $100.00
Unsold Shares
200 shares bought for $3.00
300 shares bought for $1.50
120 shares bought for $5.25
A summary of things to do
- Copy the author's Linked List code to your local directory.
Read and understand it. It will be discussed in class.
- Modify the author's linked list code so that it will support
the Deque operations.
- Implement the Deque class as a template.
- Implement the transaction class to store share and price information
in the deque.
- Implement the application in Proj2.C
- Create a makefile for the project
- Copy the question file from Mr. Frey's public directory and edit
it with your answers.
- Submit your project
Extra Credit
For 10 points of extra credit, do both of the following
- Modify the author's Linked List code so that all Deque operations
run in constant, O( 1 ) time.
- Submit a text file named ExtraCredit.txt that describes the
changes you made and explains why each Deque operation now has
constant time performance.
DO NOT post questions abou the extra credit on the Discussion Board.
Project Submission
Because you are submitting your own makefile, you are free to name your
files whatever you like, with the following restrictions:
- All class definitions appear in .H files. Header files may NOT contain
any code.
- All class implementations appear in .C files.
- The name of your executable MUST BE Proj2 (upper-case 'P'). The
submitrun program and the scripts that we use to grade your files assume
that you follow this convention for naming your executable.
Submit Tools
There are a number of tools available to you to check on
your submittal. It is your responsibility to ensure that the submittal is
correct and will result in a successful compilation of your project. Do not
wait till the last minute to submit your files. Give yourself enough time
to check that your submittal is correct.
If you don't submit a project correctly, you will not get credit for
it. Why throw away all that hard work you did to write the project? Check
your submittals. Make sure they work. Do this before the due date.
Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/.
One of the tools provided by the submit program is submitls. It
lists the names of the files you have submitted.
Additionally, there are two programs which are not part of the
UCS submit program. They are in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/ and are
named submitmake and submitrun. You can use
these programs to make or run your submitted projects.
To access these programs, do one of the following
- Create an alias in your .cshrc file (the preferred method)
alias submitmake /afs/umbc.edu/users/d/e/dennis/pub/CMSC341/submitmake
alias submitrun /afs/umbc.edu/users/d/e/dennis/pub/CMSC341/submitrun
- Type the full path name everytime you run them
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/submitmake cs341 Proj2
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/submitrun cs341 Proj2 txfile
- Copy them to your directory
You will have to give yourself permission to execute these programs
after you have copied them. This is accomplished using the chmod command
The syntax is similar to that for submit:
submitmake <class> <project>
Example: submitmake cs341 Proj2
This makes the project, and shows you the report from the make utility.
It cleans up the directory after making the project (removes .o files), but
leaves the executable in place.
submitrun <class> <project> [command-line args]
Example: submitrun cs341 Proj2 test.dat
This runs the project, assuming there is an executable (i.e. submitmake
was run successfully) and that test.dat is in your local (not submittal)
directory.
Your project will be tested using a variety of command lines, some of which
will be invalid.
Your project will also be tested using a variety of command files which
will test various conditions which your code should handle.
Project grading is described in the
Project Policy handout.
Your answers to
341-Spring03-proj2_questions.txt
are worth 10% of your project grade.
Cheating in any form will not be tolerated. Please re-read the
Project
Policy handout for further details on honesty in doing projects for
this course.
Remember, the due date is firm. Submittals made after 11:59pm of the
due date will not be accepted. Do not submit any files after that time.
Last modified on
Saturday Feb 8, 2003
by
Dennis Frey
email: frey@cs.umbc.edu