Animal Shelter Management C++

Question

I am working my way through "Cracking the Coding Interview" and I came up the question(3.6) to design a data structure to manage an Animal shelter with 2 animals, Cats, and Dogs such that when we dequeue the oldest animal should be removed first (FIFO)

E.g. if the animals were taken in order C,C,D,C,C,D (C- Cat, D- Dog) and someone wants to adopt an animal there could be 3 ways either adopt D, adopt C, or adopt any(I have just implemented for any as other two are trivial). If the person chooses to adopt D the first D to come in would be chosen from the queue similarly with C. If the person has no preference either of C, D who came first can be chosen.

I implemented it as below. What all improvements can be done here? One possible way is to improve printQueue() function using 'this'.

#include <iostream>
#include <queue>

using namespace std;

class Animal {
public:
    virtual string getClassName() = 0;

    inline int getOrder() {
        return _order;
    }

    void setOrder(int order) {
        _order = order;
    }

    int setType(string type) {
        _type = type;
    }

    inline string getType() {
        return _type;
    }

    bool Compare(Animal* animal) {
        if (this->_order > animal->_order)
            return true;
        return false;
    }
private:
    int _order;
    string _type;
};

class Cat : public Animal {
public:
    Cat(string name) : _name(name) {
    }

    inline string getClassName() {
        return "Cat";
    }

    inline string getName() {
        return _name;
    }

private:
    string _name;
};

class Dog : public Animal {
public:
    Dog(string name) : _name(name) {
    }

    inline string getClassName() {
        return "Dog";
    }

    inline string getName() {
        return _name;
    }

private:
    string _name;
};

class AnimalQueue {
public:
    void enqueue(Animal* animal) {
        if (animal->getClassName() == "Cat") {
            Cat* d = dynamic_cast<Cat*>(animal);
            if (!d) {
                cout << "\nCasting Error";
            }
            else {
                cout << "\nEnqueued Cat";
                d->setOrder(++queueOrder);
                d->setType(animal->getClassName());
                catQueue.push(d);
            }
        }
        else{

            Dog* d = dynamic_cast<Dog*>(animal);
            if (!d) {
                cout << "\nCasting Error";
            }
            else {
                cout << "\nEnqueued Dog";
                d->setOrder(++queueOrder);
                d->setType(animal->getClassName());
                dogQueue.push(d);
            }
        }
    }
    void dequeue() {
        if (catQueue.empty()) {
            dogQueue.pop();
        }
        if (dogQueue.empty())
        {
            catQueue.pop();
        }
        //Pop with smaller timestamp
        if (catQueue.front()->Compare(dogQueue.front())) {
            dogQueue.pop();
        }
        else {
            catQueue.pop();
        }
    }

    void printQueue() {
        queue<Cat*> cQueue = this->catQueue;
        queue<Dog*> dQueue = this->dogQueue;

        cout << "\nCat Queue\n";
        while (!cQueue.empty()) {
            cout << cQueue.front()->getName() << " ";
            cout << cQueue.front()->getOrder();

            cout << endl;
            cQueue.pop();
        }

        cout << "\nDog Queue\n";
        while (!dQueue.empty()) {
            cout << dQueue.front()->getName() << " ";
            cout << dQueue.front()->getOrder();

            cout << endl;
            dQueue.pop();
        }

    }

    queue<Dog*> getDogQueue() {
        return dogQueue;
    }

    queue<Cat*> getCatQueue() {
        return catQueue;
    }

private:
    queue<Cat*> catQueue;
    queue<Dog*> dogQueue;
    int queueOrder = -1;
};

int main()
{   
    Animal* d1 = new Dog("Max"),*d2 = new Dog ("Shaun"), *d3 = new Dog("Tiger");
    Animal* c1 = new Cat("Trace"), *c2 = new Cat("Han"), *c3 = new Cat("Meow");

    AnimalQueue queue;
    queue.enqueue(d1);
    queue.enqueue(c1);
    queue.enqueue(c2);
    queue.enqueue(d2);
    queue.enqueue(d3);
    queue.enqueue(c3);

    cout << endl;
    queue.printQueue();

    cout << endl;

    queue.dequeue();
    queue.printQueue();
}

Answer 1

To supplement the other reviews, here are some other things you might improve.

Use override where appropriate

When a virtual function is being overridden, it should be marked override to allow catching errors at compile time. See C.128.

