I have made a priority queue which inserts objects and compares them with cost parameter, when two costs are equal it should keep them in enqueued order, but I found after debugging one time it is in enqueued order and other time it is not in the order but I am not getting what is wrong with my code I couldn't find any other post helping.
import java.util.*;
import java.lang.*;
import java.io.*;
class Node implements Comparable<Node>
{
int x, y, dir;
Node(int x, int y, int dir)
{
this.x = x;
this.y = y;
this.dir = dir;
}
public int compareTo(Node o)
{
if (Ideone.cost[o.x][o.y] == Ideone.cost[x][y]) {
return 1;
} else {
int d = Ideone.cost[x][y] - Ideone.cost[o.x][o.y];
if (d > 0) {
return 1;
} else {
return -1;
}
}
}
}
class Ideone
{
public static int[][] cost;
static PriorityQueue<Node> p;
public static void main(String[] args)
throws Exception
{
p = new PriorityQueue<Node>();
cost = new int[13][11];
for (int[] row : cost)
Arrays.fill(row, -1);
cost[0][8] = 366564;
cost[2][9] = 368282;
cost[1][3] = 368282;
cost[4][9] = 368282;
cost[0][9] = 376564;
cost[1][9] = 372423;
cost[5][9] = 372423;
cost[0][3] = 436564;
cost[7][0] = 378282;
cost[2][10] = 378282;
cost[4][10] = 378282;
cost[0][4] = 382423;
p.add(new Node(0, 8, 8));
p.add(new Node(2, 9, 8));
p.add(new Node(1, 3, 7));
p.add(new Node(4, 9, 2));
p.add(new Node(0, 9, 8));
p.add(new Node(1, 9, 8));
p.add(new Node(5, 9, 2));
p.add(new Node(0, 3, 6));
p.add(new Node(7, 0, 3));
p.add(new Node(2, 10, 8));
p.add(new Node(4, 10, 2));
p.add(new Node(0, 4, 7));
while (p.size() != 0) {
Node n1 = p.poll();
System.out.println(n1.x + " " + n1.y + " " + cost[n1.x][n1.y]);
}
}
}
Output is
0 8 366564
1 3 368282
2 9 368282
4 9 368282
5 9 372423
1 9 372423
0 9 376564
4 10 378282
2 10 378282
7 0 378282
0 4 382423
0 3 436564
but I am expecting:
0 8 366564
2 9 368282
1 3 368282
4 9 368282
1 9 372423
5 9 372423
0 9 376564
7 0 378282
2 10 378282
4 10 378282
0 4 382423
0 3 436564
You need — as in need — to follow the suggestion from Peter Lawrey and store the insertion order in each Node you insert into the priority queue. It’s easier to explain in code. Your node class could become:
class Node implements Comparable<Node>
{
int x, y, dir;
/** the order in which the node was inserted into the priority queue (if it was) */
int insertionOrder;
Node(int x, int y, int dir, int insertionOrder)
{
this.x = x;
this.y = y;
this.dir = dir;
this.insertionOrder = insertionOrder;
}
public int compareTo(Node o)
{
int d = Ideone.cost[x][y] - Ideone.cost[o.x][o.y];
if (d == 0) {
// keep insertion order
return insertionOrder - o.insertionOrder;
} else {
return d;
}
}
}
And your main method:
public static void main(String[] args)
{
p = new PriorityQueue<Node>();
int numInserted = 0;
cost = new int[13][11];
for (int[] row : cost)
Arrays.fill(row, -1);
cost[0][8] = 366564;
cost[2][9] = 368282;
cost[1][3] = 368282;
cost[4][9] = 368282;
cost[0][9] = 376564;
cost[1][9] = 372423;
cost[5][9] = 372423;
cost[0][3] = 436564;
cost[7][0] = 378282;
cost[2][10] = 378282;
cost[4][10] = 378282;
cost[0][4] = 382423;
p.add(new Node(0, 8, 8, numInserted));
numInserted++;
p.add(new Node(2, 9, 8, numInserted));
numInserted++;
p.add(new Node(1, 3, 7, numInserted));
numInserted++;
p.add(new Node(4, 9, 2, numInserted));
numInserted++;
p.add(new Node(0, 9, 8, numInserted));
numInserted++;
p.add(new Node(1, 9, 8, numInserted));
numInserted++;
p.add(new Node(5, 9, 2, numInserted));
numInserted++;
p.add(new Node(0, 3, 6, numInserted));
numInserted++;
p.add(new Node(7, 0, 3, numInserted));
numInserted++;
p.add(new Node(2, 10, 8, numInserted));
numInserted++;
p.add(new Node(4, 10, 2, numInserted));
numInserted++;
p.add(new Node(0, 4, 7, numInserted));
numInserted++;
while (p.size() != 0) {
Node n1 = p.poll();
System.out.println(n1.x + " " + n1.y + " " + cost[n1.x][n1.y]);
}
}
The above main method prints:
0 8 366564
2 9 368282
1 3 368282
4 9 368282
1 9 372423
5 9 372423
0 9 376564
7 0 378282
2 10 378282
4 10 378282
0 4 382423
0 3 436564
I believe this was what you expected.