Instruções
Escreve uma lista duplamente ligada em Rust unsafe, incluindo um iterador sobre a lista
e um cursor para fazer mutações de forma eficiente.
A lista duplamente ligada é uma estrutura de dados fundamental em ciência de computadores.
Cada nó de uma lista duplamente ligada contém dados e ponteiros para o nó seguinte
e para o anterior, se existirem.
É possível adicionar novos nós de forma eficiente em qualquer ponto da lista, desde que já
se tenha uma referência para essa posição. Da mesma forma, é possível inserir todos os
elementos de outra lista em qualquer ponto, em tempo constante.
Em Rust, as listas ligadas são usadas muito raramente, mas de vez em quando apanham os
principiantes de surpresa, quando estes tentam implementar uma. Muitas vezes, acham
inesperadamente difícil trabalhar com o ainda desconhecido borrow checker.
Uma nota sobre unsafe
Lembra-te de que o objetivo do Rust unsafe é escrever código seguro nos casos em que o compilador não nos
pode ajudar a garantir a correção. Não pode ser possível que um utilizador cause insegurança de memória de
qualquer tipo usando apenas as interfaces seguras que expomos.
Documenta os invariantes críticos para a segurança que precisas de manter e comenta cada bloco unsafe,
explicando porque é seguro.
Qualquer função em que quem chama tem de manter invariantes críticos para a segurança deve ser marcada como
unsafe. Isto inclui as funções privadas.
Passo 1
Implementa a funcionalidade de adicionar e remover elementos (push e pop)
à frente e atrás. Isto é suficiente para usar a lista como uma fila de dupla extremidade.
Implementa também as funções len e is_empty.
Na implementação final, todas as modificações da lista devem ser feitas através da estrutura cursor,
para minimizar a duplicação. Os métodos push_* e pop_* de LinkedList
são definidos em termos dos métodos de cursor necessários, no módulo pre_implemented. Se quiseres,
podes ignorar a estrutura Cursor por agora e substituir os métodos, mas volta a pô-los como estavam no fim.
Passo 2
Implementa a iteração sobre a lista de frente para trás com a estrutura Iter.
Passo 3
Completa a funcionalidade do cursor. Deve conseguir mover-se para qualquer posição e inserir ou remover elementos nessa posição.
Passo 4
Implementa o trait Drop para a tua LinkedList, para libertar recursos.
Passo 5 (avançado e opcional)
Os testes para estas duas últimas coisas são compilados condicionalmente através da flag de funcionalidades advanced.
Adiciona a chave default = ["advanced"] ao ficheiro Cargo.toml, em [features], para as ativar.
Para dar aos utilizadores da tua estrutura a máxima flexibilidade, certifica-te de que a tua LinkedList<T> é covariante em T.
Isto significa, por exemplo, que uma LinkedList<&'static T> também pode ser usada como uma LinkedList<&'a T>.
Vê o Rustonomicon para uma explicação da variância em Rust.
Certifica-te de que a tua lista é segura de enviar e partilhar entre threads
e comunica isso ao sistema de tipos implementando Send e Sync manualmente.
Estes traits são normalmente derivados automaticamente, mas aqui não são implementados de forma automática, devido ao uso de
ponteiros em bruto. Vê a documentação de Send e Sync e o capítulo do Rustonomicon sobre eles, para mais detalhes sobre o seu significado.
