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  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 http://www.boost-consulting.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk