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

Valeh Hajiyev duke at openjdk.org
Thu Dec 28 00:29:40 UTC 2023


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  it's true that leveraging the `addAll` method could solve this issue, but I'd like to emphasize the consistency in the API design. 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. 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?

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

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


More information about the core-libs-dev mailing list