969 Intermediate

969 Circular Buffer

Functional Programming

Tutorial

The Problem

Implement a fixed-capacity circular ring buffer (FIFO) where pushing to a full buffer overwrites the oldest element. Use separate head, tail, and count indices with modular arithmetic. Unlike VecDeque (which grows), this ring buffer has a fixed capacity — modeling hardware FIFOs, event log windows, and streaming buffers.

🎯 Learning Outcomes

• Implement RingBuffer<T: Default + Clone> with Vec<T> and head/tail/count tracking

• Push: write to tail, advance tail = (tail + 1) % capacity, and when full advance head to overwrite oldest

• Pop: read from head, advance head = (head + 1) % capacity, decrement count

• Implement is_full, is_empty, size, and peek without special-casing the wrap-around

• Understand why T: Default is needed for pre-allocation: vec![T::default(); capacity]

Code Example

#![allow(clippy::all)]
// 969: Circular / Ring Buffer
// Fixed-capacity FIFO: push overwrites oldest when full
// OCaml: array + head/tail/count refs; Rust: Vec + indices

pub struct RingBuffer<T> {
    data: Vec<T>,
    capacity: usize,
    head: usize, // next read index
    tail: usize, // next write index
    count: usize,
}

impl<T: Default + Clone> RingBuffer<T> {
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0, "capacity must be > 0");
        RingBuffer {
            data: vec![T::default(); capacity],
            capacity,
            head: 0,
            tail: 0,
            count: 0,
        }
    }
}

impl<T: Clone> RingBuffer<T> {
    pub fn is_full(&self) -> bool {
        self.count == self.capacity
    }
    pub fn is_empty(&self) -> bool {
        self.count == 0
    }
    pub fn size(&self) -> usize {
        self.count
    }

    /// Push: if full, overwrites oldest element
    pub fn push(&mut self, x: T) {
        self.data[self.tail] = x;
        self.tail = (self.tail + 1) % self.capacity;
        if self.is_full() {
            // Overwrite: advance head (drop oldest)
            self.head = (self.head + 1) % self.capacity;
        } else {
            self.count += 1;
        }
    }

    /// Pop: removes and returns oldest element
    pub fn pop(&mut self) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            let x = self.data[self.head].clone();
            self.head = (self.head + 1) % self.capacity;
            self.count -= 1;
            Some(x)
        }
    }

    /// Peek: view oldest without removing
    pub fn peek(&self) -> Option<&T> {
        if self.is_empty() {
            None
        } else {
            Some(&self.data[self.head])
        }
    }

    /// Collect all elements in order (oldest first)
    pub fn to_vec(&self) -> Vec<T> {
        (0..self.count)
            .map(|i| self.data[(self.head + i) % self.capacity].clone())
            .collect()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic_push_pop() {
        let mut r: RingBuffer<i32> = RingBuffer::new(4);
        assert!(r.is_empty());
        r.push(1);
        r.push(2);
        r.push(3);
        r.push(4);
        assert!(r.is_full());
        assert_eq!(r.size(), 4);
        assert_eq!(r.peek(), Some(&1));
    }

    #[test]
    fn test_overwrite_on_full() {
        let mut r: RingBuffer<i32> = RingBuffer::new(4);
        r.push(1);
        r.push(2);
        r.push(3);
        r.push(4);
        r.push(5); // overwrites 1
        assert_eq!(r.size(), 4);
        assert_eq!(r.peek(), Some(&2));
        assert_eq!(r.to_vec(), vec![2, 3, 4, 5]);
    }

    #[test]
    fn test_pop_order() {
        let mut r: RingBuffer<i32> = RingBuffer::new(4);
        for i in 1..=4 {
            r.push(i);
        }
        assert_eq!(r.pop(), Some(1));
        assert_eq!(r.pop(), Some(2));
        assert_eq!(r.size(), 2);
    }

    #[test]
    fn test_wrap_around() {
        let mut r: RingBuffer<i32> = RingBuffer::new(4);
        for i in 1..=4 {
            r.push(i);
        }
        r.pop();
        r.pop();
        r.push(5);
        r.push(6);
        r.push(7); // overwrite
        assert_eq!(r.to_vec(), vec![4, 5, 6, 7]);
    }

    #[test]
    fn test_empty_pop() {
        let mut r: RingBuffer<i32> = RingBuffer::new(2);
        assert_eq!(r.pop(), None);
        assert_eq!(r.peek(), None);
    }
}

