# Table de pièces

En informatique, une table de pièces est une structure de données généralement utilisée pour représenter un document texte pendant qu'il est édité dans un éditeur de texte. Dans un premier temps, une référence à l'ensemble du fichier d'origine est créée, qui représente le fichier encore inchangé. Les insertions et suppressions ultérieures remplacent une référence par des combinaisons d'une, deux ou trois références à des sections du document d'origine ou à une mémoire tampon contenant du texte inséré.
En règle générale, le texte du document original est conservé dans un bloc immuable et le texte de chaque insertion ultérieure est stocké dans de nouveaux blocs immuables. Étant donné que même le texte supprimé est toujours inclus dans la table des pièces, cela rend l'annulation répétée (possiblement indéfiniment) plus facile à mettre en œuvre avec une table des pièces qu'avec des structures de données alternatives telles qu'un tampon d'espacement.
Cette structure de données a été inventée par J Strother Moore.

## Description

Pour cette description, nous utilisons un tampon comme bloc immuable pour stocker le contenu du texte.
Un tableau de pièces se compose de trois colonnes pour chaque tampon :
* Référence vers le tampon
* Index de départ dans le tampon
* Longueur dans le tampon
En plus de la table, deux tampons sont utilisés pour gérer les modifications :
* « Tampon d'origine » : un tampon vers le document texte d'origine. Ce tampon est en lecture seule.
* « Tampon d'ajouts » : un tampon vers un fichier temporaire. Il s'agit d'un tampon d'écriture

## Opérations
### Indexation

   Définition : Index(i) : renvoie le i-ème caractère du texte
Pour récupérer le i-ème caractère, l'entrée appropriée dans une table de pièces est lue.

#### Exemple

Étant donné les tampons et la table de pièces suivants :
| Tampon | Contenu |
| Fichier originel | ipsum sit amet |
| Fichier d'ajout | Lorem deletedtext dolor |
Tableau des pièces :
| Lequel | Index de départ | Longueur |
| Ajout | 0 | 6 |
| Originel | 0 | 5 |
| Ajout | 17 | 6 |
| Originel | 5 | 9 |
Pour accéder au i-ème caractère, l'entrée appropriée dans la table des pièces est recherchée.
Par exemple, pour obtenir la valeur de Index(15), la 3ème entrée de la table des pièces est récupérée. C'est parce que la 3ème entrée décrit les caractères de l'index 11 à 16 (la première entrée décrit les caractères de l'index 0 à 5, la suivante de 6 à 10). L'entrée de la table des pièces indique au programme de rechercher les caractères dans le tampon « Fichier d'ajout », en commençant à l'index 17 dans ce tampon. L'index relatif dans cette entrée est 15-11 = 4, qui est ajouté à la position de départ de l'entrée dans le tampon pour obtenir l'index de la lettre : 4+17 = 21. La valeur de Index(15) est le 21ème caractère du tampon « ajouter un fichier », qui est le caractère « o ».
Pour les tampons et le tableau des pièces donnés ci-dessus, le texte suivant est affiché :

### Insertion

L'insertion de caractères dans le texte consiste à :
* Ajouter des caractères au tampon d'ajout
* Mettre à jour l'entrée dans la table des pièces (diviser une entrée en deux ou trois)

### Suppression

La suppression d'un seul caractère peut suivre deux scénarios possibles :
* La suppression s'effectue au début ou à la fin d'une entrée de pièce, auquel cas l'entrée appropriée dans la table des pièces est modifiée.
* La suppression s'effectue au milieu d'une entrée de pièce, auquel cas l'entrée est divisée puis l'une des entrées successeurs est modifiée comme ci-dessus.

## Usage

Plusieurs éditeurs de texte utilisent en interne une table de pièces en RAM, notamment Bravo, Abiword,$^,$$^,$ Atom et Visual Studio Code.
La fonction « Sauvegarde rapide » de certaines versions de Microsoft Word utilise un tableau de pièces pour le format de fichier sur disque.
La représentation sur disque des fichiers texte dans le système Oberon utilise une technique de chaîne morcelé qui permet à des morceaux d'un document de pointer vers du texte stocké dans un autre document, de manière similaire à la transclusion.