Skip to content

Instantly share code, notes, and snippets.

@Qata
Last active October 2, 2019 04:09
Show Gist options
  • Save Qata/3c2c6ab26cd8ec96f872556f69f57c63 to your computer and use it in GitHub Desktop.
Save Qata/3c2c6ab26cd8ec96f872556f69f57c63 to your computer and use it in GitHub Desktop.
public struct RingBuffer<Element> {
public let capacity: Int
private var underlying: [Element] = []
private var index: Int = 0
public init(capacity: Int, initial: [Element] = []) {
precondition(capacity > 0, "A positive capacity is required")
underlying = Array(initial.suffix(capacity))
self.capacity = capacity
index = underlying.count % capacity
}
public mutating func push(_ value: Element) {
if underlying.count < capacity {
underlying.append(value)
} else {
underlying[index] = value
}
index = (index + 1) % capacity
}
public mutating func pop() -> Element? {
defer {
underlying = .init(dropFirst())
index = underlying.count
}
return first
}
public mutating func dropAll() {
underlying = []
index = 0
}
public subscript(offset: Int) -> Element {
return underlying[(index + offset) % underlying.count]
}
}
extension RingBuffer: Sequence {
public func makeIterator() -> AnyIterator<Element> {
let count = underlying.count
var index = 0
return AnyIterator {
defer { index += 1 }
if index < count {
return self[index]
} else {
return nil
}
}
}
}
extension RingBuffer: BidirectionalCollection {
public func index(before i: Int) -> Int {
return i - 1
}
public func index(after i: Int) -> Int {
return i + 1
}
public var startIndex: Int {
return underlying.startIndex
}
public var endIndex: Int {
return underlying.endIndex
}
}
extension RingBuffer: CustomStringConvertible {
public var description: String {
return ["[", map(String.init(describing:)).joined(separator: ", "), "]"].joined()
}
}
import SwiftCheck
import XCTest
let pint = Positive<Int>.arbitrary.map { $0.getPositive }
let ints = [Int].arbitrary
extension RingBuffer: Arbitrary where Element: Arbitrary {
public static var arbitrary: Gen<RingBuffer<Element>> {
return Gen
.zip(pint, [Element].arbitrary)
.map(RingBuffer.init)
}
}
class RingBufferTests: XCTestCase {
func tests() {
property("RingBuffer init leaves the buffer with a suffix of `capacity` from the initial array") <- forAll(pint, ints) { p, xs in
Array(RingBuffer(capacity: p, initial: xs)) == Array(xs.suffix(p))
}
property("RingBuffer is isomorphic with its initial array") <- forAll(pint, ints) { p, xs in
Array(RingBuffer(capacity: xs.count + p, initial: xs)) == xs
}
property("push functions correctly") <- forAll(pint, ints) { p, xs in
let count = max(1, xs.count - p)
var buffer = RingBuffer<Int>(capacity: count)
xs.forEach { buffer.push($0) }
return Array(buffer) == Array(xs.suffix(count))
}
property("pop functions correctly") <- forAll(pint, ints) { p, xs in
var buffer = RingBuffer(capacity: xs.count + p, initial: xs)
var values: [Int] = []
LazySequence(repeating: ()).prefix(xs.count + p).forEach {
if let value = buffer.pop() {
values.append(value)
}
}
// Test that popping an empty buffer doesn't crash.
_ = buffer.pop()
return values == xs
}
property("dropAll functions correctly") <- forAll(Int.arbitrary.proliferateNonEmpty) { xs in
var buffer = RingBuffer(capacity: xs.count, initial: xs)
buffer.dropAll()
return Array(buffer) == []
}
property("description functions correctly") <- forAll(Int.arbitrary.proliferateNonEmpty) { xs in
let buffer = RingBuffer(capacity: xs.count, initial: xs)
return Array(buffer).description == buffer.description
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment