Re: PriorityQueue PR requiring review

[David Holmes]

On 3/03/2022 11:02 pm, Julian Waters wrote:
I understand, I'll notify the author about this. I'm not sure if they'll 
be alright with discussing on the mailing lists though, since they have 
expressed that they prefer discussing it on the PR itself


That's not the way OpenJDK works, and anything in the PR (once properly 
setup) goes to the mailing list anyway.


https://openjdk.java.net/contribute/

Cheers,
David


best regards,
Julian Waters

On Thu, Mar 3, 2022 at 8:57 PM David Holmes > wrote:


On 3/03/2022 10:47 pm, Julian Waters wrote:
 > Hi David,
 >
 > I did not create the PR, I'm instead asking for others to review it
 > before I help the author create the issue on the JBS. Should I
just go
 > ahead and create the issue for them?

The best thing would be for the PR creator to discuss the proposed API
addition on the mailing list first. I have a fairly good idea what the
outcome of that discussion will be but ... :)

Cheers,
David

 > best regards,
 > Julian
 >
 > On Thu, Mar 3, 2022 at 8:45 PM David Holmes
mailto:david.hol...@oracle.com>
 > >> wrote:
 >
 >     Hi Julian,
 >
 >     On 3/03/2022 10:33 pm, Jules W. wrote:
 >      > Hi all,
 >      >
 >      > A new PR that adds methods to PriorityQueue was created
some time
 >     ago at
 >      > https://github.com/openjdk/jdk/pull/6938

 >     > but has no corresponding
 >     issue. As
 >      > I'm not too familiar with this part of the JDK I'm
querying this
 >     mailing
 >      > list for anyone to properly review the PR before I create an
 >     issue for it
 >      > in the JBS
 >
 >     First you need an issue, then you review a PR. Your PR would
not be
 >     seen
 >     by anyone unless they go looking for it, as without the
association
 >     with
 >     an issue, the system will not send the email to the mailing
lists.
 >
 >     I see someone is helping you create the issue so things
should progress
 >     in that sense. But note the bar for adding to a public API is set
 >     very high.
 >
 >     Cheers,
 >     David
 >
 >      > best regards,
 >      > Julian Waters
 >

Re: PriorityQueue PR requiring review

[Julian Waters]

I understand, I'll notify the author about this. I'm not sure if they'll be
alright with discussing on the mailing lists though, since they have
expressed that they prefer discussing it on the PR itself

best regards,
Julian Waters

On Thu, Mar 3, 2022 at 8:57 PM David Holmes  wrote:

> On 3/03/2022 10:47 pm, Julian Waters wrote:
> > Hi David,
> >
> > I did not create the PR, I'm instead asking for others to review it
> > before I help the author create the issue on the JBS. Should I just go
> > ahead and create the issue for them?
>
> The best thing would be for the PR creator to discuss the proposed API
> addition on the mailing list first. I have a fairly good idea what the
> outcome of that discussion will be but ... :)
>
> Cheers,
> David
>
> > best regards,
> > Julian
> >
> > On Thu, Mar 3, 2022 at 8:45 PM David Holmes  > > wrote:
> >
> > Hi Julian,
> >
> > On 3/03/2022 10:33 pm, Jules W. wrote:
> >  > Hi all,
> >  >
> >  > A new PR that adds methods to PriorityQueue was created some time
> > ago at
> >  > https://github.com/openjdk/jdk/pull/6938
> >  but has no corresponding
> > issue. As
> >  > I'm not too familiar with this part of the JDK I'm querying this
> > mailing
> >  > list for anyone to properly review the PR before I create an
> > issue for it
> >  > in the JBS
> >
> > First you need an issue, then you review a PR. Your PR would not be
> > seen
> > by anyone unless they go looking for it, as without the association
> > with
> > an issue, the system will not send the email to the mailing lists.
> >
> > I see someone is helping you create the issue so things should
> progress
> > in that sense. But note the bar for adding to a public API is set
> > very high.
> >
> > Cheers,
> > David
> >
> >  > best regards,
> >  > Julian Waters
> >
>

Re: PriorityQueue PR requiring review

[David Holmes]

On 3/03/2022 10:47 pm, Julian Waters wrote:

Hi David,

I did not create the PR, I'm instead asking for others to review it 
before I help the author create the issue on the JBS. Should I just go 
ahead and create the issue for them?


The best thing would be for the PR creator to discuss the proposed API 
addition on the mailing list first. I have a fairly good idea what the 
outcome of that discussion will be but ... :)


Cheers,
David


best regards,
Julian

On Thu, Mar 3, 2022 at 8:45 PM David Holmes > wrote:


Hi Julian,

On 3/03/2022 10:33 pm, Jules W. wrote:
 > Hi all,
 >
 > A new PR that adds methods to PriorityQueue was created some time
