RingBuffer.kt

RingBuffer.kt

import java.util.AbstractQueue

/**
 * RingBuffer implementation of the Queue interface, used to create a fixed-size
 * collection. A ring buffer is a collection that is safe to add to, will not
 * run out of space, and drops the oldest element when adding to a full buffer.
 */
class RingBuffer<E>(private val capacity: Int = 16) : AbstractQueue<E>() {
  private var head = 0
  override var size = 0
  private val tail
    get() = (head + size) % capacity

  private val elements = ArrayList<E?>(capacity)

  init {
    for (i in 0 until capacity) {
      elements.add(null)
    }
  }

  override fun offer(e: E?): Boolean {
    e ?: throw IllegalArgumentException("Element cannot be null")

    elements[tail] = e

    /*
     * If the buffer is full, we will drop the head element in the buffer and
     * overwrite that element.
     */
    if (size == capacity) {
      head = (head + 1) % capacity
    } else {
      size++
    }

    return true
  }

  override fun peek(): E? {
    return if (size > 0) elements[head] else null
  }

  override fun poll(): E? {
    return if (size > 0) {
      val prev = head
      head = (head + 1) % capacity
      size--

      elements[prev]
    } else {
      null
    }
  }

  override fun iterator(): MutableIterator<E> {
    return Itr()
  }

  private inner class Itr : MutableIterator<E> {
    private var cur = head
    private var first = true

    override fun hasNext(): Boolean {
      return (cur != tail || first) && size > 0
    }

    override fun next(): E {
      if (!hasNext()) {
        throw NoSuchElementException("No more elements")
      }

      val prev = cur
      cur = (cur + 1) % capacity
      first = false

      return elements[prev] ?: throw IllegalStateException("Unable to access null element at position $prev")
    }

    override fun remove() {
      while (head != cur) {
        poll()
      }
    }
  }
}

RingBufferTest.kt

import org.hamcrest.Matchers.empty
import org.hamcrest.Matchers.equalTo
import org.hamcrest.Matchers.hasSize
import org.junit.Assert.assertThat
import org.junit.Assert.fail
import org.junit.Test

class RingBufferTest {
  @Test
  fun testOffer() {
    val buffer = RingBuffer<Int>()
    for (i in 1 ..CAPACITY) {
      buffer.offer(i)
      assertThat(buffer, hasSize(i))
    }

    assertThat(buffer, hasSize(CAPACITY))
  }

  @Test
  fun testPeek() {
    val buffer = RingBuffer<Int>()
    for (i in 0 until CAPACITY) {
      buffer.offer(i)
      assertThat(buffer.peek(), equalTo(0))
    }

    assertThat(buffer, hasSize(CAPACITY))
  }

  @Test
  fun testPoll() {
    val buffer = RingBuffer<Int>()
    for (i in 1 ..CAPACITY) {
      buffer.offer(i)
    }

    assertThat(buffer, hasSize(CAPACITY))

    for (i in 1 ..CAPACITY) {
      assertThat(buffer.poll(), equalTo(i))
    }

    assertThat(buffer, empty())
  }

  @Test
  fun testWrapAround() {
    val buffer = RingBuffer<Int>()
    for (i in 0 until CAPACITY * 2) {
      buffer.offer(i)
    }

    assertThat(buffer, hasSize(CAPACITY))
    assertThat(buffer.peek(), equalTo(CAPACITY))

    for (i in CAPACITY until  CAPACITY * 2) {
      assertThat(buffer.peek(), equalTo(i))
      assertThat(buffer.poll(), equalTo(i))
    }
  }

  @Test
  fun testIterator() {
    val buffer = RingBuffer<Int>()
    for (i in 0 until CAPACITY) {
      buffer.offer(i)
    }

    assertThat(buffer, hasSize(CAPACITY))

    val iterator = buffer.iterator()
    for (i in 0 until CAPACITY) {
      assertThat(iterator.hasNext(), equalTo(true))
      assertThat(iterator.next(), equalTo(i))
      iterator.remove()
    }

    assertThat(buffer, hasSize(0))
  }

  @Test
  fun testIteratorWrapAround() {
    val buffer = RingBuffer<Int>()
    for (i in 0 until CAPACITY + CAPACITY / 2) {
      buffer.offer(i)
    }

    assertThat(buffer, hasSize(CAPACITY))
    assertThat(buffer.peek(), equalTo(CAPACITY / 2))

    val iterator = buffer.iterator()
    for (i in 0 until CAPACITY) {
      assertThat(iterator.hasNext(), equalTo(true))
      assertThat(iterator.next(), equalTo(CAPACITY / 2 + i))
      iterator.remove()
    }

    assertThat(buffer, hasSize(0))
  }

  @Test
  fun testIteratorEmpty() {
    val buffer = RingBuffer<Int>()
    val iterator = buffer.iterator()
    assertThat(iterator.hasNext(), equalTo(false))

    try {
      iterator.next()
      fail()
    } catch (ex: NoSuchElementException) {
    }

    iterator.remove()
  }

  companion object {
    const val CAPACITY = 16
  }
}