"Neal D. Becker" <ndbecker2@verizon.net> 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