Question

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 not receive credit. (You may assume that the running time for TreeMap’s operations are similar to the LLRB class in the book. You can also read the API for TreeMap to see what the running times for the various methods are.)

• You may not modify the function headers of any of the functions already present.

• The only field you may add to the PriceQueue 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.

//// PRICE JAVA /////

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;

}

}

/////// PRICE QUEUE //////

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

public class PriceQueue implements Iterable<Price> {
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 if it is not already present,
* otherwise it throws an IllegalArugmentException.
*
* @param price the Price to add
*
* @throws IllegalArgumentException if price is already in the queue.
*/
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
   throw new RuntimeException("Not Implemented!!!");
}

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

Answer 1

The modified sourcecode for Price.java is given below:

package queue;

public class Price {

   private int dollars;
   private int cents;
  
   public Price previousPrice;//This will point to the previous price in the queue
  
   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;
   }

}

I have only added a filed called previousPrice to get the price of the previous node added in the queue.

The sourcecode of the PriceQueue.java is given below:

package queue;

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

public class PriceQueue implements Iterable<Price> {
   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
   private TreeMap<Price, Node> priceMap = new TreeMap<Price, PriceQueue.Node>();
  
   // 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 if it is not already present,
   * otherwise it throws an IllegalArugmentException.
   *
   * @param price the Price to add
   *
   * @throws IllegalArgumentException if price is already in the queue.
   */
   public void enqueue(Price price) {
       /*for(Price p : this)
   if (p.equals(price))
   throw new IllegalArgumentException();*/
       if(priceMap.containsKey(price))//Runs in logarithmic time
           throw new IllegalArgumentException();
       Node oldlast = last;
       last = new Node();
       last.price = price;
       last.next = null;
       priceMap.put(price, last);
       if (isEmpty()) first = last;
       else {
           oldlast.next = last;
           last.price.previousPrice = oldlast.price;
       }
       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;
       priceMap.remove(price);//Remove from the pricemap
       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
       boolean status =true;
       //Check whether price already present in the queue or not.
       if(!priceMap.containsKey(price)) {
           status = false;
       }else {
           //Take the node to be deleted
           Node node = priceMap.get(price);//runs in logarithmic time
           //Get a reference to the previous node in the queue
           Node previousNode = null;
           if(node.price.previousPrice != null) {
               previousNode = priceMap.get(node.price.previousPrice);//runs in logarithmic time
           }
           if(previousNode == null)
               first = first.next; //The node that is deleted is the first node in the queue
           else if(node.next == null) {
               last = previousNode; //The node that is deleted is the last node in the queue
           }else {
               previousNode.next = node.next;//The node that is deleted is not a boundary node in the queue
           }
           //reduce size by 1
           n--;
       }
       return status;
   }
  
   /**
   * 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<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;
       }
   }
}

The explanation is given as comments wthin the code itself. There is not testcode given to test. So please run this code with your own testing and let me know any issue so that I can help yopu further.