Boost logo

Boost :

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

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


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

Boost list run by bdawes at, gregod at, cpdaniel at, john at