[boost] Re: ring_buffer, vector_indexing_suite

From: David Abrahams (dave_at_[hidden])
Date: 2004-04-13 07:57:30

"Neal D. Becker" <ndbecker2_at_[hidden]> writes:

> David Abrahams wrote:
>
> [...]
>> Whoa there.  A circular buffer must always have one invalid element.
>> Reaching a->b->a with positive increments should be impossible, or you
>> have a bug in your implementation.  At least, that was true the last
>> time I thought about it.  Otherwise, how can you tell the difference
>> between empty and full?
>> 
>
> To avoid further confusion, I will refer to this as ring_buffer. 
> Conceptually, a ring_buffer is nothing more than a linear contiguous array. 
> Given an index "offset", the index into the actual array is computed as 
>
> j = (offset + start) % size
>
> The virtual "start" which corresponds to index of 0 is not fixed.
>
> This is an extremely useful data structure for signal processing and
> communication application.  A typical use is to provide a history of the
> previous n samples of a signal.
>
> The user of this data structure can choose whether to write samples into
> positive indexes (which might represent future samples), and read from
> positive indexes near 0, or to write to indexes near 0 and read past
> samples as negative indexes.  The latter convention is actually better for
> multirate signal processing.  Thus, sample [0] is current time, sample[-1]
> is the previous...

Why not just use an index offset if you want valid elements on both
sides of zero?  I guess in a ring buffer you only update one pointer
when the ring advances, as opposed to 2 in a traditional circular
buffer.

> A simple implementation is to use an stl::vector.  For a ring_buffer of size
> N, we allocate an stl::vector of size N+1.
>
> To answer your question, there is no concept of empty or full.  The
> ring_buffer always contains N items.

Uh, OK.  I'm not sure that iterators fit into that world.

> Now I have a question.  I am trying to use
> boost::python::vector_indexing_suite with this data structure.  I
> believe all I need to do is overload convert_index.  According to
> the documentation, vector_indexing_suite is designed specifically to
> allow this, but I can't seem to figure out how to do it.  This code
> compiles, but my_indexing_suite::convert_index is not called:

<snip>

This stuff is Joel's department.  Joel?

BTW Joel, there appear to be a whole bunch of extraneous newlines in
the code examples on the indexing suite reference page.

-- 
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com