Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is of one the interesting problems I've solved:

An animal shelter holds only dogs and cats, and 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.

My algorithm:

  1. Maintain two Queues, CatQ and a DogQ.
  2. If the user wants a Cat, dequeue from the CatQ, and if he wants a Dog, dequeue from DogQ.
  3. The problem gets trickier for dequeueAny, since there are two Queues and should be served on FIFO basis. While enqueuing, I'm inserting the arrivalTime too, so whichever animal has the lowestarrivalTime will be dequeued first.

Implementation:

static class Node<T>{
    Node<T> next;
    T type;
    String animalName;
    int arrivalTime;
    Node(String name){
        this.animalName = name;
    }

    @Override
    public String toString(){
        return this.animalName;
    }
}

static class Dog{

}

static class Cat{

}


static class Queue<T>{
    Node<T> front, rear;


    public void enq(Node<T> toEnq){
        if(rear==null){
            rear = toEnq;
            front = rear;
        }else{
            rear.next = toEnq;
            rear = rear.next;
        }
    }


    public Node deq(){
        if(front==null){
            System.out.println("Underflow!");
            return new Node("Error");
        }else{
            Node<T> frn = front;
            front = front.next;
            return frn;
        }
    }

    public void printQ(){
        Node<T> temp = front;
        if(this.isEmpty()){
            System.out.println("No animals here");
            return;
        }
        while(temp.next!=null){
            System.out.print(temp.animalName + "->");
            temp = temp.next;
        }
        System.out.println(temp.animalName);
    }

    public boolean isEmpty(){
        return front == null;
    }

}

static class AnimalHouse{
    Queue<Cat> catQ = new Queue<Cat>() ;
    Queue<Dog> dogQ = new Queue<Dog>();
    Node prev, qFront, qRear;
    int arrivalTime = 0;
    public void enq(Node toEnq, String animal){
        toEnq.arrivalTime = this.arrivalTime;
        arrivalTime++;
        if(animal.equals("Cat")){
            catQ.enq(toEnq);
        }else{
            dogQ.enq(toEnq);
        }
    }

    public Node<Dog> deqDog(){
        return dogQ.deq();
    }

    public Node<Cat> deqCat(){
        return catQ.deq();
    }

    public Node deqAny(){
        if(catQ.isEmpty()){
            return deqDog();
        }

        if(dogQ.isEmpty()){
            return deqCat();
        }

        if(catQ.front.arrivalTime < dogQ.front.arrivalTime){
            return deqCat();
        }else{
            return deqDog();
        }

    }

    public void printAnimalHouse(){
        System.out.println("Cats in the Animal House : ");
        catQ.printQ();
        System.out.println("Dogs in the Animal House : ");
        dogQ.printQ();
    }
}


public static void main(String[] args) {
    AnimalHouse myHouse = new AnimalHouse();
    myHouse.enq(new Node<Cat>("bela"), "Cat");
    myHouse.enq(new Node<Dog>("rufus"), "Dog");
    myHouse.enq(new Node<Cat>("browny"), "Cat");
    myHouse.enq(new Node<Dog>("meenu"), "Dog");
    myHouse.enq(new Node<Cat>("chownmy"), "Cat");
    myHouse.enq(new Node<Cat>("pinky"), "Cat");
    myHouse.enq(new Node<Cat>("blacky"), "Cat");
    myHouse.enq(new Node<Dog>("leo"), "Dog");
    myHouse.enq(new Node<Dog>("rockstar"), "Dog");
    myHouse.enq(new Node<Cat>("Google"), "Cat");
    myHouse.enq(new Node<Dog>("Yahoo"), "Dog");
    myHouse.enq(new Node<Cat>("square"), "Cat");
    myHouse.enq(new Node<Cat>("rectangel"), "Cat");
    myHouse.enq(new Node<Cat>("fire"), "Cat");
    myHouse.enq(new Node<Dog>("iota"), "Dog");
    myHouse.printAnimalHouse();
    System.out.println(myHouse.deqAny());       
}

A Problem which I'd like to mention:

There's no particular reason why I made independent Cat and Dog classes; I just wanted to differentiate between those. I had a hard time resolving the issue for differentiating between Node<Cat> and Node<Dog> as it is not possible to find out the data type of generic parameter at runtime. I also don't want to complicate the instantiation process (better see the link), so in the end I had to insert node like this:

myHouse.enq(new Node<Cat>("CatName"), "Cat")

which is somewhat dumb, so are there any suggestions on how I could've made it more sensible?

share|improve this question
1  
Before I fix a spelling error in the title, I have one question: Is a toga party involved? – Damian Yerrick Jan 13 at 15:54
    
@tepples Seems like I missed your point ^_^" – Mayur Kulkarni Jan 13 at 17:01
5  
@MayurKulkarni It is a reference to an American film with the title of "Animal House." I think the reference is intended to be humorous in that in the US the facilities you refer to in your code are generally called animal shelters, not animal houses. So some Americans seeing the title of the question would first think of John Belushi, a fifth of whiskey, and toga parties. As I also did. – starrise Jan 13 at 18:29
    
I like to thank you for this good question. You see that you don't have much experience but you do show an attitude for improving yourself just by this question. I hope you stick around and we can see you evolving – chillworld Jan 13 at 20:39
    
@starrise Hahha LOL – Mayur Kulkarni Jan 14 at 3:47
up vote 10 down vote accepted

Structure

So your structure is definitely a bit off. First of all, you made your Node generic, which is good, as it could theoretically work with any content - which is what you want from a queue. But then, you have fields which just don't belong there, such as animalName (and type, which is just not needed).

So first of all, lets move animalName outside of the node and into the animal classes, where it belongs.

As cats and dogs are both animals, lets also create an Animal class which both extend:

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

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

static class Animal {
    String animalName;

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

    @Override
    public String toString() {
        return this.animalName;
    }
}

Now our Node class makes more sense (we'll remove arrivalTime later as well):

static class Node<T>{
    Node<T> next;
    int arrivalTime;
    T content;
    Node(T content){
        this.content = content;
    }

    @Override
    public String toString(){
        return this.content.toString();
    }
}

This restructuring did break some other parts of your code, but not that many. enq now doesn't work like this, so change it to:

public void enq(Node toEnq){
    toEnq.arrivalTime = this.arrivalTime;
    arrivalTime++;
    if (toEnq.content instanceof Cat) {
        catQ.enq(toEnq);
    } else {
        dogQ.enq(toEnq);
    }
}

Adding new animals is now simpler, and your queue is actually reusable, you can add anything:

myHouse.enq(new Node<Cat>(new Cat("Bella")));

Misc

  • fields should be private as to not expose implementation details
  • you could easily get rid of the arrival time by just having one queue, and if deqAny is called, return the first entry, if deqDog or deqCat is called peek until you find the correct animal, then return that. (This would worsen your performance in some corner-cases, see comments.) A better idea would be to move arrivalTime into Animal, because it's a datapoint for animals, not for nodes. Ideally, you would also use some sort of time instead of a counter, because it makes more logical sense.
  • don't shorten words in variable and method names, it makes code harder to read. Eg; printQ, what's a Q? deq? etc
  • your whitespace usage is a bit off (spaces and vertical whitespace)
  • an error node is not a good idea, nor is printing in a queue. just throw an exception, that way the code using your queue can decide how to handle that case.
  • your AnimalHouse doesn't need to know about the implementation details of the queue. So remove the node fields (which aren't used anyways), and instead of passing and returning nodes, pass and return the content instead and create the nodes inside of the queues.
share|improve this answer
2  
I suggest to test also for instance of Dog because you never know what other kinds of Animals will come up to the shelter ;) – chillworld Jan 13 at 12:28
    
@chillworld oh yes, definitely. Not everything that is not a cat is a dog (I kept the original structure for simplicity). – tim Jan 13 at 12:31
1  
"you could easily get rid of the arrival time by just having one queue" -> No, don't do that. Consider the scenario of having 9001 very young cats and one very old dog, then having a dog lover enter. Your lookup time becomes O(n). Otherwise solid suggestions. – Josh Jan 13 at 19:55
    
@Josh that's true. With my approach, it should be assumed that such corner-cases are unlikely. If they are not, and performance is important, it's not the best approach. Of course, the current approach also has corner-cases; arrivalTime only ever increases, meaning that it will eventually overflow. Anyways, a better suggestion would probably have been to move arrivalTime into Animal where it belongs, and to use dates instead of a counter. – tim Jan 13 at 20:16

I was working on refactoring your code.

When I was finished I saw that @tim already posted an answer.
He address the most what I also wanted to point out, but in mine opinion he forget 1 thing.

myHouse.enq(new Node<Cat>(new Cat("Bella")));

This is not how you should use it.
I come with a Cat, Dog or even a Bird to the shelter, not a Node.

The usage should be :

myHouse.enq(new Cat("bela"));
myHouse.enq(new Dog("rufus"));

This can be done easily by creating the Node in enq method.
With me I added the Node creation even in the Queue class, so I could return the exact Animal from the Queue
Also, throw an error if some people come with Bird because you do not shelter this type of creature.

Also with returning this is mine code :

public Dog deqDog() {
    return dogQ.deq();
}

public Cat deqCat() {
    return catQ.deq();
}

Because the catQ is initialized like this :

Queue<Cat> catQ = new Queue<>();
share|improve this answer

Your self-review is about the same as what I would say .... and the issue is that you are using Node on the public side of the API. The people calling your enq and deq* methods should have no idea that Node is a concept.

You want to have just a string value to give/take from the shelter.

This also fixes the broken generics on the Enq method.

Something like:

public void enq(String name, String animal){
    int time = arrivalTime++;
    if(animal.equals("Cat")){
        catQ.enq(new Node<Cat>(name, time));
    }else{
        dogQ.enq(new Node<Dog>(name, time));
    }
}

With he above, and corresponding changes to the deq methods, the code resolves itself to a simpler problem.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.