Implement a Fixed-Size List in Scala

1. Overview

Data structures play a pivotal role in the world of programming. One such structure that often comes in handy is a fixed-size list. Unlike standard lists that can grow indefinitely, a fixed-size list has a set limit.

In this article, we’ll explore implementing a fixed-size list in Scala. In addition, we’ll talk about a practical application for fixed-size lists.

2. The Fixed-Size List

In Scala, there are various ways to write a fixed-size list. However, the scala.collection.mutable package has a class, ListBuffer, that is ideal for this task. We can use ListBuffer, and add code to enforce the size invariant.

When the add operation results in a list with more elements than the limit, the oldest added element will be automatically removed:

2.1. Minimal Implementation Using Composition

We might consider using inheritance to extend ListBuffer. However, this would expose all ListBuffer methods, potentially allowing users to break the size limit. Therefore, we opt for composition to better encapsulate the behavior:

import scala.collection.mutable.ListBuffer

class FixedSizeList[A](maxSize: Int) extends Iterable[A] {
  private val innerBuffer = new ListBuffer[A]

  def add(element: A): Unit = {
    innerBuffer += element
    while (innerBuffer.length > maxSize) innerBuffer.remove(0)
  }

  def contains(element: A): Boolean = innerBuffer.contains(element)

  def size: Int = innerBuffer.length

  def isEmpty: Boolean = innerBuffer.isEmpty
}

The previous code is minimal yet fully functional for many applications. If we need more methods, we must ensure they maintain the size limit invariant.

2.2. Enhancing Usability with Iterable

We can make our FixedSizeList class feel like a native collection by extending the Iterable trait.

This will allow us to use the class with for loops and add functional collection methods like map(), filter(), and more:

class FixedSizeList[A](maxSize: Int) extends Iterable[A] {
  // ... (previous code)
  
  override def iterator: Iterator[A] = innerBuffer.iterator
}

By extending the Iterable[A] trait and implementing the iterator method, we can now use the FixedSizeList in a for loop:

val fixedList = new FixedSizeList[Int](3)
fixedList.add(1)
fixedList.add(2)
fixedList.add(3)

for (elem <- fixedList) println(elem)  // Prints 1, 2, 3

We’ve created a secure and functional fixed-size list using composition and implementing the Iterable trait.

This approach is secure, versatile, and extensible, fitting many practical applications.

2.3. Alternative Implementation: Circular Buffer

A Circular Buffer, also known as a Ring Buffer, is an array-based data structure that uses two pointers to keep track of the start and end positions.

This makes it incredibly efficient for both reads and writes, offering O(1) time complexity for most operations.

In a Circular Buffer, we maintain an array and two pointers: one for the start and one for the end of the data. When we add an element, it goes to the position pointed to by the “end” pointer, which moves one part forward. If the buffer is complete, the “start” pointer moves one place forward, removing the oldest element.

Let’s look at a simple Scala implementation of a Circular Buffer:

class CircularBufferFixedSizeList[A](val maxSize: Int) extends Iterable[A] {
  private val buffer = Array.ofDim[Any](maxSize)
  private var start = 0
  private var end = 0

  def add(element: A): Unit = {
    buffer(end) = element
    end = (end + 1) % maxSize

    if (end == start) {
      start = (start + 1) % maxSize
    }
  }

  def get(index: Int): Option[A] = {
    if (index >= 0 && index < size) {
      Some(buffer((start + index) % maxSize).asInstanceOf[A])
    } else {
      None
    }
  }

  override def size: Int = {
    if (end >= start) end - start
    else maxSize - start + end
  }

  override def isEmpty: Boolean = start == end

  override def iterator: Iterator[A] = new Iterator[A] {
    private var pos = start

    override def hasNext: Boolean = pos != end

    override def next(): A = {
      val elem = buffer(pos).asInstanceOf[A]
      pos = (pos + 1) % maxSize
      elem
    }
  }
}

Using a Circular Buffer, we can create a time- and space-efficient fixed-size list, making it a solid alternative to other data structures for specific use cases.

3. Practical Application: Event Logging

In a typical application, various events occur, such as user actions, system errors, or data changes. Keeping a log of these events can be crucial for debugging and monitoring.

However, logging every single event could consume a lot of memory. A fixed-size list can be used to keep only the most recent events.

Let’s write a simple Scala implementation using our FixedSizeList:

class EventLogger(maxEvents: Int) {
  private val events = new FixedSizeList[String](maxEvents)

  def logEvent(event: String): Unit = {
    events.add(event)
  }

  def getRecentEvents: List[String] = {
    events.toList
  }
}

Next, let’s see it in action:

val logger = new EventLogger(5)  // Keep the last 5 events

logger.logEvent("User logged in")
logger.logEvent("File uploaded")
logger.logEvent("Error occurred")

println(logger.getRecentEvents)  // Output: List("User logged in", "File uploaded", "Error occurred")

The advantages of this approach are:

• Memory Efficiency: Using a fixed-size list ensures that the event log doesn’t grow indefinitely, thus saving memory.
• Quick Access: The most recent events are readily available for immediate inspection or debugging.
  Using a fixed-size list for event logging, we can create an efficient and effective solution for keeping track of the most recent events in a system.

4. Conclusion

In this article, we’ve delved into the concept of fixed-size lists and their implementation in Scala.

We explored different approaches, including using standard Scala collections and the pros and cons of inheritance versus composition.

We also discussed the importance of choosing the proper data structure for specific use cases, such as event logging.

As always, the complete source code of the article is available over on GitHub.