Complete.Org: Mailing Lists: Archives: freeciv-dev: March 2002: [Freeciv-Dev] Re: Priority queue for Dijkstra

# [Freeciv-Dev] Re: Priority queue for Dijkstra

[Top] [All Lists]

 To: jdorje@xxxxxxxxxxxx Cc: freeciv-dev@xxxxxxxxxxx Subject: [Freeciv-Dev] Re: Priority queue for Dijkstra From: Gregory Berkolaiko Date: Sat, 16 Mar 2002 18:23:08 +0000 (GMT)

```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
> >   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

> 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

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.

```