Extension traits

Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

упр.08 задача 1

Предадени решения

Краен срок:
03.12.2025 23:59
Точки:
4

Срокът за предаване на решения е отминал

// Include the solution source in the same file, so we
// don't have to worry about item visibility.
// Please don't use `include!` in real code, this is a hack
// around the checking system.
include!{ "../src/lib.rs" }
fn s(s: &str) -> String {
s.to_string()
}
#[test]
fn test_list() {
let list = List::new();
assert_eq!(list.head(), None);
assert_eq!(list.tail().head(), None);
let list = list.prepend(s("one"));
assert_eq!(list.head(), Some(&s("one")));
assert_eq!(list.tail().head(), None);
let list = list.prepend(s("two")).prepend(s("three"));
assert_eq!(list.head(), Some(&s("three")));
let list = list.tail();
assert_eq!(list.head(), Some(&s("two")));
let list = list.tail();
assert_eq!(list.head(), Some(&s("one")));
let list = list.tail();
assert_eq!(list.head(), None);
}
#[test]
fn test_iterator() {
let list = List::new();
assert_eq!(list.iter().collect::<Vec<_>>(), Vec::<&String>::new());
let list = list.prepend(s("one")).prepend(s("two")).prepend(s("three"));
assert_eq!(
list.iter().collect::<Vec<_>>(),
vec![&s("three"), &s("two"), &s("one"),]
);
}

Забележка: погледнете слайдовете за Rc и RefCell преди да решавате задачата - линк

Имплементирайте структура от данни persistent linked list.

Persistent структурите от данни се различават с това, че са immutable и операциите върху тях не модифицират оригиналната структура, ами връщат нова обновена версия. Обикновенно новата версия преизползва памет от старата версия.

Имат предимства и недостатъци и са по-популярни в чисто функционалните езици, отколкото в Rust.
Персистентния свързан списък би изглеждал така:

list1 -> A ---v
list2 ------> B -> C -> D
list3 -> X ---^

Използвайте следната структура:

struct List<T> {
    head: Link<T>,
}

type Link<T> = Option<Rc<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

Имплементирайте следните методи върху List:

// Създава празен списък
fn new() -> Self

// Връща първия елемент от списъка
fn head(&self) -> Option<&T>

// Връща опашката на списъка - т.е. списък съдържащ
// всички елементи освен първия.
// Опашката на празен списък е празен списък.
fn tail(&self) -> List<T>

// Добавя елемент към списъка.
// Връща нов списък с първи елемент е `value` и
// опашка стария списък.
fn prepend(&self, value: T) -> List<T>

// Създава итератор по елементите на списъка.
// Итератора връща елементи от тип `&T`.
fn iter(&self) -> Iter<'_, T>

Имплементирайте trait Iterator за структурата Iter.
Итерацията не би трябвало да създава копия на Rc.
Опитайте се да работите с &Node<T> вместо Rc<Node<T>>.

Съвети:

  • внимавайте за конкретните типове на стойностите. Не забравяйте, че ако нещо не е ясно може да слагате експлицитен тип (let some_var: T =) като type assertion.
  • разгледайте какви методи има върху типовете. Някои примери, които могат да са ви полезни:
    • Option::as_ref: fn (&Option<T>) -> Option<&T>
    • Option::as_mut: fn (&mut Option<T>) -> Option<&mut T>
    • Option::map: fn (Option<T>, fn(T)->U) -> Option<U>
    • Option::take = std::mem::replace(&mut option_variable, None)

Бонус (1т.)
Помислете защо следния код гърми със fatal runtime error: stack overflow.
Имплементирайте решение.

fn main() {
    let mut list = List::new();
    for i in 0..1_000_000 {
        list = list.prepend(i);
    }
    std::mem::drop(list);
}

Задължително прочетете (или си припомнете): Указания за предаване на домашни

Погрижете се решението ви да се компилира с базовия тест:

// Include the solution source in the same file, so we
// don't have to worry about item visibility.
// Please don't use `include!` in real code, this is a hack
// around the checking system.
include!{ "../src/lib.rs" }
fn s(s: &str) -> String {
s.to_string()
}
#[test]
fn test_list() {
let list = List::new();
assert_eq!(list.head(), None);
assert_eq!(list.tail().head(), None);
let list = list.prepend(s("one"));
assert_eq!(list.head(), Some(&s("one")));
assert_eq!(list.tail().head(), None);
let list = list.prepend(s("two")).prepend(s("three"));
assert_eq!(list.head(), Some(&s("three")));
let list = list.tail();
assert_eq!(list.head(), Some(&s("two")));
let list = list.tail();
assert_eq!(list.head(), Some(&s("one")));
let list = list.tail();
assert_eq!(list.head(), None);
}
#[test]
fn test_iterator() {
let list = List::new();
assert_eq!(list.iter().collect::<Vec<_>>(), Vec::<&String>::new());
let list = list.prepend(s("one")).prepend(s("two")).prepend(s("three"));
assert_eq!(
list.iter().collect::<Vec<_>>(),
vec![&s("three"), &s("two"), &s("one"),]
);
}