3 Replies - 831 Views - Last Post: 02 October 2011 - 09:22 PM Rate Topic: -----

#1 TroubledMonkey  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 2
  • Joined: 02-October 11

Priority Queue ordering issue

Posted 02 October 2011 - 09:05 PM

I'm using a Priority Queue for a project, but the results of "poll" are not what I'm expecting them to be. I have created a basic Coordinate class that stores and x and y value as well as f, g, and h values for implementing the A* algorithm. I wrote this as my compareTo method in my Coord class:
public int compareTo(Coord c) {
		return f - c.getF();
	}



which should compare two coordinates by their f-values. However, in my A* algorithm, I have the lines:
PriorityQueue<Coord> openSet = new PriorityQueue<Coord>();
.
.
.
while(!openSet.isEmpty()){
   Coord x = openSet.poll();



but, for some reason, x is not getting set to the coordinate with the lowest f value. Sometimes it is, and sometimes it isn't. I've stepped through with the Eclipse debugger, and after a few iterations, there are elements in openSet with, for example, f = 20 and others with f = 23 and it will set x to one of the coordinate with f = 23. I'm really at a loss here. Is there some facet of Priority Queues in Java that I'm missing? Or could it be an issue somewhere else in my code?

Is This A Good Question/Topic? 0
  • +

Replies To: Priority Queue ordering issue

#2 TroubledMonkey  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 2
  • Joined: 02-October 11

Re: Priority Queue ordering issue

Posted 02 October 2011 - 09:19 PM

Shoot, sorry - I've actually found the problem and can't find a way to delete this post. (I really did spend a good hour in the debugger trying to fix this earlier today...glad it's finally fixed!)

If anyone's curious, my problem was that I was adding my new Coordinate y to the priority queue and then setting the f value once it was already in there, so it was getting sorted in the priority queue before it's f value had any actual meaning (defaulted to 0). Seems so obvious now... :-\
Was This Post Helpful? 1
  • +
  • -

#3 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10340
  • View blog
  • Posts: 38,260
  • Joined: 27-December 08

Re: Priority Queue ordering issue

Posted 02 October 2011 - 09:20 PM

Glad you solved your problem. Thanks for sharing your solution! :)
Was This Post Helpful? 0
  • +
  • -

#4 smohd  Icon User is online

  • Critical Section
  • member icon


Reputation: 1817
  • View blog
  • Posts: 4,625
  • Joined: 14-March 10

Re: Priority Queue ordering issue

Posted 02 October 2011 - 09:22 PM

Can we see your code? because poll() returns head or null, I dont see if that is what you were expecting
Glad you fix it

This post has been edited by smohd: 02 October 2011 - 09:23 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1