(* 969: Circular/Ring Buffer *)
(* Fixed-capacity FIFO. Write overwrites oldest when full. *)

type 'a ring = {
  data: 'a array;
  capacity: int;
  mutable head: int;   (* index to read next *)
  mutable tail: int;   (* index to write next *)
  mutable count: int;
}

let create capacity default =
  { data = Array.make capacity default;
    capacity;
    head = 0;
    tail = 0;
    count = 0 }

let is_full r = r.count = r.capacity
let is_empty r = r.count = 0
let size r = r.count

(* Push: if full, overwrite oldest (advance head) *)
let push r x =
  if is_full r then begin
    r.data.(r.tail) <- x;
    r.tail <- (r.tail + 1) mod r.capacity;
    r.head <- (r.head + 1) mod r.capacity  (* overwrite oldest *)
  end else begin
    r.data.(r.tail) <- x;
    r.tail <- (r.tail + 1) mod r.capacity;
    r.count <- r.count + 1
  end

(* Pop: returns oldest element *)
let pop r =
  if is_empty r then None
  else begin
    let x = r.data.(r.head) in
    r.head <- (r.head + 1) mod r.capacity;
    r.count <- r.count - 1;
    Some x
  end

let peek r =
  if is_empty r then None
  else Some r.data.(r.head)

let () =
  let r = create 4 0 in
  assert (is_empty r);

  push r 1;
  push r 2;
  push r 3;
  push r 4;
  assert (is_full r);
  assert (size r = 4);
  assert (peek r = Some 1);

  (* Overwrite: push 5 overwrites 1 *)
  push r 5;
  assert (size r = 4);
  assert (peek r = Some 2);

  assert (pop r = Some 2);
  assert (pop r = Some 3);
  assert (size r = 2);

  push r 6;
  push r 7;
  push r 8;
  assert (is_full r);

  assert (pop r = Some 4);
  assert (pop r = Some 5);
  assert (pop r = Some 6);
  assert (pop r = Some 7);
  assert (pop r = Some 8);
  assert (is_empty r);
  assert (pop r = None);

  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Pre-allocation	`vec![T::default(); capacity]`	`Array.make capacity default` (explicit default)
Mutable fields	`let mut` struct fields	`mutable` record fields
Modular wrap	`% capacity`	`mod capacity`
Return on pop	`Option<T>` via `Some(x.clone())`	`'a option` via `Some x`

The circular buffer is a fixed-size sliding window over a stream of values. It is the foundation of audio/video buffers, network packet queues, and producer-consumer pipelines where only the most recent n items matter.

OCaml Approach

type 'a ring_buffer = {
  data: 'a array;
  capacity: int;
  mutable head: int;
  mutable tail: int;
  mutable count: int;
}

let create capacity default =
  { data = Array.make capacity default;
    capacity; head = 0; tail = 0; count = 0 }

let push buf x =
  buf.data.(buf.tail) <- x;
  buf.tail <- (buf.tail + 1) mod buf.capacity;
  if buf.count = buf.capacity
  then buf.head <- (buf.head + 1) mod buf.capacity
  else buf.count <- buf.count + 1

let pop buf =
  if buf.count = 0 then None
  else begin
    let x = buf.data.(buf.head) in
    buf.head <- (buf.head + 1) mod buf.capacity;
    buf.count <- buf.count - 1;
    Some x
  end

OCaml's mutable record fields allow in-place update. The algorithm is identical: % capacity wraps both indices, and push on a full buffer advances head to drop the oldest entry.

Full Source

#![allow(clippy::all)]
// 969: Circular / Ring Buffer
// Fixed-capacity FIFO: push overwrites oldest when full
// OCaml: array + head/tail/count refs; Rust: Vec + indices

pub struct RingBuffer<T> {
    data: Vec<T>,
    capacity: usize,
    head: usize, // next read index
    tail: usize, // next write index
    count: usize,
}

impl<T: Default + Clone> RingBuffer<T> {
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0, "capacity must be > 0");
        RingBuffer {
            data: vec![T::default(); capacity],
            capacity,
            head: 0,
            tail: 0,
            count: 0,
        }
    }
}

