Re: [boost] [Container] Priority Deque - Refinement

Subject: Re: [boost] [Container] Priority Deque - Refinement
From: Nathaniel McClatchey (njmcclatchey1990_at_[hidden])
Date: 2013-11-24 12:16:41

Stabilizing a priority deque is not as simple as stabilizing a priority
queue.
The priority queue can be stabilized by appending to each element of the
heap an integer "tie breaker" such that each new element's tie breaker is
greater than that of any previous element. Problems with overflow can be
dealt with (in O(n) time) by adjusting all tie breakers simultaneously and
reconstructing the heap.
The same method will work for priority deques, but with one important
difference: if the maximum element is stable (FIFO), the minimum element
would have the reverse order (LIFO). Correcting this is likely to require
searching through all elements indistinguishable from the minimum, which is
potentially linear rather than logarithmic.

Personally, I would prefer to create the stabilized priority deque (with
notes about the behavior) as a thin wrapper around the unstable deque. This
is primarily because the stabilized deque may not be able to offer the same
options as the unstable deque (such as choice of underlying container).

>I assume that you're referring to begin_mutable,
>end_mutable, and make_valid?

I was thinking of begin, end, set, and erase actually.
Exposing (as protected member functions) the ability to make large-scale
changes to the deque has immediately apparent advantages. In particular, it
would allow a (mostly) stabilized heap to operate in amortized O(log n)
time, O(n) worst case.
Editing or removing a single element is highly situational, especially when
the iterators used to find that element must be discarded immediately
afterward.

>Please consider (and document) the exception
>safety guarantees that you provide.  From a
>brief glance at the code, I suspect that
>merge and push, at least can leave an invalid
>heap if they throw.

Good point. I hadn't considered exception-safety until you suggested it.
If movement and comparison do not throw, I believe I will be able to offer
as strong a guarantee as offered by the operations on the underlying
container.
If they can throw, I can offer the basic guarantee, but only because an
empty heap is a vacuously valid heap.

I'll keep working to try to improve these.

>You're going to need a lot more tests.  In
>particular, you need to check that pushing
>and popping values gives the correct results,
>not just that the priority_deque's invariants
>hold.

You are correct. I do need more tests. My original plan was to wait to
create unit tests until the revision stage was done, because testing
preservation of invariants is more sensitive to failures than most other
tests, but I can see your point (need to make sure that the elements added
are actually in the deque, and that the popped elements are indeed removed
from it).

>What I'd actually
>prefer to see is for this to be implemented as
>algorithms akin to std::push_heap and std::pop_heap.
>That way priority_deque is just a thin wrapper

>If your implementation would have std::make_heap/etc functions (which are
desirable on their own, as Steven mentioned) then it is even >possible to
have two interfaces: Boost.Heap-like and std::priority_queue-like.

> I think it is worth to consider to make it part of Boost.Heap library (
> http://www.boost.org/doc/libs/1_55_0/doc/html/heap.html ).

I had considered this possibility previously, but I thought the interfaces
of the private functions were too complicated to expose to an average user.
There are also some concerns over whether an average user would find my
internal design choices to be intuitive. For example, I realized early on
that either the minimum or maximum would have a slight performance
advantage over the other, depending on how I constructed my intervals.
Because the priority deque is so similar to the priority queue, I decided
to give the advantage to the maximum; this has resulted in intervals of the
form [max, min], rather than the intuitive [min, max]. It would not be
difficult to change this, but it is still something to consider.

Nevertheless, this is worth revisiting. I will consider ways to simplify,
separate, and make intuitive the interval-heap functions.

>* mutability

I would appreciate a clarification of what was meant. I included functions
for traversing the deque, editing individual elements, and editing large
numbers of elements, so I must assume that my intuitive definition of the
meaning of "mutability" differs from yours.