Struktur Data Kustom

Ketika Anda pertama kali mulai memprogram di Cairo, Anda kemungkinan besar ingin menggunakan array (Array<T>) untuk menyimpan kumpulan data. Namun, Anda akan segera menyadari bahwa array memiliki satu keterbatasan besar - data yang disimpan di dalamnya bersifat tidak dapat diubah. Setelah Anda menambahkan nilai ke dalam array, Anda tidak dapat memodifikasinya.

Ini dapat menjadi frustrasi ketika Anda ingin menggunakan struktur data yang dapat diubah. Sebagai contoh, katakanlah Anda membuat sebuah game di mana para pemain memiliki level, dan mereka dapat naik level. Anda mungkin mencoba menyimpan level para pemain dalam sebuah array:

    let mut level_players = array![5, 1, 10];

Tetapi kemudian Anda menyadari bahwa Anda tidak dapat meningkatkan level di indeks tertentu setelah diatur. Jika seorang pemain mati, Anda tidak dapat menghapusnya dari array kecuali jika dia kebetulan berada di posisi pertama.

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 create a struct that contains, among others, a Felt252Dict<T>.

Note: Several concepts used in this chapter were already presented earlier in the book. We recommend checking out the following chapters if you need to revise them: Structs, Methods, Generic types, Traits.

Kamus sebagai Anggota Struktur

Mendefinisikan kamus sebagai anggota struktur memungkinkan dalam Cairo, tetapi berinteraksi dengan mereka dengan benar mungkin tidak sepenuhnya mulus. Mari mencoba mengimplementasikan basis data pengguna kustom yang akan memungkinkan kita menambahkan pengguna dan mengajukan pertanyaan kepada mereka. Kita akan perlu mendefinisikan sebuah struktur untuk mewakili tipe baru dan sebuah trait untuk menentukan fungsinya:

struct UserDatabase<T> {
    users_updates: u64,
    balances: Felt252Dict<T>,
}

trait UserDatabaseTrait<T> {
    fn new() -> UserDatabase<T>;
    fn update_user<+Drop<T>>(ref self: UserDatabase<T>, name: felt252, balance: T);
    fn get_balance<+Copy<T>>(ref self: UserDatabase<T>, name: felt252) -> T;
}

Tipe baru kita UserDatabase<T> mewakili basis data pengguna. Ini bersifat generik terhadap saldo pengguna, memberikan fleksibilitas utama kepada siapa pun yang menggunakan tipe data kita. Dua anggotanya adalah:

• users_updates, the number of users updates in the dictionary.
• balances, pemetaan setiap pengguna dengan saldo mereka.

Fungsionalitas inti basis data didefinisikan oleh UserDatabaseTrait. Metode-metode berikut didefinisikan:

• new untuk dengan mudah membuat tipe UserDatabase baru.
• update_user to update the balance of users in the database.
• get_balance untuk menemukan saldo pengguna dalam basis data.

The only remaining step is to implement each of the methods in UserDatabaseTrait, but since we are working with Generic types we also need to correctly establish the requirements of T so it can be a valid Felt252Dict<T> value type:

1. T harus mengimplementasikan Copy<T> karena ini diperlukan untuk mendapatkan nilai dari Felt252Dict<T>.
2. Semua tipe nilai dari kamus mengimplementasikan Felt252DictValue<T>, tipe generik kita juga seharusnya demikian.
3. To insert values, Felt252DictTrait<T> requires all value types to be droppable (implement the Drop<T> trait).

The implementation, with all restrictions in place, would be as follows:

impl UserDatabaseImpl<T, +Felt252DictValue<T>> of UserDatabaseTrait<T> {
    // Creates a database
    fn new() -> UserDatabase<T> {
        UserDatabase { users_updates: 0, balances: Default::default() }
    }

    // Get the user's balance
    fn get_balance<+Copy<T>>(ref self: UserDatabase<T>, name: felt252) -> T {
        self.balances.get(name)
    }

    // Add a user
    fn update_user<+Drop<T>>(ref self: UserDatabase<T>, name: felt252, balance: T) {
        self.balances.insert(name, balance);
        self.users_updates += 1;
    }
}

Our database implementation is almost complete, except for one thing: the compiler doesn't know how to make a UserDatabase<T> go out of scope, since it doesn't implement the Drop<T> trait, nor the Destruct<T> trait. Since it has a Felt252Dict<T> as a member, it cannot be dropped, so we are forced to implement the Destruct<T> trait manually (refer to the Ownership chapter for more information). Using #[derive(Destruct)] on top of the UserDatabase<T> definition won't work because of the use of Generic types in the struct definition. We need to code the Destruct<T> trait implementation by ourselves:

impl UserDatabaseDestruct<T, +Drop<T>, +Felt252DictValue<T>> of Destruct<UserDatabase<T>> {
    fn destruct(self: UserDatabase<T>) nopanic {
        self.balances.squash();
    }
}

Mengimplementasikan Destruct<T> untuk UserDatabase adalah langkah terakhir kita untuk mendapatkan basis data yang sepenuhnya fungsional. Sekarang kita bisa mencobanya:

use core::dict::Felt252Dict;

struct UserDatabase<T> {
    users_updates: u64,
    balances: Felt252Dict<T>,
}

trait UserDatabaseTrait<T> {
    fn new() -> UserDatabase<T>;
    fn update_user<+Drop<T>>(ref self: UserDatabase<T>, name: felt252, balance: T);
    fn get_balance<+Copy<T>>(ref self: UserDatabase<T>, name: felt252) -> T;
}

impl UserDatabaseImpl<T, +Felt252DictValue<T>> of UserDatabaseTrait<T> {
    // Creates a database
    fn new() -> UserDatabase<T> {
        UserDatabase { users_updates: 0, balances: Default::default() }
    }

    // Get the user's balance
    fn get_balance<+Copy<T>>(ref self: UserDatabase<T>, name: felt252) -> T {
        self.balances.get(name)
    }

    // Add a user
    fn update_user<+Drop<T>>(ref self: UserDatabase<T>, name: felt252, balance: T) {
        self.balances.insert(name, balance);
        self.users_updates += 1;
    }
}

impl UserDatabaseDestruct<T, +Drop<T>, +Felt252DictValue<T>> of Destruct<UserDatabase<T>> {
    fn destruct(self: UserDatabase<T>) nopanic {
        self.balances.squash();
    }
}

fn main() {
    let mut db = UserDatabaseTrait::<u64>::new();

    db.update_user('Alex', 100);
    db.update_user('Maria', 80);

    db.update_user('Alex', 40);
    db.update_user('Maria', 0);

    let alex_latest_balance = db.get_balance('Alex');
    let maria_latest_balance = db.get_balance('Maria');

    assert!(alex_latest_balance == 40, "Expected 40");
    assert!(maria_latest_balance == 0, "Expected 0");
}

Simulating a Dynamic Array with Dicts

Pertama, mari pertimbangkan bagaimana kita ingin array dinamis yang dapat diubah kita berperilaku. Operasi apa yang seharusnya didukungnya?

Seharusnya:

• 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.

Kita dapat mendefinisikan antarmuka ini di Cairo seperti:

trait MemoryVecTrait<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 MemoryVec as it is similar to the Vec<T> data structure in Rust.

Note: The core library of Cairo already includes a Vec<T> data structure, strictly used as a storage type in smart contracts. To differentiate our data structure from the core library's one, we named our implementation MemoryVec.

Implementing a Dynamic Array in Cairo

Untuk menyimpan data kita, kita akan menggunakan Felt252Dict<T> yang memetakan nomor indeks (felt) ke nilai. Kita juga akan menyimpan bidang terpisah len untuk melacak panjangnya.

Berikut tampilan struktur kita. Kami melingkupi tipe T dalam pointer Nullable untuk memungkinkan penggunaan setiap tipe T dalam struktur data kami, seperti dijelaskan dalam bagian Kamus:

use core::dict::Felt252Dict;
use core::nullable::NullableTrait;
use core::num::traits::WrappingAdd;

trait MemoryVecTrait<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;
}

struct MemoryVec<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize,
}

impl DestructMemoryVec<T, +Drop<T>> of Destruct<MemoryVec<T>> {
    fn destruct(self: MemoryVec<T>) nopanic {
        self.data.squash();
    }
}

impl MemoryVecImpl<T, +Drop<T>, +Copy<T>> of MemoryVecTrait<MemoryVec<T>, T> {
    fn new() -> MemoryVec<T> {
        MemoryVec { data: Default::default(), len: 0 }
    }

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

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

    fn push(ref self: MemoryVec<T>, value: T) -> () {
        self.data.insert(self.len.into(), NullableTrait::new(value));
        self.len.wrapping_add(1_usize);
    }
    fn set(ref self: MemoryVec<T>, index: usize, value: T) {
        assert!(index < self.len(), "Index out of bounds");
        self.data.insert(index.into(), NullableTrait::new(value));
    }
    fn len(self: @MemoryVec<T>) -> usize {
        *self.len
    }
}

Since we again have Felt252Dict<T> as a struct member, we need to implement the Destruct<T> trait to tell the compiler how to make MemoryVec<T> go out of scope.

use core::dict::Felt252Dict;
use core::nullable::NullableTrait;
use core::num::traits::WrappingAdd;

trait MemoryVecTrait<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;
}

struct MemoryVec<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize,
}

impl DestructMemoryVec<T, +Drop<T>> of Destruct<MemoryVec<T>> {
    fn destruct(self: MemoryVec<T>) nopanic {
        self.data.squash();
    }
}

impl MemoryVecImpl<T, +Drop<T>, +Copy<T>> of MemoryVecTrait<MemoryVec<T>, T> {
    fn new() -> MemoryVec<T> {
        MemoryVec { data: Default::default(), len: 0 }
    }

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

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

    fn push(ref self: MemoryVec<T>, value: T) -> () {
        self.data.insert(self.len.into(), NullableTrait::new(value));
        self.len.wrapping_add(1_usize);
    }
    fn set(ref self: MemoryVec<T>, index: usize, value: T) {
        assert!(index < self.len(), "Index out of bounds");
        self.data.insert(index.into(), NullableTrait::new(value));
    }
    fn len(self: @MemoryVec<T>) -> usize {
        *self.len
    }
}

Hal kunci yang membuat vektor ini dapat diubah adalah kita dapat menyisipkan nilai ke dalam kamus untuk mengatur atau memperbarui nilai dalam struktur data kita. Sebagai contoh, untuk memperbarui nilai pada indeks tertentu, kita lakukan:

use core::dict::Felt252Dict;
use core::nullable::NullableTrait;
use core::num::traits::WrappingAdd;

trait MemoryVecTrait<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;
}

struct MemoryVec<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize,
}

impl DestructMemoryVec<T, +Drop<T>> of Destruct<MemoryVec<T>> {
    fn destruct(self: MemoryVec<T>) nopanic {
        self.data.squash();
    }
}

impl MemoryVecImpl<T, +Drop<T>, +Copy<T>> of MemoryVecTrait<MemoryVec<T>, T> {
    fn new() -> MemoryVec<T> {
        MemoryVec { data: Default::default(), len: 0 }
    }

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

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

    fn push(ref self: MemoryVec<T>, value: T) -> () {
        self.data.insert(self.len.into(), NullableTrait::new(value));
        self.len.wrapping_add(1_usize);
    }
    fn set(ref self: MemoryVec<T>, index: usize, value: T) {
        assert!(index < self.len(), "Index out of bounds");
        self.data.insert(index.into(), NullableTrait::new(value));
    }
    fn len(self: @MemoryVec<T>) -> usize {
        *self.len
    }
}

Ini menimpa nilai yang sudah ada sebelumnya pada indeks tersebut dalam kamus.

Meskipun array bersifat tidak dapat diubah, kamus memberikan fleksibilitas yang kita butuhkan untuk struktur data yang dapat dimodifikasi seperti vektor.

Implementasi sisa antarmukanya cukup langsung. Implementasi semua metode yang didefinisikan dalam antarmuka kita dapat dilakukan sebagai berikut:

use core::dict::Felt252Dict;
use core::nullable::NullableTrait;
use core::num::traits::WrappingAdd;

trait MemoryVecTrait<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;
}

struct MemoryVec<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize,
}

impl DestructMemoryVec<T, +Drop<T>> of Destruct<MemoryVec<T>> {
    fn destruct(self: MemoryVec<T>) nopanic {
        self.data.squash();
    }
}

impl MemoryVecImpl<T, +Drop<T>, +Copy<T>> of MemoryVecTrait<MemoryVec<T>, T> {
    fn new() -> MemoryVec<T> {
        MemoryVec { data: Default::default(), len: 0 }
    }

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

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

    fn push(ref self: MemoryVec<T>, value: T) -> () {
        self.data.insert(self.len.into(), NullableTrait::new(value));
        self.len.wrapping_add(1_usize);
    }
    fn set(ref self: MemoryVec<T>, index: usize, value: T) {
        assert!(index < self.len(), "Index out of bounds");
        self.data.insert(index.into(), NullableTrait::new(value));
    }
    fn len(self: @MemoryVec<T>) -> usize {
        *self.len
    }
}

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

Simulating a Stack with Dicts

Sekarang kita akan melihat contoh kedua dan detail implementasinya: sebuah Stack.

Sebuah Stack adalah koleksi LIFO (Last-In, First-Out). Penyisipan elemen baru dan penghapusan elemen yang sudah ada terjadi di ujung yang sama, yang direpresentasikan sebagai puncak tumpukan.

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.
• Memeriksa apakah masih ada elemen di dalam stack.

Dari spesifikasi ini, kita dapat mendefinisikan antarmuka berikut:

trait StackTrait<S, T> {
    fn push(ref self: S, value: T);
    fn pop(ref self: S) -> Option<T>;
    fn is_empty(self: @S) -> bool;
}

Menerapkan Stack Yang Dapat Diubah di Cairo

Untuk membuat struktur data tumpukan (stack) di Cairo, kita dapat lagi menggunakan Felt252Dict<T> untuk menyimpan nilai-nilai tumpukan beserta sebuah bidang usize untuk melacak panjang tumpukan agar dapat melakukan iterasi atasnya.

Struktur data Stack didefinisikan sebagai berikut:

struct NullableStack<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize,
}

Selanjutnya, mari kita lihat bagaimana fungsi utama kami, push dan pop, diimplementasikan.

use core::dict::Felt252Dict;
use core::nullable::{match_nullable, FromNullableResult, NullableTrait};

trait StackTrait<S, T> {
    fn push(ref self: S, value: T);
    fn pop(ref self: S) -> Option<T>;
    fn is_empty(self: @S) -> bool;
}

struct NullableStack<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize,
}

impl DestructNullableStack<T, +Drop<T>> of Destruct<NullableStack<T>> {
    fn destruct(self: NullableStack<T>) nopanic {
        self.data.squash();
    }
}


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(), NullableTrait::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 to 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 decreases the value of len to update the position of the stack top and then retrieves the last value at position len.

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.

Ringkasan

Well done! Now you have knowledge of arrays, dictionaries and even custom data structures. 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.