From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=0.6 required=5.0 tests=BAYES_05,INVALID_DATE
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,3dcbc816db6189a8
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 1994-11-08 20:48:45 PST
Path: 
 nntp.gmd.de!xlink.net!howland.reston.ans.net!pipex!uunet!news.uiowa.edu!news
From: jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H
 MLH,3193350740,3193382879)
Newsgroups: comp.lang.ada
Subject: Re: priority queues?????????
Date: 9 Nov 1994 03:23:23 GMT
Organization: University of Iowa, Iowa City, IA, USA
Distribution: world
Message-ID: <39pfbb$456@nexus.uiowa.edu>
References: <39ok0c$60p@columbia.acc.brad.ac.uk>
NNTP-Posting-Host: pyrite.cs.uiowa.edu
Date: 1994-11-09T03:23:23+00:00
List-Id: <comp.lang.ada>

>From article <39ok0c$60p@columbia.acc.brad.ac.uk>,
by J.Coates@bradford.ac.uk (JC):
> 
> can anybody mail me a fully working and documented ada priority queue ..

What you want is available from the following FTP and WWW servers:

	ftp://ftp.cs.uiowa.edu/pub/jones
	www://www.cs.uiowa.edu/~jones/index.html

Look under simulation support tools, then under event set implementations,
and you'll find a splay-tree implementation of the pending event set.
The pending event set, as used in discrete event simulation, is exactly
a priority queue.  The particular implementation provided has O(log n)
expected time for enqueue and dequeue, assuming randomly distributed
priorities.  It gets better if they aren't random.

The same code is in the STARS library.  Either nobody uses the stuff,
or there really aren't any bugs in it.  I've been using it for years.
Cross your fingers.  If you really can't FTP it, I can mail it.

				Doug Jones
				jones@cs.uiowa.edu