[Freeciv-Dev] Re: Priority queue for Dijkstra

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Sat, 16 Mar 2002, Jason Short wrote:

> > 
> > Mmm, the one on my computer seems to be broken.  I sort an array, than 
> > apply compare function to few neighbours and it changes sign!
> > Or maybe my head is broken...
> 
> I've gotten this behavior when I make a mistake in writing the 
> comparison function.  If this function returns inconsistent comparisons 
> the resulting sort is garbage.

Mmmm, cannot see what's wrong with the function.
Here it is:

static int list_cmp_function(const void *value1, const void *value2)
{
  const struct refuel *point1 = (const struct refuel *) value1;
  const struct refuel *point2 = (const struct refuel *) value2;

  return (MAX_FLIGHT * (point1->turns - point2->turns) 
          - (point1->moves_left - point2->moves_left));
}

Oh well, anyway I'm not going to use qsort.

> > that's right.
> > it wasn't very right of me to call it "from time to time".
> > the easiest alternative is to run find_minimal function, which is O(n).
> 
> Ouch.  Compared to O(log n), O(n) is awful.

Depends on n, really ;)

> > where is _the_ existing priority queue class?
> > are you talking about 
> >   add_to_mapqueue
> >   get_from_mapqueue
> > routines?  They are just priority-indexed arrays of LILO queues (with a 
> > weird implementation).  This is a solid O(1) solution, unless you have too 
> > many indices.
> 
> Ahh, I see.  So you're saying this "priority queue" will degrade badly 
> as the number of possible priorities increases.  (If you have a limited 

precisely.  I can't really say it will degrade badly though...

> number of keys, you don't need to worry about quicksort.  You can just 
> do a bucket sort, which is O(n), and corresponds with what you describe 
> for add_to_mapqueue/get_from_mapqueue.)

I am not sure where n is coming from.  Each queue is LILO, no sorting 
invloved.  And each new piece of data comes with the number of the queue 
it wants to be put in.

> The solution is to either convert add_to_mapqueue/get_from_mapqueue to 
> be a "real" priority queue, or write a new priority queue, or (best 
> choice) find some library implementation of a priority queue.

Found it.  The next question: where should I declare the new file 
(configure.in or somewhere else) ?

> > In the SINGLE_MOVE sentence I was talking about land move.
> > The idea is that if you make railroads cost 1/10, the number of possible 
> > movecosts will be multiplied by 10 !
> 
> Yes, I see.  And you're saying this is a problem given the current 
> implementation of the priority queue.

Exactly.

G.