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; } } /** * 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; } /** * 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; }
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;
}
}
/**
* 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;
}
/**
* 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;
}
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 6 images