impl<T: Clone> RingBuffer<T> {
    pub fn is_full(&self) -> bool {
        self.count == self.capacity
    }
    pub fn is_empty(&self) -> bool {
        self.count == 0
    }
    pub fn size(&self) -> usize {
        self.count
    }

    /// Push: if full, overwrites oldest element
    pub fn push(&mut self, x: T) {
        self.data[self.tail] = x;
        self.tail = (self.tail + 1) % self.capacity;
        if self.is_full() {
            // Overwrite: advance head (drop oldest)
            self.head = (self.head + 1) % self.capacity;
        } else {
            self.count += 1;
        }
    }

    /// Pop: removes and returns oldest element
    pub fn pop(&mut self) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            let x = self.data[self.head].clone();
            self.head = (self.head + 1) % self.capacity;
            self.count -= 1;
            Some(x)
        }
    }

    /// Peek: view oldest without removing
    pub fn peek(&self) -> Option<&T> {
        if self.is_empty() {
            None
        } else {
            Some(&self.data[self.head])
        }
    }

    /// Collect all elements in order (oldest first)
    pub fn to_vec(&self) -> Vec<T> {
        (0..self.count)
            .map(|i| self.data[(self.head + i) % self.capacity].clone())
            .collect()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic_push_pop() {
        let mut r: RingBuffer<i32> = RingBuffer::new(4);
        assert!(r.is_empty());
        r.push(1);
        r.push(2);
        r.push(3);
        r.push(4);
        assert!(r.is_full());
        assert_eq!(r.size(), 4);
        assert_eq!(r.peek(), Some(&1));
    }

    #[test]
    fn test_overwrite_on_full() {
        let mut r: RingBuffer<i32> = RingBuffer::new(4);
        r.push(1);
        r.push(2);
        r.push(3);
        r.push(4);
        r.push(5); // overwrites 1
        assert_eq!(r.size(), 4);
        assert_eq!(r.peek(), Some(&2));
        assert_eq!(r.to_vec(), vec![2, 3, 4, 5]);
    }

    #[test]
    fn test_pop_order() {
        let mut r: RingBuffer<i32> = RingBuffer::new(4);
        for i in 1..=4 {
            r.push(i);
        }
        assert_eq!(r.pop(), Some(1));
        assert_eq!(r.pop(), Some(2));
        assert_eq!(r.size(), 2);
    }

    #[test]
    fn test_wrap_around() {
        let mut r: RingBuffer<i32> = RingBuffer::new(4);
        for i in 1..=4 {
            r.push(i);
        }
        r.pop();
        r.pop();
        r.push(5);
        r.push(6);
        r.push(7); // overwrite
        assert_eq!(r.to_vec(), vec![4, 5, 6, 7]);
    }

    #[test]
    fn test_empty_pop() {
        let mut r: RingBuffer<i32> = RingBuffer::new(2);
        assert_eq!(r.pop(), None);
        assert_eq!(r.peek(), None);
    }
}

(* 969: Circular/Ring Buffer *)
(* Fixed-capacity FIFO. Write overwrites oldest when full. *)

type 'a ring = {
  data: 'a array;
  capacity: int;
  mutable head: int;   (* index to read next *)
  mutable tail: int;   (* index to write next *)
  mutable count: int;
}

let create capacity default =
  { data = Array.make capacity default;
    capacity;
    head = 0;
    tail = 0;
    count = 0 }

let is_full r = r.count = r.capacity
let is_empty r = r.count = 0
let size r = r.count

(* Push: if full, overwrite oldest (advance head) *)
let push r x =
  if is_full r then begin
    r.data.(r.tail) <- x;
    r.tail <- (r.tail + 1) mod r.capacity;
    r.head <- (r.head + 1) mod r.capacity  (* overwrite oldest *)
  end else begin
    r.data.(r.tail) <- x;
    r.tail <- (r.tail + 1) mod r.capacity;
    r.count <- r.count + 1
  end

(* Pop: returns oldest element *)
let pop r =
  if is_empty r then None
  else begin
    let x = r.data.(r.head) in
    r.head <- (r.head + 1) mod r.capacity;
    r.count <- r.count - 1;
    Some x
  end

let peek r =
  if is_empty r then None
  else Some r.data.(r.head)