ago at
 > https://github.com/openjdk/jdk/pull/6938
 but has no corresponding
issue. As
 > I'm not too familiar with this part of the JDK I'm querying this
mailing
 > list for anyone to properly review the PR before I create an
issue for it
 > in the JBS

First you need an issue, then you review a PR. Your PR would not be
seen
by anyone unless they go looking for it, as without the association
with
an issue, the system will not send the email to the mailing lists.

I see someone is helping you create the issue so things should progress
in that sense. But note the bar for adding to a public API is set
very high.

Cheers,
David

 > best regards,
 > Julian Waters

Re: PriorityQueue PR requiring review

[Julian Waters]

Hi David,

I did not create the PR, I'm instead asking for others to review it before
I help the author create the issue on the JBS. Should I just go ahead and
create the issue for them?

best regards,
Julian

On Thu, Mar 3, 2022 at 8:45 PM David Holmes  wrote:

> Hi Julian,
>
> On 3/03/2022 10:33 pm, Jules W. wrote:
> > Hi all,
> >
> > A new PR that adds methods to PriorityQueue was created some time ago at
> > https://github.com/openjdk/jdk/pull/6938 but has no corresponding
> issue. As
> > I'm not too familiar with this part of the JDK I'm querying this mailing
> > list for anyone to properly review the PR before I create an issue for it
> > in the JBS
>
> First you need an issue, then you review a PR. Your PR would not be seen
> by anyone unless they go looking for it, as without the association with
> an issue, the system will not send the email to the mailing lists.
>
> I see someone is helping you create the issue so things should progress
> in that sense. But note the bar for adding to a public API is set very
> high.
>
> Cheers,
> David
>
> > best regards,
> > Julian Waters
>

Re: PriorityQueue PR requiring review

[Julian Waters]

Hi David,

No worries :)

regards,
Julian

On Thu, Mar 3, 2022 at 8:47 PM David Holmes  wrote:

> Sorry Julian, I see now you were the person aiding the person who
> created the PR.
>
> David
>
> On 3/03/2022 10:45 pm, David Holmes wrote:
> > Hi Julian,
> >
> > On 3/03/2022 10:33 pm, Jules W. wrote:
> >> Hi all,
> >>
> >> A new PR that adds methods to PriorityQueue was created some time ago at
> >> https://github.com/openjdk/jdk/pull/6938 but has no corresponding
> >> issue. As
> >> I'm not too familiar with this part of the JDK I'm querying this mailing
> >> list for anyone to properly review the PR before I create an issue for
> it
> >> in the JBS
> >
> > First you need an issue, then you review a PR. Your PR would not be seen
> > by anyone unless they go looking for it, as without the association with
> > an issue, the system will not send the email to the mailing lists.
> >
> > I see someone is helping you create the issue so things should progress
> > in that sense. But note the bar for adding to a public API is set very
> > high.
> >
> > Cheers,
> > David
> >
> >> best regards,
> >> Julian Waters
>

Re: PriorityQueue PR requiring review

[David Holmes]

Sorry Julian, I see now you were the person aiding the person who 
created the PR.


David

On 3/03/2022 10:45 pm, David Holmes wrote:

Hi Julian,

On 3/03/2022 10:33 pm, Jules W. wrote:

Hi all,

A new PR that adds methods to PriorityQueue was created some time ago at
https://github.com/openjdk/jdk/pull/6938 but has no corresponding 
issue. As

I'm not too familiar with this part of the JDK I'm querying this mailing
list for anyone to properly review the PR before I create an issue for it
in the JBS


First you need an issue, then you review a PR. Your PR would not be seen 
by anyone unless they go looking for it, as without the association with 
an issue, the system will not send the email to the mailing lists.


I see someone is helping you create the issue so things should progress 
in that sense. But note the bar for adding to a public API is set very 
high.


Cheers,
David


best regards,
Julian Waters

Re: PriorityQueue PR requiring review

[David Holmes]

Hi Julian,

On 3/03/2022 10:33 pm, Jules W. wrote:

Hi all,

A new PR that adds methods to PriorityQueue was created some time ago at
https://github.com/openjdk/jdk/pull/6938 but has no corresponding issue. As
I'm not too familiar with this part of the JDK I'm querying this mailing
list for anyone to properly review the PR before I create an issue for it
in the JBS


First you need an issue, then you review a PR. Your PR would not be seen 
by anyone unless they go looking for it, as without the association with 
an issue, the system will not send the email to the mailing lists.


I see someone is helping you create the issue so things should progress 
in that sense. But note the bar for adding to a public API is set very high.


Cheers,
David


best regards,
Julian Waters

Re: PriorityQueue

[Brett Bernstein]

