<commit_before>\documentclass[../../main.tex]{subfiles}

\begin{document}

\chapter{Técnicas gerais} \label{cap:geral}

Nos capítulos anteriores, discutimos como tornar estruturas de dados específicas (pilhas, filas, deques) persistentes. Como dito na introdução, outro caminho é criar técnicas gerais para tornar qualquer ED persistente.

%Apresentaremos uma técnica chamada \deff{Node Copying}, que permite tornar EDs parcialmente persistentes sem tornar seu tempo assintoticamente pior, ou seja, com overhead de~$\Oh(1)$.  Esta técnica foi inicialmente discutida por Driscoll, Sarnak, Sleator e Tarjan~\cite{DriscollSST1989}.

\section{Modelo de computação}

Para tomar uma abordagem tão geral, é necessário definir formalmente uma estrutura de dados.  Usaremos o modelo de~\deff{estruturas ligadas}, no qual uma estrutura de dados é um conjunto de \emph{nós}, ou \emph{objetos}, cada um contendo um número constante de campos. Cada campo pode armazenar um valor (um inteiro ou booleano, por exemplo) ou um ponteiro para outro nó. Ponteiros também podem armazenar o valor especial~\keyword{null}.  Acesso à estrutura é dado por um número constante de~\deff{nós de entrada}.

% XXX Preciso assumir que todos os nós são do mesmo tipo?

Uma pilha implementada com lista ligada, como no Capítulo~\ref{cap:pilha}, é uma estrutura desse tipo, onde o primeiro elemento da lista é o nó de entrada. A estrutura recursiva para deques do Capítulo~\ref{cap:deque2} também é dessa forma, e tem nós de~2 tipos, os nós da estrutura, e nós que são os pares. O nó de entrada também é o primeiro nó da estrutura.  Uma árvore de busca binária também é deste tipo, já que cada nó tem dois ponteiros (para o filho esquerdo e direito), e um valor; e a raiz é o nó de entrada.  A estrutura para deque do Capítulo~\ref{cap:deque1} não é deste tipo, pois o preprocessamento para o LA armazena em cada nó um vetor de tamanho~$\floor{\lg d}$, onde~$d$ é a altura do nó.

Vamos formalizar também as definições de operações de acesso e modificação. Uma~\deff{operação de acesso} produz um~\deff{conjunto de acesso}. No início da operação, este conjunto está vazio.  A cada passo, chamado de~\deff{passo de acesso}, adiciona-se um nó a este conjunto. O nó adicionado deve ser um nó de entrada ou deve ser indicado por um ponteiro em algum nó já no conjunto de acesso. O tempo consumido por uma operação de acesso é o número de passos de acesso. Operações também retornam valores, calculados usando seu conjunto de acesso.

A busca em uma ABB por um elemento é um exemplo de operação de acesso, que retorna se o elemento está ou não na ABB. Um exemplo mais complicado é a operação~\textsc{k-th} da deque recursiva, que primeiro encontra o nó da estrutura em que se localiza o $k$-ésimo elemento, e depois ``descasca'' os pares para encontrar e retornar este elemento.

Uma~\deff{operação de modificação} é parecida com uma de acesso. Ela consiste de passos de acesso, que funcionam da mesma forma, e~\deff{passos de modificação}. Em um passo de modificação, cria-se um novo nó, e este é adicionado ao conjunto de acesso, ou modifica-se um campo de algum nó do conjunto de acesso, ou modifica-se um nó de entrada. Se um ponteiro foi modificado, seu novo valor deve ser~\keyword{null} ou deve ser algum ponteiro do conjunto de acesso. O tempo consumido por esta operação é o número de passos, e o tempo de modificação é o número de passos de modificação.

Adicionar um elemento em uma ABB, por exemplo, consiste de achar sua posição, que pode levar até~$h$ passos de acesso, onde~$h$ é a altura da árvore, e criar um novo vértice ali, modificando um dos ponteiros desse nó. Logo esta operação consome tempo~$\Oh(h)$ e tempo de modificação~$\Oh(1)$.

Essas definições descrevem uma estrutura de dados efêmera, ou seja, operações de acesso e modificação podem apenas ser feitas na versão mais atual da estrutura. Nosso objetivo é tornar esta estrutura genérica em uma estrutura total ou parcialmente persistente.

Consideramos que o número total de operações de modificação é~$m$, e o número de operações de acesso é~$a$. Da mesma forma, o número total de passos de modificação é~$M$ e de passos de acesso é~$A$. A $i$-ésima operação de moficicação cria a versão~$i$ da estrutura. A versão~0 é a estrutura vazia. Se estamos considerando uma estrutura totalmente persistente, temos uma árvore de versões, caso contrário, uma lista.

Consideramos que cada operação recebe, além de seus parâmetros normais, também um inteiro que indica sob qual versão deve ser feita essa operação. Dizemos que~$i \rightarrow j$ se a operação que cria a versão~$j$ é feita sobre a versão~$i$.

Note que assumimos que a estrutura se encontra nesse modelo, mas nossas soluções podem não estar. Por exemplo, é muito comum armazenar um vetor com os nós de entrada para cada versão.

\section{Off-line}

Em geral, estamos interessados em implementações on-line das estruturas persistentes, ou seja, uma operação deve ser completada para se ter acesso à próxima, porém, vamos considerar o caso off-line, em que todas as~$m+a$ operações são conhecidas de antemão. Obteremos uma implementação totalmente persistente que não faz nenhuma suposição adicional sobre a estrutura de dados, não aumenta assintoticamente o tempo consumido pelas operações, e gasta apenas~$\Oh(1)$ de espaço adicional por passo de modificação, o melhor que pode-se esperar.

Inicialmente, constrói-se o grafo de versões. Em cada vértice desse grafo deve-se armazenar, além dos outros dados necessários (como uma lista de adjacência), a operação de modificação que criou aquela versão (seus parâmetros), e uma lista das operações de acesso que são feitas naquela versão. Isso pode ser feito em tempo~$\Oh(m+a)$, armazenando um vetor de nós, indexados pelo seu número de versão. O nó relacionado à~$i$-ésima versão é~$v_i$.

Queremos realizar uma busca em profundidade (DFS) nesta árvore, seguindo a seguinte ideia:
\begin{enumerate}
	\item Ao acessar um nó~$v_i$ pela DFS, a estrutura está na versão~$j$, onde~$j \rightarrow i$.
	\item Aplicamos a operação, transformando a versão em~$i$, e calculamos os retornos para as operações de acesso feitas em~$i$ e em todas as versões descendentes de~$i$.
	\item Ao final do acesso do nó~$v_i$, revertemos as mudanças feitas e a estrutura está novamente na versão~$j$.
\end{enumerate}

Dessa forma, no passo~2 podemos acessar os nós que são filhos de~$v_i$ recursivamente, já que, devido ao passo~3, quando o acesso a eles terminar, a versão da será a versão~$i$, e no passo~3 de~$v_i$ basta reverter as mudanças feitas nessa versão.

Para reverter mudanças de forma genérica, sempre que um passo de modificação altera um campo de um objeto, guardamos uma tripla~$(\V{obj}, \V{field}, \V{oldValue})$ indicando que o campo~$\V{field}$ do objeto~$\V{val}$ mudou de valor, e seu valor anterior era~$\V{oldValue}$. Isso é informação o bastante para, ao final do procedimento, reverter essa mudança. Se o passo de modificação altera um nó de entrada, este também pode ser armazenado desta forma.

Como não impusemos restrições nas operações de mudança, elas podem modificar um mesmo campo muitas vezes, logo é necessário que o valor original seja restaurado, e não um valor intermediário. Para isso, desfazemos as mudanças na ordem inversa que foram feitas, usando uma pilha.

\begin{algorithm}
\caption{Persistência total off-line} \label{lst:geraloffline}
\begin{algorithmic}[1]

\Function{DFS}{$v_i$}
	\State $\V{mod} = \Call{Stack}{\null}$
	\State Aplicar a $i$-ésima operação de modificação, guardando valores antigos em~$\V{mod}$.
	\State Responder todas as operações de acesso realizadas na versão~$i$. \label{line:off:opac}
	\For{$v_j \in$ lista de adjacência de $v_i$} \label{line:off:for}
		\State \Call{DFS}{$v_j$}
	\EndFor
	\While{$\V{mod}.\Call{Size}{\null} > 0$} \label{line:off:while}
		\State $(\V{obj}, \V{field}, \V{oldValue}) = \V{mod}.\Call{Pop}{\null}$
		\State $\V{obj}.\V{field} = \V{oldValue}$
	\EndWhile
\EndFunction

\Function{TotalPersistenceOffline}{\null}
	\State Montar o grafo de versões.
	\State \Call{DFS}{$v_0$}
\EndFunction

\end{algorithmic}
\end{algorithm}

O Código~\ref{lst:geraloffline} mostra uma implementação, em alto nível, do algoritmo discutido. Assumimos que, ao realizar uma operação, seu valor de retorno seja armazenado em algum lugar. A operação na linha~\nref{line:off:opac} deve iterar pela lista de operações de acesso no vértice~$v_i$ e aplicá-las.

\begin{proposition}
	Se a função~{\normalfont \Call{DFS}{$v_i$}} é chamada com a estrutura de dados na versão~$j$, onde~${j \rightarrow i}$, então ela aplica corretamente todas as operações de acesso de alguma versão cujo nó é descendente de~$v_i$. Além disso, ao final da execução da função, a versão da estrutura é~$j$.
\end{proposition}

\begin{proof}
A prova é por indução na altura de~$v_i$. No início da função, estamos na versão~$j$, então ao aplicar a operação~$i$, a estrutura muda para a versão~$i$. Além disso, todas as mudanças para reverter a versão~$i$ para~$j$ estão armazenadas em~$\V{mod}$.

A linha~\nref{line:off:opac} aplica as operações de acesso da versão~$i$. O~\keyword{for} da linha~\nref{line:off:for} chama, para cada filho de~$v_i$, a função~\textsc{DFS} deste. Seja~$v_x$ o primeiro filho acessado; pela hipótese de indução, como~$v_x$ tem altura menor que~$v_i$ e a estrutura está na versão~$i$ e~${i \rightarrow x}$, temos que a função aplica corretamente as operações de acesso das versões na sub-árvore de~$v_x$, e ao final da chamada desta, a estrutura está novamente no estado~$i$.

Dessa forma, as chamadas da função~\textsc{DFS} para todos os filhos de~$v_i$ são corretas, e por isso as operações de acesso de todos os descendentes de~$v_i$ são realizadas. Por último, o~\keyword{while} da linha~\nref{line:off:while} desfaz as mudanças feitas na versão~$i$ e retorna a estrutura para a versão~$j$, completando a prova.
\end{proof}

Então, é possível transformar qualquer estrutura ligada em totalmente persistente, de forma off-line, com overhead de consumo de tempo de~$\Oh(M+A)$ e~$\Oh(M)$ de espaço.

\section{Implementação funcional}

A técnica que usamos nas estruturas apresentadas até agora é tornar a implementação funcional, ou seja, nunca modificar nenhum campo de um nó já criado.

Se for possível implementar a estrutura desta forma, ela se torna totalmente persistente. Pois, se temos os nós de entrada da versão~$i$, e nenhum nó foi modificado, os nós que podem ser acessados a partir desses são exatamente os mesmos de quando a versão~$i$ foi criada, independente de versões criadas posteriormente. Logo, apenas armazenando os nós de entrada (e não apagando nenhum nó), tornamos nossa estrutura totalmente persistente.

Algumas estruturas ligadas já funcionam naturalmente dessa forma, como por exemplo a pilha implementada no Capítulo~\ref{cap:pilha}, nunca é necessário alterar nenhum nó. Quando a estrutura não funciona dessa forma, é possível tentar ``forçar'' isso. Durante operações de modificação podemos, ao adicionar um nó ao conjunto de acesso, adicionar na verdade uma cópia desse nó, já que ela pode vir a ser modificada por um passo de modificação.

A estrutura recursiva de deque do Capítulo~\ref{cap:deque2} faz isso, copiando todos os nós acessados durante um~\textsc{Push} ou~\textsc{Pop}. Isso sempre deixa a implementação funcional, já que não modificamos nenhum nó; porém, isso pode deixar a implementação inválida, já que pode ser possível alcançar a versão antiga de um nó que já foi copiado. Este foi o problema encontrado na implementação da deque de Kaplan e Tarjan, já que na primeira ideia de implementação, era possível acessar a versão antiga de um nó, como discutido na Seção~\ref{sec:implfunc}.

Esta técnica, de copiar todos os nós adicionados ao conjunto de acesso, funciona apenas se não existem nós atingíveis que não estão no conjunto de acesso e tem ponteiro para algum elemento cuja cópia está no conjunto de acesso. Se existe algum nó~$u$ desse tipo, então existe um caminho para~$u$, ou seja, uma sequência de passos de acesso que adicionam~$u$ ao conjunto de acesso, pois ele é atingível; e com mais um passo de acesso é possível adicionar a versão antiga do nó ao conjunto de acesso, que pode ter informação desatualizada.

Se os nós de estrutura formam uma árvore, como no caso da pilha e da deque recursiva, ou mesmo árvores binárias, então esse método pode ser aplicado. Na Seção~\ref{sec:implfunc}, a estrutura foi modificada para ser uma árvore, e dessa forma essa técnica poder ser aplicada.

Se a estrutura segue essas restrições, esse método torna estrutura totalmente persistente com overhead de consumo de tempo de~$\Oh(M+A)$ e espaço~$\Oh(M+A_m)$, onde~$A_m$ é o número de passos de acesso que ocorrem durante operações de modificação, já que é necessário copiar o nó mesmo que este não vá ser modificado.

\end{document}<commit_msg>Fat node + node copying WIP<commit_after>\documentclass[../../main.tex]{subfiles}

\begin{document}

\chapter{Técnicas gerais} \label{cap:geral}

Nos capítulos anteriores, discutimos como tornar estruturas de dados específicas (pilhas, filas, deques) persistentes. Como dito na introdução, outro caminho é criar técnicas gerais para tornar qualquer ED persistente.


\section{Modelo de computação}

Para tomar uma abordagem tão geral, é necessário definir formalmente uma estrutura de dados.  Usaremos o modelo de~\deff{estruturas ligadas}, no qual uma estrutura de dados é um conjunto de \emph{nós}, ou \emph{objetos}, cada um contendo um número constante de campos. Cada campo pode armazenar um valor (um inteiro ou booleano, por exemplo) ou um ponteiro para outro nó. Ponteiros também podem armazenar o valor especial~\keyword{null}.  Acesso à estrutura é dado por um número constante de~\deff{nós de entrada}.

% XXX Preciso assumir que todos os nós são do mesmo tipo?

Uma pilha implementada com lista ligada, como no Capítulo~\ref{cap:pilha}, é uma estrutura desse tipo, onde o primeiro elemento da lista é o nó de entrada. A estrutura recursiva para deques do Capítulo~\ref{cap:deque2} também é dessa forma, e tem nós de~2 tipos, os nós da estrutura, e nós que são os pares. O nó de entrada também é o primeiro nó da estrutura.  Uma árvore de busca binária também é deste tipo, já que cada nó tem dois ponteiros (para o filho esquerdo e direito), e um valor; e a raiz é o nó de entrada.  A estrutura para deque do Capítulo~\ref{cap:deque1} não é deste tipo, pois o preprocessamento para o LA armazena em cada nó um vetor de tamanho~$\floor{\lg d}$, onde~$d$ é a altura do nó.

Vamos formalizar também as definições de operações de acesso e modificação. Uma~\deff{operação de acesso} produz um~\deff{conjunto de acesso}. No início da operação, este conjunto está vazio.  A cada passo, chamado de~\deff{passo de acesso}, adiciona-se um nó a este conjunto. O nó adicionado deve ser um nó de entrada ou deve ser indicado por um ponteiro em algum nó já no conjunto de acesso. O tempo consumido por uma operação de acesso é o número de passos de acesso. Operações também retornam valores, calculados usando seu conjunto de acesso.

A busca em uma ABB por um elemento é um exemplo de operação de acesso, que retorna se o elemento está ou não na ABB. Um exemplo mais complicado é a operação~\textsc{k-th} da deque recursiva, que primeiro encontra o nó da estrutura em que se localiza o $k$-ésimo elemento, e depois ``descasca'' os pares para encontrar e retornar este elemento.

Uma~\deff{operação de modificação} é parecida com uma de acesso. Ela consiste de passos de acesso, que funcionam da mesma forma, e~\deff{passos de modificação}. Em um passo de modificação, cria-se um novo nó, e este é adicionado ao conjunto de acesso, ou modifica-se um campo de algum nó do conjunto de acesso, ou modifica-se um nó de entrada. Se um ponteiro foi modificado, seu novo valor deve ser~\keyword{null} ou deve ser algum ponteiro do conjunto de acesso. O tempo consumido por esta operação é o número de passos, e o tempo de modificação é o número de passos de modificação.

Adicionar um elemento em uma ABB, por exemplo, consiste de achar sua posição, que pode levar até~$h$ passos de acesso, onde~$h$ é a altura da árvore, e criar um novo vértice ali, modificando um dos ponteiros desse nó. Logo esta operação consome tempo~$\Oh(h)$ e tempo de modificação~$\Oh(1)$.

Essas definições descrevem uma estrutura de dados efêmera, ou seja, operações de acesso e modificação podem apenas ser feitas na versão mais atual da estrutura. Nosso objetivo é tornar esta estrutura genérica em uma estrutura total ou parcialmente persistente.

Consideramos que o número total de operações de modificação é~$m$, e o número de operações de acesso é~$a$. Da mesma forma, o número total de passos de modificação é~$M$ e de passos de acesso é~$A$. A $i$-ésima operação de moficicação cria a versão~$i$ da estrutura. A versão~0 é a estrutura vazia. Se estamos considerando uma estrutura totalmente persistente, temos uma árvore de versões, caso contrário, uma lista.

Consideramos que cada operação recebe, além de seus parâmetros normais, também um inteiro que indica sob qual versão deve ser feita essa operação. Dizemos que~$i \rightarrow j$ se a operação que cria a versão~$j$ é feita sobre a versão~$i$.

Note que assumimos que a estrutura se encontra nesse modelo, mas nossas soluções podem não estar. Por exemplo, é muito comum armazenar um vetor com os nós de entrada para cada versão.

\section{Off-line}

Em geral, estamos interessados em implementações on-line das estruturas persistentes, ou seja, uma operação deve ser completada para se ter acesso à próxima, porém, vamos considerar o caso off-line, em que todas as~$m+a$ operações são conhecidas de antemão. Obteremos uma implementação totalmente persistente que não faz nenhuma suposição adicional sobre a estrutura de dados, não aumenta assintoticamente o tempo consumido pelas operações, e gasta apenas~$\Oh(1)$ de espaço adicional por passo de modificação, o melhor que pode-se esperar.

Inicialmente, constrói-se o grafo de versões. Em cada vértice desse grafo deve-se armazenar, além dos outros dados necessários (como uma lista de adjacência), a operação de modificação que criou aquela versão (seus parâmetros), e uma lista das operações de acesso que são feitas naquela versão. Isso pode ser feito em tempo~$\Oh(m+a)$, armazenando um vetor de nós, indexados pelo seu número de versão. O nó relacionado à~$i$-ésima versão é~$v_i$.

Queremos realizar uma busca em profundidade (DFS) nesta árvore, seguindo a seguinte ideia:
\begin{enumerate}
	\item Ao acessar um nó~$v_i$ pela DFS, a estrutura está na versão~$j$, onde~$j \rightarrow i$.
	\item Aplicamos a operação, transformando a versão em~$i$, e calculamos os retornos para as operações de acesso feitas em~$i$ e em todas as versões descendentes de~$i$.
	\item Ao final do acesso do nó~$v_i$, revertemos as mudanças feitas e a estrutura está novamente na versão~$j$.
\end{enumerate}

Dessa forma, no passo~2 podemos acessar os nós que são filhos de~$v_i$ recursivamente, já que, devido ao passo~3, quando o acesso a eles terminar, a versão da será a versão~$i$, e no passo~3 de~$v_i$ basta reverter as mudanças feitas nessa versão.

Para reverter mudanças de forma genérica, sempre que um passo de modificação altera um campo de um objeto, guardamos uma tripla~$(\V{obj}, \V{field}, \V{oldValue})$ indicando que o campo~$\V{field}$ do objeto~$\V{val}$ mudou de valor, e seu valor anterior era~$\V{oldValue}$. Isso é informação o bastante para, ao final do procedimento, reverter essa mudança. Se o passo de modificação altera um nó de entrada, este também pode ser armazenado desta forma.

Como não impusemos restrições nas operações de mudança, elas podem modificar um mesmo campo muitas vezes, logo é necessário que o valor original seja restaurado, e não um valor intermediário. Para isso, desfazemos as mudanças na ordem inversa que foram feitas, usando uma pilha.

\begin{algorithm}
\caption{Persistência total off-line} \label{lst:geraloffline}
\begin{algorithmic}[1]

\Function{DFS}{$v_i$}
	\State $\V{mod} = \Call{Stack}{\null}$
	\State Aplicar a $i$-ésima operação de modificação, guardando valores antigos em~$\V{mod}$.
	\State Responder todas as operações de acesso realizadas na versão~$i$. \label{line:off:opac}
	\For{$v_j \in$ lista de adjacência de $v_i$} \label{line:off:for}
		\State \Call{DFS}{$v_j$}
	\EndFor
	\While{$\V{mod}.\Call{Size}{\null} > 0$} \label{line:off:while}
		\State $(\V{obj}, \V{field}, \V{oldValue}) = \V{mod}.\Call{Pop}{\null}$
		\State $\V{obj}.\V{field} = \V{oldValue}$
	\EndWhile
\EndFunction

\Function{TotalPersistenceOffline}{\null}
	\State Montar o grafo de versões.
	\State \Call{DFS}{$v_0$}
\EndFunction

\end{algorithmic}
\end{algorithm}

O Código~\ref{lst:geraloffline} mostra uma implementação, em alto nível, do algoritmo discutido. Assumimos que, ao realizar uma operação, seu valor de retorno seja armazenado em algum lugar. A operação na linha~\nref{line:off:opac} deve iterar pela lista de operações de acesso no vértice~$v_i$ e aplicá-las.

\begin{proposition}
	Se a função~{\normalfont \Call{DFS}{$v_i$}} é chamada com a estrutura de dados na versão~$j$, onde~${j \rightarrow i}$, então ela aplica corretamente todas as operações de acesso de alguma versão cujo nó é descendente de~$v_i$. Além disso, ao final da execução da função, a versão da estrutura é~$j$.
\end{proposition}

\begin{proof}
A prova é por indução na altura de~$v_i$. No início da função, estamos na versão~$j$, então ao aplicar a operação~$i$, a estrutura muda para a versão~$i$. Além disso, todas as mudanças para reverter a versão~$i$ para~$j$ estão armazenadas em~$\V{mod}$.

A linha~\nref{line:off:opac} aplica as operações de acesso da versão~$i$. O~\keyword{for} da linha~\nref{line:off:for} chama, para cada filho de~$v_i$, a função~\textsc{DFS} deste. Seja~$v_x$ o primeiro filho acessado; pela hipótese de indução, como~$v_x$ tem altura menor que~$v_i$ e a estrutura está na versão~$i$ e~${i \rightarrow x}$, temos que a função aplica corretamente as operações de acesso das versões na sub-árvore de~$v_x$, e ao final da chamada desta, a estrutura está novamente no estado~$i$.

Dessa forma, as chamadas da função~\textsc{DFS} para todos os filhos de~$v_i$ são corretas, e por isso as operações de acesso de todos os descendentes de~$v_i$ são realizadas. Por último, o~\keyword{while} da linha~\nref{line:off:while} desfaz as mudanças feitas na versão~$i$ e retorna a estrutura para a versão~$j$, completando a prova.
\end{proof}

