1: Add methods peek() and updateFront(E item) to LinkedQueue< E > class. Method peek() should return the item from the front of the queue without removing it from the queue. Method updateFront(E item) should replace the element at the front of the queue with the given item. Headers of the methods are the following:

 public E peek( ) public void updateFront(E item) 

2: When a share of common stock of some company is sold, the capital gain (or, sometimes, loss) is the difference between the share's selling price and the price originally paid to buy it. The rule is easy to understand for a single share, but if we sell multiple shares of stock bought over a long period of time, then we must identify the shares actually being sold. A standard accounting principle for identifying which shares of a stock were sold in such a case is to use a FIFO protocol - the shares sold are the ones that have been held the longest (indeed, this is the default method built into several finance software packages). For example, suppose we buy 100 shares at $20 each on day 1, 20 shares at $24 on day 2, 200 shares at $36 on day 3, and then sell 150 shares on day 4 at $30 each. Then, applying the FIFO protocol means that of the 150 shares sold, 100 were bought on day 1, 20 were bought on day 2, and 30 were bought on day 3. The capital gain in this case would therefore be 100*(30-20)+20*(30-24)+30*(30-36), or 100*10+20*6+30*(-6), or $940.

Write a Java program that

- prompts the user for the name of the file containing a sequence of transactions, - reads from the file transactions of the form "buy x share(s) at $y each" or "sell x share(s) at $y each", assuming that the transactions occur on consecutive days and the values x and y are integers,

- given this input sequence of transactions, the output should be the total capital gain (or loss) for the entire sequence, using FIFO protocol to identify shares, and

the number of shares left (if any).

- If at any point there is an attempt to sell more shares than were bought up until that moment, your program must output a message saying that and finish execution.

You may assume that transactions in a file are always in the specified format, as in the following sample transactions files: transactions.txt, transactions1.txt.

Sample run of the program may look like the following:

Please enter transactions file name: transactions.txt The following transactions were read from the file:

 Buy 100 at $20 Buy 20 at $24 Buy 200 at $36 Sell 150 at $30 Buy 50 at $28 Sell 100 at $32 

 Processing transaction: Buy 100 at $20 Processing transaction: Buy 20 at $24 Processing transaction: Buy 200 at $36 Processing transaction: Sell 150 at $30 Processing transaction: Buy 50 at $28 Processing transaction: Sell 100 at $32 

 Capital gain is $540. There are 120 shares left. 

Another sample run of the program may look like the following:

Please enter transactions file name: transactions1.txt The following transactions were read from the file:

 Buy 10 at $10 Buy 20 at $5 Sell 50 at $8 Buy 50 at $20 

Processing transaction: Buy 10 at $10 Processing transaction: Buy 20 at $5 Processing transaction: Sell 50 at $8 Error: attempt to sell non-existing shares!

Implementation details:

You must use class Transaction to represent a transaction. The code for Transaction class is provided: Transaction.java.

You must use two queues in your program, one for all transactions (all queue) and the other one for "buy" transactions (buy queue).

First, all transactions from the input file should be read and placed in the all queue (the one for all transactions). Then, you should remove transactions from the all queue, one at a time, and process each transaction in the following manner. If it is a buy transaction you place it in a "buy" queue. If it is a sell transaction you use it and transactions from the "buy" queue to compute the change in capital gain (or loss). If there is an attempt to sell more shares than are available, then your program should output a message like "Error: attempt to sell non-existing shares" and finish execution.

In this assignment you need to read data from a file. One way to do it is to use the Scanner class. Scanner class is described in Appendix B of the textbook. You may take a look at an example of opening a text file for reading with Scanner .

Conversion from String to integer may be done as in the following example:

String str = "25";

int i = Integer.parseInt(str); 

*****************java files needed for this assignment*******

// File: LinkedQueue.java from the package edu.colorado.collections // Complete documentation is available from the LinkedQueue link in: // http://www.cs.colorado.edu/~main/docs/

//package edu.colorado.collections;

import java.util.NoSuchElementException; //import edu.colorado.nodes.Node;

