A RingBuffer collection

collection

(Daryle Walker) #1

Related to two other threads, I updated their Gist to include a ring-buffer collection type.

RingBuffer<Element> is a random-access collection that allows mutation of its elements. It does not support RangeReplaceableCollection, because adding elements is restricted to two methods: pushThrough(asFirstElement:) and pushThrough(asLastElement:). These methods insert an element and remove another at the same time, exposed as an optional return. The size of the ring is set by the initial sequence fed to it, which can't be empty. I stuffed as many Standard Library helper protocols as possible too.

It's originally meant to aid the various Sequence methods who need to retain a limited number of elements while iterating. In fact, RingBuffer is used in another search method to Sequence in the same Gist. Of course, RingBuffer assumes the rotation-related types also go in. It also supports internal rotation of the ring, moving the pointer of first index instead of swapping around elements.


(Johannes Weiss) #2

Just wanted to point out that NIO contains CircularBuffer which is an expanding ring buffer. Note that usually a ring buffer will overwrite elements when the ring capacity is exhausted but CircularBuffer will instead expand the storage.

I should also point out that we learned a lot since writing it so we're probably going to re-write it using opaque indices some point soon :slight_smile:.


(Karoy Lorentey) #3

I also have a (somewhat outdated) Deque package implementing a circular buffer, conforming to RandomAccessCollection, MutableCollection, as well as RangeReplaceableCollection.

I wholeheartedly agree with Johannes about the need for opaque indices. (If desired, we can add accessors for elements at zero-based integer offsets as an alternative, labeled subscript operation.)

Double-ended queues are frequently useful, even within the stdlib itself -- for example, in the internals of some other basic data structures we'd like to add, like "array"-based ordered sets and B-tree-based sorted sets.