## CS 151 - Introduction to Data Structures

### Using Stacks

There are three parts to this homework. In the first part you will complete a partial implementation of an array-based stack. In the second and third parts you will use that stack to compute capital gains on stock transactions

Create a new folder, presumably named Assignment5, and copy the following code into it.
• StackIntf.java
• ArrayStackHW5.java
Also get the following data files
• A.csv
• B.csv
• C.csv
• baA.csv
• bsABC.csv
All of the code is available on goldengate (and all of the lab computers) in the directory /home/gtowell/Public/151/A05/. Use cp or scp as needed to copy this code to the directory containing the work for this assignment.

## Gains and Losses in the Stock Market

#### 80 percent

When you buy and sell stocks in the United States your taxable "capital gains" are computed using a queue or a stack. For instance, suppose that you made the following trades
```		Buy 150 shares at \$5 per share
Buy 100 shares at \$10 per share
Sell 200 shares at \$8 per share
Sell 150 at \$12
```
Then, using the stack approach, the "capital gain" (or loss) is computed by "selling" as much of the most recent purchase as is necessary to offset the sale. If there is not enough, use the next oldest, etc. So given my example data, the capital gain as a result of the first sale would be:
```		100*(8-5) + 100*(8-10)
100*3 + 100*-2
300 - 200
100
```
and the gain from the second sale would be
```		100*(12-10) + 50*(12-5)
100*2 + 50*7
200 + 350
550
```
The queue based calculation is similar except that you use the oldest purchase rather than the newest purchase. (Note that these give different results, the queue approach shows a gain of 350 on the first sale.) You can read about calculating capital gains, in great depth, on the internet.

In this assignment, you will do a stack based calculation of capital gains.

Thre are 5 data files, 3 containing pricing data and 2 containing trades. The price files are actual daily prices for 3 stocks from 2010 through 2021. I will just refer to these as A, B and C. Every price file contains exactly 2923 rows. In the price file, the only data you actually care about is column 5 (start counting at 1). Ignore everything else, even the date. Price files are cleverly named A.csv, B.csv and C.csv

The trading files contains three columns as follows:

1. date The date is an integer in the range 1-2923. It is strictly increasing. The number refers to a row in the price file.
2. stock Either A, B, or C indicating which stock is being traded.
3. amount of purchase or sale A positive or negative integer. The net number of shares held will never be less than zero.
So, the idea is to read in the price files and just hold onto them. Then with the trade file, read and process one line at a time. If a purchase, push information onto a stack. If a sale, compute gains, popping the stack as needed to do so. (I.e., pop from the stack when the number of shares in the purchase at the top of the stack is zero.)

### Step 0

#### 10 Percent

Write a system for reading and holding the price data, in a convenient and useful form. I recommend starting with the venerable ReadCSV code. I do not consider and ArrayList containing Arrays of Strings to be a useful form.

### Step 1

#### 55 Percent

In this step, just get the system working for a single company using the file bsA.csv. Your program should show the capital gains resulting from each sale as well as the total capital gains. For instance, the output of my program is:
```661 SELL 354 net -6060.480000000001
1144 Sell 29 net 1367.3500000000001
1144 SELL 252 net 8625.960000000005
1611 SELL 48 net 1034.88
2094 SELL 106 net -563.9199999999993
2384 Sell 14 net 62.44000000000011
2384 SELL 45 net 913.5000000000005
2772 SELL 111 net -3872.7899999999986
[A a=9700 p=143.07, A a=221 p=187.90, A a=91 p=177.31, A a=59 p=166.73]
Total net Capital Gains = 1506.9400000000064
Shares remaining: 10062
```
The line "[A ...]" is the remaining purchases on the stack after all of the trades have been processed.

### Step 2

#### 15 Percent

Only work on this after you have the previous part compeltely working.
Get your system working for 3 companies. The output should be similar to that of your single company system, except that you should indicate which company the sale is for. For this part, I imagine that somewhere in your code you will have a line like:
```		String[] companies = {"A", "B", "C"};
```
which comtains the names of all of the companies you are processing. Alternately you could build this information on the fly while reading the the trades file -- that is just a little harder.

Your system must scale up easily to handle 1000 (or more) companies. You should probably use Maps or hashtables to hold all of the information. For instance, you might hold price information in a structure such as:
```		Map151<String, ArrayList<StockPriceData>>
```
That is, you have a Map that has a key of a string (the stock symbol) and the value is an ArrayList of a class named "StockPriceData".

Your system should read each file exactly once. That is, do not read the trades file once to process the trades for A, then read it again for B, ... Similarly, do not create a preprocessor that splits the bsABC.csv file up into three separate files; one for A, one for B and one for C.

### What to Turn In

1. All code your wrote or edited, well commented
2. README with the usual information.
3. A script file (see directions for collecting a script in assignment 4) showing the output of your program both parts 2 and 3. (These can be separate files, or a single file, or included in the README)

#### Electronic Submissions

Your program will be graded based on how it runs on the department’s Linux server, not how it runs on your computer. The submission should include the following items: