package hw5;

import java.util.Iterator; import java.util.NoSuchElementException;

public class PriceQueue implements Iterable { private Node first; // beginning of queue private Node last; // end of queue private int n; // number of elements on queue // TODO - Add a TreeMap that maps prices to the node before that price in the queue // and maps the first price (nothing before it) to null // // NOTE: You will need to modify preexisting methods to maintain the invariant on the TreeMap

// helper linked list class private static class Node { private Price price; private Node next; }

/** * Initializes an empty queue. */ public PriceQueue() { first = null; last = null; n = 0; }

/** * Returns true if this queue is empty. * * @return {@code true} if this queue is empty; {@code false} otherwise */ public boolean isEmpty() { return first == null; }

/** * Returns the number of Prices in this queue. * * @return the number of Prices in this queue */ public int size() { return n; }

/** * Returns the Price least recently added to this queue. * * @return the Price least recently added to this queue * @throws NoSuchElementException if this queue is empty */ public Price peek() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); return first.price; }

/** * Adds the Price to this queue. * * @param Price the Price to add */ public void enqueue(Price price) { for(Price p : this) if (p.equals(price)) throw new IllegalArgumentException(); Node oldlast = last; last = new Node(); last.price = price; last.next = null; if (isEmpty()) first = last; else oldlast.next = last; n++; }

/** * Removes and returns the Price on this queue that was least recently added. * * @return the Price on this queue that was least recently added * @throws NoSuchElementException if this queue is empty */ public Price dequeue() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); Price price = first.price; first = first.next; n--; if (isEmpty()) last = null; // to avoid loitering return price; } /** * Deletes a Price from the queue if it was present. * @param price the Price to be deleted. * @return {@code true} if the Price was deleted and {@code false} otherwise */ public boolean delete(Price price) { // TODO implelment me!!! // Make sure the running time is no worse than logrithmic!!! // You will want to use Java's TreeMap class to map Prices to the node // that precedes the Price in the queue return false; }

/** * Returns a string representation of this queue. * * @return the sequence of Prices in FIFO order, separated by spaces */ public String toString() { StringBuilder s = new StringBuilder(); for (Price price : this) { s.append(price); s.append(' '); } return s.toString(); }

/** * Returns an iterator that iterates over the Prices in this queue in FIFO order. * * @return an iterator that iterates over the Prices in this queue in FIFO order */ public Iterator iterator() { return new PriceListIterator(first); }

// an iterator, doesn't implement remove() since it's optional private class PriceListIterator implements Iterator { private Node current;

public PriceListIterator(Node first) { current = first; }

public boolean hasNext() { return current != null; } public void remove() { throw new UnsupportedOperationException(); }

public Price next() { if (!hasNext()) throw new NoSuchElementException(); Price price = current.price; current = current.next; return price; } } }

The Price Queue class is identical to the Queue class from the book's website with the following modifications: Instead of it being a generic queue, the queue only contains Price objects. The prices in the queue are unique. If a price that is already in the queue is enqueued again, an IllegalArgumentException is thrown. There is an additional unimplemented method called delete that takes a Price argument. You must implement the delete method. Below are the requirements: The delete method takes a Price as an argument and removes the price from the queue if it is present. (If the Price was not present, the method does nothing). The method returns true if the Price was deleted and false otherwise. The method must run in logarithmic time. This is a key requirement. Solutions that are linear or worse will lose 60 points! You may not modify the function headers of any of the functions already present. The only field you may add to the Price Queue class is a single TreeMap. (See Java's API for the TreeMap class. It is basically the same as the book's RedBlackBST class) You may not change or remove the package declaration at the top of the files. The rest of the queue should continue to behave as expected. In particular, the remaining Prices should still come out of the queue in FIFO order. The enqueue and dequeue methods should also run in logarithmic time while the size, peek, and isEmpty methods continue to run in constant time. Note, the enqueue method given to you runs in linear time because it scans the list to see if the price being added is already in the queue. You will need to replace this with a different way of checking that doesn't take linear time. (Hint: Use the map!) You will need to make changes to the Price class as well, but you can only add new functionality. You may not make any changes to the functions that are already there and they must continue to behave as before. The Price Queue class is identical to the Queue class from the book's website with the following modifications: Instead of it being a generic queue, the queue only contains Price objects. The prices in the queue are unique. If a price that is already in the queue is enqueued again, an IllegalArgumentException is thrown. There is an additional unimplemented method called delete that takes a Price argument. You must implement the delete method. Below are the requirements: The delete method takes a Price as an argument and removes the price from the queue if it is present. (If the Price was not present, the method does nothing). The method returns true if the Price was deleted and false otherwise. The method must run in logarithmic time. This is a key requirement. Solutions that are linear or worse will lose 60 points! You may not modify the function headers of any of the functions already present. The only field you may add to the Price Queue class is a single TreeMap. (See Java's API for the TreeMap class. It is basically the same as the book's RedBlackBST class) You may not change or remove the package declaration at the top of the files. The rest of the queue should continue to behave as expected. In particular, the remaining Prices should still come out of the queue in FIFO order. The enqueue and dequeue methods should also run in logarithmic time while the size, peek, and isEmpty methods continue to run in constant time. Note, the enqueue method given to you runs in linear time because it scans the list to see if the price being added is already in the queue. You will need to replace this with a different way of checking that doesn't take linear time. (Hint: Use the map!) You will need to make changes to the Price class as well, but you can only add new functionality. You may not make any changes to the functions that are already there and they must continue to behave as before