Implement a generic priority queue in Java and test it with an abstract Cryptid class and two concrete Cryptid classes, Yeti and Bigfoot. Create a code package called pq and put all the code for this assignment in it. Write the abstract class Cryptid. A Cryptid has a name (a String) and a public abstract void attack() method. Name should be protected. The class implements Comparable. The compareTo method returns a negative int if the instance Cryptid's name (that is, the name of the Cryptid you called the method on) is earlier in lexicographic order than the name of the other Cryptid (the one passed in as an argument; it returns a positive int if the other Cryptid's name is earlier in lex order, and returns 0 if they are equal (that is, if they have all the same characters.) This part is easy; just have the method call String's compareTo() method on the instance Cryptid's name, with the other Cryptid's name as the argument, and return the result. Extend Cryptid with two concrete classes, Yeti and Bigfoot. In addition to the inherited variable name, Yeti also has a fangLength (a double), a constructor that sets the name and fang length based on its parameters, and a reasonable toString() method. It implements the attack method by printing a message like this: Yolanda the Yeti attacks with their 22.3 cm fangs! Bigfoot has a shoeSize (an int), a constrcutor that sets the name and shoe size based on parameters, and a reasonable toString(). It implements attack() by printing a message like Barbara the Bigfoot stomps with their size 30 feet! Write the class PQ. Give it this exact name; in particular, do not call it PriorityQueue, because the JDK already has a class with this name. The parameterizing type for PQ should be >, because Yeti and Bigfoot inherit Cryptid’s implementation of Comparable, which uses a compareTo that can compare the Yeti or Bigfoot to any Cryptid. Therefore, the parameterizing class must be comparable to any subclass of its superclass (super E). The most efficient way to represent a priority queue is usually with a min heap of E, but you should use an ArrayList of E. You do not need to implement Array List-use the ArrayList class in the JDK. We will also simplify the priority queue by using compareTo() to determine the order in which values come out of the PQ instead of using a separate priority field. You will need to write the insert, min, removeMin, size, and isEmpty methods. Think about the argument and return types of insert, min, and removeMin(), then implement those methods. Insert should add the E to the list. Min should return a reference to the E in the list that is smallest according to the compareTo() calls. RemoveMin should do the same, but also remove the E form the list. Size() and isEmpty() should be easy to implement. Use this driver code, and make sure the output is correct. The Cryptids should always come out of the PQ in ascending lexicographic order by name. package pq; public class PQDriver { public static void main(String[] args) { PQ pqy = new PQ(); pqy.insert(new Yeti("Yolanda", 22.3)); pqy.insert(new Yeti("Jann", 24.1)); pqy.insert(new Yeti("Yacov", 19.7)); pqy.insert(new Yeti("Yesenia", 25.8)); System.out.println("PQ of Yetis: "); System.out.println("size: " + pqy.size()); System.out.println("min: " + pqy.min()); while(!pqy.isEmpty()) pqy.removeMin().attack(); PQ pqc = new PQ(); pqc.insert(new Yeti("Yolanda", 22.3)); pqc.insert(new Yeti("Jann", 24.1)); pqc.insert(new Yeti("Yacov", 19.7)); pqc.insert(new Yeti("Yesenia", 25.8)); pqc.insert(new Bigfoot("Bob", 32)); pqc.insert(new Bigfoot("Babette", 33)); pqc.insert(new Bigfoot("Brian", 29)); pqc.insert(new Bigfoot("Barbara", 30)); System.out.println("PQ of Cryptids: "); System.out.println("size: " + pqc.size()); System.out.println("min: " + pqc.min()); while(!pqc.isEmpty()) pqc.removeMin().attack(); } }
Implement a generic priority queue in Java and test it with an abstract Cryptid class and two concrete Cryptid classes, Yeti and Bigfoot. Create a code package called pq and put all the code for this assignment in it.
- Write the abstract class Cryptid. A Cryptid has a name (a String) and a public abstract void attack() method. Name should be protected. The class implements Comparable<Cryptid>. The compareTo method returns a negative int if the instance Cryptid's name (that is, the name of the Cryptid you called the method on) is earlier in lexicographic order than the name of the other Cryptid (the one passed in as an argument; it returns a positive int if the other Cryptid's name is earlier in lex order, and returns 0 if they are equal (that is, if they have all the same characters.) This part is easy; just have the method call String's compareTo() method on the instance Cryptid's name, with the other Cryptid's name as the argument, and return the result.
- Extend Cryptid with two concrete classes, Yeti and Bigfoot.
In addition to the inherited variable name, Yeti also has a fangLength (a double), a constructor that sets the name and fang length based on its parameters, and a reasonable toString() method. It implements the attack method by printing a message like this:
Yolanda the Yeti attacks with their 22.3 cm fangs!
Bigfoot has a shoeSize (an int), a constrcutor that sets the name and shoe size based on parameters, and a reasonable toString(). It implements attack() by printing a message like
Barbara the Bigfoot stomps with their size 30 feet!
-
Write the class PQ. Give it this exact name; in particular, do not call it PriorityQueue, because the JDK already has a class with this name.
The parameterizing type for PQ should be <E extends Comparable <? super E>>, because Yeti and Bigfoot inherit Cryptid’s implementation of Comparable, which uses a compareTo that can compare the Yeti or Bigfoot to any Cryptid. Therefore, the parameterizing class must be comparable to any subclass of its superclass (super E).
The most efficient way to represent a priority queue is usually with a min heap of E, but you should use an ArrayList of E. You do not need to implement Array List-use the ArrayList class in the JDK.
We will also simplify the priority queue by using compareTo() to determine the order in which values come out of the PQ instead of using a separate priority field.
You will need to write the insert, min, removeMin, size, and isEmpty methods.
Think about the argument and return types of insert, min, and removeMin(), then implement those methods. Insert should add the E to the list. Min should return a reference to the E in the list that is smallest according to the compareTo() calls. RemoveMin should do the same, but also remove the E form the list.
Size() and isEmpty() should be easy to implement.
- Use this driver code, and make sure the output is correct. The Cryptids should always come out of the PQ in ascending lexicographic order by name.
package pq;
public class PQDriver {
public static void main(String[] args) {
PQ<Yeti> pqy = new PQ<Yeti>();
pqy.insert(new Yeti("Yolanda", 22.3));
pqy.insert(new Yeti("Jann", 24.1));
pqy.insert(new Yeti("Yacov", 19.7));
pqy.insert(new Yeti("Yesenia", 25.8));
System.out.println("PQ of Yetis: ");
System.out.println("size: " + pqy.size());
System.out.println("min: " + pqy.min());
while(!pqy.isEmpty())
pqy.removeMin().attack();
PQ<Cryptid> pqc = new PQ<Cryptid>();
pqc.insert(new Yeti("Yolanda", 22.3));
pqc.insert(new Yeti("Jann", 24.1));
pqc.insert(new Yeti("Yacov", 19.7));
pqc.insert(new Yeti("Yesenia", 25.8));
pqc.insert(new Bigfoot("Bob", 32));
pqc.insert(new Bigfoot("Babette", 33));
pqc.insert(new Bigfoot("Brian", 29));
pqc.insert(new Bigfoot("Barbara", 30));
System.out.println("PQ of Cryptids: ");
System.out.println("size: " + pqc.size());
System.out.println("min: " + pqc.min());
while(!pqc.isEmpty())
pqc.removeMin().attack();
}
}
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 1 images
