# raywenderlich / swift-algorithm-club

Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
RingBuffer.playground Oct 13, 2018
RingBuffer.swift Aug 24, 2017

# Ring Buffer

Also known as a circular buffer.

The problem with a queue based on an array is that adding new items to the back of the queue is fast, O(1), but removing items from the front of the queue is slow, O(n). Removing is slow because it requires the remaining array elements to be shifted in memory.

A more efficient way to implement a queue is to use a ring buffer or circular buffer. This is an array that conceptually wraps around back to the beginning, so you never have to remove any items. All operations are O(1).

Here is how it works in principle. We have an array of a fixed size, say 5 items:

``````[    ,    ,    ,    ,     ]
r
w
``````

Initially, the array is empty and the read (`r`) and write (`w`) pointers are at the beginning.

Let's add some data to this array. We'll write, or "enqueue", the number `123`:

``````[ 123,    ,    ,    ,     ]
r
---> w
``````

Each time we add data, the write pointer moves one step forward. Let's add a few more elements:

``````[ 123, 456, 789, 666,     ]
r
-------------> w
``````

There is now one open spot left in the array, but rather than enqueuing another item the app decides to read some data. That's possible because the write pointer is ahead of the read pointer, meaning data is available for reading. The read pointer advances as we read the available data:

``````[ 123, 456, 789, 666,     ]
---> r              w
``````

``````[ 123, 456, 789, 666,     ]
--------> r    w
``````

Now the app decides it's time to write again and enqueues two more data items, `333` and `555`:

``````[ 123, 456, 789, 666, 333 ]
r    ---> w
``````

Whoops, the write pointer has reached the end of the array, so there is no more room for object `555`. What now? Well, this is why it's a circular buffer: we wrap the write pointer back to the beginning and write the remaining data:

``````[ 555, 456, 789, 666, 333 ]
---> w         r
``````

We can now read the remaining three items, `666`, `333`, and `555`.

``````[ 555, 456, 789, 666, 333 ]
w         --------> r
``````

Of course, as the read pointer reaches the end of the buffer it also wraps around:

``````[ 555, 456, 789, 666, 333 ]
w
---> r
``````

And now the buffer is empty again because the read pointer has caught up with the write pointer.

Here is a very basic implementation in Swift:

```public struct RingBuffer<T> {
fileprivate var array: [T?]
fileprivate var writeIndex = 0

public init(count: Int) {
array = [T?](repeating: nil, count: count)
}

public mutating func write(_ element: T) -> Bool {
if !isFull {
array[writeIndex % array.count] = element
writeIndex += 1
return true
} else {
return false
}
}

public mutating func read() -> T? {
if !isEmpty {
let element = array[readIndex % array.count]
return element
} else {
return nil
}
}

}

public var isEmpty: Bool {
}

fileprivate var availableSpaceForWriting: Int {
}

public var isFull: Bool {
return availableSpaceForWriting == 0
}
}```

The `RingBuffer` object has an array for the actual storage of the data, and `readIndex` and `writeIndex` variables for the "pointers" into the array. The `write()` function puts the new element into the array at the `writeIndex`, and the `read()` function returns the element at the `readIndex`.

But hold up, you say, how does this wrapping around work? There are several ways to accomplish this and I chose a slightly controversial one. In this implementation, the `writeIndex` and `readIndex` always increment and never actually wrap around. Instead, we do the following to find the actual index into the array:

`array[writeIndex % array.count]`

and:

`array[readIndex % array.count]`

In other words, we take the modulo (or the remainder) of the read index and write index divided by the size of the underlying array.

The reason this is a bit controversial is that `writeIndex` and `readIndex` always increment, so in theory these values could become too large to fit into an integer and the app will crash. However, a quick back-of-the-napkin calculation should take away those fears.

Both `writeIndex` and `readIndex` are 64-bit integers. If we assume that they are incremented 1000 times per second, which is a lot, then doing this continuously for one year requires `ceil(log_2(365 * 24 * 60 * 60 * 1000)) = 35` bits. That leaves 28 bits to spare, so that should give you about 2^28 years before running into problems. That's a long time. :-)

To play with this ring buffer, copy the code to a playground and do the following to mimic the example above:

```var buffer = RingBuffer<Int>(count: 5)

buffer.write(123)
buffer.write(456)
buffer.write(789)
buffer.write(666)

buffer.write(333)
buffer.write(555)

The implementation given here is not thread-safe. It only serves as an example of how a ring buffer works. That said, it should be fairly straightforward to make it thread-safe for a single reader and single writer by using `OSAtomicIncrement64()` to change the read and write pointers.