Então, é possível transformar qualquer estrutura ligada em totalmente persistente, de forma off-line, com overhead de consumo de tempo de~$\Oh(M+A)$ e~$\Oh(M)$ de espaço.

\section{Implementação funcional}

A técnica que usamos nas estruturas apresentadas até agora é tornar a implementação funcional, ou seja, nunca modificar nenhum campo de um nó já criado.

Se for possível implementar a estrutura desta forma, ela se torna totalmente persistente. Pois, se temos os nós de entrada da versão~$i$, e nenhum nó foi modificado, os nós que podem ser acessados a partir desses são exatamente os mesmos de quando a versão~$i$ foi criada, independente de versões criadas posteriormente. Logo, apenas armazenando os nós de entrada (e não apagando nenhum nó), tornamos nossa estrutura totalmente persistente.

Algumas estruturas ligadas já funcionam naturalmente dessa forma, como por exemplo a pilha implementada no Capítulo~\ref{cap:pilha}, nunca é necessário alterar nenhum nó. Quando a estrutura não funciona dessa forma, é possível tentar ``forçar'' isso. Durante operações de modificação podemos, ao adicionar um nó ao conjunto de acesso, adicionar na verdade uma cópia desse nó, já que ela pode vir a ser modificada por um passo de modificação.

A estrutura recursiva de deque do Capítulo~\ref{cap:deque2} faz isso, copiando todos os nós acessados durante um~\textsc{Push} ou~\textsc{Pop}. Isso sempre deixa a implementação funcional, já que não modificamos nenhum nó; porém, isso pode deixar a implementação inválida, já que pode ser possível alcançar a versão antiga de um nó que já foi copiado. Este foi o problema encontrado na implementação da deque de Kaplan e Tarjan, já que na primeira ideia de implementação, era possível acessar a versão antiga de um nó, como discutido na Seção~\ref{sec:implfunc}.

Esta técnica, de copiar todos os nós adicionados ao conjunto de acesso, funciona apenas se não existem nós atingíveis que não estão no conjunto de acesso e tem ponteiro para algum elemento cuja cópia está no conjunto de acesso. Se existe algum nó~$u$ desse tipo, então existe um caminho para~$u$, ou seja, uma sequência de passos de acesso que adicionam~$u$ ao conjunto de acesso, pois ele é atingível; e com mais um passo de acesso é possível adicionar a versão antiga do nó ao conjunto de acesso, que pode ter informação desatualizada.

Se os nós de estrutura formam uma árvore, como no caso da pilha e da deque recursiva, ou mesmo árvores binárias, então esse método pode ser aplicado. Na Seção~\ref{sec:implfunc}, a estrutura foi modificada para ser uma árvore, e dessa forma essa técnica poder ser aplicada.

Se a estrutura segue essas restrições, esse método torna estrutura totalmente persistente com overhead de consumo de tempo de~$\Oh(M+A)$ e espaço~$\Oh(M+A_m)$, onde~$A_m$ é o número de passos de acesso que ocorrem durante operações de modificação, já que é necessário copiar o nó mesmo que este não vá ser modificado.

\section{Fat node}

É possível alcançar persistência parcial em uma estrutura ligada genérica aumentando os seus nós para armazenar todas as mudanças já feitas. Essa técnica foi inicialmente apresentada por Driscoll, Sarnak, Sleator e Tarjan~\cite{DriscollSST1989}.

Modifica-se cada nó da estrutura para que cada campo seja substituido por um vetor de pares, que guarda pares~$(i, v)$, indicando que a~$i$-ésima operação de modificação modificou aquele campo para armazenar o valor~$v$. Ao invés de modificar um campo de um objeto, adicionasse um par no vetor correspondente, indicando a versão atual e o novo valor para o campo. Como estamos fazendo uma implementação parcialmente persistente, o índice de versão adicionado é sempre maior que todos os anteriores, dessa forma o vetor se mantém ordenado (considerando apenas os índices).

Para realizar um acesso do campo~$c$ na versão~$i$, é necessário procurar no vetor associado à~$c$ o par com maior índice que não excede~$i$, ou seja, a última atualização feita até no máximo a versão~$i$. Diferente das outras técnicas, esta também aumenta o tempo de um passo de acesso.

Utilizar esta técnica transforma qualquer estrutura ligada em uma estrutura parcialmente persistente, com overhead de consumo de tempo de~$\Oh((M+A) \lg{M})$ e espaço~$\Oh(M)$.

\section{Node copying}

No método Fat node, ao armazenar todas as modificações de um campo, precisamos de tempo logarítmico para descobrir o valor desse campo em uma dada versão. O método de~\deff{Node copying} diminui esse tempo armazenando apenas um número constante de versões em um mesmo nó, e fazendo uma cópia do nó quando este ficar muito grande. Este método também foi apresentado em~\cite{DriscollSST1989}.

Precisamos, contudo, fazer mais suposições sobre a estrutura. Supomos que os nós da estrutura ligada tem grau de entrada constante, ou seja, existe uma constante~$\V{in}$ tal que, a qualquer momento, para qualquer sequência de operações, vale que, para qualquer nó~$u$, o número de nós que tem em um de seus campos um ponteiro para~$u$ é no máximo~$\V{in}$. Note que, pela forma que definimos uma estrutura ligada, o grau de saída de um nó também é constante.

Para representar um nó da estrutura efêmera, teremos uma lista de nós persistentes, cada um representando o nó efêmero em algumas versões. O último nó dessa lista é chamado de nó~\deff{ativo}, pois representa o nó efêmero no estado atual da estrutura, e portanto, como estamos tratando de persistência parcial, é o único nó que precisamos considerar ao fazer operações de modificação. Usamos a notação que~$u_e$ é um nó da estrutura efêmera no estado atual, e~$u_a$ é o nó ativo associado à~$u_e$.

Um nó persistente~$u$ é similar a um nó efêmero, mas com campos adicionais. O campo~$\V{timestamp}$ indica a versão em que~$u$ foi criado. O campo~$\V{copy}$ é um ponteiro para o próximo nó na lista de nós persistentes, ou~\keyword{null} se~$u$ for ativo. Temos um vetor de triplas~$\V{changes}$ de tamanho~$\V{in}$ que armazena as mudanças feitas nos campos de~$u$, ou seja, se este vetor tem a tripla~$(\V{version}, \V{field}, \V{value})$ então na versão~$\V{version}$ o campo~$\V{field}$ de~$u$ foi modificado para o valor~$\V{value}$.

Quando a~$i$-ésima operação de modificação modifica~$u_e.\V{field}$ para~$\V{value}$, fazemos o seguinte
\begin{enumerate}
	\item Se~$u$ tem~$\V{timestamp} = i$, apenas modificamos seu campo~$\V{field}$ para~$\V{value}$.
	\item Se~$u.\V{changes}$ tem uma tripla~$(i, \V{field}, x)$, trocamos o último elemento da tripla para~$\V{value}$.
	\item Se~$u.\V{changes}$ não está cheio, adicionamos a tripla~$(i, \V{field}, \V{value})$ a este.
	\item Caso contrário, criamos um novo nó~$u'$. Seus campos recebem as versões mais novas das modificações, e o vetor~$u'.\V{changes}$ fica vazio.
	
\end{enumerate}

Além disso, temos um vetor~$\V{parent}$ de tamanho~$\V{in}$, que armazena ponteiros para os nós~$v_a$ tal que~$v_e$ tem um ponteiro para~$u_e$, ou seja, se~$u$ é ativo, esse vetor armazena ponteiros para todos os nós ativos que tem, em seus campos, um ponteiro para~$u$.




\end{document}
{'fraction_non_alphanumeric': 0.07664517000371408, 'fraction_numerical': 0.001316811290812709, 'mean_word_length': 4.832611264277275, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '338723', 'n_tokens_mistral': 10219, 'n_tokens_neox': 10231, 'n_words': 4371}