Make sure all paths return a value

The setType routine claims it returns an int but it does not. That's an error that should be addressed.

Don't use std::endl if you don't really need it

The difference betweeen std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

Think carefully about object ownership

The traditional role of a shelter is to take in animals and then give them to a new owner on adoption. This shelter seems to only do bookkeeping of the location of animals (by handling only pointers) rather than actually taking ownership of them. What is actually a more appropriate way to express this is by the use of a std::unique_ptr. See R.20

Think carefully about the domain and range of numbers

The _queueOrder increases without bound and is used to assign the _order of each animal. What happens when that number wraps around?

Use polymorphism effectively

Whenever you find yourself writing code like this:

if (animal->getClassName() == "Cat") {
        Cat* d = dynamic_cast<Cat*>(animal);

stop and question whether this is really needed. By using animal->getClassName() as a sort of home-grown polymorphism, the code is made much more brittle and hard to maintain. Here's how I'd write that using a std::unique_ptr instead:

void enqueue(std::unique_ptr<Animal> &&animal) {
    animal->setOrder(++queueOrder);
    if (typeid(*animal) == typeid(Cat)) {
        catQueue.push_back(std::move(animal));
    } else if (typeid(*animal) == typeid(Dog)) {
        dogQueue.push_back(std::move(animal));
    } else {
        throw std::runtime_error("This animal is not suitable for the shelter");
    }
}

Note that this uses true RTTI, built into the language, instead of inventing a poor imitation. It also throws an error if the passed animal is neither a cat nor a dog. This could be handy if someone attempted to drop off a pet rhinocerous.

Don't expose class internals

It seems to me that getDogQueue and getCatQueue are both ill-advised and unneeded. I'd simply omit them both.

Base destructors should be virtual

The destructor of a base class, including a pure virtual one like Animal, should be virtual. Otherwise, deleting the object could lead to undefined behavior and probably memory leaks.

Consolidate common items into a base class

Since all of the derived classes have _name, why not move that functionality into the base class?

Use const where practical

The getName() function does not alter the underlying class because it returns a copy of the name. Similarly, the getClassName() function does not alter the class. Both should be declared const.

Use standard operators

Rather than the vaguely named Compare, better would be to simply use the standard operator<. Here's how I'd write it as a member function of Animal:

bool operator<(const Animal& b) const {
    return _order < b._order;
}

Use better names

Most of the names are not bad, but rather than AnimalQueue and enqueue and dequeue, I'd suggest giving them more usage-oriented names rather than describing the internal structure. So perhaps AnimalShelter, dropoff and adopt would be more suitable.

Think carefully about data types

If you use a std::deque instead of a std::queue, you gain access to iterators which are useful for printing as shown in the next suggestion.

Use an ostream &operator<< instead of display

The current code has printQueue() function but what would make more sense and be more general purpose would be to overload an ostream operator<< instead. This renders the resulting function much smaller and easier to understand:

friend std::ostream& operator<<(std::ostream& out, const AnimalShelter& as) {
    out << "\nCat Queue\n";
    for (const auto& critter : as.catQueue) {
        out << *critter << '\n';
    }
    out << "\nDog Queue\n";
    for (const auto& critter : as.dogQueue) {
        out << *critter << '\n';
    }
    return out;
}

I also modified the base class to include _name as mentioned above and wrote this friend function of Animal:

friend std::ostream& operator<<(std::ostream& out, const Animal& a) {
    return out << a.getClassName() << ' ' << a._name << ' ' << a._order;
}

Implement the problem specification completely

The description of the problem mentions that one might be able to adopt either a cat or a dog or the first available, but only the latter function has been implemented. Here's how I wrote all three:

std::unique_ptr<Animal> adopt() {
    std::unique_ptr<Animal> adoptee{nullptr};
    if (catQueue.empty() && dogQueue.empty())
        return adoptee;

    if (catQueue.empty()) {
        std::swap(adoptee, dogQueue.front());
        dogQueue.pop_front();
    } else if (dogQueue.empty() || (catQueue.front() < dogQueue.front())) {
        std::swap(adoptee, catQueue.front());
        catQueue.pop_front();
    } else {
        std::swap(adoptee, dogQueue.front());
        dogQueue.pop_front();
    }
    return adoptee;
}

std::unique_ptr<Animal> adoptCat() {
    std::unique_ptr<Animal> adoptee{nullptr};
    if (!catQueue.empty()) {
        std::swap(adoptee, catQueue.front());
        catQueue.pop_front();
    }
    return adoptee;
}

std::unique_ptr<Animal> adoptDog() {
    std::unique_ptr<Animal> adoptee{nullptr};
    if (!dogQueue.empty()) {
        std::swap(adoptee, dogQueue.front());
        dogQueue.pop_front();
    }
    return adoptee;
}

Results

Here is the modified main to exercise the revised code:

int main()
{   
    AnimalShelter shelter;
    shelter.dropoff(std::unique_ptr<Animal>(new Dog{"Max"}));
    shelter.dropoff(std::unique_ptr<Animal>(new Cat{"Trace"}));
    shelter.dropoff(std::unique_ptr<Animal>(new Cat{"Han"}));
    shelter.dropoff(std::unique_ptr<Animal>(new Dog{"Shaun"}));
    shelter.dropoff(std::unique_ptr<Animal>(new Dog{"Tiger"}));
    shelter.dropoff(std::unique_ptr<Animal>(new Cat{"Meow"}));
    try {
        shelter.dropoff(std::unique_ptr<Animal>(new Rhino{"Buster"}));
    } catch (std::runtime_error &err) {
        std::cout << err.what() << '\n';
    }
    std::cout << shelter << '\n';

    for (int i = 0; i < 2; ++i) {   
        auto pet = shelter.adoptDog();
        if (pet) {
            std::cout << "You have adopted " << *pet << "\n";
        } else {
            std::cout << "sorry, there are no more pets\n";
        }
        std::cout << shelter << '\n';
    }

    for (int i = 0; i < 6; ++i) {  // adopt any
        auto pet = shelter.adopt();
        if (pet) {
            std::cout << "You have adopted " << *pet << "\n";
        } else {
            std::cout << "sorry, there are no more pets\n";
        }
        std::cout << shelter << '\n';
    }

    std::cout << "Final: \n" << shelter << '\n';
}

Answer 2

In addition to the suggestions given by 1201ProgramAlarm's answer, I have the following suggestions.

First, your (over)use of RTTI seems overkill here. Even dynamic polymorphism is not necessary. A simple class is enough:

enum class Species { cat, dog };

struct Animal {
    Species species;
    std::string name;
};

(You are missing #include <string>)

Second, you maintain two queues. Since this is an animal shelter, why not merge them? You can use vector to accommodate for adopters that prefer a specified species.

std::vector<Animal> animals;

Third, dequeue returns void. This is abandonment, not adoption. It should return the Animal. (An animal protectionist can even go further and mark the function [[nodiscard]].)

Also, let print accept an ostream&, so you can print to any stream.

Here's the revised version:

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

enum class Species { cat, dog };

std::string to_string(Species species)
{
    switch (species) {
    case Species::cat:
        return "cat";
    case Species::dog:
        return "dog";
    default:
        throw std::invalid_argument{"Unrecognized species"};
    }
}

struct Animal {
    Species species;
    std::string name;
};

class Shelter {
public:
    void enqueue(Animal animal)
    {
        animals.push_back(animal);
    }
    // adopt a specific species
    Animal dequeue(Species species)
    {
        auto it = std::find_if(animals.begin(), animals.end(),
                               [=](const Animal& animal) {
                                   return animal.species == species;
                               });
        if (it == animals.end())
            throw std::logic_error{"No animal to adopt"};
        Animal animal = std::move(*it);
        animals.erase(it);
        return animal;
    }
    // adopt any animal
    Animal dequeue()
    {
        if (animals.empty())
            throw std::logic_error{"No animal to adopt"};
        Animal animal = std::move(animals.front());
        animals.erase(animals.begin());
        return animal;
    }
    void print(std::ostream& os)
    {
        for (const auto& animal : animals) {
            os << animal.name << " (" << to_string(animal.species) << ")\n";
        }
    }
private:
    std::vector<Animal> animals;
};

int main()
{
    Shelter shelter;
    shelter.enqueue({Species::dog, "Max"});
    shelter.enqueue({Species::cat, "Trace"});
    shelter.enqueue({Species::cat, "Han"});
    shelter.enqueue({Species::dog, "Shaun"});
    shelter.enqueue({Species::dog, "Tiger"});
    shelter.enqueue({Species::cat, "Meow"});

    shelter.print(std::cout);
    std::cout << "\n";

    auto new_pet = shelter.dequeue();
    shelter.print(std::cout);
    std::cout << "\n";

    auto new_dog = shelter.dequeue(Species::dog);
    shelter.print(std::cout);
}

Output:

Max (dog)
Trace (cat)
Han (cat)
Shaun (dog)
Tiger (dog)
Meow (cat)

Trace (cat)
Han (cat)
Shaun (dog)
Tiger (dog)
Meow (cat)

Trace (cat)
Han (cat)
Tiger (dog)
Meow (cat)

Answer 3

First off, you should avoid using namespace ::std.

In Animal, getOrder and getType should be const (int getOrder() const). Since they're defined within the class definition, you don't need to include the inline keyword. Similarly, getters in the derived classes should be const.

It is rarely ever necessary to use the this keyword, and the places where you use this-> to access a member variable can do without it.

Compare should also be const (and take its parameter as a const Animal *, and can be simplified to return _order > animal->_order;.

You never delete any of the memory you allocate with new.

You should declare a virtual destructor for Animal since it is used as a base class. It isn't a direct problem here, since you never delete any of the memory you allocate, but if you'd delete Animals you dequeue, you'd still leak memory as the strings in the derived classes would not be freed.

In AnimalQueue you can have separate enqueue methods that take Cat * and Dog * parameters. This would avoid needing to have all that code to check the type, and would work better if you have further derived classes (like "Tiger" derived from "Cat" or "Wolf" derived from "Dog"). The generic enqueue(Animal *) can call the proper overloaded enqueue after checking the result of the dynamic cast. Something like

if (auto cat = dynamic_cast<Cat*>(animal))
    enqueue(cat);
else if (auto dog = dynamic_cast<Dog*>(animal))
    enqueue(dog);
else /* error handling */;

assuming you're using a compiler that supports the variable declarations in if conditional expressions.

dequeue has several bugs. It will attempt to remove elements from empty containers, and could also try to access elements from empty containers.

printQueue should be const, and should use iterators to print the contents of the queues. Since displaying the two queues has a bunch of duplicated code, make a function that will display one queue and call that for each queue you want to display.

getDogQueue and getCatQueue should be const and return const references.

Answer 4

In addition to other answers: you're using inline a lot. Do not.

Modern compilers (almost all starting from year 2000) don't use it for optimization anyways: they are already clever enough to do so without hints when possible. These days inline have another meaning in some contexts (when function is defined in many translation units), but in your situation it's a simple no-op.

Answer 5

I'll assume in 2019 that C++17 is available.

All other answers seem to be using two queues, one for each type of animal, but I think it kinda defeats the purpose that the FIFO behaviour has to be on the whole set of animals. With two queues, the FIFO has to be implemented by an _order stored with the animal, which mixes the data with the algorithm. Once the animal is adopted, out of the shelter, the _orderhas no meaning, but is still part of the structure.

Using a queue, I would use a single queue of animals, which implements FIFO. (But the deque allows you to remove from the middle of it)

std::deque<Animal> _animals;

Now, the animal being either a cat or a dog, I would just say so

using Animal = std::variant<Dog,Cat>;

And implement each species as its own class.

class Cat { /* implementation*/ };
class Dog { /* implementation*/ };

Then, borrowing terminology from Edward's answer, I would simply implement:

void dropoff(Animal a) { _animals.emplace_back(std::move(a)) };
std::optional<Animal> adoptAny() {
   if(_animals.empty()) return std::nullopt;

   auto adoptee = std::move(_animals.front());
   _animals.pop_front();
   return adoptee; // NRVO
}


template<typename T>
auto adoptFirstOfType() -> std::optional<T> {
  // Find first animal of given type
  const auto adoptee_it = std::find_if(
      begin(_animals),
      end(_animals), 
      [](const Animal& a) { return a.holds_alternative<T>(); };

  // If not found, return empty optional.
  if(adoptee_it == end(_animals)) {
      return std::nullopt;
  }

   // If found, steal the right alternative, remove from queue and return
   auto adoptee = std::get<T>(std::move(*adoptee_it));
   _animals.erase(adoptee_it);
   return adoptee; //NRVO
}

auto adoptDog() { // type deduced consistently from returned expression
   return adoptFirstOfType<Dog>();
}
auto adoptCat() { // type deduced consistently from returned expression
   return adoptFirstOfType<Cat>();
}

Edward's main function should work fine as is, because optional has the same "container access" interface as unique_ptr.

This allows to simply drop the _order and operator< hacks from his solution. (because yes, implementing operator< is a hack - it makes no sense that a Dog be more than a Cat because it arrived first in the shelter)

Answer 6

Design

Is a single queue acceptable, or does each animal need its own?

Multiple queues need more bookkeeping, as well as slight overhead when enqueueing an animal, or dequeueing the senior resident regardless of species.
While one can put the entrance-order in the animal-class, it certainly does not belong.

A single queue potentially require looking at every single animal to find one of a specific species. On the flip-side, adding additional species comes naturally.

Implementation

1. ::std is not designed for wholesale inclusion. It contains myriad symbols, there is no comprehensive list, and it is always evolving. Your code might not "work" today, but tomorrow it might fail to compile, or worse silently change ist meaning.
   Read "Why is “using namespace std” considered bad practice?" for more detail.

2. You are flat-out leaking all your animals.

   As the program terminates directly afterwards, and deleteing them has no observable effect you depend on, that could be a good idea.
   That is, if it was intentional, well-explained, and not demo-code, but neither is the case.

   Consider an appropriate use of smart-pointers, specifically std::unique_ptr, as manual resource-management is error-prone.

3. Generally, polymorphic types should have a virtual dtor, so they can be deleted polymorphically.

4. The string type is set to the classname when enqueueing? Rip that out at the roots, you can use the source directly.

5. Unless you need a friendly name for presistence or display, consider fully relying on builtin RTTI instead of adding your own home-grown variant. Use typeid if you want exact type-matching, or dynamic_cast if subtypes are fair game.

6. All member-functions defined inline are automatically inline.

7. Avoid needlessly copying strings, that's inefficient. Prefer std::string_view where applicable.

8. Mark functions noexcept if you can.

9. Mark overrides override for documentation and to allow the compiler to catch mistakes.

10. printQueue() clears it? That violates all expectations. And anyway, it should be std::ostream& operator<<(std::ostream&, AnimalQueue const&).

    You probably should move from std::queue to directly using std::deque when fixing that, even though you can safely access the underlying container.

Using a single shared queue (also live on coliru):

#include <algorithm>
#include <iostream>
#include <memory>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

class Animal {
public:
    virtual std::string_view friendlyName() noexcept = 0;
    virtual ~Animal() = default;
};

class Cat : public Animal {
    std::string _name;
public:
    Cat(std::string name) : _name(std::move(name)) {}

    std::string_view friendlyName() noexcept override { return "Cat"; }
};

class Dog : public Animal {
    std::string _name;
public:
    Dog(std::string name) : _name(std::move(name)) {}

    std::string_view friendlyName() noexcept override { return "Dog"; }
};

class Shelter {
    std::vector<std::unique_ptr<Animal>> _queue;
public:
    template <class T = Animal>
    std::unique_ptr<T> get() noexcept {
        auto pos = std::find_if(_queue.begin(), _queue.end(), [](auto&& x){ return dynamic_cast<T*>(x.get()); });
        if (pos == _queue.end())
            return {};
        std::unique_ptr<T> r(dynamic_cast<T*>(pos->release()));
        _queue.erase(pos);
        return r;
    }

    void put(std::unique_ptr<Animal>&& a) {
        if (a)
            _queue.push_back(std::move(a));
    }

    friend std::ostream& operator<<(std::ostream& os, Shelter const& s) {
        for (auto&& x : s._queue)
            os << x->friendlyName() << ' ';
        os << '\n';
        return os;
    }
};

int main()
{
    auto d1 = std::make_unique<Dog>("Max");
    auto d2 = std::make_unique<Dog>("Shaun");
    auto d3 = std::make_unique<Dog>("Tiger");
    auto c1 = std::make_unique<Cat>("Trace");
    auto c2 = std::make_unique<Cat>("Han");
    auto c3 = std::make_unique<Cat>("Meow");

    Shelter shelter;
    shelter.put(std::move(d1));
    shelter.put(std::move(c1));
    shelter.put(std::move(c2));
    shelter.put(std::move(d2));
    shelter.put(std::move(d3));
    shelter.put(std::move(c3));

    std::cout << shelter;
    shelter.get();
    std::cout << shelter;
}