Java implement PriorityQueue - when no Comparator provided

1
votes

I am trying to implement my own version of a generic PriorityQueue in Java (using binary heaps). I have chosen to use an Object array for my heap.

Object[] qArray = new Object[initial_Size];

If a user provides a comparator - the implementation is pretty straightforward as I can use the comparator's compare method when I am doing my element comparisons.

Comparator<T> comparator; //Set to a user-provided comparator in my constructor.

if(comparator.compare((T)qArray[i], (T)qArray[j])
    //do something

However, the problem comes when user does not provide a default comparator. One way I could potentially handle this is to make my PriorityQueue class implement Comparator and have the comparator do the following compare -

@Override
public int compare(T o1, T o2)
{
    if(this.comparator == null) //no comparator provided by user
    {
        return o1.toString().compareTo(o2.toString());
    }
    else
    {
        return this.comparator.compare(o1, o2);
    }
}

However, this comparator is a little lame. It obviously works brilliantly for PriorityQueues of type String, but in case of (say) Integers, not quite (It would think 5 is greater than 49). Another approach would be to force the user to provide a comparator - but I know that Java Util's implementation of PriorityQueue is much kinder.

So, I tried to reverse-engineer Java's PriorityQueue a little bit and initialized a Priority Queue of a custom class type without passing in a comparator. 

public class TestClass {

    public class SomeClass
    {
        int value;
        SomeClass(int value)
        {
            this.value = value;
        }
    }

    public static void main(String[] args)
    {
        TestClass tClass = new TestClass();
        TestClass.SomeClass sClass1 = tClass.new SomeClass(10);
        TestClass.SomeClass sClass2 = tClass.new SomeClass(20);

        PriorityQueue<TestClass.SomeClass> pQueue = new PriorityQueue<TestClass.SomeClass>();
        pQueue.add(sClass1);
    }
}

StackTrace

So this siftUpComparable method potentially holds some important clues about how the util package does its comparing, but when I tried to read the source code I was lost.

So any ideas for implementation here - wherein if a natural ordering comparator is defined on the provided object type (like Integer or String) it should be used by default.

2
javapriority-queuecomparator
Store some interface implementation (like Comparable) instead of Objects? - John3136

2 Answers

2
votes

The Exception reveals it all: Java tries to cast the given object to Comparable, if you do not provide a Comparator.

You cannot just compare objects of arbitrary types with a generic algorithm. That is exactly why you either have to provide a Comparator or make sure that your objects support the compareTo method and implement Comparable.

1
votes

As you don't pass Comparator, SomeClass should implement Comparable interface i.e

public class SomeClass implements Comparable<Integer>
{
    int value;
    SomeClass(int value)
    {
        this.value = value;
    }
    public int compareTo(Integer o) {
        ....... // Logic to compare
    }
}