Done.

Apart from my small comment, this looks good :-)

Thanks for the explanation. I added evaluating changing to a single queue (maybe
using a global-to-merge-and-shrink function-like class to compute distances
given a transition system) to my agenda.

For this issue, I think removing the debug output as a default is a good solution.

Can I merge this?
(https://bitbucket.org/SilvanS/fd-dev/pull-requests/28/issue737/diff)

If I have to guess, it is probably good for performance to (re-) use a single
queue. The conversion from bucket-based to heap-based comes at a cost, and also
for both queue types in general they have reallocation overheads that can be
amortized better if they are reused multiple times over a longer period. So
trying to reuse the same queue where possible is often a good idea. For example,
in heuristics like h^FF I think we got a substantial speed boost when we started
reusing the priority queue between different heuristic evaluations, even though
the queue is empty in between and in terms of code readability, making the queue
local to each heuristic evaluation would be cleaner.

Regarding Silvan's question in msg6544, I *think* that typically most of the
queues in the same planning task will end up behaving the same way, so only
having to decide once that bucket-based ones are a bad idea could be good for
performance. But it's hard to be sure without measuring.


Having said all that, I think that code clarity very likely suffers a lot in
cases like Silvan describes if we start reusing these queues because the callers
of the code suddently have to start worrying about an implementation detail. And
it's also a legitimate wish not to have the queue be as chatty as it currently
is. I'd be fine with disabling the output from AdaptiveQueue by default and
adding a compile-time debug flag (usually set to false) that enables the current
output.

Fancier solutions are possible, but probably fall under YAGNI.

I understand. I just wanted to offer two alternatives, one of which proved 
beneficial in my code. In your case they might be difficult to apply (but you 
could pass a queue object to your new instances in principle).

What does this have to do with the discussion? :-)

If I use an AdaptiveQueue, I expect it to behave as a bucket-based queue until
it decides to switch. Reusing an already used queue doesn't serve this purpose.

In my scenario, I create lots of instances of a class that uses an
AdaptiveQueue; hence even if I were willing to reuse it, I couldn't do so.

I'm assuming that each user of the queue needs the same kind of queue.

Does this make sense? Doesn't this mean that after the first switch to
heap-based queue, this queue stays a heap-based queue for ever? This is not the
behavior you have if you use a new queue that starts out bucket-based. Or do you
reset your queue?

Probably.

In the CEGAR code, I reuse a single queue to avoid the switches you mention and 
to reduce the number of memory allocations.

That defeats the purpose of having an AdaptiveQueue, doesn't it?

Maybe you could analyze the cost values beforehand and choose the Queue class 
accordingly?

If using many AdaptiveQueue objects, they can produce lots of output of the form:

Switch from bucket-based to heap-based queue at key = x, num_pushes = y

I'd like to either remove that output entirely or at least have an option to
silence it. (The to-be-merged score-based MIASM merge strategy, see issue668,
computes lots of temporary merge-and-shrink Distances objects that use
AdapativeQueues. On tasks with large cost values, this can lead to log files of
many tens of megabytes.)