5.19 Implementing a Ring Buffer

Credit: Sébastien Keim

5.19.1 Problem

You want to define a buffer with a fixed size, so that when it fills up, adding another element must overwrite the first (oldest) one. This kind of data structure is particularly useful for storing log and history information.

5.19.2 Solution

This recipe changes the buffer object's class on the fly, from a non-full buffer class to a full-buffer class, when it fills up:

class RingBuffer:
    """ class that implements a not-yet-full buffer """
    def _ _init_ _(self,size_max):
        self.max = size_max
        self.data = []

    class _ _Full:
        """ class that implements a full buffer """
        def append(self, x):
            """ Append an element overwriting the oldest one. """
            self.data[self.cur] = x
            self.cur = (self.cur+1) % self.max
        def get(self):
            """ return list of elements in correct order """
            return self.data[self.cur:]+self.data[:self.cur]

    def append(self,x):
        """append an element at the end of the buffer"""
        self.data.append(x)
        if len(self.data) == self.max:
            self.cur = 0
            # Permanently change self's class from non-full to full
            self._ _class_ _ = _ _Full

    def get(self):
        """ Return a list of elements from the oldest to the newest. """
        return self.data

# sample usage
if _ _name_ _=='_ _main_ _':
    x=RingBuffer(5)
    x.append(1); x.append(2); x.append(3); x.append(4)
    print x._ _class_ _, x.get(  )
    x.append(5)
    print x._ _class_ _, x.get(  )
    x.append(6)
    print x.data, x.get(  )
    x.append(7); x.append(8); x.append(9); x.append(10)
    print x.data, x.get(  )

5.19.3 Discussion

A ring buffer is a buffer with a fixed size. When it fills up, adding another element overwrites the oldest one that was still being kept. It's particularly useful for the storage of log information and history. There is no direct support in Python for this kind of structure, but it's easy to construct one. The implementation in this recipe is optimized for element insertion.

The notable design choice in the implementation is that, since these objects undergo a nonreversible state transition at some point in their lifetimes�from non-full buffer to full-buffer (and behavior changes at that point)�I modeled that by changing self._ _class_ _. This works even in Python 2.2, as long as both classes have the same slots (for example, it works fine for two classic classes, such as RingBuffer and _ _Full in this recipe).

Changing the class of an instance may be strange in many languages, but it is a Pythonic alternative to other ways of representing occasional, massive, irreversible, and discrete changes of state that vastly affect behavior, as in this recipe. Good thing that Python supports it for all kinds of classes.

5.19.4 See Also

The Reference Manual section on the standard type hierarchy.