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; } } }