Arena

This package is very much work in progress.

Arena is an implementation of the generational arena data structure in Swift.

An Arena is useful for example for building data models with highly interdependent data (e.g. graphs).

Another example is data with the parent-child relationship. With the OOP approach, one would have to resort to using the weak which gets messy pretty fast.

So what's a generational arena? Think of it as an array which, unlike an array, has stable indices and which recycles indices.

What do we mean by stable indices? If you create an array with some elements, and then remove some elements, if you wanted to reference these elements by their indices, the indices you kept around are invalidated after you remove elements from the array.

With an Arena you can do the following:

var arena = Arena<Int>()
let idx0 = arena.insert(10)
let idx1 = arena.insert(20)

arena.remove(idx0)

assert(arena[idx1] == 20)

If we were using an array, we could theoretically only ever append new elements and if we remove elements, leave those slots empty but this would make the array grow very large in size very quickly.

Arena recycles indices so that the empty slots can be reused but if you have a dangling index (an index referencing a removed element) and then try to get the elements, you get a nil.

Arena performs lookups in O(1).

Here's an example of dealing with the parent child relationship.

import Arena

struct Node {
    var parent: Index
   ?
    
   var children: [
   Index
   
    ]
}


    var nodes 
    = Arena
    <Node
    >()


    let parentIndex 
    = nodes.
    insert(
    Node(
    parent: 
    nil, 
    children: []))


    let childIdx 
    = nodes.
    insert(
    Node(
    parent: parentIndex, 
    children: []))


    // the closure has mutable access to the element of the Arena

    nodes.
    transform(
    at: parentIndex) { 
    
    $0.
    children.
    append(childIdx)
}