Sorting a stack

[Touchstone57]

I am just wandering, how can I sort a stack in ascending order? I have tried using the Collection.sort method on my stack, but I get the following error


Bound mismatch: The generic method sort(List<T>) of type Collections is not applicable for the arguments (List<LibraryItem>). The inferred type LibraryItem is not a valid substitute for the bounded parameter <T extends Comparable<? super T>>

With the following line of code that I use

Collections.sort(pl.PublicLibraryStack);

I am wandering, why is it unable to sort my stack? It contains a collection of different objects, which are printed out fine, and when I try the Collection.reverse method on my stack that seems to work, just not the sort method.

Any help would be greatly appreciated, thanks.

[Fou-Lu]

I didn't think you could sort a stack, learn something new every day.
The error indicates that you're LibraryItem object doesn't have a suitable comparator. Implement Comparable or Comparable<LibraryItem> in the LibraryItem class to allow it to sort.

[abduraooft]

I didn't think you could sort a stack, Isn't it against the concept of stack(LIFO)?

[shyam]

yea...a sorted stack...i wonder where u'd use it

[Fou-Lu]

These were exactly what I was thinking, and also why I figured you just couldn't sort a stack.
I can't see where it would be useful either, generally speaking I'd say if you needed to sort, reverse, index, or search a stack or queue, you've kinda defeated the point. This is why we have arraylists, hashmaps, linked lists and trees.
But, I'm sure there will be a time when I'm like 'dang, I need to sort that stack' too.

[Touchstone57]

Okay I understand this now, but why is it allowing me to invoke the reverse method on my stack without any errors?

Collections.reverse(pl.PublicLibraryStack);

And, I instead tried to use the sort method on a LinkedList I created, but to no effect.

Collections.sort(ll.LongTermLibraryList);

Bound mismatch: The generic method sort(List<T>) of type Collections is not applicable for the arguments (List<LibraryItem>). The inferred type LibraryItem is not a valid substitute for the bounded parameter <T extends Comparable<? super T>>

[Old Pedant]

Reversing a stack does *NOT* imply any need to COMPARE the items in the stack with each other. It's essentially the same as reversing the order of items in an array: You don't care what the *values* are, you only care about the order.

But any kind of SORT *must* involve comparing values, and so the items that are to be sorted *must* implement Comparable, exactly as the error message says and exactly as the first response said.

[Fou-Lu]

I'll check when I have a chance, but I'm guessing that both sort and reverse are implemented in the Collection interface; I thought they were a part of the List interface (if it is indeed this way, I have no idea why they put it together this way). Nonetheless, reversing is a piece of cake, it doesn't need a comparator to reverse a collection since you can perform a reversal without even caring what the data inside the node is. But to sort it, it doesn't understand how to sort complex types, which is why you need to implement the Comparable interface on the LibraryItem class. Same would go for the Linked List as well. Java looks at a LibraryItem and another LibraryItem and pretty much tries to equate them together. Without a compareTo method, it has no idea which is considered greater of the two.

What we are refering to is the logic of its usage. A stack should always follow LIFO methods, so sorting or reversing it isn't logical. Same goes for a Queue which is the FIFO method. LinkedLists and trees make more sense if you're looking to sort, search or reverse.

So, make sure you're LibraryItem is like so:

public class LibraryItem implements Comparable<LibraryItem>

I don't know if you're extending or implementing other stuff, but I'm sure you know what to do. CompareTo will return an int, and require a LibraryItem as a parameter.

[Touchstone57]

I get some of the gist of what's going on, but I'm still having difficulty getting it working.

So far I've done

public abstract class LibraryItem implements Comparable<LibraryItem>

But you see, the LibraryItem is a super class, of which many other classes inherit, as I have classes of libray items, such as book, video, etc, each used to create objects of their type. So, I am prompted to implement abstract compareTo methods (Eclipse), in all of the classes that inherit from LibraryItem. What I'm asking here is, do I write the method code in the LibraryItem class, or in the sub classes? At the moment I'm only working with the book items so I don't care about the others.

I hope that makes sense, thanks.

Edit:
To note, I am trying to order the list of books by the year they where published. Here is a sample of code from my LibraryItem class. I'm not sure I've structured the compareTo method right at all.

//Variable I'm using,
protected int publicationYear;

//Super constructor
public LibraryItem(String staffID, String nTitle, int year){
title = nTitle;
libraryID = nTitle+year+staffID + System.currentTimeMillis();
publicationYear = year;

//Get year published
public int getYearPublished(){
return publicationYear;

//Comparing the year published
@Override
public int compareTo(LibraryItem obj) {
LibraryItem tmp = (LibraryItem)obj;
if(getYearPublished() < tmp.getYearPublished())
{
/* instance lt received */
return -1;
}
else if(getYearPublished() > tmp.getYearPublished())
{
/* instance gt received */
return 1;
}
/* instance == received */
return 0;
}
}

[Fou-Lu]

You're compareto is correct.
You won't need to perform a cast on the incoming object though, it requires a typeof LibraryItem.

public int compareTo(LibraryItem obj)
{
return this.getYearPublished() - obj.getYearPublished();
}


You don't need to return 0, -1 and +1, you just need to return 0, a negative, and a positive number. So when you're using a number, I'd just return the difference between them (ie: this is 1998, obj is 2002, it will return -4 indicating that 'this' is less than 'that').
You can implement the compareTo in the LibraryItem abstract so long as it declares the methods in use or forces for an abstract implementation of a method. Otherwise, override it where necessary in subclasses. I'm trying to recall if you can toss it a typeof the inherited class in the signature (ie: public int compareTo(Book obj);) without providing a new implementation of the Comparable interface. Offhand I can't recall if this is the case (a book is technically a libraryItem). But if you override and you can't resignature easily, simply cast it to the correct class in a try/catch. I think you can simply signature for a <T extends LibraryItem> type, but its been awhile since I've used the generics to a heavy extent.

Hope that helps!

[Touchstone57]

Okay, I implemented the compareTo method in my book classes, and finally got it to work! Thanks a lot for your help guys.

I am getting the desired output, even though I'm performing the sort operation on a stack. Is this meant to be possible?

[Fou-Lu]

It sounds like Java lets you do it, if they've implemented the sort on the Collection interface. Its not wrong to perform a sort so much as its not really logical. Instead of a stack, you should consider using an arrayList, vector or linkedList. Since you're allowing sorting, I'd go with probably an arrayList or Vector, they have a little less overhead than the other data collections.