CODEWITHSUNDEEP
javaequalspriority-queuecompareto
TimeToCodeTheRoad
TimeToCodeTheRoad

Reputation: 7312

Unexpected behavior with PriorityQueue remove: Why isn't compareTo used?

I am trying to use the priority queue, but the remove() is not working: My code:

PriorityQueue<OwnClass> pq=new PriorityQueue<OwnClass>();
OwnClass a=new OwnClass(1);
OwnClass b=new OwnClass(2);
OwnClass c=new OwnClass(3);
pq.add(a);
pq.add(b);
pq.add(c);
System.out.println("head:"+pq.peek());
pq.remove(new OwnClass(1));
System.out.println(pq.peek());

And the class implementation:

class OwnClass implements Comparable{

    int x;

    public OwnClass(int x){
        this.x=x;
    }

    public int compareTo(Object arg0) {

        OwnClass a=(OwnClass) arg0;
        if(a.x>this.x)
            return -1;
        if(a.x<x)
            return 1;
        return 0;
    }

    public String toString(){
        return ""+x;        
    }
}

I think the output final output should be 2, since I am removing the added '1'. The compareTo() should be used by priority queue remove() but his does not seem to be the case. What I am doing wrong? I know pq.remove(a) will work, but then my code should also work

Upvotes: 1

Views: 1548

Answers (3)

sarumont
sarumont

Reputation: 1762

remove() will not use compareTo(), rather it will use equals() to find the object to remove. You need to override equals() on your class as well.

Edit: Javadoc for PriorityQueue (Thanks, @templatetypedef)

Upvotes: 8

NiranjanBhat
NiranjanBhat

Reputation: 1832

Please note that PriorityQueue has an other constructor that takes a Comparator. So it could be to keep the remove behavior consistent even if a Comparator is used or the objects in the priorityQueue implement the Comparable Interface, equals does not depend on any comparison except the base equals property of the Object.

Upvotes: 2

templatetypedef
templatetypedef

Reputation: 372814

The PriorityQueue class's remove method has the following description:

Removes a single instance of the specified element from this queue, if it is present. More formally, removes an element e such that o.equals(e), if this queue contains one or more such elements. Returns true if and only if this queue contained the specified element (or equivalently, if this queue changed as a result of the call).

Thus compareTo is not used when determining whether to remove something. I believe that this is because PriorityQueue implements Collection, and the behavior of remove must therefore be consistent with the behavior specified in Collection, which is

Removes a single instance of the specified element from this collection, if it is present (optional operation). More formally, removes an element e such that (o==null ? e==null : o.equals(e)), if this collection contains one or more such elements.

In other words, I believe this design decision is motivated by trying to fit PriorityQueue into the Collection framework, even though it is a bit odd.

Hope this helps!

Upvotes: 2

Related Questions