/****************************************************************************** * A LinkedQueue is a queue of references to E objects. * *

Limitations:

* Beyond Int.MAX_VALUE items, size is wrong. *

* *

Java Source Code for this class:

* * http://www.cs.colorado.edu/~main/edu/colorado/collections/LinkedQueue.java * * * @author Michael Main * (main@colorado.edu) * * @version * Jul 21, 2005 * * @see ArrayQueue ******************************************************************************/ public class LinkedQueue implements Cloneable { // Invariant of the LinkedQueue class: // 1. The number of items in the queue is stored in the instance variable // manyNodes. // 2. The items in the queue are stored in a linked list, with the front // of the queue stored at the head node, and the rear of the queue at // the final node. // 3. For a non-empty queue, the instance variable front is the head // reference of the linked list of items and the instance variable rear // is the tail reference of the linked list. For an empty queue, both // front and rear are the null reference. private int manyNodes; private Node front; private Node rear;

/** * Initialize an empty queue. * @param - none *

Postcondition:

* This queue is empty. **/ public LinkedQueue( ) { front = null; rear = null; }

/** * Put a new a new item in this queue. * @param item * the item to be pushed onto this queue *

Postcondition:

* The item has been pushed onto this queue. * @exception OutOfMemoryError * Indicates insufficient memory for increasing the queue's capacity. *

Note:

* An attempt to increase the capacity beyond * Integer.MAX_VALUE will cause the queue to fail with an * arithmetic overflow. **/ public void add(E item) { if (isEmpty( )) { // Insert first item. front = new Node(item, null); rear = front; } else { // Insert an item that is not the first. rear.addNodeAfter(item); rear = rear.getLink( ); } manyNodes++; } /** * Generate a copy of this queue. * @param - none * @return * The return value is a copy of this queue. Subsequent changes to the * copy will not affect the original, nor vice versa. Note that the return * value must be type cast to an LinkedQueue before it can be used. * @exception OutOfMemoryError * Indicates insufficient memory for creating the clone. **/ @SuppressWarnings("unchecked") public LinkedQueue clone( ) { // Clone a LinkedQueue. LinkedQueue answer; Node[ ] cloneInfo; try { answer = (LinkedQueue) super.clone( ); } catch (CloneNotSupportedException e) { // This exception should not occur. But if it does, it would probably indicate a // programming error that made super.clone unavailable. The most comon error // The most common error would be forgetting the "Implements Cloneable" // clause at the start of this class. throw new RuntimeException ("This class does not implement Cloneable"); } cloneInfo = Node.listCopyWithTail(front); answer.front = cloneInfo[0]; answer.rear = cloneInfo[1]; return answer; }

/** * Determine whether this queue is empty. * @param - none * @return * true if this queue is empty; * false otherwise. **/ public boolean isEmpty( ) { return (manyNodes == 0); }

/** * Get the front item, removing it from this queue. * @param - none *

Precondition:

* This queue is not empty. *

Postcondition:

* The return value is the front item of this queue, and the item has * been removed. * @exception NoSuchElementException * Indicates that this queue is empty. **/ public E remove( ) { E answer;

if (manyNodes == 0) // NoSuchElementException is from java.util and its constructor has no argument. throw new NoSuchElementException("Queue underflow"); answer = front.getData( ); front = front.getLink( ); manyNodes--; if (manyNodes == 0) rear = null; return answer; } /** * Accessor method to determine the number of items in this queue. * @param - none * @return * the number of items in this queue **/ public int size( ) { return manyNodes; }

}

*******************************************

// File: Node.java from the package edu.colorado.nodes // Complete documentation is available from the Node link in: // http://www.cs.colorado.edu/~main/docs

// package edu.colorado.nodes;

/****************************************************************************** * A Node provides a generic node for a linked list. Each node * contains a piece of data (which is a reference to an E object) and a link * (which is a reference to the next node of the list). The reference stored * in a node can be null. * * @note * Lists of nodes can be made of any length, limited only by the amount of * free memory in the heap. But beyond Integer.MAX_VALUE (2,147,483,647), * the answer from listLength is incorrect because of arithmetic * overflow. * @see * * Java Source Code for this class * (www.cs.colorado.edu/~main/edu/colorado/nodes/Node.java) * * @author Michael Main * (main@colorado.edu) * * @version * Jul 17, 2005 * * @see BooleanNode * @see ByteNode * @see CharNode * @see DoubleNode * @see FloatNode * @see IntNode * @see LongNode * @see ShortNode ******************************************************************************/ public class Node { // Invariant of the Node class: // 1. Each node has one reference to an E Object, stored in the instance // variable data. // 2. For the final node of a list, the link part is null. // Otherwise, the link part is a reference to the // next node of the list. private E data; private Node link;

/** * Initialize a node with a specified initial data and link to the next * node. Note that the initialLink may be the null reference, * which indicates that the new node has nothing after it. * @param initialData * the initial data of this new node * @param initialLink * a reference to the node after this new node--this reference may be null * to indicate that there is no node after this new node. * @postcondition * This node contains the specified data and link to the next node. **/ public Node(E initialData, Node initialLink) { data = initialData; link = initialLink; }

/** * Modification method to add a new node after this node. * @param element * the data to place in the new node * @postcondition * A new node has been created and placed after this node. * The data for the new node is element. Any other nodes * that used to be after this node are now after the new node. * @exception OutOfMemoryError * Indicates that there is insufficient memory for a new * Node. **/ public void addNodeAfter(E element) { link = new Node(element, link); } /** * Accessor method to get the data from this node. * @param - none * @return * the data from this node **/ public E getData( ) { return data; } /** * Accessor method to get a reference to the next node after this node. * @param - none * @return * a reference to the node after this node (or the null reference if there * is nothing after this node) **/ public Node getLink( ) { return link; } /** * Copy a list. * @param source * the head of a linked list that will be copied (which may be * an empty list in where source is null) * @return * The method has made a copy of the linked list starting at * source. The return value is the head reference for the * copy. * @exception OutOfMemoryError * Indicates that there is insufficient memory for the new list. **/ public static Node listCopy(Node source) { Node copyHead; Node copyTail; // Handle the special case of the empty list. if (source == null) return null; // Make the first node for the newly created list. copyHead = new Node(source.data, null); copyTail = copyHead; // Make the rest of the nodes for the newly created list. while (source.link != null) { source = source.link; copyTail.addNodeAfter(source.data); copyTail = copyTail.link; } // Return the head reference for the new list. return copyHead; } /** * Copy a list, returning both a head and tail reference for the copy. * @param source * the head of a linked list that will be copied (which may be * an empty list in where source is null) * @return * The method has made a copy of the linked list starting at * source. The return value is an * array where the [0] element is a head reference for the copy and the [1] * element is a tail reference for the copy. * @exception OutOfMemoryError * Indicates that there is insufficient memory for the new list. **/ public static Node[ ] listCopyWithTail(Node source) { Node copyHead; Node copyTail; Node[ ] answer = (Node[]) new Object[2]; // Handle the special case of the empty list. if (source == null) return answer; // The answer has two null references . // Make the first node for the newly created list. copyHead = new Node(source.data, null); copyTail = copyHead; // Make the rest of the nodes for the newly created list. while (source.link != null) { source = source.link; copyTail.addNodeAfter(source.data); copyTail = copyTail.link; } // Return the head and tail references. answer[0] = copyHead; answer[1] = copyTail; return answer; } /** * Compute the number of nodes in a linked list. * @param head * the head reference for a linked list (which may be an empty list * with a null head) * @return * the number of nodes in the list with the given head * @note * A wrong answer occurs for lists longer than Int.MAX_VALUE. **/ public static int listLength(Node head) { Node cursor; int answer; answer = 0; for (cursor = head; cursor != null; cursor = cursor.link) answer++; return answer; }

/** * Copy part of a list, providing a head and tail reference for the new copy. * @param start/end * references to two nodes of a linked list * @param copyHead/copyTail * the method sets these to refer to the head and tail node of the new * list that is created * @precondition * start and end are non-null references to nodes * on the same linked list, * with the start node at or before the end node. * @return * The method has made a copy of the part of a linked list, from the * specified start node to the specified end node. The return value is an * array where the [0] component is a head reference for the copy and the * [1] component is a tail reference for the copy. * @exception IllegalArgumentException * Indicates that start and end do not satisfy * the precondition. * @exception OutOfMemoryError * Indicates that there is insufficient memory for the new list. **/ public static Node[ ] listPart(Node start, Node end) { Node copyHead; Node copyTail; Node cursor; Node[ ] answer = (Node[]) new Object[2]; // Check for illegal null at start or end. if (start == null) throw new IllegalArgumentException("start is null"); if (end == null) throw new IllegalArgumentException("end is null"); // Make the first node for the newly created list. copyHead = new Node(start.data, null); copyTail = copyHead; cursor = start; // Make the rest of the nodes for the newly created list. while (cursor != end) { cursor = cursor.link; if (cursor == null) throw new IllegalArgumentException ("end node was not found on the list"); copyTail.addNodeAfter(cursor.data); copyTail = copyTail.link; } // Return the head and tail references answer[0] = copyHead; answer[1] = copyTail; return answer; } /** * Find a node at a specified position in a linked list. * @param head * the head reference for a linked list (which may be an empty list in * which case the head is null) * @param position * a node number * @precondition * position > 0. * @return * The return value is a reference to the node at the specified position in * the list. (The head node is position 1, the next node is position 2, and * so on.) If there is no such position (because the list is too short), * then the null reference is returned. * @exception IllegalArgumentException * Indicates that position is zero. **/ public static Node listPosition(Node head, int position) { Node cursor; int i; if (position == 0) throw new IllegalArgumentException("position is zero"); cursor = head; for (i = 1; (i < position) && (cursor != null); i++) cursor = cursor.link;

return cursor; }

/** * Search for a particular piece of data in a linked list. * @param head * the head reference for a linked list (which may be an empty list in * which case the head is null) * @param target * a target to search for * @return * The return value is a reference to the first node that contains the * specified target. If the target is non-null, then the * target.equals method is used to find such a node. * The target may also be null, in which case the return value is a * reference to the first node that contains a null reference for its * data. If there is no node that contains the target, then the null * reference is returned. **/ public static Node listSearch(Node head, E target) { Node cursor; if (target == null) { // Search for a node in which the data is the null reference. for (cursor = head; cursor != null; cursor = cursor.link) if (cursor.data == null) return cursor; } else { // Search for a node that contains the non-null target. for (cursor = head; cursor != null; cursor = cursor.link) if (target.equals(cursor.data)) return cursor; } return null; }

/** * Modification method to remove the node after this node. * @param - none * @precondition * This node must not be the tail node of the list. * @postcondition * The node after this node has been removed from the linked list. * If there were further nodes after that one, they are still * present on the list. * @exception NullPointerException * Indicates that this was the tail node of the list, so there is nothing * after it to remove. **/ public void removeNodeAfter( ) { link = link.link; } /** * Modification method to set the data in this node. * @param newData * the new data to place in this node * @postcondition * The data of this node has been set to newData. * This data is allowed to be null. **/ public void setData(E newData) { data = newData; } /** * Modification method to set the link to the next node after this node. * @param newLink * a reference to the node that should appear after this node in the linked * list (or the null reference if there is no node after this node) * @postcondition * The link to the node after this node has been set to newLink. * Any other node (that used to be in this link) is no longer connected to * this node. **/ public void setLink(Node newLink) { link = newLink; } }

***********************************************

/** Represents a transaction */ public class Transaction { private int number; /** number of shares in the transaction */ private int price; /** price per share in the transaction */ private boolean sell; /** type of the transaction (true if "sell", false if "buy") */ /** Construct a Transaction with specified type, number, and price * Parameters: * s - type of transaction (true if it is a sell transaction, * false otherwise) * n - number of shares * p - price per share * Postcondition: This Transaction has been initialized with the * specified type (s), number (n), and price (p) */ public Transaction(boolean s, int n, int p) { sell = s; number = n; price = p; } /** Determines whether this Transaction is a sell transaction * or not * Returns: * the type of this transaction (true if "sell", false if "buy") */ public boolean isSell() { return sell; } /** Get the number of shares of this Transaction * Returns: the number of shares */ public int getNumber() { return number; } /** Get the price per share of this Transaction * Returns: the price per share */ public int getPrice() { return price; } /** Change the number of shares in this Transaction * Parameter: newNumber - the new number of shares * Postcondition: * This Transaction's number of shares has been changed * to the new number of shares (newNumber) */ public void changeNumber(int newNumber) { number = newNumber; } /** Returns a string representation of the transaction */ public String toString(){ if (sell) return ("Sell " + number + " at $" + price); else return ("Buy " + number + " at $" + price); } }

************** transaction.txt ******

buy 100 shares at $20 each buy 20 shares at $24 each buy 200 shares at $36 each sell 150 shares at $30 each buy 50 shares at $28 each sell 100 shares at $32 each

************** transaction1.txt ******

buy 10 shares at $10 each buy 20 shares at $5 each sell 50 shares at $8 each buy 50 shares at $20 each