🚀 go-pugleaf

It seems I've found a bug in the LEDA priority queue (p_queue).

The problem is with the copy constructor when multiple elements with
the same priority exist.  In this case, the replicated version has
elements with that same priority in the reverse order of the original.
The LEDA manual makes no mention that priority queues should only have
one instance of a priority per queue (unlike for sorted sequences), so
I assume this is legal.  

Here's some sample code.

// Paul LeMahieu
//
// pqueuebug.cc

#include <LEDA/p_queue.h>
#include <iostream.h>

// print out queue by popping min elements from a copy
void print_val(p_queue<int,int> pq)
{
   pq_item it;
   while(!pq.empty()) {
      it = pq.find_min();
      cout << pq.prio(it) << ", " << pq.inf(it) << endl;
      pq.del_item(it);
   }
}

// _identical_ to print_val but pass by reference
void print_ref(p_queue<int,int>& pq)
{
   pq_item it;
   while(!pq.empty()) {
      it = pq.find_min();
      cout << pq.prio(it) << ", " << pq.inf(it) << endl;
      pq.del_item(it);
   }
}

main(void)
{
   p_queue<int,int> pq;

   pq.insert(1,3);
   pq.insert(1,2);
   pq.insert(1,1);

   print_val(pq);
   cout << endl;
   print_ref(pq);
}

This gives the following results:

1, 1
1, 2
1, 3

1, 3
1, 2
1, 1

Note that the copied version gets the elements popped off in
reverse order from the original.


-- Paul LeMahieu
   lemahieu@paradise.caltech.edu