How can I implement a PriorityStack that accepts objects with the Comparable interface?

Question

I took a look at the code in this thread: https://codereview.stackexchange.com/questions/98105/priority-stack-in-java

This implements a PriorityStack using the object and the priority. I need an implementation where you only add the object to the PriorityStack, and using the Comparable interface you can define which attribute should be prioritized.

For example:

I have a list of dogs:

• name = "Skip", age = 4
• name = "Gregory", age = 3
• name = "Ziggy", age = 4

In the Dog object I would implement the Comparable interface with:

public int compareTo(Dog other) {
    if(other == null) {
        return -1;
    }
    return this.age - other.age;
}

How can I use this to prioritize my PriorityStack?

The result of this should be the youngest dog first, and then the other 2 dogs based on First In Last Out

Answer 1

(Edited answer after the clarifications given in the comments)

In the PriorityStack in the link, it takes two values and stored them in a TreeMap. In your case, once you make the Dog class comparable (and the Dog objects contain a .age attribute) then you can store these Dog objects in a TreeSet (which is a sorted collection, sorted according to your compareTo() method in Dog).

You would instantiate the TreeSet as TreeSet<Dog> stack = new TreeSet<>();

Answer 2

Consider that a stack can be viewed as a priority queue that prioritizes based on the time the item was enqueued. It wouldn't be as efficient as what we typically call a stack, but it would be LIFO.

That PriorityStack can more easily be implemented with a PriorityQueue, and probably a whole lot more efficiently. The only catch is that you'll either need to add a time field to your Dog class, or wrap the Dog object in another class that has a time field. I'd favor the latter: call it PQDog. And of course you'll need a custom comparer.

The time field doesn't have to be the actual time something was enqueued. It could be an integer if you make sure to increment it for each item enqueued. Provided you're not going to enqueue more than 2 billion items over the lifetime of the queue. Come to think of it, if you start the sequence at Integer.MinValue (or whatever it's called in Java), you could extend that range to 4 billion.

The idea is that you'd define the class:

class PQDog {
  int sequenceNumber;
  Dog dog;
}

I'm not really a Java programmer, so don't expect the code below to compile without trouble. But I think it's enough to point you in the right direction.

When you want to put a Dog in the queue, you wrap it in a PQDog object and add the new sequence number. Imagine you have a static variable called QueueSequence that you increment every time just before enqueueing.

PriorityQueue dogQueue = new PriorityQueue<PQDog>();
static int QueueSequence = 0;

// and to add something to the queue
PQDog newDog = new PQDog(QueueSequence++, Dog);
dogQueue.add(newDog);

And of course when you pop from the queue you'll have to unwrap the Dog.

It seems like your ordering requirement is "By ascending age and descending time". So your comparer would be something like:

public int compareTo(PQDog other) {
    if(other == null) {
        return -1;
    }
    // sort younger dogs first
    if (this.Dog.age < other.Dog.age) return -1;
    if (this.Dog.age > other.Dog.age) return 1;

    // ages are the same, so compare enqueue time
    if (this.sequenceNumber > other.sequenceNumber) return -1;
    if (this.sequenceNumber < other.sequenceNumber) return 1;

    // Probably should raise an exception here
    // If you have two entries with the same sequence number,
    // something has gone horribly wrong.
    return 0;
}

Or, if the Dog class already has a CompareTo that compares by age, you'd change the above code to:

if (this.Dog.CompareTo(other.Dog) == 0) return;

// and then compare the sequenceNumbers if the
// dogs' ages aren't equal.

Seems silly to me to introduce an incomplete and un-vetted custom PriorityStack data structure when you can solve your problem using the standard Java PriorityQueue, a custom comparer, and a few lines of interface code.

As an aside, you shouldn't in general use return a - b in a Comparable. Imagine what happens when a is equal to the minimum integer (or sufficiently negative, anyway) and b is a large enough positive number. Integer overflow (actually underflow, but same thing) rears its ugly head. The result will be a positive number, erroneously indicating that a is greater than b.

Yes, I realize that in this particular case you won't run into that issue. At least, I don't think you have any dogs that are negative 2 billion years old. But much of what we do as programmers relies on patterns and common practice. One should get in the habit of writing bulletproof code when practical. No telling what somebody will do with your code after you write it. Perhaps some beginner is looking for a Comparable implementation, runs across your code, copies it to his program with that return a - b in there. All the unit tests and integration tests pass, the code goes into production, and four months later something breaks.

Not that I'm talking from experience or anything . . .