RFR: 6356745: (coll) Add PriorityQueue(Collection, Comparator) [v4]

[jmehrens]

On Mon, 25 Dec 2023 05:52:51 GMT, jmehrens <duke at openjdk.org> wrote:

>> Valeh Hajiyev has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   updated the javadoc
>
> Would adding a fast path to addAll solve this issue?  I asked this back in 2006 in JDK-6356745.  The [TreeMap::putAll](https://github.com/openjdk/jdk/blob/2d609557ffe8e15ab81fb51dce90e40780598371/src/java.base/share/classes/java/util/TreeMap.java#L348) is already implemented to work this way so we could apply the same concept to PriorityQueue and BlockingPriorityQueue
> 
> For example sake:
> 
>  public boolean addAll(Collection<? extends E> c) {
>         if (c == null)
>             throw new NullPointerException();
>         if (c == this)
>             throw new IllegalArgumentException();
>         
>         if (size == 0) {
>             return addAllEmpty(c); 
>         }
>         return super.addAll(c);
>     }
>     
>     private boolean addAllEmpty(Collection<? extends E> c) {
>         //assert size == 0 : size;
>         Object[] old = this.queue;
>         try {
>             if (c instanceof SortedSet<?> ss 
>                 && Objects.equals(this.comparator, ss.comparator()) {
>                 initElementsFromCollection(ss);
>             }
>             else if (c instanceof PriorityQueue<?> pq
>                 && Objects.equals(this.comparator, pq.comparator())) {
>                 initFromPriorityQueue(pq);
>             } else {
>                 initFromCollection(c);
>             }
>         } catch (Throwable t) {
>             size = 0;
>             this.queue = old;
>             //super.addAll(c); //Punish the wicked or get rid of all or nothing behavior.
>             throw t;
>         }
>         return size != 0;
>     }
> 
> 
> This would allow an empty PQ to heapfiy/siftDown.  There is a change in that the addAll is all or nothing in the empty case.

> @jmehrens If we apply the similar way of thinking, the `PriorityQueue(Collection)` constructor should not exist either, as it is redundant because of the `addAll()` method. 

The copy constructor is document in in the [Collection interface](https://github.com/openjdk/jdk/blob/2a59243cbaf3e7d5d1bfc9f247d28bc648687ea5/src/java.base/share/classes/java/util/Collection.java#L52):

> ...should provide two "standard" constructors: a void (no arguments) constructor, which creates an empty collection, and a constructor with a single argument of type Collection, which creates a new collection with the same elements as its argument.

While redundant it is super convenient and common to write a "return safe copy of this collection" or "pass a safe copy of this collection" on one line.  The Queue and BlockingQueue interfaces do not seem to document these two constructors like the other interfaces.  It would be nice if Queue and BlockingQueue were updated to document constructors in a new ticket.

>Given that we already have constructors like `PriorityQueue(Collection)` and `PriorityQueue(Comparator)`, it seems appropriate to maintain a similar approach. I believe introducing `PriorityQueue(Collection, Comparator)` aligns with the selected design appraoch and offers users a clear and intuitive way to initialize the queue based on the specifications. wdyt?

The other constructors are borrowed from [SortedSet](https://github.com/openjdk/jdk/blob/2a59243cbaf3e7d5d1bfc9f247d28bc648687ea5/src/java.base/share/classes/java/util/SortedSet.java#L60)

> ... provide four "standard" constructors: 
>1) A void (no arguments) constructor, which creates an empty sorted set sorted according to the natural ordering of its elements.  
>2) A constructor with a single argument of type Comparator, which creates an empty sorted set sorted according to the specified comparator.  
>3) A constructor with a single argument of type Collection, which creates a new sorted set with the same elements as its argument, sorted according to the natural ordering of the elements.
>4) A constructor with a single argument of type SortedSet,

Even though PQ can't and doesn't implement sorted set it appears that PriorityQueue(Comparator), PriorityQueue(PriorityQueue) and PriorityQueue::comparator() are borrowed from that interface under points 2 and 4.

Going back to the JIRA issue the sections for justification, expect, and actual are about performance.  The submitter states that a new constructor was only solution known at the time and it is to serve the need of performance and not API design.  The only complaint about using addAll approach is that it is slow not that it is inconvenient.  We know that we can fix performance addAll.

Both this ticket and the duplicate ticket are really focused on performance but actively sell the reader on change the API.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/17045#issuecomment-1872379255