[Circular Buffer] draft approaches (exercism#3640)

colinleach · BethanyG · web-flow · commit 125a3f69038c · 2024-03-05T00:33:10.000-08:00
* [Circular Buffer] draft approaches

* introduction - add guidance

* Links and Additions

Added `memoryview`, `buffer protocol`, `array.array` and supporting links for various things.

---------

Co-authored-by: BethanyG &lt;BethanyG@users.noreply.github.com&gt;
diff --git a/exercises/practice/circular-buffer/.approaches/built-in-types/content.md b/exercises/practice/circular-buffer/.approaches/built-in-types/content.md
@@ -0,0 +1,91 @@
+# Built In Types
+
+
+```python
+class CircularBuffer:
+    def __init__(self, capacity: int) -> None:
+        self.capacity = capacity
+        self.content = []
+
+    def read(self) -> str:
+        if not self.content:
+            raise BufferEmptyException("Circular buffer is empty")
+        return self.content.pop(0)
+
+    def write(self, data: str) -> None:
+        if len(self.content) == self.capacity:
+            raise BufferFullException("Circular buffer is full")
+        self.content.append(data)
+
+    def overwrite(self, data: str) -> None:
+        if len(self.content) == self.capacity:
+            self.content.pop(0)
+        self.write(data)
+
+    def clear(self) -> None:
+        self.content = []
+```
+
+In Python, the `list` type is ubiquitous and exceptionally versatile.
+Code similar to that shown above is a very common way to implement this exercise.
+Though lists can do much more, here we use `append()` to add an entry to the end of the list, and `pop(0)` to remove an entry from the beginning.
+
+
+By design, lists have no built-in length limit and can grow arbitrarily, so the main task of the programmer here is to keep track of capacity, and limit it when needed.
+A `list` is also designed to hold an arbitrary mix of Python objects, and this flexibility in content is emphasized over performance.
+For more precise control, at the price of some increased programming complexity, it is possible to use a [`bytearray`][bytearray], or the [`array.array`][array.array] type from the [array][[array-module] module.
+For details on using `array.array`, see the [standard library][approaches-standard-library] approach.
+
+In the case of a `bytearray`, entries are of fixed type: integers in the range `0 <= n < 256`.
+
+The tests are designed such that this is sufficient to solve the exercise, and byte handling may be quite a realistic view of how circular buffers are often used in practice.
+
+The code below shows an implementation using this lower-level collection class:
+
+
+```python
+class CircularBuffer:
+    def __init__(self, capacity):
+        self.capacity = bytearray(capacity)
+        self.read_start = 0
+        self.write_start = 0
+
+    def read(self):
+        if not any(self.capacity):
+            raise BufferEmptyException('Circular buffer is empty')
+        
+        data = chr(self.capacity[self.read_start])
+        self.capacity[self.read_start] = 0
+        self.read_start = (self.read_start + 1) % len(self.capacity)
+        
+        return data
+
+    def write(self, data):
+        if all(self.capacity):
+            raise BufferFullException('Circular buffer is full')
+        
+        try:
+            self.capacity[self.write_start] = data
+        except TypeError:
+            self.capacity[self.write_start] = ord(data)
+        
+        self.write_start = (self.write_start + 1) % len(self.capacity)
+
+    def overwrite(self, data):
+        try:
+            self.capacity[self.write_start] = data
+        except TypeError:
+            self.capacity[self.write_start] = ord(data)
+            
+        if all(self.capacity) and self.write_start == self.read_start:
+            self.read_start = (self.read_start + 1) % len(self.capacity)
+            self.write_start = (self.write_start + 1) % len(self.capacity)
+
+    def clear(self):
+        self.capacity = bytearray(len(self.capacity))
+```
+
+[approaches-standard-library]: https://exercism.org/tracks/python/exercises/circular-buffer/approaches/standard-library
+[array-module]: https://docs.python.org/3/library/array.html#module-array
+[array.array]: https://docs.python.org/3/library/array.html#array.array
+[bytearray]: https://docs.python.org/3/library/stdtypes.html#binary-sequence-types-bytes-bytearray-memoryview
diff --git a/exercises/practice/circular-buffer/.approaches/built-in-types/snippet.txt b/exercises/practice/circular-buffer/.approaches/built-in-types/snippet.txt
@@ -0,0 +1,5 @@
+from queue import Queue
+
+class CircularBuffer:
+    def __init__(self, capacity):
+        self.buffer = Queue(capacity)
diff --git a/exercises/practice/circular-buffer/.approaches/config.json b/exercises/practice/circular-buffer/.approaches/config.json
@@ -0,0 +1,30 @@
+{
+  "introduction": {
+    "authors": [
+      "colinleach",
+      "BethanyG"
+    ]
+  },
+  "approaches": [
+    {
+      "uuid": "a560804f-1486-451d-98ab-31251926881e",
+      "slug": "built-in-types",
+      "title": "Built In Types",
+      "blurb": "Use a Python list or bytearray.",
+      "authors": [
+        "colinleach",
+        "BethanyG"
+      ]
+    },
+    {
+      "uuid": "f01b8a10-a3d9-4779-9a8b-497310fcbc73",
+      "slug": "standard-library",
+      "title": "Standard Library",
+      "blurb": "Use a Queue or deque object for an easier implementation.",
+      "authors": [
+        "colinleach",
+        "BethanyG"
+      ]
+    }
+  ]
+}
diff --git a/exercises/practice/circular-buffer/.approaches/introduction.md b/exercises/practice/circular-buffer/.approaches/introduction.md
@@ -0,0 +1,100 @@
+# 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.
+
+```python
+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.
+
+A less versatile variants include [`bytearray`][bytearray] and [`array.array`][array.array].
+
+`bytearray`s are similar to `list`s 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][approaches-built-in] approach.
+
+
+Finally, [`memoryview`s][memoryview] allow for direct access to the binary data (_ without copying_) of Python objects that support the  [`Buffer Protocol`][buffer-protocol].
+ `memoryview`s 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][ctypes] from outside libraries and C [structs][struct].
+
+ For additional information on the `buffer protocol`, see [Emulating Buffer Types][emulating-buffer-types] in the Python documentation.
+ As of Python `3.12`, the abstract class [collections.abc.Buffer][abc-Buffer] is also available for classes that provide the [`__buffer__()`][dunder-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`][queue-module] module contains the [`Queue`][Queue-class] class, which can be initialized with a maximum capacity.
+- The [`collections`][collections-module] module contains a [`deque`][deque-class] class (short for Double Ended QUEue), which can also be set to a maximum capacity.
+- The [`array`][array.array] module contains an [`array`][array-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][approaches-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 `memoryview`s into `bytearray`s or [`numpy` arrays][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)][circular-buffer], [memoryview Python Performance][memoryview-py-performance], and [Less Copies in Python with the buffer protocol and memoryviews][less-copies-in-Python].
+
+
+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.
+
+[Queue-class]: https://docs.python.org/3.11/library/queue.html#queue.Queue
+[abc-Buffer]: https://docs.python.org/3/library/collections.abc.html#collections.abc.Buffer
+[approaches-built-in]: https://exercism.org/tracks/python/exercises/circular-buffer/approaches/built-in-types
+[approaches-standard-library]: https://exercism.org/tracks/python/exercises/circular-buffer/approaches/standard-library
+[array-array]: https://docs.python.org/3.11/library/array.html#array.array
+[array.array]: https://docs.python.org/3.11/library/array.html#module-array
+[buffer-protocol]: https://docs.python.org/3/c-api/buffer.html
+[bytearray]: https://docs.python.org/3/library/stdtypes.html#bytearray
+[circular-buffer]: https://towardsdatascience.com/circular-queue-or-ring-buffer-92c7b0193326
+[collections-module]: https://docs.python.org/3.11/library/collections.html
+[ctypes]: https://docs.python.org/3/library/ctypes.html
+[deque-class]: https://docs.python.org/3.11/library/collections.html#collections.deque
+[dunder-buffer]: https://docs.python.org/3/reference/datamodel.html#object.__buffer__
+[emulating-buffer-types]: https://docs.python.org/3/reference/datamodel.html#emulating-buffer-types
+[less-copies-in-Python]: https://eli.thegreenplace.net/2011/11/28/less-copies-in-python-with-the-buffer-protocol-and-memoryviews
+[memoryview-py-performance]: https://prrasad.medium.com/memory-view-python-performance-improvement-method-c241a79e9843
+[memoryview]: https://docs.python.org/3/library/stdtypes.html#memoryview
+[numpy-arrays]: https://numpy.org/doc/stable/reference/generated/numpy.array.html
+[queue-module]: https://docs.python.org/3.11/library/queue.html
+[struct]: https://docs.python.org/3/library/struct.html
diff --git a/exercises/practice/circular-buffer/.approaches/standard-library/content.md b/exercises/practice/circular-buffer/.approaches/standard-library/content.md
@@ -0,0 +1,119 @@
+# Standard Library
+
+
+```python
+from queue import Queue
+
+class CircularBuffer:
+    def __init__(self, capacity):
+        self.buffer = Queue(capacity)
+
+    def read(self):
+        if self.buffer.empty():
+            raise BufferEmptyException("Circular buffer is empty")
+        return self.buffer.get()
+
+    def write(self, data):
+        if self.buffer.full():
+            raise BufferFullException("Circular buffer is full")
+        self.buffer.put(data)
+
+    def overwrite(self, data):
+        if self.buffer.full():
+            _ = self.buffer.get()
+        self.buffer.put(data)
+
+    def clear(self):
+        while not self.buffer.empty():
+            _ = self.buffer.get()
+```
+
+The above code uses a [`Queue` object][queue] to "implement" the buffer, a collection class which assumes entries will be added at the end and removed at the beginning.
+This is a "queue" in British English, though Americans call it a "line".
+
+
+Alternatively, the `collections` module provides a [`deque` object][deque], a double-ended queue class.
+A `deque` allows adding and removing entries at both ends, which is not something we need for a circular buffer.
+However, the syntax may be even more concise than for a `queue`:
+
+
+```python
+from collections import deque
+from typing import Any
+
+class CircularBuffer:
+    def __init__(self, capacity: int):
+        self.buffer = deque(maxlen=capacity)
+
+    def read(self) -> Any:
+        if len(self.buffer) == 0:
+            raise BufferEmptyException("Circular buffer is empty")
+        return self.buffer.popleft()
+
+    def write(self, data: Any) -> None:
+        if len(self.buffer) == self.buffer.maxlen:
+            raise BufferFullException("Circular buffer is full")
+        self.buffer.append(data)
+
+    def overwrite(self, data: Any) -> None:
+        self.buffer.append(data)
+
+    def clear(self) -> None:
+        if len(self.buffer) > 0:
+            self.buffer.popleft()
+```
+
+Both `Queue` and `deque` have the ability to limit the queues length by declaring a 'capacity' or 'maxlen' attribute.
+This simplifies empty/full and read/write tracking.
+
+
+Finally, the [`array`][array-array] class from the [`array`][array.array] module can be used to initialize a 'buffer' that works similarly to a built-in `list` or `bytearray`, but with efficiencies in storage and access:
+
+
+```python
+from array import array
+
+
+class CircularBuffer:
+    def __init__(self, capacity):
+        self.buffer = array('u')
+        self.capacity = capacity
+        self.marker = 0
+
+    def read(self):
+        if not self.buffer: 
+            raise BufferEmptyException('Circular buffer is empty')   
+
+        else:
+            data = self.buffer.pop(self.marker)
+            if self.marker > len(self.buffer)-1: self.marker = 0
+            
+            return data
+    
+    def write(self, data):
+        if len(self.buffer) < self.capacity:
+            try:
+                self.buffer.append(data)
+            except TypeError:
+                self.buffer.append(data)
+        
+        else: raise BufferFullException('Circular buffer is full')
+    
+    def overwrite(self, data):
+        if len(self.buffer) < self.capacity: self.buffer.append(data)
+        
+        else:
+            self.buffer[self.marker] = data
+
+            if self.marker < self.capacity - 1: self.marker += 1  
+            else: self.marker = 0
+    
+    def clear(self):
+        self.marker = 0
+        self.buffer = array('u')
+```
+
+[queue]: https://docs.python.org/3/library/queue.html
+[deque]: https://docs.python.org/3/library/collections.html#deque-objects
+[array-array]: https://docs.python.org/3.11/library/array.html#array.array
+[array.array]: https://docs.python.org/3.11/library/array.html#module-array
diff --git a/exercises/practice/circular-buffer/.approaches/standard-library/snippet.txt b/exercises/practice/circular-buffer/.approaches/standard-library/snippet.txt
@@ -0,0 +1,4 @@
+class CircularBuffer:
+    def __init__(self, capacity: int) -> None:
+        self.capacity = capacity
+        self.content = []
