Has anyone written a relatively efficient array-based priority queue?
(preferably with dynamic bounds)

I could probably cook something up myself, if I had to, but if anyone has one
that I could use, I'd be grateful.

That said, a P-Queue structure might make a nice addition to the SDL...

A.D.B.

Post a reply to this message

Anthony D. Baye <Sha### [at] spamnomorehotmailcom> wrote:
> Has anyone written a relatively efficient array-based priority queue?

  AFAIK a heap is usually used for priority queues because it can be
implemented inside an array (with no ancillary data whatsoever necessary),
insertion is an O(log n) operation, and getting the highest-priority element
is constant-time (removing it from the heap is O(log n)).

http://en.wikipedia.org/wiki/Heap_(data_structure)

-- 
                                                          - Warp

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> Anthony D. Baye <Sha### [at] spamnomorehotmailcom> wrote:
> > Has anyone written a relatively efficient array-based priority queue?
>
>   AFAIK a heap is usually used for priority queues because it can be
> implemented inside an array (with no ancillary data whatsoever necessary),
> insertion is an O(log n) operation, and getting the highest-priority element
> is constant-time (removing it from the heap is O(log n)).
>
> http://en.wikipedia.org/wiki/Heap_(data_structure)
>
> --
>                                                           - Warp

I meant in the POV SDL.

I'm working on something that would be best accomplished using a Priority queue,
and I didn't want to have to write my own.

But, as I said, I probably could if I had to.

A.D.B.

Post a reply to this message

I was, perhaps, unclear as to what I am looking for.  All I need is a
First-in-First-out structure.  A plain old queue which, preferably, grows and
shrinks with need.

I apologize for the confusion.

A.D.B.

"Anthony D. Baye" <Sha### [at] spamnomorehotmailcom> wrote:
> Warp <war### [at] tagpovrayorg> wrote:
> > Anthony D. Baye <Sha### [at] spamnomorehotmailcom> wrote:
> > > Has anyone written a relatively efficient array-based priority queue?
> >
> >   AFAIK a heap is usually used for priority queues because it can be
> > implemented inside an array (with no ancillary data whatsoever necessary),
> > insertion is an O(log n) operation, and getting the highest-priority element
> > is constant-time (removing it from the heap is O(log n)).
> >
> > http://en.wikipedia.org/wiki/Heap_(data_structure)
> >
> > --
> >                                                           - Warp
>
> I meant in the POV SDL.
>
> I'm working on something that would be best accomplished using a Priority queue,
> and I didn't want to have to write my own.
>
> But, as I said, I probably could if I had to.
>
> A.D.B.

Post a reply to this message

Le 16/07/2009 06:18, Anthony D. Baye nous fit lire :
> I was, perhaps, unclear as to what I am looking for.  All I need is a
> First-in-First-out structure.  A plain old queue which, preferably, grows and
> shrinks with need.
> 
> I apologize for the confusion.
> 
> A.D.B.

As the parser of the SDL is mono-thread/process, using a producer-consumer approach
seems
a bit of overkill and ineffective.
Have you looked at the spline & arrays ?
For arrays, dimensions & dimension_size might be handy in closed macros.

Now, I cannot really see a reason to need a FIFO structure in SDL, short of a somehow
deficient coding at the conception level: reexamine it! (or provide actual code that
cannot be rewritten). When you only have a hammer, everything looks like a nail...
programmer with single coding scheme must learn new tools and adapt to the language.

At worst, you could use a simple strings as a holder for linearized data (and
implement a
partial parser for your linearized data...), removing parsed parts with
string-operations.

As a side note, it seems that a min & max index of spline functions is missing so far.
(to know the minimal/maximal index usable with a spline, for instance). Might be a
handy
addition to the SDL. (Or did I missed the right page in doc ?)

> 
> "Anthony D. Baye" <Sha### [at] spamnomorehotmailcom> wrote:
>> Warp <war### [at] tagpovrayorg> wrote:
>>> Anthony D. Baye <Sha### [at] spamnomorehotmailcom> wrote:
>>>> Has anyone written a relatively efficient array-based priority queue?
>>>   AFAIK a heap is usually used for priority queues because it can be
>>> implemented inside an array (with no ancillary data whatsoever necessary),
>>> insertion is an O(log n) operation, and getting the highest-priority element
>>> is constant-time (removing it from the heap is O(log n)).
>>>
>>> http://en.wikipedia.org/wiki/Heap_(data_structure)
>>>
>>> --
>>>                                                           - Warp
>> I meant in the POV SDL.
>>
>> I'm working on something that would be best accomplished using a Priority queue,
>> and I didn't want to have to write my own.
>>
>> But, as I said, I probably could if I had to.
>>
>> A.D.B.
> 
> 
> 
>

Post a reply to this message

"Anthony D. Baye" <Sha### [at] spamnomorehotmailcom> wrote:
> I was, perhaps, unclear as to what I am looking for.  All I need is a
> First-in-First-out structure.  A plain old queue which, preferably, grows and
> shrinks with need.

If you can identify an upper limit for the size, a circular buffer would
probably be the easiest to implement, e.g.:

  #declare MAX_FIFO_SIZE 1000;
  #declare MyFifo       = array[MAX_FIFO_SIZE];
  #declare MyFifoInPos  = 0;
  #declare MyFifoOutPos = 0;
  #declare MyFifoSize   = 0;

  // push
  #if( MyFifoSize >= MAX_FIFO_SIZE )
    // overrun
  #else
    #declare MyFifo[MyFifoInPos] = Whatever;
    #declare MyFifoInPos = mod( MyFifoInPos + 1, MAX_FIFO_SIZE );
    #declare MyFifoSize = MyFifoSize + 1;
  #end

  // pull
  #if( MyFifoSize <= 0 )
    // underrun
  #else
    #declare Whatever = MyFifo[MyFifoOutPos];
    #declare MyFifoOutPos = mod( MyFifoOutPos + 1, MAX_FIFO_SIZE );
    #declare MyFifoSize = MyFifoSize - 1;
  #end

Note that you can handle overrun by resizing the array (by allocating a new one
and copying the data); in this case, being able to specify an absolute maximum
size beforehand is not required.

(You can get away without MyFifoSize, computing the size from MyFifoInPos and
MyFifoOutPos, but then the buffer can effectively hold at most MAX_FIFO_SIZE-1
elements.)

Post a reply to this message

Anthony D. Baye <Sha### [at] spamnomorehotmailcom> wrote:
> Warp <war### [at] tagpovrayorg> wrote:
> > Anthony D. Baye <Sha### [at] spamnomorehotmailcom> wrote:
> > > Has anyone written a relatively efficient array-based priority queue?
> >
> >   AFAIK a heap is usually used for priority queues because it can be
> > implemented inside an array (with no ancillary data whatsoever necessary),
> > insertion is an O(log n) operation, and getting the highest-priority element
> > is constant-time (removing it from the heap is O(log n)).
> >
> > http://en.wikipedia.org/wiki/Heap_(data_structure)

> I meant in the POV SDL.

  I implied nothing else. I just pointed out which data structure would be
the best for that task.

-- 
                                                          - Warp

Post a reply to this message

Anthony D. Baye <Sha### [at] spamnomorehotmailcom> wrote:
> I was, perhaps, unclear as to what I am looking for.  All I need is a
> First-in-First-out structure.  A plain old queue which, preferably, grows and
> shrinks with need.

  You talked about a *priority* queue in your original post, which is a
rather different thing than a plain queue...

-- 
                                                          - Warp

Post a reply to this message