New methods in PriorityQueue

[Julian Waters]

Hi Stuart and Roger, thanks for your patience,

Attached below is the response from the author:

@TheShermanTanker Cool. Thank you very much for relaying the messages from
the list here!

All right, I understand the concerns. My first thought about how to address
them would be a functional API. Something like this:

    /**
     * Applies the re-prioritization function {@code mutator}
     * to the item x and relocates it to its proper place in the queue.
     *
     * If the item's priority is raised by the {@code mutator},
     * it will potentially be moved closer to the start.
     *
     * If the item's priority is lowered by the {@code mutator},
     * it will potentially be moved closer to the end.
     *
     * If the {@code mutator} does not change the item's priority
     * it will not be moved.
     *
     * The call has no effect if the item cannot be found in the queue
     * by referential equality.
     *
     * @param x the item to sift up
     * @param mutator a function to be applied to x to change its priority
     */
    public void rePrioritize(E x, Consumer<E> mutator) { ... }

As it is already documented on the class that it is not thread-save, this
should get past those concerns then, shouldn't it?

If yes, the next thing to do for me, would be to get creative and implement
this in a manner that is equally performant than the original suggestion
(e.g. much faster than remove(), mutate(), add()). I am sure that this
could be done. If an item's priority was an int or long, it would be
trivial. But since items are only comparable, the implementation would be,
well, non-trivial.

But before I start wrecking my brain about the implementation, let me take
a break here and re-focus. As said, I understand the concerns that have
been raised against the initial suggestion (e.g. this PR). And even though
an attempt at finding a working solution has not been discouraged so far,
at the moment I don't a big enough upside of having these methods available
in the API as well, that would justify the investment for me. When making
this PR, my motivation was also (1.) that I was curious about the reasons
why they are missing and (2.) about the JDK PR process in general. And this
curiosity has been satisfied.

   1.

   I was not really aware about the requirements of the API user to
   maintain the "invariants of the PriorityQueue" while using it. (Btw. I have
   not found any explicitly documentation of the concept of "[collection]
   invariants" or "[t]he general rule for collections that use [...]
   comparison methods" on the class or the add() method. Does anybody think it
   would make sense to fix that or did I just not see it, maybe elsewhere?)
   2.

   I am convinced that the PR approval process works well and and will
   recommend anyone that has a real / legitimate need to have a change merged,
   to have the discussion.

Thank you very much to Roger and Stuart as well as to @TheShermanTanker!


best regards,

Julian

On Fri, Mar 4, 2022 at 3:08 PM Julian Waters <tanksherman27 at gmail.com>
wrote:

> Hi all,
>
> I apologize for the confusion, it seems like something went awry on my end
> with the mailing lists, since there are apparently now 2 copies of the same
> thread with different names. I guess I'll just go with this one, since the
> technical discussion is going on here.
>
> To clarify, I wasn't the one who created the PR, I'll relay the feedback
> to the author since I'm not really in the position to give any feedback
> myself, given my inexperience with this area of the JDK.
>
> Thank you Stuart and Roger for the replies, have a great day! :)
>
> best regards,
> Julian
>
>
>
> On Fri, Mar 4, 2022 at 1:37 PM Stuart Marks <stuart.marks at oracle.com>
> wrote:
>
>> I agree with Roger. Let me amplify this.
>>
>> The general rule for collections that use hashes and comparison methods
>> (such as
>> HashMap and TreeMap, as well as PriorityQueue) is that one mustn't mutate
>> any
>> element that resides in such a collection in any way that changes the
>> results of
>> hashCode, equals, or the comparison method. It's a bad precedent to add
>> APIs that
>> seem to support such mutation. As Roger said, the supported way of doing
>> this is to
>> remove, mutate, and then reinsert.
>>
>> It seems like it might be safe to mutate an element, only temporarily
>> violating the
>> PQ's invariants until the mutated element is sifted into the correct
>> position.
>> However, even a "temporary" violation is exceedingly dangerous. If some
>> other
>> modification is made to the PQ while it's in this state, it could end up
>> permanently
>> corrupting the PQ.
>>
>> Managing such a situation would need to be handled exceedingly carefully.
>> As such,
>> this seems like a highly specialized use case, thus the proposal isn't
>> suitable as a
>> general-purpose API.
>>
>> s'marks
>>
>>
>> On 3/3/22 10:18 AM, Roger Riggs wrote:
>> > Hi Julian,
>> >
>> > Modifying the priorities of elements in the PriorityQueue violates the
>> > invariants of the PriorityQueue established at insertion and maintained
>> > at removal by the Comparator.
>> >
>> > To maintain the invariant the element should be removed, its priority
>> modified,
>> > and re-inserted.
>> >
>> > An API to manually manipulate the order is inconsistent with the design
>> of
>> > PriorityQueue.
>> >
>> > Regards, Roger
>> >
>> >
>> > On 3/3/22 6:59 AM, 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
>> >>
>> >> best regards,
>> >> Julian Waters
>> >
>>
>