Exposing MinMaxPriorityQueue#maxSize

[JensRantil]

Background: I need a (synchronized) MinMaxPriorityQueue that adheres to the BlockingQueue interface. To do this, I am implementing a simple wrapper around a MinMaxPriorityQueue instance. Current working name for my class is CappedPriorityBlockingQueue and it takes a MinMaxPriorityQueue in its constructor to make it easier for external parties to construct the proper MinMaxPriorityQueue.

Problem: BlockingQueue contains the remainingCapacity method and it feels like it should reasonably return maxSize - size for the wrapped MinMaxPriorityQueue. This can't be done, since MinMaxPriorityQueue#maxSize isn't exposed.

Proposed solution: Expose the capacity of MinMaxPriorityQueue as a getter.

Workaround: I've created a CappedPriorityBlockingQueue.Builder that is essentially the same as MinMaxPriorityQueue.Builder except that it catches the maxSize and stores it in my CappedPriorityBlockingQueue. Annoyingly one cannot simply instanciate a MinMaxPriorityQueue.Builder using the common MinMaxPriorityQueue#builder construct. This means I need to handle all the three variants of creating a MinMaxPriorityQueue.Builder in my builder. See #2119.

[lowasser]

MinMaxPriorityQueue is not intended to be used as a simple size-capped priority queue. It should only be used for when you need efficient access to both the minimum and the maximum element.

[lowasser]

Is it possible you could wrap a basic PriorityQueue instead? That would be more efficient for the problem it sounds like you are trying to solve.

[JensRantil]

@lowasser Well, the problem is that a PriorityQueue is implemented using a heap, which can't poll the least prioritized element. MinMaxPriorityQueue can do this (efficiently, too). My other alternative is to wrap a TreeMap, but I suspect MinMaxPriorityQueue will be more efficiently implemented in terms of memory allocations if nothing else.

[kevinb9n]

On Thu, Jul 30, 2015 at 1:55 AM, Jens Rantil notifications@github.com
wrote:

@lowasser https://github.com/lowasser Well, the problem is that a
PriorityQueue is implemented using a heap, which can't poll the least
prioritized element.

Louis's point is that, actually, it can -- if you have no need to poll
the most prioritized element. You just reverse the comparator. While it
might seem like I'm stating the obvious, we have found inside Google that a
very large fraction of MMPQ users had missed this option.

MinMaxPriorityQueue can do this (efficiently, too). My other alternative
is to wrap a TreeMap, but I suspect MinMaxPriorityQueue will be more
efficiently implemented in terms of memory allocations if nothing else.

—
Reply to this email directly or view it on GitHub
#2118 (comment).

Kevin Bourrillion | Java Librarian | Google, Inc. | kevinb@google.com

[JensRantil]

@kevinb9n I see. Yeah, sadly in my case I do need to poll the most prioritized element. Maybe I didn't make that clear enough.

[kevinb9n]

In general though, I should just paste what we said on the other bug:

The big problem with MMPQ is that it's very rarely used and most of the time when it is used, a
careful reading of the Javadoc would have told the user something better. It's an extremely niche
utility, and we're unlikely to spend time improving it futher - sorry.