introduction.md

Introduction

The key to this exercise is to:

• Create a suitable collection object to hold the values.
• Keep track of size as elements are added and removed.

General Guidance

Approaches to this exercise vary from easy but rather boring, to complex but educational.

It would be useful to think about what you want from completing the exercise, then choose an appropriate collection class that fits your aims.

Exception classes

All the approaches rely on being able to raise two custom exceptions, with suitable error messages.

class BufferFullException(BufferError):
    """Exception raised when CircularBuffer is full."""
    
    def __init__(self, message):
        self.message = message

class BufferEmptyException(BufferError):
    """Exception raised when CircularBuffer is empty."""
    
    def __init__(self, message):
        self.message = message

Code for these error handling scenarios is always quite similar, so for brevity this aspect will be omitted from the various approaches to the exercise.

Approach: Using built-in types

Python has an exceptionally flexible and widely-used list type. Most submitted solutions to Circular Buffer are based on this data type.

Less versatile variants include bytearray and array.array.

bytearrays are similar to lists in many ways, but they are limited to holding only bytes (represented as integers in the range 0 <= n < 256).

For details, see the built-in types approach.

Finally, memoryviews allow for direct access to the binary data (_ without copying_) of Python objects that support the Buffer Protocol. memoryviews can be used to directly access the underlying memory of types such as bytearray, array.array, queue, dequeue, and list as well as working with ctypes from outside libraries and C structs.

For additional information on the buffer protocol, see Emulating Buffer Types in the Python documentation. As of Python 3.12, the abstract class collections.abc.Buffer is also available for classes that provide the __buffer__() method and implement the buffer protocol.

Approach: Using collection classes from the standard library

A circular buffer is a type of fixed-size queue, and Python provides various implementations of this very useful type of collection.

• The queue module contains the Queue class, which can be initialized with a maximum capacity.
• The collections module contains a deque class (short for Double Ended QUEue), which can also be set to a maximum capacity.
• The array module contains an array class that is similar to Python's built-in list, but is limited to a single datatype (available datatypes are mapped to C datatypes). This allows values to be stored in a more compact and efficient fashion.

For details, see the standard library approach.

Which Approach to Use?

Anyone just wanting to use a circular buffer to get other things done and is not super-focused on performance is likely to pick a Queue or deque, as either of these will handle much of the low-level bookkeeping.

For a more authentic learning experience, using a list will provide practice in keeping track of capacity, with bytearray or array.array taking the capacity and read/write tracking a stage further.

For a really deep dive into low-level Python operations, you can explore using memoryviews into bytearrays or numpy arrays, or customize your own buffer protocol-supporting Python object, ctype or struct. Some 'jumping off' articles for this are circular queue or ring buffer (Python and C), memoryview Python Performance, and Less Copies in Python with the buffer protocol and memoryviews.

In reality, anyone wanting to get a deeper understanding of how these collection structures work "from scratch" might do even better to try solving the exercise in a statically-typed system language such as C, Rust, or even try an assembly language like MIPS.