## Monday, 13 August 2018

### Algorithms | Animal Shelter

An animal shelter, which holds only dogs and cats, operates on a strictly "first in, first out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog, and dequeueCat. You may use the built-in Linked list data structure.

There are many approaches to solve this problem
1. We could maintain a single queue and keep inserting the element in the Queue. Using a single queue, dequeueAny is easy, but dequeueDog and dequeueCat would require iteration through the queue to find the first dog or cat. This would increase the complexity of the solution and decrease the efficiency.

2. An alternative approach that is simple, clean and efficient is to simply use separate queues for dogs and cats, and to place them within a wrapper class called an AnimalShelterQueue. We will store some sort of time stamp (insertion order) to mark when each animal was enqueued. When we call dequeueAny, will return the oldest of the tops of both the dog and cat queue. For operation dequeueDog and dequeueCat, we will return the top of respective queue.

package com.algorithmforum.cci.stack;
import java.util.EmptyStackException;
import java.util.Queue;

abstract class Animal {
private String name;
private int order;

public Animal(String name) {
this.name = name;
}

public int getOrder() {
return order;
}

public void setOrder(int order) {
this.order = order;
}

public String getName() {
return name;
}

/**
* Inserting the element with Order and incrementing the order by one for every new element.
* Latest element will maintain the largest value of the Order.
*
* @param animal
* @return boolean value
*/
public boolean isOlderThan(Animal animal) {
return this.order < animal.getOrder();
}
}

class Dog extends Animal {
public Dog(String name) {
super(name);
}

@Override
public String toString() {
return "Dog Name: " + this.getName();
}
}

class Cat extends Animal {
public Cat(String name) {
super(name);
}

@Override
public String toString() {
return "Cat Name: " + this.getName();
}
}

/**
* A clean and efficient approach to maintaining separate queues for dogs and cats,
* and to place them within a wrapper class called An AnimalShelterStack.
*
* We then store some sort of time stamp(insertion order) to mark when each animal was enqueued.
* When we call dequeueAny, will return the oldest of the tops of both the dog
* and cat queue.
* @author rajesh.kumar
* @since Aug 13, 2018 11:22:56 AM
*/
public class AnimalShelterQueue {

private Queue dogs;
private Queue cats;
private int order;

public AnimalShelterQueue() {
this.order = 0;
}

/**
* dequeueAny cases:
* #1: if both stacks are empty, throw exception as no Animal will found.
* #2: if dogs stack is empty, return top from the cats stack.
* #3: if cats stack is empty, return top from the dogs stack.
* #4: if cats & dogs contains element, return older of top of both stack.
* @return
*/
public Animal dequeueAny() {

System.out.println("------------------dequeueAny------------------");
if (dogs.isEmpty() && cats.isEmpty()) {
throw new EmptyStackException();
} else if (dogs.isEmpty()) {
return dequeueCat();
} else if (cats.isEmpty()) {
return dequeueDog();
}

/**
* Look at top of dog and cat queues, and pop the queue with the oldest value.
*/
Animal dog = dogs.peek();
Animal cat = cats.peek();
boolean isDog = dog.isOlderThan(cat);

if (isDog) {
return dequeueDog();
} else {
return dequeueCat();
}
}

/**
* Check the type of Animal instance and insert in respective 'stack'.
* @param animal
* @return boolean
*/
public boolean enqueue(Animal animal) {
/**
* order is used as a sort of time stamp.
* It can be used to compare the insertion order of a dog to a cat.
**/
animal.setOrder(order++);
if (animal instanceof Cat) {
} else {
}
}

/**
* Return the top of dogs Queue.
* @return animal
*/
public Animal dequeueDog() {
System.out.println("------------------dequeueDog------------------");
return dogs.poll();
}

/**
* Return the top of cats Queue.
* @return animal
*/
public Animal dequeueCat() {
System.out.println("------------------dequeueCat------------------");
return cats.poll();
}

/**
* Test the queue.
* @param args
*/
public static void main(String[] args) {

AnimalShelterQueue queue = new AnimalShelterQueue();
queue.enqueue(new Dog("dog1"));
queue.enqueue(new Cat("cat1"));
queue.enqueue(new Cat("cat2"));
queue.enqueue(new Dog("dog2"));
queue.enqueue(new Cat("cat2"));
queue.enqueue(new Dog("dog3"));

// Should print 'cat1' as it was the first cat entered in Shelter.
System.out.println(queue.dequeueCat());

// Should print dog1 as it was the first animal entered in Shelter.
System.out.println(queue.dequeueAny());

// Should print cat1 as it is the only cat in the Shelter.
System.out.println(queue.dequeueDog());
}
}

OUTPUT:
------------------dequeueCat------------------
Cat Name: cat1
------------------dequeueAny------------------
------------------dequeueDog------------------
Dog Name: dog1
------------------dequeueDog------------------
Dog Name: dog2