I believe the linked sequence of messages refer to the addition of a
PriorityQueue constructor only taking a Comparator which was does appear in
Java 1.8.  Did you have a link to something regarding the a constructor
taking a Collection and a Comparator (2 arguments)?


On Thu, May 14, 2015 at 2:08 AM, Martin Buchholz marti...@google.com
wrote:

 Software is hard.
 We tried and got stuck, although the former effort can be revived.
 RFR : 6799426 : (xs) Add constructor PriorityQueue(Comparator)
 http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-July/019124.html



 On Wed, May 13, 2015 at 10:17 PM, Brett Bernstein 
 brett.bernst...@gmail.com wrote:

 To whom this may concern:
 I believe the list of PriorityQueue constructors has a glaring omission
 that could be easily rectified.  That is, there is no constructor that
 takes a Collection and a Comparator.  What steps should I go through to
 get
 this suggested to be added to the class?

 Thanks,
 Brett Bernstein

Re: PriorityQueue

[Paul Sandoz]

On May 15, 2015, at 4:04 PM, Chris Hegarty chris.hega...@oracle.com wrote:

 And/Or should PriorityQueue override addAll and provide a more performant 
 implementation for common Collection types ( just like the constructor )?
 

It should be possible to improve this case too: create a new array, 
appropriately sized, holding the current elements and those of the collection 
(via toArray or iteration), then reestablish the heap invariant.

Paul.

Re: PriorityQueue

[Paul Sandoz]

On May 15, 2015, at 3:20 PM, Vitaly Davidovich vita...@gmail.com wrote:

 Paul,
 
 I don't think you're missing anything obvious (unless I am as well :)).  What 
 you wrote is basically what I meant by creating static helper method in 
 Brett's own code that does exactly what you wrote.  The asymptotic complexity 
 will be nlogn in both cases, but the constant factor will be different since 
 addAll() makes iterative add() calls with some overhead (branches, modCount 
 bump, etc).  The only O(n) constructors there are one taking SortedSet and 
 copy constructor.
 
 

Yes.

 Brett did mention he wanted the bulk add functionality (i.e. remove constant 
 factor), and given the class already supports that internally, seems like a 
 harmless change.
 
 

I agree.

This seems like an ideal issue for someone to pick up who is interesting in 
contributing a patch+tests to OpenJDK. Brett, i gather you might be interested 
in doing so?

Paul.

Re: PriorityQueue

[Paul Sandoz]

On May 14, 2015, at 8:17 AM, Brett Bernstein brett.bernst...@gmail.com wrote:

 I believe the linked sequence of messages refer to the addition of a
 PriorityQueue constructor only taking a Comparator which was does appear in
 Java 1.8.  Did you have a link to something regarding the a constructor
 taking a Collection and a Comparator (2 arguments)?
 

There is an old issue already logged for this:

  https://bugs.openjdk.java.net/browse/JDK-6356745

Give that one can already do:

  Collection c = ...
  Comparator cmp = ...
  PriorityQueue p =new PriorityQueue(c.size(), cmp);
  p.addAll(c);

Is there a huge need for a new constructor that accepts a collection and a 
comparator? 

It seems a nice to have and may be marginally more efficient but AFAICT O-wise 
addAll and establishing the heap invariant for the entire tree that is 
initially unordered is the same (unless i am missing something obvious here).

Paul.

Re: PriorityQueue

[Stuart Marks]

Yes, this is very subtle, and Brett mentioned it (albeit somewhat obliquely) in 
an email on jdk9-dev: [1]



If someone needs to make a
heap and their data is Comparable, the corresponding constructor gives a
O(n) runtime.  If their data uses a Comparator, the corresponding runtime
(using addAll) is O(n*log(n)).


I was initially confused by this because it seems to attribute the algorithmic 
difference to Comparable vs Comparator, which doesn't make any sense. (I managed 
to unconfuse myself before opening my big mouth, though.) The real issue is that 
the Collection-consuming constructor code path goes through heapify() and 
siftDown(), whereas the non-Collection-consuming constructor followed by 
addAll() goes through siftUp().


The problem is that if you want your own Comparator, there's no constructor that 
takes a Collection, so you're forced to the slow path.


Earlier in this thread, Paul unearthed JDK-6356745 [2] which says essentially 
the same thing as proposed here. I'll update it with some notes.



s'marks


[1] http://mail.openjdk.java.net/pipermail/jdk9-dev/2015-May/002205.html

[2] https://bugs.openjdk.java.net/browse/JDK-6356745



On 5/15/15 9:45 AM, Vitaly Davidovich wrote:

Whoops, I believe you're right -- I completely overlooked that as well :(

On Fri, May 15, 2015 at 12:40 PM, Paul Sandoz paul.san...@oracle.com
wrote:



