Provide a "real" priority queue abstraction?

[fingolfin]

A "real" priority queue might have a Push method like this:

  function(prioqueue, priority, obj)
     Push(prioqueue!.heap, [priority, obj]);
  end;

where prioqueue!.heap is a heap with less-function is {x,y} -> x[1] < y[1].
The Pop method then would basically do

 function(prioqueue)
   local x;
   x:= Pop(prioqueue!.heap);
   if x = fail then return fail; fi;
   return x[2];
 end;

The constructor could optionally take a custom comparison function, I guess, and also optionally a heap constructor (if none given, default to e.g. binary heap)

[stevelinton]

If you require that the objects in the queue support < or promise never to push two objects with the same priority then the underlying heap actually has default isLess which is nice for performance.

[fingolfin]

@stevelinton Good point. Of course in that case, there is almost no reason left to not use a heap directly ;-). But some people will appreciate the extra sugar coating.

BTW, of course we could also add another special case to the heap implementations, to recognize {x,y} -> x[1] < y[1] (or rather: we'd define a function doing that, perhaps on the C-level, and add a special case for when that function is used).

[stevelinton]

If we did that we should probably do the same thing in Position so that PositionFirstComponent could eventually go.