JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
TreeSet has screwed me up.. | Reply
As clear from heading , this time i am having problems with TreeSet which i am using for Dijkstra as suggested in the tutorial article .

I went through a similar post frm sb on topcoder but got no help there..

I think i am doing somewhere wrong in the comparator which i have used in the node...

The node class i have created is:

class node implements Comparable
{
public int x,y,life;

public node(int x1,int y1,int l)
{
x=x1;
y=y1;
life=l;

}
public int compareTo(Object o)
{
node right = (node)o;
if (life < right.life) return -1;
if (life >= right.life) return 1;

return 0;
}

}

And the line which is creating problem is:

TreeSet pq=new TreeSet();
pq.remove(pq.first());

Any help would be appreciated ...
Re: TreeSet has screwed me up.. (response to post by sumantbhardvaj) | Reply
Well, first of all, you might want to use PriorityQueue for that?

And, you didn't put anything in that set, what are you taking out?
Re: TreeSet has screwed me up.. (response to post by sumantbhardvaj) | Reply
well , i have not put the whole code there..just parts..

I initialize the TreeSet with the Start node.

and then a while loop starts which pops off the item with max priority.
Finally the code goes like this..


TreeSet<node> pq=new TreeSet<node>();
pq.add(new node(x,y,z));
visited[x][y]=true;

while(pq.size() !=0)
{
node n=(node)pq.first();
pq.remove(pq.first());
..............
.............
}
Re: TreeSet has screwed me up.. (response to post by sumantbhardvaj) | Reply
As darko_aleksic mentioned, you may want to use PriorityQueue instead of TreeSet.
PriorityQueue<node> pq=new PriorityQueue<node>();
pq.add(new node(x,y,z));
node n=pq.poll();
Re: TreeSet has screwed me up.. (response to post by sumantbhardvaj) | Reply
yaa ..

using a priority queue worked instantly ...
thnx a lot..

TreeSet are not meant for such usage i think..
Re: TreeSet has screwed me up.. (response to post by sumantbhardvaj) | Reply
That would be true :-)
Re: TreeSet has screwed me up.. (response to post by sumantbhardvaj) | Reply
I have to disagree about TreeSet vs PriorityQueue. First of all, I don't know the exact problem but your comparator seems wrong, the line with "return 0" is unreachable, because you have ">=" instead of ">" in the line above.

I just realized after several tests that TreeSet have several advantages over PriorityQueue, the only thing you need to care about is a proper comparator. TreeSet's remove() method has better performance than PriorityQueue's remove(). Also, with TreeSet you have less elements since PriorityQueue allows duplicates you generally don't need, at least for short paths.
Re: TreeSet has screwed me up.. (response to post by sumantbhardvaj) | Reply
...forgot to mention, this way is even faster for getting and removing:

Iterator<Node> it = treeSet.iterator();
Node node = it.next();
it.remove();
RSS