On May 15, 2015, at 6:15 PM, Louis Wasserman lowas...@google.com wrote:


http://lcm.csa.iisc.ernet.in/dsa/node139.html suggests an algorithm for
heapifying an unsorted array in O(n), corroborated elsewhere at
http://courses.csail.mit.edu/6.006/fall10/handouts/recitation10-8.pdf .
Any particular reason we can't use that approach?



Thanks. I got things wrong before. I believe the PQ.heapify() does exactly
that:

private void heapify() {
 for (int i = (size  1) - 1; i = 0; i--)
 siftDown(i, (E) queue[i]);
}

So there is more value in the constructor than i originally thought.

Paul.

Re: PriorityQueue

[Vitaly Davidovich]

Whoops, I believe you're right -- I completely overlooked that as well :(

On Fri, May 15, 2015 at 12:40 PM, Paul Sandoz paul.san...@oracle.com
wrote:


 On May 15, 2015, at 6:15 PM, Louis Wasserman lowas...@google.com wrote:

  http://lcm.csa.iisc.ernet.in/dsa/node139.html suggests an algorithm for
  heapifying an unsorted array in O(n), corroborated elsewhere at
  http://courses.csail.mit.edu/6.006/fall10/handouts/recitation10-8.pdf .
  Any particular reason we can't use that approach?
 

 Thanks. I got things wrong before. I believe the PQ.heapify() does exactly
 that:

 private void heapify() {
 for (int i = (size  1) - 1; i = 0; i--)
 siftDown(i, (E) queue[i]);
 }

 So there is more value in the constructor than i originally thought.

 Paul.

Re: PriorityQueue

[Paul Sandoz]

On May 15, 2015, at 6:15 PM, Louis Wasserman lowas...@google.com wrote:

 http://lcm.csa.iisc.ernet.in/dsa/node139.html suggests an algorithm for
 heapifying an unsorted array in O(n), corroborated elsewhere at
 http://courses.csail.mit.edu/6.006/fall10/handouts/recitation10-8.pdf .
 Any particular reason we can't use that approach?
 

Thanks. I got things wrong before. I believe the PQ.heapify() does exactly that:

private void heapify() {
for (int i = (size  1) - 1; i = 0; i--)
siftDown(i, (E) queue[i]);
}

So there is more value in the constructor than i originally thought.

Paul.

Re: PriorityQueue

[Vitaly Davidovich]

 I was initially confused by this because it seems to attribute the
 algorithmic difference to Comparable vs Comparator, which doesn't make any
 sense


That's exactly what threw me off as well, but I didn't bother checking
(doh!).  Anyway, I think the upside is we're all in agreement now that this
is *definitely* a worthwhile improvement :).

On Fri, May 15, 2015 at 1:30 PM, Stuart Marks stuart.ma...@oracle.com
wrote:

 Yes, this is very subtle, and Brett mentioned it (albeit somewhat
 obliquely) in an email on jdk9-dev: [1]

  If someone needs to make a
 heap and their data is Comparable, the corresponding constructor gives a
 O(n) runtime.  If their data uses a Comparator, the corresponding runtime
 (using addAll) is O(n*log(n)).


 I was initially confused by this because it seems to attribute the
 algorithmic difference to Comparable vs Comparator, which doesn't make any
 sense. (I managed to unconfuse myself before opening my big mouth, though.)
 The real issue is that the Collection-consuming constructor code path goes
 through heapify() and siftDown(), whereas the non-Collection-consuming
 constructor followed by addAll() goes through siftUp().

 The problem is that if you want your own Comparator, there's no
 constructor that takes a Collection, so you're forced to the slow path.

 Earlier in this thread, Paul unearthed JDK-6356745 [2] which says
 essentially the same thing as proposed here. I'll update it with some notes.


 s'marks


 [1] http://mail.openjdk.java.net/pipermail/jdk9-dev/2015-May/002205.html

 [2] https://bugs.openjdk.java.net/browse/JDK-6356745




 On 5/15/15 9:45 AM, Vitaly Davidovich wrote:

 Whoops, I believe you're right -- I completely overlooked that as well :(

 On Fri, May 15, 2015 at 12:40 PM, Paul Sandoz paul.san...@oracle.com
 wrote:


 On May 15, 2015, at 6:15 PM, Louis Wasserman lowas...@google.com
 wrote:

  http://lcm.csa.iisc.ernet.in/dsa/node139.html suggests an algorithm for
 heapifying an unsorted array in O(n), corroborated elsewhere at
 http://courses.csail.mit.edu/6.006/fall10/handouts/recitation10-8.pdf .
 Any particular reason we can't use that approach?


 Thanks. I got things wrong before. I believe the PQ.heapify() does
 exactly
 that:

 private void heapify() {
  for (int i = (size  1) - 1; i = 0; i--)
  siftDown(i, (E) queue[i]);
 }

 So there is more value in the constructor than i originally thought.

 Paul.

