Özel Veri Yapıları

Cairo'da programlamaya başladığınızda, veri koleksiyonlarını saklamak için dizileri (Array<T>) kullanmak isteyeceksiniz. Ancak, dizilerin bir büyük kısıtlaması olduğunu hızlıca fark edeceksiniz - içlerinde saklanan veriler değiştirilemez. Bir dizinin sonuna bir değer ekledikten sonra, bu değeri modifiye edemezsiniz.

Bu, değiştirilebilir bir veri yapısı kullanmak istediğinizde sinir bozucu olabilir. Örneğin, oyuncuların bir seviyesi olduğu ve seviye atlayabildikleri bir oyun yapıyorsunuz diyelim. Oyuncuların seviyelerini bir diziye saklamayı deneyebilirsiniz:

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

Ancak daha sonra, belirli bir indeksteki seviyeyi ayarlandıktan sonra artıramayacağınızı fark edersiniz. Bir oyuncu ölürse, ilk pozisyonda değilse, onu diziden çıkaramazsınız.

Şans eseri, Cairo değiştirilebilir veri yapılarının davranışını simüle etmemize izin veren Felt252Dict<T> adında kullanışlı yerleşik bir sözlük türü sunar. Önce, aralarında bir Felt252Dict<T> içeren bir yapı oluşturmayı inceleyelim.

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.

Struct Üyeleri Olarak Sözlükler

Cairo'da yapı üyeleri olarak sözlükleri tanımlamak mümkündür ancak onlarla doğru şekilde etkileşim kurmak tamamen sorunsuz olmayabilir. Kullanıcıları ekleyebileceğimiz ve sorgulayabileceğimiz özel bir kullanıcı veritabanı uygulamayı deneyelim. Yeni tipi temsil etmek için bir yapı ve işlevselliğini tanımlamak için bir özellik tanımlamamız gerekecek:

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

Yeni tipimiz UserDatabase<T>, kullanıcıların bir veritabanını temsil eder. Kullanıcıların bakiyeleri üzerinden genel olarak tanımlanmıştır, bu da veri tipimizi kullanan herkese büyük bir esneklik sağlar. İki üyesi vardır:

• users_updates, the number of users updates in the dictionary.
• balances, her bir kullanıcının bakiyesiyle eşleştirilmesi.

Veritabanının temel işlevselliği UserDatabaseTrait tarafından tanımlanır. Tanımlanan metodlar şunlardır:

• new, yeni UserDatabase türlerini kolayca oluşturmak için.
• update_user, veritabanındaki kullanıcıların bakiyelerini güncellemek için.
• get_balance, veritabanında kullanıcının bakiyesini bulmak için.

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, bir Felt252Dict<T>'den değerler almak için gereken Copy<T> trait'ini uygulamalıdır.
2. Bir sözlüğün tüm değer türleri Felt252DictValue<T>'i uygular, bizim genel türümüz de bunu yapmalıdır.
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();
    }
}

UserDatabase için Destruct<T>'yi uygulamak, tamamen işlevsel bir veritabanına sahip olmak için son adımımızdı. Şimdi bunu deneyebiliriz:

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

Öncelikle, değiştirilebilir dinamik dizimizin nasıl davranmasını istediğimiz hakkında düşünelim. Hangi işlemleri desteklemelidir?

It should:

• Sonuna öğe eklememize izin verin.
• Herhangi bir öğeye dizine göre erişelim.
• Bir öğenin değerini belirli bir dizinde ayarlamaya izin verir.
• Geçerli uzunluğu döndürür.

Bu arayüzü Cairo'daki gibi tanımlayabiliriz:

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

Verilerimizi saklamak için, indeks numaralarını (felts) değerlere eşleyen bir Felt252Dict<T> kullanacağız. Ayrıca, uzunluğu takip etmek için ayrı bir len alanı saklayacağız.

İşte yapımızın nasıl göründüğü. T türünü Nullable işaretçi içine sarıyoruz ki, Sözlükler bölümünde açıklandığı gibi, veri yapımızda herhangi bir T türünü kullanabilmemize izin verilsin:

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
    }
}

Bu vektörü değiştirilebilir kılan ana şey, veri yapımızda değerleri ayarlamak veya güncellemek için sözlüğe değerler ekleyebilmemizdir. Örneğin, belirli bir indeksteki değeri güncellemek için şunu yaparız:

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
    }
}

Bu, sözlükteki o indeksteki önceden var olan değerin üzerine yazar.

Diziler değiştirilemezken, sözlükler vektörler gibi değiştirilebilir veri yapıları "için ihtiyacımız olan esnekliği sağlar.

Arayüzün geri kalanının uygulanması basittir. Arayüzümüzde tanımlanan tüm metodların "uygulanması şu şekilde yapılabilir:

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

Şimdi ikinci bir örneğe ve onun uygulama detaylarına bakacağız: Bir Stack.

Bir Yığın, LIFO (Last-In, First-Out) bir koleksiyondur. Yeni bir elemanın ekleme ve mevcut bir elemanın çıkarma işlemi aynı uçta, yığının tepesi olarak temsil edilen yerde gerçekleşir.

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

• Yığının tepesine bir öğe ekleyin.
• Yığının tepesinden bir öğe çıkarın.
• Yığında hala eleman olup olmadığını kontrol edin.

Bu özelliklerden yola çıkarak aşağıdaki arayüzü tanımlayabiliriz:

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

Cairo'da Değiştirilebilir Bir Yığın Uygulamak

Cairo'da bir yığın veri yapısı oluşturmak için, yığının değerlerini saklamak ve üzerinde yineleme yapmak için yığının uzunluğunu takip etmek amacıyla bir usize alanı ile birlikte yine bir Felt252Dict<T> kullanabiliriz.

Stack yapısı şu şekilde tanımlanır:

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

Şimdi, ana fonksiyonlarımız olan push ve pop'un nasıl uygulandığını görelim.

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.

Özet

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.