##
Fast Bucket-based Queues

Although you could grab any priority queue implementation

from a general algorithms book or standard library, that

would be overkill (and slow!) for what you need in a

ROAM implementation (typically requiring walking and

modifying log(N) branches of some kind of tree, where

N is the number of items queued). Instead you can

*approximately* sort the triangles using (e.g. 2048)

buckets, hence the iq index. Each bucket contains

an otherwise unsorted, doubly-linked list of triangles

with the same iq index. Insert adds to the head of the

bucket, delete just adjusts links to the triangle before

and after in the bucket list. Both these take a tiny

amount of time. What's left is maintaining the index

iqmax (or iqmin for the merge queue) of the highest-index

non-empty bucket. When an insert occurs, if iq>iqmax

then set iqmax=iq. For deletes, if the bucket becomes

empty and iq==iqmax, then scan iq-1, iq-2 etc until the

first non-empty bucket, which becomes the new iqmax.

This may *occasionally* take dozens of steps, but these

steps are extremely fast and, more important, there are

only a tiny number of them *on average*. Try it and

instrument your code to get some stats--I think you'll be

pleased.

##
Contact Information

Mark A. Duchaineau
-- duchaineau1@llnl.gov

Updated Dec 22, 1999