let () =
  let r = create 4 0 in
  assert (is_empty r);

  push r 1;
  push r 2;
  push r 3;
  push r 4;
  assert (is_full r);
  assert (size r = 4);
  assert (peek r = Some 1);

  (* Overwrite: push 5 overwrites 1 *)
  push r 5;
  assert (size r = 4);
  assert (peek r = Some 2);

  assert (pop r = Some 2);
  assert (pop r = Some 3);
  assert (size r = 2);

  push r 6;
  push r 7;
  push r 8;
  assert (is_full r);

  assert (pop r = Some 4);
  assert (pop r = Some 5);
  assert (pop r = Some 6);
  assert (pop r = Some 7);
  assert (pop r = Some 8);
  assert (is_empty r);
  assert (pop r = None);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic_push_pop() {
        let mut r: RingBuffer<i32> = RingBuffer::new(4);
        assert!(r.is_empty());
        r.push(1);
        r.push(2);
        r.push(3);
        r.push(4);
        assert!(r.is_full());
        assert_eq!(r.size(), 4);
        assert_eq!(r.peek(), Some(&1));
    }

    #[test]
    fn test_overwrite_on_full() {
        let mut r: RingBuffer<i32> = RingBuffer::new(4);
        r.push(1);
        r.push(2);
        r.push(3);
        r.push(4);
        r.push(5); // overwrites 1
        assert_eq!(r.size(), 4);
        assert_eq!(r.peek(), Some(&2));
        assert_eq!(r.to_vec(), vec![2, 3, 4, 5]);
    }

    #[test]
    fn test_pop_order() {
        let mut r: RingBuffer<i32> = RingBuffer::new(4);
        for i in 1..=4 {
            r.push(i);
        }
        assert_eq!(r.pop(), Some(1));
        assert_eq!(r.pop(), Some(2));
        assert_eq!(r.size(), 2);
    }

    #[test]
    fn test_wrap_around() {
        let mut r: RingBuffer<i32> = RingBuffer::new(4);
        for i in 1..=4 {
            r.push(i);
        }
        r.pop();
        r.pop();
        r.push(5);
        r.push(6);
        r.push(7); // overwrite
        assert_eq!(r.to_vec(), vec![4, 5, 6, 7]);
    }

    #[test]
    fn test_empty_pop() {
        let mut r: RingBuffer<i32> = RingBuffer::new(2);
        assert_eq!(r.pop(), None);
        assert_eq!(r.peek(), None);
    }
}

Deep Comparison

Circular Buffer — Comparison

Core Insight

A ring buffer uses modular arithmetic (i = (i + 1) % capacity) to wrap around array indices, creating the illusion of a circular structure from a linear array. Three indices (head, tail, count) fully describe state. Both OCaml and Rust implement this identically; the main difference is OCaml uses mutable record fields vs Rust's let mut struct fields.

OCaml Approach

• mutable head/tail/count in a record

• Array.make capacity default — requires a default value

• r.head <- (r.head + 1) mod r.capacity — modular advance

• Handles full/empty via count field

• Overwrite policy: advance both tail and head when full

Rust Approach

• Struct with head: usize, tail: usize, count: usize

• vec![T::default(); capacity] — requires T: Default + Clone

• self.tail = (self.tail + 1) % self.capacity — same modular advance

• Check is_full() before incrementing count (slightly different branch order)

• to_vec() for snapshot: (0..count).map(|i| data[(head+i)%cap])

Comparison Table

Aspect	OCaml	Rust
State	Mutable record fields	`&mut self` struct
Array init	`Array.make cap default`	`vec![T::default(); cap]`
Modular advance	`(i + 1) mod capacity`	`(i + 1) % capacity`
Full check	`count = capacity`	`count == capacity`
Overwrite	Advance both head and tail	Advance head after tail write
Snapshot	Manual fold	`.map(\|i\| data[(head+i)%cap])`
Generic	`'a ring`	`RingBuffer<T>` with `T: Clone`

Exercises

Implement to_vec(&self) -> Vec<T> that returns elements in FIFO order (oldest first).

Implement iter(&self) -> impl Iterator<Item=&T> that traverses from head to tail.

Add a push_no_overwrite variant that returns Err instead of overwriting when full.

Implement a sliding-window average: push each new sample, then compute the mean of all current elements.

Implement a thread-safe ring buffer using Mutex<RingBuffer<T>> and benchmark it vs crossbeam's bounded channel.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust