Re: Somewhere in this constructor of PriorityBlockingQueue is hard to understand

Liu,

Do you have a test case to show the behavior where null slips by and is allowed?  I think my test case here captures your intent but perhaps I'm missing a specific detail as I'm unable to make the test fail.

====
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.concurrent.PriorityBlockingQueue;

public class HeapifyTest {
	
	private static final int SIZE = 16;
	
	public static void main(String[] args) {
		for (int i=1; i<SIZE; i++) {
			testArrayList(i);
		}
	}
	
	private static void testArrayList(int size) {
		for (int i=0; i<size; i++) {
			ArrayList<Integer> al = new ArrayList<>(size);
			for (int j=0; j<size; j++) {
				if (i != j) {
					al.add(j);
				} else {
					al.add(null);
				}
			}
			
			testNull(al);
			
			Collections.reverse(al);
			testNull(al);
			
			Collections.shuffle(al);
			testNull(al);
			
			Collections.reverse(al);
			testNull(al);
		}
	}
	
	private static void testNull(Collection<Integer> c) {
		Objects.requireNonNull(c);
		try {
			new PriorityQueue<>(c);
			System.err.println("PQ FAIL contans null: " + c);
		} catch(NullPointerException expected) {
			System.err.println("PASS: " + c);
		}
		
		try {
			new PriorityBlockingQueue<>(c);
			System.err.println("PBQ FAIL contains null: " + c);
		} catch(NullPointerException expected) {
			System.err.println("PASS: " + c);
		}
	}
}
===

Jason

________________________________________
From: Liu <[email protected]>
Sent: Tuesday, August 4, 2020 10:55 AM
To: [email protected]
Cc: Concurrency-interest
Subject: Re:  [concurrency-interest] Somewhere in this constructor of PriorityBlockingQueue is hard to understand

Thanks for your answer!

About first question, if you say so, then maybe Instanceof allows subclasses which could be coded to break the assumption that items are not null.
I mean, only when "pq.getClass() == PriorityBlockingQueue.class" Expression holds, then you could do "screen = false".
Am i wrong?

> If the size is greater than one and there is no comparator heapify() will catch the null element.

About Third question, I think heapify() could not catch the null element that is at the back of array.
Because heapify() from last-non-leaf-node index to zero to invoke siftDownComparable(),
so heapify() couldn't Traverse every node.
And siftDownComparable() has a "while (k < half)", which half means first-leaf-node index,
so when k become a leaf-node index, the siftDown will stop too.
To sum up, heapify() could not catch the null element that is at the back of array.

--------------------------------------------------------------------------------
Regards
Liu
_______________________________________________
Concurrency-interest mailing list
[email protected]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest