Custom Data Structures

When you first start programming in Cairo, you'll likely want to use arrays (Array<T>) to store collections of data. However, you will quickly realize that arrays have one big limitation - the data stored in them is immutable. Once you append a value to an array, you can't modify it.

This can be frustrating when you want to use a mutable data structure. For example, say you're making a game where the players have a level, and they can level up. You might try to store the level of the players in an array:

let mut level_players = Array::new();
level_players.append(5);
level_players.append(1);
level_players.append(10);

But then you realize you can't increase the level at a specific index once it's set. If a player dies, you cannot remove it from the array unless he happens to be in the first position.

Fortunately, Cairo provides a handy built-in dictionary type called Felt252Dict<T> that allows us to simulate the behavior of mutable data structures. Let's first explore how to use it to create a dynamic array implementation.

Note: Several concepts used in this chapter are presented in later parts of the book. We recommend you to check out the following chapter first: Structs, Methods, Generic types, Traits

Simulating a dynamic array with dicts

First, let's think about how we want our mutable dynamic array to behave. What operations should it support?

It should:

Allow us to append items at the end
Let us access any item by index
Allow setting the value of an item at a specific index
Return the current length

We can define this interface in Cairo like:

#![allow(unused)]
fn main() {
trait VecTrait<V, T> {
    fn new() -> V;
    fn get(ref self: V, index: usize) -> Option<T>;
    fn at(ref self: V, index: usize) -> T;
    fn push(ref self: V, value: T) -> ();
    fn set(ref self: V, index: usize, value: T);
    fn len(self: @V) -> usize;
}
}

This provides a blueprint for the implementation of our dynamic array. We named it Vec as it is similar to the Vec<T> data structure in Rust.

Implementing a dynamic array in Cairo

To store our data, we'll use a Felt252Dict<T> which maps index numbers (felts) to values. We'll also store a separate len field to track the length.

Here is what our struct looks like. We wrap the type T inside Nullable pointer to allow using any type T in our data structure, as explained in the Dictionaries section:

#![allow(unused)]
fn main() {
struct NullableVec<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize
}
}

The key thing that makes this vector mutable is that we can insert values into the dictionary to set or update values in our data structure. For example, to update a value at a specific index, we do:

    fn set(ref self: NullableVec<T>, index: usize, value: T) {
        assert(index < self.len(), 'Index out of bounds');
        self.data.insert(index.into(), nullable_from_box(BoxTrait::new(value)));
    }

This overwrites the previously existing value at that index in the dictionary.

While arrays are immutable, dictionaries provide the flexibility we need for modifiable data structures like vectors.

The implementation of the rest of the interface is straightforward. The implementation of all the methods defined in our interface can be done as follow :

#![allow(unused)]
fn main() {
impl NullableVecImpl<T, +Drop<T>, +Copy<T>> of VecTrait<NullableVec<T>, T> {
    fn new() -> NullableVec<T> {
        NullableVec { data: Default::default(), len: 0 }
    }

    fn get(ref self: NullableVec<T>, index: usize) -> Option<T> {
        if index < self.len() {
            Option::Some(self.data.get(index.into()).deref())
        } else {
            Option::None
        }
    }

    fn at(ref self: NullableVec<T>, index: usize) -> T {
        assert(index < self.len(), 'Index out of bounds');
        self.data.get(index.into()).deref()
    }

    fn push(ref self: NullableVec<T>, value: T) -> () {
        self.data.insert(self.len.into(), nullable_from_box(BoxTrait::new(value)));
        self.len = integer::u32_wrapping_add(self.len, 1_usize);
    }
    fn set(ref self: NullableVec<T>, index: usize, value: T) {
        assert(index < self.len(), 'Index out of bounds');
        self.data.insert(index.into(), nullable_from_box(BoxTrait::new(value)));
    }
    fn len(self: @NullableVec<T>) -> usize {
        *self.len
    }
}
}

The full implementation of the Vec structure can be found in the community-maintained library Alexandria.

Simulating a Stack with dicts

We will now look at a second example and its implementation details: a Stack.

A Stack is a LIFO (Last-In, First-Out) collection. The insertion of a new element and removal of an existing element takes place at the same end, represented as the top of the stack.

Let us define what operations we need to create a stack :

Push an item to the top of the stack
Pop an item from the top of the stack
Check whether there are still any elements in the stack.

From these specifications we can define the following interface :

#![allow(unused)]
fn main() {
trait StackTrait<S, T> {
    fn push(ref self: S, value: T);
    fn pop(ref self: S) -> Option<T>;
    fn is_empty(self: @S) -> bool;
}
}

Implementing a Mutable Stack in Cairo

To create a stack data structure in Cairo, we can again use a Felt252Dict<T> to store the values of the stack along with a usize field to keep track of the length of the stack to iterate over it.

The Stack struct is defined as:

#![allow(unused)]
fn main() {
struct NullableStack<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize,
}
}

Next, let's see how our main functions push and pop are implemented.

#![allow(unused)]
fn main() {
impl NullableStackImpl<T, +Drop<T>, +Copy<T>> of StackTrait<NullableStack<T>, T> {
    fn push(ref self: NullableStack<T>, value: T) {
        self.data.insert(self.len.into(), nullable_from_box(BoxTrait::new(value)));
        self.len += 1;
    }

    fn pop(ref self: NullableStack<T>) -> Option<T> {
        if self.is_empty() {
            return Option::None;
        }
        self.len -= 1;
        Option::Some(self.data.get(self.len.into()).deref())
    }

    fn is_empty(self: @NullableStack<T>) -> bool {
        *self.len == 0
    }
}
}

The code uses the insert and get methods to access the values in the Felt252Dict<T>. To push an element at the top of the stack, the push function inserts the element in the dict at index len - and increases the len field of the stack to keep track of the position of the stack top. To remove a value, the pop function retrieves the last value at position len-1 and then decreases the value of len to update the position of the stack top accordingly.

The full implementation of the Stack, along with more data structures that you can use in your code, can be found in the community-maintained Alexandria library, in the "data_structures" crate.

Summary

While Cairo's memory model is immutable and can make it difficult to implement mutable data structures, we can fortunately use the Felt252Dict<T> type to simulate mutable data structures. This allows us to implement a wide range of data structures that are useful for many applications, effectively hiding the complexity of the underlying memory model.

The Cairo Programming Language