Table à pièces - Piece table
Un tableau de pièces est une structure de données généralement utilisée pour représenter une série de modifications sur un document texte . Une référence initiale (ou « étendue ») à l'ensemble du fichier d'origine est créée, les insertions et suppressions ultérieures étant créées en tant que combinaisons d'une, deux ou trois références à des sections du document d'origine ou des étendues associées à inserts.
Typiquement, le texte du document original est contenu dans un bloc immuable , et le texte de chaque insertion suivante est stocké dans de nouveaux blocs immuables. Étant donné que même le texte supprimé est toujours inclus dans la table de pièces, cela rend l' annulation à plusieurs niveaux ou illimitée plus facile à mettre en œuvre avec une table de 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 .
La description
Pour cette description, nous utilisons buffer comme bloc immuable pour contenir le contenu.
Un tableau de pièces se compose de trois colonnes :
- Quel tampon
- Index de début 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.
- " Ajouter un tampon " : Un tampon dans un fichier temporaire. Ce tampon est à ajout uniquement.
Opérations
Indice
Définition :
Index(i): renvoie le caractère à la position i
Pour récupérer le i- ième caractère, l'entrée appropriée dans une table de pièces est lue.
Exemple
Compte tenu des tampons et de la table des pièces suivants :
| Amortir | Teneur |
|---|---|
| Fichier d'origine |
ipsum sit amet
|
| Ajouter le fichier |
Lorem deletedtext dolor
|
| Lequel | Index de départ | Longueur |
|---|---|---|
| Ajouter | 0 | 6 |
| Original | 0 | 6 |
| Ajouter | 18 | 5 |
| Original | 6 | 9 |
Pour accéder au i- 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. En effet, la 3e entrée décrit les caractères de l'index 12 à 16 (la première entrée décrit les caractères de l'index 0 à 5, la suivante est de 6 à 11). L'entrée de la table des pièces indique au programme de rechercher les caractères dans le tampon " ajouter un fichier ", en commençant à l'index 18 dans ce tampon. L'index relatif dans cette entrée est 15-12 = 3, qui est ajouté à la position de départ de l'entrée dans le tampon pour obtenir l'index de la lettre : 3+18 = 21. La valeur de Index(15)est le 21e caractère du "add file", qui est le caractère "o".
Pour les tampons et le tableau des pièces ci-dessus, le texte suivant est affiché :
Lorem ipsum dolor sit amet
Insérer
L'insertion de caractères dans le texte consiste à :
- Ajouter des caractères au tampon "ajouter un fichier", et
- Mise à jour de l'entrée dans le tableau des pièces (fractionnement d'une entrée en deux ou trois)
Effacer
La suppression implique uniquement la modification de l'entrée appropriée dans le tableau des pièces.
Usage
Plusieurs éditeurs de texte utilisent une table de morceaux en RAM en interne, notamment Bravo , Abiword , Atom et Visual Studio Code .
La fonction « enregistrement 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 de morceaux qui permet aux morceaux d'un document de pointer vers le texte stocké dans un autre document, similaire à la transclusion .
Voir également
- Corde (informatique)
- Gap buffer , une structure de données couramment utilisée dans les éditeurs de texte qui permet des opérations d'insertion et de suppression efficaces regroupées près du même emplacement