C++: An STL-like circular buffer (Part 11)

In this part, we'll get back to some basics. In a brief intermission from iterators, we'll add the complement to front(), back(), which returns a reference to the last item in the buffer. We provide a const and a non-const version:

// In declaration
reference       back();
const_reference back() const;

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::back()
{
assert(m_front);
return *wrap(m_back-1);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::back() const
{
assert(m_front);
return *wrap(m_back-1);
}

To make this work, we need to make wrap cope with pointers that stray below m_buffer:

value_type *wrap(value_type *ptr) const
{
   assert(ptr < m_buffer + m_capacity*2);
   assert(ptr > m_buffer - m_capacity);
   if (ptr >= m_buffer+m_capacity)
       return ptr-m_capacity;
   else if (ptr < m_buffer)
       return ptr+m_capacity;
   else
       return ptr;
}

As ever, I'll add some tests that exercise the code, and reproduce the entire thing below for your cut-n-paste pleasure...

#include <algorithm>
#include <cassert>
#include <stdexcept>

template <typename T, typename A = std::allocator<T> >
class circular_buffer
{
public:
typedef T                                            value_type;
typedef A                                            allocator_type;
typedef typename allocator_type::size_type           size_type;
typedef typename allocator_type::difference_type     difference_type;
typedef typename allocator_type::reference           reference;
typedef typename allocator_type::const_reference     const_reference;
typedef typename allocator_type::pointer             pointer;
typedef typename allocator_type::const_pointer       const_pointer;
class                                                iterator;

explicit circular_buffer(size_type capacity,
                        const allocator_type &a = allocator_type());
~circular_buffer();
allocator_type get_allocator() const;

size_type size() const;
size_type max_size() const;
bool      empty() const;

size_type capacity() const;

reference       front();
const_reference front() const;
reference       back();
const_reference back() const;
reference       operator[](size_type n);
const_reference operator[](size_type n) const;
reference       at(size_type n);
const_reference at(size_type n) const;

iterator begin();
iterator end();

bool push_back(const value_type &);
void pop_front();
void clear();

private:
size_type       m_capacity;
allocator_type  m_allocator;
pointer         m_buffer;
pointer         m_front;
pointer         m_back; // points to next unused item

typedef circular_buffer<T> class_type;

circular_buffer(const class_type &);
class_type &operator=(const class_type &);

value_type *wrap(value_type *ptr) const
{
   assert(ptr < m_buffer + m_capacity*2);
   assert(ptr > m_buffer - m_capacity);
   if (ptr >= m_buffer+m_capacity)
       return ptr-m_capacity;
   else if (ptr < m_buffer)
       return ptr+m_capacity;
   else
       return ptr;
}
};

template <typename T, typename A>
inline
circular_buffer<T,A>::circular_buffer
    (size_type capacity, const allocator_type &allocator)
: m_capacity(capacity),
m_allocator(allocator),
m_buffer(m_allocator.allocate(capacity)),
m_front(0),
m_back(m_buffer)
{
assert(capacity > 0);
}

template <typename T, typename A>
inline
circular_buffer<T,A>::~circular_buffer()
{
clear(); // deallocates all objects
m_allocator.deallocate(m_buffer, m_capacity);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::allocator_type
circular_buffer<T,A>::get_allocator() const
{
return m_allocator;
}


template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::capacity() const
{
return m_capacity;
}

template <typename T, typename A>
inline
bool circular_buffer<T,A>::empty() const
{
return !m_front;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::size() const
{
return !m_front ? 0
               : (m_back > m_front ? m_back : m_back+m_capacity) - m_front;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::max_size() const
{
return m_allocator.max_size();
}

template <typename T, typename A>
inline
bool circular_buffer<T,A>::push_back(const value_type &value)
{
if (m_front && m_front == m_back)
   m_allocator.destroy(m_back);

m_allocator.construct(m_back, value);

value_type *const next = wrap(m_back+1);
if (!m_front)
{
   // first entry in the buffer
   m_front = m_back;
   m_back = next;
   return true;
}
else if (m_front == m_back)
{
   // buffer is full already, throw something away
   m_front = m_back = next;
   return false;
}
else
{
   m_back = next;
   return true;
}
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::front()
{
assert(m_front);
return *m_front;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::front() const
{
assert(m_front);
return *m_front;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::back()
{
assert(m_front);
return *wrap(m_back-1);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::back() const
{
assert(m_front);
return *wrap(m_back-1);
}

template <typename T, typename A>
inline
void circular_buffer<T,A>::pop_front()
{
assert(m_front);

m_allocator.destroy(m_front);
value_type *const next = wrap(m_front+1);
if (next == m_back)
   m_front = 0;
else
   m_front = next;
}

template <typename T, typename A>
inline
void circular_buffer<T,A>::clear()
{
if (m_front)
{
   do
   {
       m_allocator.destroy(m_front);
       m_front = wrap(m_front+1);
   }
   while (m_front != m_back);
}
m_front = 0;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::operator[]
(size_type n)
{
return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::operator[]
(size_type n) const
{
return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::at(size_type n)
{
if (n >= size()) throw std::out_of_range("Parameter out of range");
return (*this)[n];
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::at
    (size_type n) const
{
if (n >= size()) throw std::out_of_range("Parameter out of range");
return (*this)[n];
}

template <typename T, typename A>
class circular_buffer<T,A>::iterator
: public std::iterator<std::random_access_iterator_tag,
                      value_type,
                      size_type,
                      pointer,
                      reference>
{
public:
typedef circular_buffer<T>             parent_type;
typedef typename parent_type::iterator self_type;

iterator(parent_type &parent, size_type index)
   : parent(parent), index(index) {}

self_type &operator++()
{
   ++index;
   return *this;
}
self_type operator++(int) // postincrement
{
   self_type old(*this);
   operator++();
   return old;
}
self_type &operator--()
{
   --index;
   return *this;
}
self_type operator--(int) // postdecrement
{
   self_type old(*this);
   operator--();
   return old;
}

reference operator*() { return parent[index]; }
pointer operator->()  { return &(parent[index]); }

bool operator==(const self_type &other) const
   { return &parent == &other.parent && index == other.index; }
bool operator!=(const self_type &other) const
   { return !(other == *this); }

private:
parent_type &parent;
size_type    index;
};

template <typename T, typename A>
typename circular_buffer<T,A>::iterator circular_buffer<T,A>::begin()
{
return iterator(*this, 0);
}

template <typename T, typename A>
typename circular_buffer<T,A>::iterator circular_buffer<T,A>::end()
{
return iterator(*this, size());
}

namespace tests
{
void pushing_and_popping()
{
   circular_buffer<int> cb(5);

   assert(cb.size() == 0);
   assert(cb.capacity() == 5);
   assert(cb.empty());
   assert(cb.max_size() > 0);

   assert(cb.push_back(1));
   assert(cb.size() == 1);
   assert(cb.capacity() == 5);
   assert(!cb.empty());
   assert(cb.front() == 1);
   assert(cb.back()  == 1);

   assert(cb.push_back(2));
   assert(cb.size() == 2);
   assert(cb.capacity() == 5);
   assert(!cb.empty());
   assert(cb.front() == 1);
   assert(cb.back()  == 2);

   assert(cb.push_back(3));
   assert(cb.push_back(4));
   assert(cb.push_back(5));
   assert(cb.size() == 5);
   assert(cb.capacity() == 5);
   assert(!cb.empty());
   assert(cb.front() == 1);
   assert(cb.back()  == 5);

   assert(!cb.push_back(6));
   assert(cb.size() == 5);
   assert(cb.capacity() == 5);
   assert(!cb.empty());
   assert(cb.front() == 2);
   assert(cb.back()  == 6);

   cb.pop_front();
   assert(cb.size() == 4);
   assert(cb.capacity() == 5);
   assert(!cb.empty());
   assert(cb.front() == 3);
   assert(cb.back()  == 6);

   cb.pop_front();
   assert(cb.size() == 3);
   assert(cb.front() == 4);
   assert(cb.back()  == 6);

   cb.pop_front();
   assert(cb.size() == 2);
   assert(cb.front() == 5);
   assert(cb.back()  == 6);

   cb.pop_front();
   assert(cb.size() == 1);
   assert(cb.front() == 6);
   assert(cb.back()  == 6);

   cb.pop_front();
   assert(cb.size() == 0);
   assert(cb.capacity() == 5);
   assert(cb.empty());

   // empty again

   assert(cb.push_back(7));
   assert(cb.size() == 1);
   assert(cb.capacity() == 5);
   assert(!cb.empty());
   assert(cb.front() == 7);
   assert(cb.back()  == 7);

   assert(cb.push_back(8));
   assert(cb.push_back(9));
   assert(cb.size() == 3);
   assert(!cb.empty());
   assert(cb.front() == 7);
   assert(cb.back()  == 9);

   cb.clear();
   assert(cb.size() == 0);
   assert(cb.capacity() == 5);
   assert(cb.empty());
}

void indexing()
{
   circular_buffer<int> cb(5);

   // A helper - like asssert, but checks for an exception
        #define assert_throws(a,b) \
        {\
            try { a; throw "Failed to throw"; } \
            catch (const b&) { /*OK*/ } \
            catch (...) { throw "Threw wrong thing"; } \
        }

   // We loop round this test several times so our data wraps around the
   // internal m_buffer array a few times.
   for (size_t n = 0; n < 10; ++n)
   {
       assert(cb.empty());

       const circular_buffer<int> &const_cb(cb);

       assert_throws(cb.at(0), std::out_of_range);
       assert_throws(cb.at(1), std::out_of_range);
       assert_throws(const_cb.at(0), std::out_of_range);
       assert_throws(const_cb.at(0), std::out_of_range);
       // we could check that operator[] explodes, but there's little point!

       assert(cb.push_back(0));
       assert(cb.push_back(1));
       assert(cb.push_back(2));
       assert(cb.at(0) == 0); assert(const_cb.at(0) == 0);
       assert(cb.at(1) == 1); assert(const_cb.at(1) == 1);
       assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
       assert(cb[0] == 0);    assert(const_cb[0] == 0);
       assert(cb[1] == 1);    assert(const_cb[1] == 1);
       assert(cb[2] == 2);    assert(const_cb[2] == 2);

       assert(cb.front() == 0);
       cb[0] = 3;
       assert(cb.front() == 3);
       assert(cb.at(0) == 3); assert(const_cb.at(0) == 3);
       assert(cb.at(1) == 1); assert(const_cb.at(1) == 1);
       assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
       assert(cb[0] == 3);    assert(const_cb[0] == 3);
       assert(cb[1] == 1);    assert(const_cb[1] == 1);
       assert(cb[2] == 2);    assert(const_cb[2] == 2);

       cb[1] = 4;
       assert(cb.at(0) == 3); assert(const_cb.at(0) == 3);
       assert(cb.at(1) == 4); assert(const_cb.at(1) == 4);
       assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
       assert(cb[0] == 3);    assert(const_cb[0] == 3);
       assert(cb[1] == 4);    assert(const_cb[1] == 4);
       assert(cb[2] == 2);    assert(const_cb[2] == 2);

       cb.pop_front();
       assert(cb[0] == 4);    assert(const_cb[0] == 4);
       assert(cb[1] == 2);    assert(const_cb[1] == 2);

       cb.pop_front();
       assert(cb[0] == 2);    assert(const_cb[0] == 2);

       cb.pop_front();
   }

}
}

int main()
{
tests::pushing_and_popping();
tests::indexing();
return 0;
}

C++: An STL-like circular buffer (Part 10)

Part 10 already! There's quite a lot of detail involved in writing an STL-like container. Now we're going to delve into some of the more interesting stuff...

I promised you iterators, and so iterators is what you'll get. Like the indexing operations we added in part 8, a circular buffer traditionally doesn't let you iterate through the contents. But where's the fun in that?

Different containers support different classes of iterator:

• An input iterator allows you to read values with forward movement. It can be incremented, compared, and deferenced.
  
• An output iterator also moves forwards, but allows you to write values rather than read them on the way.
  
• A forward iterator effectively combines the input and output iterators, allowing you to read or write values with forward movement.
  
• A bidirectional iterator adds the capability to move backwards; you can increment and decrement them.
  
• A random access iterator allows you to read and write with the ability to do pointer arithmentic and pointer-like comparisons of the iterators.
  
• A reverse iterator is a bidirectional or random iterator that moves through the container in the reverse direction.
  

So what kind of iterator should we support? In our simple container it's perfectly possible to support a random access iterator.

First steps

The container must supply the following nested types: iterator and const_iterator. These can be typedefs or nested class declarations (for example, the most efficient iterator implementation for the std::vector is a typedef of a pointer). However, to start off with, we can simply construct a nested class inside circular_buffer.

Let's start off with the non-const iterator version.

    // In declaration
 class iterator;
 iterator begin();
 iterator end();

Our most implementation is not quite as simple as a pointer, but not much more complex. We need only maintain an index into the buffer and a back-pointer to the parent circular_buffer class. The iterator can be implemented in terms of circular_buffer::operator[].

Like a container, and an allocator, an STL iterator must provide a number of nested type definitions for algorithms to be able to use them appropriately. These include:

• difference_type
  
• value_type
  
• pointer
  
• reference
  
• iterator_category
  

These are picked up by the std::iterator_traits class (see section 24.3.1 of the standard). You needn't follow the mechanics here completely, since the standard library provides a convenient iterator base class, std::iterator, that your iterator implementation can inherit from. This base class will define all the relevant types for you based on the template parameters you give it. The template parameters are:

• the iterator category (these are tag types in the std namespace)
  
• the difference_type
  
• the pointer type
  
• the reference type
  

All of these can be selected from circular_buffer's existing pool of typedefs.

Here's our first stab at an implementation:

template <typename T, typename A>
class circular_buffer<T,A>::iterator
 : public std::iterator<std::random_access_iterator_tag,
                        value_type,
                        size_type,
                        pointer,
                        reference>
{
public:
 typedef circular_buffer<T>             parent_type;
 typedef typename parent_type::iterator self_type;

 iterator(parent_type &parent, size_type index)
     : parent(parent), index(index) {}

 self_type &operator++()
 {
     ++index;
     return *this;
 }
 self_type operator++(int) // postincrement
 {
     self_type old(*this);
     operator++();
     return old;
 }
 self_type &operator--()
 {
     --index;
     return *this;
 }
 self_type operator--(int) // postdecrement
 {
     self_type old(*this);
     operator--();
     return old;
 }

 reference operator*() { return parent[index]; }
 pointer operator->()  { return &(parent[index]); }

 bool operator==(const self_type &other) const
     { return &parent == &other.parent && index == other.index; }
 bool operator!=(const self_type &other) const
     { return !(other == *this); }

private:
 parent_type &parent;
 size_type    index;
};

template <typename T, typename A>
typename circular_buffer<T,A>::iterator circular_buffer<T,A>::begin()
{
 return iterator(*this, 0);
}

template <typename T, typename A>
typename circular_buffer<T,A>::iterator circular_buffer<T,A>::end()
{
 // Remember: end() is one past the last element.
 return iterator(*this, size());
}

This works nicely enough, although we'll refine the design as we add more facilities to the iterator.

Make sure that you understand the difference between preincrement and postincrement and how you overload each operator in a class declaration. Also make sure you know the difference between operator* and operator->.

Implementing reverse iterators

If we want to support reverse iteration, we must provide type definitions for the iterator and const_iterator counterparts: reverse_iterator and const_reverse_iterator.

Helpfully, the C++ standard library provides a useful implementation trick for reverse iteration: std::reverse_iterator. This class wraps a bidirectional/random forward iterator and adapts forward and backward movement to appropriate calls on the underlying forwards iterator.

We can use it like this:

    typedef std::reverse_iterator<iterator> reverse_iterator;
 reverse_iterator rbegin() { return reverse_iterator(end()); }
 reverse_iterator rend()   { return reverse_iterator(begin()); }

When we eventually write a const_iterator, we can also write this:

    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
 const_reverse_iterator rend()   const { return const_reverse_iterator(begin()); }

It's that simple.

The Last Man Standing

You may recall that my company has decided to shut down our Cambridge office and scale back its development operation significantly. Since that announcement I've been busily looking for other gainful employment, and have been pleasantly surprised that the job market is not entirely stagnant. I've had a number interesting leads that I'm still following up.

However, in a dramatic turnaround I have now secured a safe position in my existing organisation, which is a huge weight off my mind. (That doesn't necessarily mean I'll stop looking for other work, but it means I'm secure in the meantime). I am The Last Man Standing.

I was a little disappointed that we didn't have an Apprentice-style face-off for the position, with the CEO saying you're fired to team members in turn. In the end the selection process was little more than a job proposal, some phone calls to the states, and a little negotiation. No pistols at dawn.

This new role is going to be somewhat taxing. Solely responsible for the future of the codebase we've developed, reporting to the US, without the safety net of on-site QA or hardware support, working on my own (in a location yet to be determined). I'm genuinely unsure of how well I'll be able to work on my own; I've never done that before. It's going to be a bumpy ride...

And, I'm not entirely sure how I'm going to structure my development process. Let's be honest, it's hard to do XP in a team of one. Pair programming will be somewhat tricky, and code reviews hard to elicit. I'm going to need to build in something to replace the accountability in our existing development process. All comments and suggestions welcomed...

It's been a great three years working with a team of talented and motivated people, and a real shame to get to the end of the era at this early stage. There was a lot more potential in the team that we hadn't yet exploited.

C++: An STL-like circular buffer (Part 9)

Here's a little extra method we can easily add: back(). In a similar way to std::vector, std::deque, and std::list, the circular_buffer can support a back method, which returns a reference to the item at the end of the container.

Remember, m_back refers to the next unused item, so if we have anything in the buffer, it will be stored in the previous element.

// In declaration
reference       back();
const_reference back() const;

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::back()
{
  assert(m_front);
  return *wrap(m_back-1);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::back() const
{
  assert(m_front);
  return *wrap(m_back-1);
}

C++: An STL-like circular buffer (Part 8)

The circular_buffer is looking in pretty good shape now. We've squashed bugs and introduced an allocator. And, to be fair, we could stop here and have a perfectly usable class.

However, let's add some more methods to the container to learn a bit more about writing STL-like containers. The story can't end here after all, there's been no dramatic climax.

operator[] and at

These two methods aren't strictly required of a circular buffer. Section 23.1.1 of the standard claims these operations are only provided when they take constant time. We can achieve constant time indexing with our class, so let's write them.

    // In declaration
   reference       operator[](size_type n);
   const_reference operator[](size_type n) const;
   reference       at(size_type n);
   const_reference at(size_type n) const;

at() is an index operator that performs bounds checking, throwing a std::out_of_range error if the index is invalid. operator[] itself need perform no bounds checking. Given our wrap() method, the implementations are simple:

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::operator[]
   (size_type n)
{
   return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::operator[]
   (size_type n) const
{
   return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::at(size_type n)
{
   if (n >= size()) throw std::out_of_range("Parameter out of range");
   return (*this)[n];
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::at
    (size_type n) const
{
   if (n >= size()) throw std::out_of_range("Parameter out of range");
   return (*this)[n];
}

We implement at() in terms of operator[]. To use std::out_of_range, you'll need to include <stdexcept>

We should write some more tests for test these new methods. In showing you this, I'll reproduce the entire class so far.

#include <algorithm>
#include <stdexcept>

template <typename T, typename A = std::allocator<T> >
class circular_buffer
{
public:
   typedef T                                            value_type;
   typedef A                                            allocator_type;
   typedef typename allocator_type::size_type           size_type;
   typedef typename allocator_type::difference_type     difference_type;
   typedef typename allocator_type::reference           reference;
   typedef typename allocator_type::const_reference     const_reference;
   typedef typename allocator_type::pointer             pointer;
   typedef typename allocator_type::const_pointer       const_pointer;

   explicit circular_buffer(size_type capacity,
                            const allocator_type &a = allocator_type());
   ~circular_buffer();
   allocator_type get_allocator() const;

   size_type size() const;
   size_type max_size() const;
   bool      empty() const;

   size_type capacity() const;

   reference       front();
   const_reference front() const;

   bool push_back(const value_type &);
   void pop_front();
   void clear();

   reference       operator[](size_type n);
   const_reference operator[](size_type n) const;
   reference       at(size_type n);
   const_reference at(size_type n) const;

private:
   size_type       m_capacity;
   allocator_type  m_allocator;
   pointer         m_buffer;
   pointer         m_front;
   pointer         m_back; // points to next unused item

   typedef circular_buffer<T> class_type;

   circular_buffer(const class_type &);
   class_type &operator=(const class_type &);

   value_type *wrap(value_type *ptr) const
   {
       assert(ptr < m_buffer + m_capacity*2);
       if (ptr >= m_buffer+m_capacity)
           return ptr-m_capacity;
       else
           return ptr;
   }
};

template <typename T, typename A>
inline
circular_buffer<T,A>::circular_buffer
    (size_type capacity, const allocator_type &allocator)
: m_capacity(capacity),
 m_allocator(allocator),
 m_buffer(m_allocator.allocate(capacity)),
 m_front(0),
 m_back(m_buffer)
{
   assert(capacity > 0);
}

template <typename T, typename A>
inline
circular_buffer<T,A>::~circular_buffer()
{
   clear(); // deallocates all objects
   m_allocator.deallocate(m_buffer, m_capacity);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::allocator_type
circular_buffer<T,A>::get_allocator() const
{
   return m_allocator;
}


template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::capacity() const
{
   return m_capacity;
}

template <typename T, typename A>
inline
bool circular_buffer<T,A>::empty() const
{
   return !m_front;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::size() const
{
   return !m_front ? 0
                   : (m_back > m_front ? m_back : m_back+m_capacity) - m_front;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::max_size() const
{
   return m_allocator.max_size();
}

template <typename T, typename A>
inline
bool circular_buffer<T,A>::push_back(const value_type &value)
{
   if (m_front && m_front == m_back)
       m_allocator.destroy(m_back);

   m_allocator.construct(m_back, value);

   value_type *const next = wrap(m_back+1);
   if (!m_front)
   {
       // first entry in the buffer
       m_front = m_back;
       m_back = next;
       return true;
   }
   else if (m_front == m_back)
   {
       // buffer is full already, throw something away
       m_front = m_back = next;
       return false;
   }
   else
   {
       m_back = next;
       return true;
   }
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::front()
{
   assert(m_front);
   return *m_front;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::front() const
{
   assert(m_front);
   return *m_front;
}

template <typename T, typename A>
inline
void circular_buffer<T,A>::pop_front()
{
   assert(m_front);

   m_allocator.destroy(m_front);
   value_type *const next = wrap(m_front+1);
   if (next == m_back)
       m_front = 0;
   else
       m_front = next;
}

template <typename T, typename A>
inline
void circular_buffer<T,A>::clear()
{
   if (m_front)
   {
       do
       {
           m_allocator.destroy(m_front);
           m_front = wrap(m_front+1);
       }
       while (m_front != m_back);
   }
   m_front = 0;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::operator[]
   (size_type n)
{
   return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::operator[]
   (size_type n) const
{
   return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::at(size_type n)
{
   if (n >= size()) throw std::out_of_range("Parameter out of range");
   return (*this)[n];
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::at
    (size_type n) const
{
   if (n >= size()) throw std::out_of_range("Parameter out of range");
   return (*this)[n];
}

namespace tests
{
   void pushing_and_popping()
   {
       circular_buffer<int> cb(5);

       assert(cb.size() == 0);
       assert(cb.capacity() == 5);
       assert(cb.empty());
       assert(cb.max_size() > 0);

       assert(cb.push_back(1));
       assert(cb.size() == 1);
       assert(cb.capacity() == 5);
       assert(!cb.empty());
       assert(cb.front() == 1);

       assert(cb.push_back(2));
       assert(cb.size() == 2);
       assert(cb.capacity() == 5);
       assert(!cb.empty());
       assert(cb.front() == 1);

       assert(cb.push_back(3));
       assert(cb.push_back(4));
       assert(cb.push_back(5));
       assert(cb.size() == 5);
       assert(cb.capacity() == 5);
       assert(!cb.empty());
       assert(cb.front() == 1);

       assert(!cb.push_back(6));
       assert(cb.size() == 5);
       assert(cb.capacity() == 5);
       assert(!cb.empty());
       assert(cb.front() == 2);

       cb.pop_front();
       assert(cb.size() == 4);
       assert(cb.capacity() == 5);
       assert(!cb.empty());
       assert(cb.front() == 3);

       cb.pop_front();
       assert(cb.size() == 3);
       assert(cb.front() == 4);

       cb.pop_front();
       assert(cb.size() == 2);
       assert(cb.front() == 5);

       cb.pop_front();
       assert(cb.size() == 1);
       assert(cb.front() == 6);

       cb.pop_front();
       assert(cb.size() == 0);
       assert(cb.capacity() == 5);
       assert(cb.empty());

       // empty again

       assert(cb.push_back(7));
       assert(cb.size() == 1);
       assert(cb.capacity() == 5);
       assert(!cb.empty());
       assert(cb.front() == 7);

       assert(cb.push_back(8));
       assert(cb.push_back(9));
       assert(cb.size() == 3);
       assert(!cb.empty());
       assert(cb.front() == 7);

       cb.clear();
       assert(cb.size() == 0);
       assert(cb.capacity() == 5);
       assert(cb.empty());
   }

   void indexing()
   {
       circular_buffer<int> cb(5);

       // A helper - like asssert, but checks for an exception
        #define assert_throws(a,b) \
        {\
            try { a; throw "Failed to throw"; } \
            catch (const b&) { /*OK*/ } \
            catch (...) { throw "Threw wrong thing"; } \
        }

       // We loop round this test several times so our data wraps around the
       // internal m_buffer array a few times.
       for (size_t n = 0; n < 10; ++n)
       {
           assert(cb.empty());

           const circular_buffer<int> &const_cb(cb);

           assert_throws(cb.at(0), std::out_of_range);
           assert_throws(cb.at(1), std::out_of_range);
           assert_throws(const_cb.at(0), std::out_of_range);
           assert_throws(const_cb.at(0), std::out_of_range);
           // we could check that operator[] explodes, but there's little point!

           assert(cb.push_back(0));
           assert(cb.push_back(1));
           assert(cb.push_back(2));
           assert(cb.at(0) == 0); assert(const_cb.at(0) == 0);
           assert(cb.at(1) == 1); assert(const_cb.at(1) == 1);
           assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
           assert(cb[0] == 0);    assert(const_cb[0] == 0);
           assert(cb[1] == 1);    assert(const_cb[1] == 1);
           assert(cb[2] == 2);    assert(const_cb[2] == 2);

           assert(cb.front() == 0);
           cb[0] = 3;
           assert(cb.front() == 3);
           assert(cb.at(0) == 3); assert(const_cb.at(0) == 3);
           assert(cb.at(1) == 1); assert(const_cb.at(1) == 1);
           assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
           assert(cb[0] == 3);    assert(const_cb[0] == 3);
           assert(cb[1] == 1);    assert(const_cb[1] == 1);
           assert(cb[2] == 2);    assert(const_cb[2] == 2);

           cb[1] = 4;
           assert(cb.at(0) == 3); assert(const_cb.at(0) == 3);
           assert(cb.at(1) == 4); assert(const_cb.at(1) == 4);
           assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
           assert(cb[0] == 3);    assert(const_cb[0] == 3);
           assert(cb[1] == 4);    assert(const_cb[1] == 4);
           assert(cb[2] == 2);    assert(const_cb[2] == 2);

           cb.pop_front();
           assert(cb[0] == 4);    assert(const_cb[0] == 4);
           assert(cb[1] == 2);    assert(const_cb[1] == 2);

           cb.pop_front();
           assert(cb[0] == 2);    assert(const_cb[0] == 2);

           cb.pop_front();
       }

   }
}

int main()
{
   tests::pushing_and_popping();
   tests::indexing();
   return 0;
}