Add a TreeMap that maps a price to the node before that price in the queue and maps the first price (nothing before it) to null. You will need to maintain this invariant on the TreeMap. You will use the TreeMap to improve the running time of enqueue and delete so that they run in logarithmic time. Because you add a new field (the TreeMap), you need to consider how ALL the methods in the PriceQueue class might need to change in order to correctly maintain the invariants on the TreeMap. public class Price { private int dollars; private int cents; public Price(int dollars, int cents) { if (dollars < 0 || cents < 0 || cents > 99) throw new IllegalArgumentException(); this.dollars = dollars; this.cents = cents; } public String toString() { String answer = "$" + dollars + "."; if (cents < 10) answer = answer + "0" + cents; else answer = answer + cents; return answer; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Price other = (Price) obj; if (cents != other.cents) return false; if (dollars != other.dollars) return false; return true; } } import java.util.Iterator; import java.util.NoSuchElementException; public class Queue implements Iterable { private int n; private Node first; private Node last; // helper linked list class private class Node { private Item item; private Node next; } public Queue() { first = null; last = null; n = 0; } public boolean isEmpty() { return first == null; } public int size() { return n; } public int length() { return n; } public Item peek() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); return first.item; } /** * Adds a Price to the front of the queue if it is not already present * in the queue. * * @param price the Price to be added * @return {@code true} if the Price was added and {@code false} if it was * not added (it was already present in the queue). */ public boolean enqueue(Price price) { for(Price p : this) if (p.equals(price)) return false; Node oldlast = last; last = new Node(); last.price = price; last.next = null; if (isEmpty()) first = last; else oldlast.next = last; n++; return true; } /** * Removes and returns the Price in 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) { if (first == null) return false; if (first.price.equals(price)) { first = first.next; n--; if (first == null) last = null; return true; } Node current = first; while (current.next != null && !current.next.price.equals(price)) current = current.next; if (current.next == null) return false; current.next = current.next.next; n--; if (current.next == null) last = current; return true; } /** * 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; } } }
Add a TreeMap that maps a price to the node before that price in the queue and maps the first price (nothing before it) to null. You will need to maintain this invariant on the TreeMap. You will use the TreeMap to improve the running time of enqueue and delete so that they run in logarithmic time. Because you add a new field (the TreeMap), you need to consider how ALL the methods in the PriceQueue class might need to change in order to correctly maintain the invariants on the TreeMap.
public class Price {
private int dollars;
private int cents;
public Price(int dollars, int cents) {
if (dollars < 0 || cents < 0 || cents > 99)
throw new IllegalArgumentException();
this.dollars = dollars;
this.cents = cents;
}
public String toString() {
String answer = "$" + dollars + ".";
if (cents < 10)
answer = answer + "0" + cents;
else
answer = answer + cents;
return answer;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Price other = (Price) obj;
if (cents != other.cents)
return false;
if (dollars != other.dollars)
return false;
return true;
}
}
import java.util.Iterator;
import java.util.NoSuchElementException;
public class Queue<Item> implements Iterable<Item> {
private int n;
private Node first;
private Node last;
// helper linked list class
private class Node {
private Item item;
private Node next;
}
public Queue() {
first = null;
last = null;
n = 0;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return n;
}
public int length() {
return n;
}
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
return first.item;
}
/**
* Adds a Price to the front of the queue if it is not already present
* in the queue.
*
* @param price the Price to be added
* @return {@code true} if the Price was added and {@code false} if it was
* not added (it was already present in the queue).
*/
public boolean enqueue(Price price) {
for(Price p : this)
if (p.equals(price))
return false;
Node oldlast = last;
last = new Node();
last.price = price;
last.next = null;
if (isEmpty()) first = last;
else oldlast.next = last;
n++;
return true;
}
/**
* Removes and returns the Price in 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) {
if (first == null)
return false;
if (first.price.equals(price)) {
first = first.next;
n--;
if (first == null)
last = null;
return true;
}
Node current = first;
while (current.next != null && !current.next.price.equals(price))
current = current.next;
if (current.next == null)
return false;
current.next = current.next.next;
n--;
if (current.next == null)
last = current;
return true;
}
/**
* 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<Price> iterator() {
return new PriceListIterator(first);
}
// an iterator, doesn't implement remove() since it's optional
private class PriceListIterator implements Iterator<Price> {
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;
}
}
}
![](/static/compass_v2/shared-icons/check-mark.png)
Step by step
Solved in 5 steps with 6 images
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)