Mesa de peças - Piece table

Uma tabela de peças é uma estrutura de dados normalmente usada para representar uma série de edições em um documento de texto . Uma referência inicial (ou 'extensão') para todo o arquivo original é criada, com as inserções e exclusões subsequentes sendo criadas como combinações de uma, duas ou três referências a seções do documento original ou das extensões associadas a anteriores inserções.

Normalmente, o texto do documento original é mantido em um bloco imutável e o texto de cada inserção subsequente é armazenado em novos blocos imutáveis. Como até mesmo o texto excluído ainda está incluído na tabela de peças, isso torna o desfazer em vários níveis ou ilimitado mais fácil de implementar com uma tabela de peças do que com estruturas de dados alternativas, como um buffer de lacuna .

Esta estrutura de dados foi inventada por J Strother Moore .

Descrição

Para esta descrição, usamos buffer como o bloco imutável para conter o conteúdo.

Uma tabela de peças consiste em três colunas:

  • Qual buffer
  • Índice inicial no buffer
  • Comprimento no buffer

Além da tabela, dois buffers são usados ​​para lidar com as edições:

  • " Buffer original ": um buffer para o documento de texto original. Este buffer é somente leitura.
  • " Adicionar buffer ": Um buffer para um arquivo temporário. Este buffer é somente para acréscimos.

Operações

Índice

Definição:: Index(i) retorna o caractere na posição i

Para recuperar o i -ésimo caractere, a entrada apropriada em uma tabela de peças é lida.

Exemplo

Dados os seguintes buffers e tabela de peças:

Amortecedor Contente
Arquivo original ipsum sit amet
Adicionar ficheiro Lorem deletedtext dolor
Mesa de peças
Que Índice inicial Comprimento
Adicionar 0 6
Original 0 6
Adicionar 18 5
Original 6 9

Para acessar o i -ésimo caractere, a entrada apropriada na tabela de peças é pesquisada.

Por exemplo, para obter o valor de Index(15), a 3ª entrada da tabela de peças é recuperada. Isso ocorre porque a terceira entrada descreve os caracteres do índice 12 a 16 (a primeira entrada descreve os caracteres no índice 0 a 5, a próxima é de 6 a 11). A entrada da tabela de peças instrui o programa a procurar os caracteres no buffer " adicionar arquivo ", começando no índice 18 nesse buffer. O índice relativo nessa entrada é 15-12 = 3, que é adicionado à posição inicial da entrada no buffer para obter o índice da letra: 3 + 18 = 21. O valor de Index(15)é o 21º caractere do "add arquivo "buffer, que é o caractere" o ".

Para os buffers e a tabela de peças fornecidas acima, o seguinte texto é mostrado: 

Lorem ipsum dolor sit amet

Inserir

A inserção de caracteres no texto consiste em:

  • Anexar caracteres ao buffer "adicionar arquivo" e
  • Atualizando a entrada na tabela de peças (dividindo uma entrada em duas ou três)

Excluir

A exclusão envolve apenas a modificação da entrada apropriada na tabela de peças.

Uso

Vários editores de texto usam uma tabela de peças em RAM internamente, incluindo Bravo , Abiword , Atom e Visual Studio Code .

O recurso de "salvamento rápido" em algumas versões do Microsoft Word usa uma tabela de peças para o formato de arquivo em disco.

A representação em disco de arquivos de texto no Sistema Oberon usa uma técnica de encadeamento de peças que permite que pedaços de um documento apontem para o texto armazenado em algum outro documento, semelhante à transclusão .

Veja também

Referências