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

[jmehrens]

On Tue, 19 Dec 2023 21:17:02 GMT, Valeh Hajiyev <duke at openjdk.org> wrote:

>> This commit addresses the current limitation in the `PriorityQueue` implementation, which lacks a constructor to efficiently create a priority queue with a custom comparator and an existing collection. In order to create such a queue, we currently need to initialize a new queue with custom comparator, and after that populate the queue using `addAll()` method, which in the background calls `add()` method (which takes `O(logn)` time) for each element of the collection (`n` times).  This is resulting in an overall time complexity of `O(nlogn)`. 
>> 
>> 
>> PriorityQueue<String> pq = new PriorityQueue<>(customComparator);
>> pq.addAll(existingCollection);
>> 
>> 
>> The pull request introduces a new constructor to streamline this process and reduce the time complexity to `O(n)`.  If you create the queue above using the new constructor, the contents of the collection will be copied (which takes `O(n)` time) and then later  `heapify()` operation (Floyd's algorithm) will be called once (another `O(n)` time). Overall the operation will be reduced from `O(nlogn)` to `O(2n)` -> `O(n)` time.
>> 
>> 
>> PriorityQueue<String> pq = new PriorityQueue<>(existingCollection, customComparator);
>
> 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.

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

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