PriorityQueue

[arthurr.ie]

I got a simple priority queue of <node> objects.

Priority Queue<node> queue =  new Priority Queue<node>(n,compare);

the node object has a few fields, one of them an int field called LB(lower bound)
I've build a compare class so the queue would use my compare to sort itself.

The problem is that when I'm trying to add the first object to the queue I get nullpointerexception.
I assume that it's because he doesn't have anything to compare to.

this is the compare function.
I've tried adding a condition so that if one of the nodes X or Y is null return 1 but it didn't help

import java.util.Comparator;


public class nodecompartor implements Comparator<node>  {

	public int compare(node x,node y)
	{
	
		if(x.getLB()>=y.getLB())
			return 1;
		if(x.getLB()<y.getLB())
			return -1;
		return 0;
		
	}
}

thanks
Arthur

[jon.kiparsky]

I've tried adding a condition so that if one of the nodes X or Y is null return 1 but it didn't help

If the null pointer were turning up in here:

#
if(x.getLB()>=y.getLB())
return 1;
if(x.getLB()<y.getLB())
return -1;

then something like

if (x==null||y==null) return 1;

would guard against that.
If that's not working, as you say, then it must be somewhere else.
Can you post the error message and the lines of code that it points you to?

(look at the stack trace, it'll point you to various spots in the code - the topmost line of your code is usually the first place to look)

You could kludge around it - use some boolean "queueIsEmpty" which is initially true. If it's true, use an insert method that doesn't compare, just inserts, and then set queueIsEmpty to false, and it should work. However, that's not a very attractive solution.

[Arthurr]

It didn't help.

the error i get is

Exception in thread "main" java.lang.NullPointerException
at brunch_and_bound.initiate(brunch_and_bound.java:71)
at brunch_and_bound.brunch_bound(brunch_and_bound.java:26)
at main.main(main.java:92)

and it is at the line where I add to the queue

LB=Math.max(0, Q-input[i][3])*(input[i][2]);
			node N=new node(n,Q,LB);
			if(LB<ub) 
				
				queue.add(N);

by the way, if there is a way to insert into the queue without it using compare that would solve my problem.But I couldn't find anything that does it

Thanks
Arthur

[jon.kiparsky]

If this

queue.add(N);

is line 71, the there are two things that can be null there.
To find out which it is, put in two test lines.

if (queue==null) S.o.println("queue is null");
if (N==null) S.o.println("N is null");

Put those in just before the offending line. I have a suspicion about what's going on, but let's see what you get from this.

[Arthurr]

queue is null..

[jon.kiparsky]

Thought so. Okay, then - do you think you can work out why queue is null there?
I can help you walk through it if you like, but you might find it worth doing yourself.

[Arthurr]

if you can walk me through I'd be glad
I'm not a seasoned programmer, and this is only a school assignment.

[jon.kiparsky]

Okay, my first assumption would be - having seen none of your code beyond a few snippets - that you've declared a PriorityQueue called "queue", but when you get to your line 71, that object has not been assigned to point to a correctly created PriorityQueue object on the heap.

There are a few ways that can happen. Let's take a look at your code - first thing I always look at is the main method.

[Arthurr]

this is the class where i create the queue
nothing else uses the qeueu.

import java.util.*;

public class brunch_and_bound  
{
	private static int Q=0;
	private static int LB=0;
	
	private PriorityQueue<node> queue;

	private node opt_node;
	
	public brunch_and_bound(int n) throws NullPointerException
	{
		Comparator<node> compare = new nodecompartor();
		PriorityQueue<node> queue =  new PriorityQueue<node>(n,compare);
	}
	
	public node brunch_bound(int ub,int [][] input,int n)
	{
		int q=0;
		int lb=0;
		int tj=0;
		int wj=0;
		int dj=0;
		node temp=new node(0,0,0);
		initiate(input,ub,n);
		opt_node=queue.peek();
		while((temp=queue.poll()) != null)
		{
			if(temp.getAdded().size()==n)
				continue;
			for(int i=0;i<temp.getjobsSize();i++)
			{
				tj=input[temp.getWaiting().get(i)-1][1];
				wj=input[temp.getWaiting().get(i)-1][2];
				dj=input[temp.getWaiting().get(i)-1][3];
				q=temp.getQ()-tj;
				lb=temp.getLB()+wj*(Math.max(0, q-dj));
				if(lb<ub)
				{
					node N=new node(q,lb,temp,i);
					queue.add(N);
					if(lb<opt_node.getLB())
						opt_node=N;
					
				}
			}
			
		}
		return opt_node;
		
	}


	private void initiate(int[][] input, int ub, int n) 
	{
	
		for(int i=0;i<n;i++)
		{
			 Q+=input[i][1];
		}
		for(int i=0;i<n;i++)
		{
			
			
			LB=Math.max(0, Q-input[i][3])*(input[i][2]);
			node N=new node(n,Q,LB);
			System.out.println(N.getLB());
			if(LB<ub) 
				   
				
				queue.add(N);
			
			 
				 
		}
		
	}


	
	
}

[jon.kiparsky]

Oh, okay, that was simple.

Look at your constructor. What happens on the second line?

[Arthurr]

oh, you mean the PriorityQueue<node> statement repeats?
That was the problem.
But why?

[jon.kiparsky]

What that line did was it declared a local variable called "queue" and pointed it to a new PriorityQueue of nodes. There was already a class field called queue, which this new variable shadowed - if there are two variables with the same name, the most local reference takes priority. Local variables go out of scope when their local context ends, in this case, when the constructor completes. So you created a Priority Queue, assigned it to a place on the stack, and then let it go out of scope. The field "queue" was never touched.

If the line reads

queue =  new PriorityQueue<node>(n,compare);

then it's not declaring a variable, it's referring to one that already exists. Since there is such a variable in scope now, it finds it and uses it.

This gives you a little peek into the machine - you're seeing the difference between the local stack and the heap, and you're getting a sense of how scope and context work - so think about it a little bit. There's more here than just "okay, my program works now"!
But now your program should work, as well.

[Arthurr]

oh i see
the second time i typed the "priorityqueue<node>"
but why it makes the queue null

[Arthurr]

thanks a lot!
This "little typo" kept me behind for two days!

[jon.kiparsky]

Glad it helped. Go ahead and mark the thread as solved, then...

[Arthurr]

I can't see the "solved" button.
or i just don't know where to look

[jon.kiparsky]

You should see the link directly below the words "Has this thread been answered?" at the bottom of the thread...