Re: PriorityQueue

[Martin Buchholz]

Software is hard.
We tried and got stuck, although the former effort can be revived.
RFR : 6799426 : (xs) Add constructor PriorityQueue(Comparator)
http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-July/019124.html



On Wed, May 13, 2015 at 10:17 PM, Brett Bernstein brett.bernst...@gmail.com
 wrote:

 To whom this may concern:
 I believe the list of PriorityQueue constructors has a glaring omission
 that could be easily rectified.  That is, there is no constructor that
 takes a Collection and a Comparator.  What steps should I go through to get
 this suggested to be added to the class?

 Thanks,
 Brett Bernstein

Re: PriorityQueue

[Martin Buchholz]

On Wed, May 13, 2015 at 11:17 PM, Brett Bernstein brett.bernst...@gmail.com
 wrote:

 I believe the linked sequence of messages refer to the addition of a
 PriorityQueue constructor only taking a Comparator which was does appear in
 Java 1.8.  Did you have a link to something regarding the a constructor
 taking a Collection and a Comparator (2 arguments)?


Oops - you are right...  The one I referenced did get added, and your
constructor is still missing.
You may have trouble finding someone with the same enthusiasm for this
constructor as yourself.

Re: PriorityQueue

[Dawid Weiss]

 You may have trouble finding someone with the same enthusiasm for this 
 constructor as yourself.

This probably applies to many data structures that have specific (and
rare) applications. A priority queue that takes a custom comparator
seems like a pretty frequent (algorithmic) use case to me, however
(and so does a
limited capacity queue).

As an example, you can see the implementation of such a PQ in Apache
Lucene -- it is used all over the place [1].

Dawid

[1] 
https://github.com/apache/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java#L75-L79


On Thu, May 14, 2015 at 8:21 AM, Martin Buchholz marti...@google.com wrote:
 On Wed, May 13, 2015 at 11:17 PM, Brett Bernstein brett.bernst...@gmail.com
 wrote:

 I believe the linked sequence of messages refer to the addition of a
 PriorityQueue constructor only taking a Comparator which was does appear in
 Java 1.8.  Did you have a link to something regarding the a constructor
 taking a Collection and a Comparator (2 arguments)?


 Oops - you are right...  The one I referenced did get added, and your
 constructor is still missing.
 You may have trouble finding someone with the same enthusiasm for this
 constructor as yourself.

Re: PriorityQueue(collection) should throw NPE

[Chris Hegarty]

Hi David, Martin,

Thanks for filing the bug David, I'll just add a link to the email 
thread in the archive for reference.


Just one minor observation while reviewing the changes. Is it necessary 
for initFromPriorityQueue to call initFromCollection ( in the case where 
you're given a PriorityQueue subclass), or can it simply call 
initElementsFromCollection?


-Chris.

On 07/05/2010 03:37, David Holmes wrote:

Hi Martin,

CR 6950540 filed. (Chris might want to tidy it up :) )

Changes look okay to me.

Thanks,
David

Martin Buchholz said the following on 05/07/10 12:19:

David,

Of course you're right.
I didn't realize that the hole was one-element nulls.

