[boost] ring_buffer, vector_indexing_suite

From: Neal D. Becker (ndbecker2_at_[hidden])
Date: 2004-04-13 06:18:51

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

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.

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:

#include <boost/python/module.hpp>
#include <boost/python/def.hpp>
#include <boost/python/class.hpp>
#include <boost/python/init.hpp>
#include <boost/python/suite/indexing/vector_indexing_suite.hpp>
#include "RingBuffer.H"

using namespace boost::python;

template<class Container>
struct my_indexing_suite : public vector_indexing_suite<Container> {
  typedef typename vector_indexing_suite<Container>::index_type index_type;

   static index_type
   convert_index(Container& container, PyObject* i_) {
     throw ("help");
   }
};

BOOST_PYTHON_MODULE(Ring_wrap)
{
  class_<RingBuffer<int> >("RI")
    .def(init<size_t>())
    .def(init<const RingBuffer<int>&>())
    .def (my_indexing_suite<RingBuffer<int> >())
    .def ("Shift", &RingBuffer<int>::Shift)
    ;
}

Here is a (rather trivial) RingBuffer.H:
// arch-tag: RingBuffer.H

#ifndef _RingBuffer_H
#define _RingBuffer_H

//! \version $Id: RingBuffer.H,v 1.3 2003/12/10 15:49:53 nbecker Exp $

//#include <math.h>
//#include <iostream>
#include <cstddef>              // size_t, etc.
#include <iterator>
#include <vector>
#include <iosfwd>
#include <stdexcept>

/*! A Ring buffer.  size is the allocated size, which is the size of
  the history you can read.
*/
template<class Cont>
class RingBufferIter;

template <class T>
class RingBuffer {
public:

  typedef T value_type;
  typedef RingBufferIter<T> iterator;
  typedef const iterator const_iterator;
  typedef typename std::vector<value_type>::size_type size_type;
  typedef typename std::vector<value_type>::difference_type difference_type;

  struct NotImplemented : public std::runtime_error {
    NotImplemented (const std::string& arg) :
      std::runtime_error (arg) {}
  };
    
private:

  size_t size_;
  size_t allocated;
  int position;
  std::vector<value_type> array;
  
  int index (int offset) const {
    int x = (offset + position) % int(allocated);
    if (x >= 0)
      return x;
    else
      return x + allocated;
  }
      
public:

  RingBuffer() {}

  RingBuffer (size_t _size, size_t _alloc=0) :
    size_ (_size),
    allocated (_alloc ? _alloc : _size+1),
    position (0),
    array (_alloc ? _alloc : _size+1)
  {
    Clear();
  }

  template<typename in_t>
  RingBuffer (in_t in, in_t inend) :
    size_ (inend - in),
    allocated (inend - in + 1),
    position (0),
    array (inend - in + 1) {
    std::copy (in, inend, array.begin());
  }

  void Shift (int offset = 1) {
    position = (position + offset) % int (allocated); // prevent integer
overflow
  }

  void Set (int offset = 0) {
    position = offset;
  }

    
  void Clear (T x = T()) {
    for (size_t i = 0; i < allocated; i++)
      array[i] = x;
  }

  size_t Size() const {
    return size_;
  }

  size_t size() const {
    return size_;
  }

  void resize (size_t _size, size_t _alloc=0) {
    array.resize (_alloc ? _alloc : _size+1);
    size_ = _size;
    allocated = _alloc ? _alloc : _size+1;
  }

  //! Why is iterator initialized with offset=0?  Because the offset
  //! will be added back in when the iterator is dereferenced.
  iterator begin() { return iterator (*this, 0); }

  const_iterator begin() const { return iterator (*this, 0); }

  iterator end() { return iterator (*this, Size()); }

  const_iterator end() const { return iterator (*this, Size()); }

  T& operator [] (int offset) {
    return array[index (offset)];
  }

  const T& operator [] (int offset) const {
    return array[index (offset)];
  }

  int Position() const { return position; }

  size_t Allocated() const { return allocated; }

  void erase (iterator i) {
    throw NotImplemented ("erase");
  }

  void erase (iterator i, iterator j) {
    throw NotImplemented ("erase");
  }

  void insert (iterator, value_type) {
    throw NotImplemented ("insert");
  }

  template<typename in_t>
  void insert (iterator, in_t, in_t) {
    throw NotImplemented ("insert");
  }

  void push_back (value_type) {
    throw NotImplemented ("push_back");
  }

};

template<class T>
class RingBufferIter  {
public:
  typedef std::random_access_iterator_tag iterator_category;
  typedef RingBufferIter self;
  typedef T value_type;
  typedef T& reference;
  typedef T* pointer;
  typedef ptrdiff_t difference_type;
  typedef size_t size_type;

private:
  RingBuffer<T>& RB;
  size_t offset;

public:
  reference operator*() const { return RB[offset]; }

  // Is this correct?
  pointer operator->() const { return &(operator*()); }

  RingBufferIter (RingBuffer<T>& _RB, size_t _offset) :
    RB (_RB),
    offset (_offset)
    {}

  self& operator++ () {
    offset++;
    return *this;
  }

  self operator++ (int) {
    self tmp = *this;
    ++*this;
    return tmp;
  }

  self& operator-- () {
    offset--;
    return *this;
  }

  self operator-- (int) {
    self tmp = *this;
    --*this;
    return tmp;
  }

  self& operator+=(difference_type n) {
    offset += n;
    return *this;
  }

  self& operator-=(difference_type n) { return *this += -n; }

  self operator+(difference_type n) const {
    self tmp = *this;
    return tmp += n;
  }

  self operator-(difference_type n) const {
    return operator+(-n);
  }

  reference operator[](difference_type n) const { return *(*this + n); }

  bool operator==(const self& x) const { return &(operator*()) ==
&(x.operator*()); }

  bool operator!=(const self& x) const { return !(*this == x); }

  //! We will assume that the offsets don't wrap around.  They only increase
  //! linearly.  The *buffer* wraps around, but the offsets don't.
  //! Note that it only makes sense to compare two positions in the *same*
  //! ring buffer with the same RB.position.
  difference_type operator- (const self& x) const {
      return offset - x.offset;
  }

};

#endif