With the following interfaces and classes, I need to write a main method that im

Question

With the following interfaces and classes, I need to write a main method that implements a Fast Removal/Slow Insertion approach using the priority que. In this approach we insert a new element a location such that the queue is always sorted by the key in ascending order. I have put a main method already, I just need to change is so that it matches the above requirements.

public interface PriorityQueue<K,V> {

// Returns the number of items in the priority queue.

public int size();

// Returns whether the priority queue is empty.

public boolean isEmpty();

// Returns but does not remove an entry with minimum key.

public Entry<K,V> min() throws PriorityQueueException;

// Inserts a key-value pair and return the entry created.

public Entry<K,V> insert(K key, V value) throws PriorityQueueException;;

// Removes and returns an entry with minimum key.

public Entry<K,V> removeMin() throws PriorityQueueException;;

}

public class PriorityQueueException extends Exception {

public PriorityQueueException(String s){

    super(s);

}

}

import java.util.Comparator;

import java.util.PriorityQueue;

class PQEntry{

Integer key;

Character value;

public PQEntry(Integer key, Character value){

      this.key = key;

      this.value = value;

}

public String toString(){

      return "(" + key + ", " + value + ")";

}

}

class MyComparator implements Comparator<PQEntry>{

public int compare(PQEntry a, PQEntry b){

      return a.key - b.key;

}

}

public class Main{

public static void main(String[] args){

    MyComparator comparator = new MyComparator();

    SortedListPriorityQueue<Integer, Character> pq

new SortedListPriorityQueue<Integer, Character>(comparator);

    pq.insert(5, 'A'); System.out.println(pq.toString());

    pq.insert(9, 'C'); System.out.println(pq.toString());

    pq.insert(3, 'B'); System.out.println(pq.toString());

    pq.insert(7, 'D'); System.out.println(pq.toString());

    Entry e = pq.min(); String s = "(" + e.getKey() + ", " + e.getValue() + ")";

    System.out.print(s); System.out.println(pq.toString());

    e = pq.removeMin(); s = "(" + e.getKey() + ", " + e.getValue() + ")";

    System.out.print(s); System.out.println(pq.toString());

    System.out.print(pq.size()); System.out.println(pq.toString());

    e = pq.removeMin(); s = "(" + e.getKey() + ", " + e.getValue() + ")";

    System.out.print(s); System.out.println(pq.toString());

    e = pq.removeMin(); s = "(" + e.getKey() + ", " + e.getValue() + ")";

    System.out.print(s); System.out.println(pq.toString());

    e = pq.removeMin(); s = "(" + e.getKey() + ", " + e.getValue() + ")";

    System.out.print(s); System.out.println(pq.toString());

    //Removing comment from the following throws an exception.

    //e = pq.removeMin(); s = "(" + e.getKey() + ", " + e.getValue() + ")";

    //System.out.print(s); System.out.println(pq.toString());

    System.out.println(pq.isEmpty());

}

}

Explanation / Answer

public interface PriorityQueue<K,V> {
// Returns the number of items in the priority queue.
public int size();
// Returns whether the priority queue is empty.
public boolean isEmpty();
// Returns but does not remove an entry with minimum key.
public Entry<K,V> min() throws PriorityQueueException;
// Inserts a key-value pair and return the entry created.
public Entry<K,V> insert(K key, V value) throws PriorityQueueException;;
// Removes and returns an entry with minimum key.
public Entry<K,V> removeMin() throws PriorityQueueException;;
}
  
public class PriorityQueueException extends Exception {
public PriorityQueueException(String s){
super(s);
}
}
import java.util.Comparator;
import java.util.PriorityQueue;

class PQEntry{
Integer key;
Character value;

public PQEntry(Integer key, Character value){
this.key = key;
this.value = value;
}

public String toString(){
return "(" + key + ", " + value + ")";
}
}

class MyComparator implements Comparator<PQEntry>{
public int compare(PQEntry a, PQEntry b){
return a.key - b.key;
}
}
public class Main{
public static void main(String[] args){
MyComparator comparator = new MyComparator();
SortedListPriorityQueue<Integer, Character> pq
new SortedListPriorityQueue<Integer, Character>(comparator);
pq.insert(5, 'A'); System.out.println(pq.toString());
pq.insert(9, 'C'); System.out.println(pq.toString());
pq.insert(3, 'B'); System.out.println(pq.toString());
pq.insert(7, 'D'); System.out.println(pq.toString());
Entry e = pq.min(); String s = "(" + e.getKey() + ", " + e.getValue() + ")";
System.out.print(s); System.out.println(pq.toString());
e = pq.removeMin(); s = "(" + e.getKey() + ", " + e.getValue() + ")";
System.out.print(s); System.out.println(pq.toString());
System.out.print(pq.size()); System.out.println(pq.toString());
e = pq.removeMin(); s = "(" + e.getKey() + ", " + e.getValue() + ")";
System.out.print(s); System.out.println(pq.toString());
e = pq.removeMin(); s = "(" + e.getKey() + ", " + e.getValue() + ")";
System.out.print(s); System.out.println(pq.toString());
e = pq.removeMin(); s = "(" + e.getKey() + ", " + e.getValue() + ")";
System.out.print(s); System.out.println(pq.toString());
//Removing comment from the following throws an exception.
//e = pq.removeMin(); s = "(" + e.getKey() + ", " + e.getValue() + ")";
//System.out.print(s); System.out.println(pq.toString());
System.out.println(pq.isEmpty());
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.