(Why is software always 10 times harder than you'd think?)

Updated webrev, with lots more tests for corner cases.

I still need a bug filed in bugtraq.

Martin

On Thu, May 6, 2010 at 16:53, David Holmes david.hol...@oracle.com
wrote:

Hi Martin,

Martin Buchholz said the following on 05/07/10 09:13:

On Thu, May 6, 2010 at 15:58, David Holmes david.hol...@oracle.com
wrote:

Fix:


http://cr.openjdk.java.net/~martin/webrevs/openjdk7/PriorityQueueConstructor/


I'm not sure this is necessarily the right fix. It seems to me that
incidental nulls will be caught in many/most cases by the sorting code
for
collections assumed to contain Comparable's.

The comparator might accept nulls.

True but a Comparator is only used if the Collection is a SortedSet or a
PriorityQueue. For any other Collection the elements must implement
Comparable and the code in:

private void siftDownComparable(int k, E x) {
Comparable? super E key = (Comparable? super E)x;
int half = size  1; // loop while a non-leaf
while (k  half) {
int child = (k  1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right  size 
((Comparable? super E) c).compareTo((E) queue[right])  0)
c = queue[child = right];
if (key.compareTo((E) c) = 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}

will throw NPE at key.compareTo if the item is null. (There's probably a
missed case where the collection contains only a null element).


But even if it doesn't, it is possible to create a corrupted PQ
using the PQ(collection) constructor, and we don't allow
that sort of thing in java.util.

But that's the hole we're fixing now.


And we don't need to check when
filling from an existing PriorityQueue.

Strictly speaking, the source PriorityQueue might be a subclass that
has been modified to accept nulls.

Yes I suppose. So we could change from an instanceof test to a
getClass()
test.


But yes, we could have a version of the fix that only checks for nulls
if the source is not a PQ.


So is it only the case for filling
from a SortedSet that needs the explicit null check?

The source can be an arbitrary Collection.

But as noted above for anything other than a SortedSet (or corrupt
PQ) the
sorting code will already catch nulls.

Cheers,
David


Martin


David

Re: PriorityQueue(collection) should throw NPE

[David Holmes]

Hi Chris,

Chris Hegarty said the following on 05/07/10 19:55:

Hi David, Martin,

Thanks for filing the bug David, I'll just add a link to the email 
thread in the archive for reference.


Thanks.

Just one minor observation while reviewing the changes. Is it necessary 
for initFromPriorityQueue to call initFromCollection ( in the case where 
you're given a PriorityQueue subclass), or can it simply call 
initElementsFromCollection?


It's possible that the subclass overrides toArray to return an array 
that doesn't preserve the internal order. Hence we need to re-sort, 
hence initFromCollection.


David


-Chris.

On 07/05/2010 03:37, David Holmes wrote:

Hi Martin,

CR 6950540 filed. (Chris might want to tidy it up :) )

Changes look okay to me.

Thanks,
David

Martin Buchholz said the following on 05/07/10 12:19:

David,

Of course you're right.
I didn't realize that the hole was one-element nulls.

(Why is software always 10 times harder than you'd think?)

Updated webrev, with lots more tests for corner cases.

I still need a bug filed in bugtraq.

Martin

On Thu, May 6, 2010 at 16:53, David Holmes david.hol...@oracle.com
wrote:

Hi Martin,

Martin Buchholz said the following on 05/07/10 09:13:

On Thu, May 6, 2010 at 15:58, David Holmes david.hol...@oracle.com
wrote:

Fix:


http://cr.openjdk.java.net/~martin/webrevs/openjdk7/PriorityQueueConstructor/ 




I'm not sure this is necessarily the right fix. It seems to me that
incidental nulls will be caught in many/most cases by the sorting 
code

for
collections assumed to contain Comparable's.

The comparator might accept nulls.
True but a Comparator is only used if the Collection is a SortedSet 
or a

PriorityQueue. For any other Collection the elements must implement
Comparable and the code in:

private void siftDownComparable(int k, E x) {
Comparable? super E key = (Comparable? super E)x;
int half = size  1; // loop while a non-leaf
while (k  half) {
int child = (k  1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right  size 
((Comparable? super E) c).compareTo((E) queue[right])  0)
c = queue[child = right];
if (key.compareTo((E) c) = 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}

will throw NPE at key.compareTo if the item is null. (There's 
probably a

missed case where the collection contains only a null element).


But even if it doesn't, it is possible to create a corrupted PQ
using the PQ(collection) constructor, and we don't allow
that sort of thing in java.util.

But that's the hole we're fixing now.


And we don't need to check when
filling from an existing PriorityQueue.

Strictly speaking, the source PriorityQueue might be a subclass that
has been modified to accept nulls.

Yes I suppose. So we could change from an instanceof test to a
getClass()
test.


But yes, we could have a version of the fix that only checks for nulls
if the source is not a PQ.


So is it only the case for filling
from a SortedSet that needs the explicit null check?

The source can be an arbitrary Collection.

But as noted above for anything other than a SortedSet (or corrupt
PQ) the
sorting code will already catch nulls.

Cheers,
David


Martin


David

Re: PriorityQueue(collection) should throw NPE

[Chris Hegarty]

On 07/05/2010 11:47, David Holmes wrote:

Hi Chris,

Chris Hegarty said the following on 05/07/10 19:55:

Hi David, Martin,

Thanks for filing the bug David, I'll just add a link to the email
thread in the archive for reference.


Thanks.


Just one minor observation while reviewing the changes. Is it
necessary for initFromPriorityQueue to call initFromCollection ( in
the case where you're given a PriorityQueue subclass), or can it
simply call initElementsFromCollection?


It's possible that the subclass overrides toArray to return an array
that doesn't preserve the internal order. Hence we need to re-sort,
hence initFromCollection.


OK, not problem. Just checking.

-Chris.



David

Re: PriorityQueue(collection) should throw NPE

[Martin Buchholz]

On Fri, May 7, 2010 at 03:47, David Holmes david.hol...@oracle.com wrote:
 Hi Chris,

 Chris Hegarty said the following on 05/07/10 19:55:

 Hi David, Martin,

 Thanks for filing the bug David, I'll just add a link to the email thread
 in the archive for reference.

 Thanks.

 Just one minor observation while reviewing the changes. Is it necessary
 for initFromPriorityQueue to call initFromCollection ( in the case where
 you're given a PriorityQueue subclass), or can it simply call
 initElementsFromCollection?

 It's possible that the subclass overrides toArray to return an array that
 doesn't preserve the internal order. Hence we need to re-sort, hence
 initFromCollection.

Yes.

As a thought experiment, suppose you're writing a spiffy new
priority queue implementation that is supposed to be a drop-in
replacement for PriorityQueue.  You might choose to
subclass PriorityQueue even if you're not reusing any
of the implementation (because we made the
mistake of not making PriorityQueue an interface).
PriorityQueue's iterator and toArray methods make
no promises about element order.

On the bright side, heapify() will be O(N), not O(N log N)
if the input array is already heapified.

Martin

Re: PriorityQueue(collection) should throw NPE

[David Holmes]

Martin,

Martin Buchholz said the following on 05/07/10 08:24:

This is a bug report with fix.
(Chris, please file a bug)

Summary: PriorityQueue(collection) should throw NPE if collection
contains a null

Description:
PriorityQueue spec says:

A priority queue does not permit {...@code null} elements.

but the constructor taking a collection does not enforce that.

Fix:
http://cr.openjdk.java.net/~martin/webrevs/openjdk7/PriorityQueueConstructor/


I'm not sure this is necessarily the right fix. It seems to me that 
incidental nulls will be caught in many/most cases by the sorting code 
for collections assumed to contain Comparable's. And we don't need to 
check when filling from an existing PriorityQueue. So is it only the 
case for filling from a SortedSet that needs the explicit null check?


David

Re: PriorityQueue(collection) should throw NPE

[Martin Buchholz]

On Thu, May 6, 2010 at 15:58, David Holmes david.hol...@oracle.com wrote:
 Fix:

 http://cr.openjdk.java.net/~martin/webrevs/openjdk7/PriorityQueueConstructor/

 I'm not sure this is necessarily the right fix. It seems to me that
 incidental nulls will be caught in many/most cases by the sorting code for
 collections assumed to contain Comparable's.

The comparator might accept nulls.
But even if it doesn't, it is possible to create a corrupted PQ
using the PQ(collection) constructor, and we don't allow
that sort of thing in java.util.

 And we don't need to check when
 filling from an existing PriorityQueue.

Strictly speaking, the source PriorityQueue might be a subclass that
has been modified to accept nulls.
But yes, we could have a version of the fix that only checks for nulls
if the source is not a PQ.

 So is it only the case for filling
 from a SortedSet that needs the explicit null check?

The source can be an arbitrary Collection.

Martin

 David

Re: PriorityQueue(collection) should throw NPE

[David Holmes]

Hi Martin,

Martin Buchholz said the following on 05/07/10 09:13:

On Thu, May 6, 2010 at 15:58, David Holmes david.hol...@oracle.com wrote:

Fix:

http://cr.openjdk.java.net/~martin/webrevs/openjdk7/PriorityQueueConstructor/

I'm not sure this is necessarily the right fix. It seems to me that
incidental nulls will be caught in many/most cases by the sorting code for
collections assumed to contain Comparable's.


The comparator might accept nulls.


True but a Comparator is only used if the Collection is a SortedSet or a 
PriorityQueue. For any other Collection the elements must implement 
Comparable and the code in:


   private void siftDownComparable(int k, E x) {
Comparable? super E key = (Comparable? super E)x;
int half = size  1;// loop while a non-leaf
while (k  half) {
int child = (k  1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right  size 
((Comparable? super E) c).compareTo((E) queue[right]) 
 0)

c = queue[child = right];
if (key.compareTo((E) c) = 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}

will throw NPE at key.compareTo if the item is null. (There's probably a 
missed case where the collection contains only a null element).



But even if it doesn't, it is possible to create a corrupted PQ
using the PQ(collection) constructor, and we don't allow
that sort of thing in java.util.


But that's the hole we're fixing now.


And we don't need to check when
filling from an existing PriorityQueue.


Strictly speaking, the source PriorityQueue might be a subclass that
has been modified to accept nulls.


Yes I suppose. So we could change from an instanceof test to a 
getClass() test.



But yes, we could have a version of the fix that only checks for nulls
if the source is not a PQ.


So is it only the case for filling
from a SortedSet that needs the explicit null check?


The source can be an arbitrary Collection.


But as noted above for anything other than a SortedSet (or corrupt PQ) 
the sorting code will already catch nulls.


Cheers,
David


Martin


David

Re: PriorityQueue(collection) should throw NPE

[Martin Buchholz]

David,

Of course you're right.
I didn't realize that the hole was one-element nulls.

(Why is software always 10 times harder than you'd think?)

Updated webrev, with lots more tests for corner cases.

I still need a bug filed in bugtraq.

Martin

On Thu, May 6, 2010 at 16:53, David Holmes david.hol...@oracle.com wrote:
 Hi Martin,

 Martin Buchholz said the following on 05/07/10 09:13:

 On Thu, May 6, 2010 at 15:58, David Holmes david.hol...@oracle.com
 wrote:

 Fix:


 http://cr.openjdk.java.net/~martin/webrevs/openjdk7/PriorityQueueConstructor/

 I'm not sure this is necessarily the right fix. It seems to me that
 incidental nulls will be caught in many/most cases by the sorting code
 for
 collections assumed to contain Comparable's.

 The comparator might accept nulls.

 True but a Comparator is only used if the Collection is a SortedSet or a
 PriorityQueue. For any other Collection the elements must implement
 Comparable and the code in:

   private void siftDownComparable(int k, E x) {
        Comparable? super E key = (Comparable? super E)x;
        int half = size  1;        // loop while a non-leaf
        while (k  half) {
            int child = (k  1) + 1; // assume left child is least
            Object c = queue[child];
            int right = child + 1;
            if (right  size 
                ((Comparable? super E) c).compareTo((E) queue[right])  0)
                c = queue[child = right];
            if (key.compareTo((E) c) = 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }

 will throw NPE at key.compareTo if the item is null. (There's probably a
 missed case where the collection contains only a null element).

 But even if it doesn't, it is possible to create a corrupted PQ
 using the PQ(collection) constructor, and we don't allow
 that sort of thing in java.util.

 But that's the hole we're fixing now.

 And we don't need to check when
 filling from an existing PriorityQueue.

 Strictly speaking, the source PriorityQueue might be a subclass that
 has been modified to accept nulls.

 Yes I suppose. So we could change from an instanceof test to a getClass()
 test.

 But yes, we could have a version of the fix that only checks for nulls
 if the source is not a PQ.

 So is it only the case for filling
 from a SortedSet that needs the explicit null check?

 The source can be an arbitrary Collection.

 But as noted above for anything other than a SortedSet (or corrupt PQ) the
 sorting code will already catch nulls.

 Cheers,
 David

 Martin

 David

Re: PriorityQueue(collection) should throw NPE

[David Holmes]

Hi Martin,

CR 6950540 filed. (Chris might want to tidy it up :) )

Changes look okay to me.

Thanks,
David

Martin Buchholz said the following on 05/07/10 12:19:

David,

Of course you're right.
I didn't realize that the hole was one-element nulls.

(Why is software always 10 times harder than you'd think?)

Updated webrev, with lots more tests for corner cases.

I still need a bug filed in bugtraq.

Martin

On Thu, May 6, 2010 at 16:53, David Holmes david.hol...@oracle.com wrote:

Hi Martin,

Martin Buchholz said the following on 05/07/10 09:13:

On Thu, May 6, 2010 at 15:58, David Holmes david.hol...@oracle.com
wrote:

Fix:


http://cr.openjdk.java.net/~martin/webrevs/openjdk7/PriorityQueueConstructor/

I'm not sure this is necessarily the right fix. It seems to me that
incidental nulls will be caught in many/most cases by the sorting code
for
collections assumed to contain Comparable's.

The comparator might accept nulls.

True but a Comparator is only used if the Collection is a SortedSet or a
PriorityQueue. For any other Collection the elements must implement
Comparable and the code in:

  private void siftDownComparable(int k, E x) {
   Comparable? super E key = (Comparable? super E)x;
   int half = size  1;// loop while a non-leaf
   while (k  half) {
   int child = (k  1) + 1; // assume left child is least
   Object c = queue[child];
   int right = child + 1;
   if (right  size 
   ((Comparable? super E) c).compareTo((E) queue[right])  0)
   c = queue[child = right];
   if (key.compareTo((E) c) = 0)
   break;
   queue[k] = c;
   k = child;
   }
   queue[k] = key;
   }

will throw NPE at key.compareTo if the item is null. (There's probably a
missed case where the collection contains only a null element).


But even if it doesn't, it is possible to create a corrupted PQ
using the PQ(collection) constructor, and we don't allow
that sort of thing in java.util.

But that's the hole we're fixing now.


And we don't need to check when
filling from an existing PriorityQueue.

Strictly speaking, the source PriorityQueue might be a subclass that
has been modified to accept nulls.

Yes I suppose. So we could change from an instanceof test to a getClass()
test.


But yes, we could have a version of the fix that only checks for nulls
if the source is not a PQ.


So is it only the case for filling
from a SortedSet that needs the explicit null check?

The source can be an arbitrary Collection.

But as noted above for anything other than a SortedSet (or corrupt PQ) the
sorting code will already catch nulls.

Cheers,
David


Martin


David