The Dog class

To represent a dog, we have provided you with a class called Dog. This class contains the following fields:

• A name for the dog (String)
• An age estimate of the dog (int)
• The number of days they have spent at the shelter (int)
• The number of days until their next vet appointment (int)
• The expected cost (in dollars) of their next vet appointment (double)

Note that this class implements Comparable and several public methods are available to you. Please note thatyou must not modify this class.

The Shelter

A template for the DogShelter class has been provided to you. This class contains a DogNode inner class and a field root which contains a reference to the root node of the tree representing the shelter. This class also implements the interface Iterable and an inner class called DogShelterIterator is also included. Inside the DogShelter class, you will notice several public methods that have already been implemented. These are all non-static methods that will be called on objects of type DogShelter. Most of these methods call methods from the DogNode class that you will need to implement.

The tree we are using to represent a shelter is a tree where we store elements of type Dog. It is a binary search tree when we look at the dog's ages, and a max heap when we look at the number of days the dogs have been spending at the shelter.

The DogNode inner class is used to represent a node in the tree and it contains the following fields:

• Dog d: a reference to an object of type Dog. This is the element/key stored in the node. It contains information regarding a dog in the shelter.
• DogNode younger: this node is the root of the left subtree which stores information about dogs that are younger than the dog stored in the current node.
• DogNode older: this node is the root of the right subtree which stores information about dogs that are older than the dog stored in the current node.
• DogNode parent: this node is the parent node of the current node. Hence it stores information about a dog that has been at the shelter longer than the dog stored in the current node and has therefore higher adoption priority than the dog at the current node.

DogNode.shelter()ONLY ADD CODE IN WHERE IS SAID ADD CODE

This method takes as input a Dog object d and adds it to the tree that has as root the DogNode on which the method was called. The method returns the root to the new tree that now contains d.

As explained above the tree we are trying to implement is a binary search tree when we look at the dog's ages, and a max heap when we look at the number of days the dogs have been spending at the shelter. Adding a new dog d to the tree has to be done in two steps:

1. Add a new node to the tree in the leaf position where binary search determines a node for d should be inserted. (see add() for binary search tree learned in class)
2. Fix the trees so that the properties of the max heap are maintained (i.e. the parent node must have higher adoption priority than its children). This means that we need to perform upheap if needed. Note that since this is also a binary search tree, we need to make sure that when performing upheap we don't break the properties of the binary search tree. To ensure this, instead of performing upheap as seen in class, we will need to implement a tree rotation that reverses the parent-child relationship whenever necessary. Depending if the child that has to be swap in the parent position is the left or the right child, we will need to perform a right rotation or a left rotation. This is how the rotations work:

-To swap the left child in the parent position, we perform a right rotation as follows:

P L

/ \ right rotation/\

LR -------------> AP

/\ /\

A B BR

DogNode.adopt()

This method takes as input a Dog object d and removes the key equals to d from the tree that has as root the DogNode on which the method was called. The method returns the root to the new tree that now does not contain the dog d.

As explained above, the tree we are trying to implement is a binary search tree when we look at the dog's ages, and a max heap when we look at the number of days the dogs have been spending at the shelter. Hence, removing a dog d from the tree has to be done trying to maintain both properties.

1. Remove the node that contains a dog equal to d similarly to how we did it in class. Differently from the algorithm seen in class, when the node to be removed has both children, find the oldest dog oldD in the left subtree, use oldD to replace the dog to be removed, and remove oldD from the left subtree (the algorithm we have seen in class was doing the same thing, but using instead the smallest key from the right subtree).

2. If the changes made from removing the node above broke the properties of the max heap, then perform downheap to fix the tree. Here you want to think about which are the situations in which removing a node would break the properties of the max heap and tackle only such situations. You do not want to blindly perform downheap through the entire tree. As for upheap, also downheap will have to be implemented differently from how we saw in class, since we need to make sure to maintain the properties of the binary search tree. Once again, you will have to determine which of the two children should be swapped in the parent position and based on that perform the correct tree rotation as explained above

Code for dog class

package assignment3;

public class Dog implements Comparable{

private String name;

private int ageEstimate;

private int daysAtTheShelter;

private int daysToNextVetAppointment;

private double expectedVetCost;

public Dog(String name, int ageEstimate, int daysAtTheShelter, int daysToNextVetAppointment, double vetCost) {

this.name = name;

this.ageEstimate = ageEstimate;

this.daysAtTheShelter = daysAtTheShelter;

this.daysToNextVetAppointment = daysToNextVetAppointment;

this.expectedVetCost = vetCost;

}

public String toString(){

String result = this.name + "(" + this.ageEstimate + " , " + this.daysAtTheShelter + ")";

return result;

}

public int getAge() {

return this.ageEstimate;

}

public int getDaysAtTheShelter() {

return this.daysAtTheShelter;

}

public int getDaysToNextVetAppointment() {

return this.daysToNextVetAppointment;

}

public double getExpectedVetCost() {

return this.expectedVetCost;

}

public int compareTo(Dog d) {

int ageDiff = this.ageEstimate - d.ageEstimate;

if (ageDiff != 0)

return ageDiff;

else

return this.daysAtTheShelter - d.daysAtTheShelter;

}

public boolean equals(Object obj) {

return obj instanceof Dog && this.compareTo((Dog) obj) == 0;

}

}