Tampon d'espacement
La mise en forme de cet article est à améliorer ().
La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».
Cet article contient des anglicismes ().
Certains termes anglais peu courants en français devraient être remplacés par des termes français équivalents mieux connus. Discutez des points à améliorer en page de discussion.
En informatique, un tampon d'espacement est un tableau dynamique qui permet des opérations d'insertion et de suppression efficaces regroupées à proximité du même emplacement. Les tampons d'espacement sont particulièrement courants dans les éditeurs de texte, où la plupart des modifications apportées au texte se produisent à l'emplacement actuel du curseur ou à proximité de celui-ci. Le texte est stocké dans un tampon constitué de deux segments contigus, avec un espace entre eux pour l'insertion d'un nouveau texte. Le déplacement du curseur implique la copie du texte d'un côté de l'espace à l'autre (parfois, la copie est retardée jusqu'à la prochaine opération qui modifie le texte). L'insertion ajoute un nouveau texte à la fin du premier segment; la suppression le supprime.
Le texte dans un tampon d'espacement est représenté sous forme de deux chaînes de caractères, qui occupent très peu d'espace supplémentaire. La recherche de motifs et l'affichage sont très rapides, par rapport à des structures de données plus sophistiquées telles que les listes chaînées. Cependant, les opérations à différents endroits du texte et celles qui comblent l'espace vide (nécessitant la création d'un nouvel espace vide) peuvent nécessiter la copie de la majeure partie du texte, ce qui est particulièrement inefficace pour les fichiers volumineux. L'utilisation de tampons d'espacement repose sur l'hypothèse selon laquelle une telle recopie se produit suffisamment rarement pour que son coût puisse être amorti sur les opérations à faible coût les plus courantes. Cela fait du tampon d'espacement une alternative plus simple à la corde pour une utilisation dans les éditeurs de texte [1] tels qu'Emacs[2].
Exemple
modifierCi-dessous sont décrits quelques exemples d’opérations avec des tampons d'espacement. L'espacement est représenté par l'espace vide entre les crochets. Cette représentation est un peu trompeuse : dans une implémentation typique, les points de terminaison de l'espace sont suivis à l'aide de pointeurs ou d'indices de tableau, et le contenu de l'espace est ignoré ; cela permet, par exemple, d'effectuer des suppressions en ajustant un pointeur sans modifier le texte dans le tampon.
État initial :
This is the way [ ]out.
L'utilisateur insère du texte :
This is the way the world started [ ]out.
L'utilisateur déplace le curseur avant « started »; le système déplace « started » du premier tampon au deuxième tampon.
This is the way the world [ ]started out.
L'utilisateur ajoute du texte en remplissant l'espacement; le système crée un nouvel espacement :
This is the way the world as we know it [ ]started out.
Voir aussi
modifier- Tableau dynamique, cas particulier d'un tampon d'espacement où l'espacement est toujours à la fin
- Zipper (structure de données), conceptuellement une généralisation du tampon d'espacement.
- Liste chaînée
- Tampon circulaire
- Corde (informatique)
- Table de pièces - structure de données utilisée par Bravo et Microsoft Word
Références
modifier- Mark C. Chu-Carroll. "Gap Buffers, or, Don’t Get Tied Up With Ropes?" ScienceBlogs, 2009-02-18. Accessed 2013-01-30.
- emacs gap buffer info Accessed 2013-01-30.
Liens externes
modifier- Implementation in C
- Overview and implementation in .NET/C#
- Brief overview and sample C++ code
- Implementation of a cyclic sorted gap buffer in .NET/C#
- Use of gap buffer in early editor. (Entre 1969 et 1971)
- Emacs gap buffer info (Référence sur le tampon d'espacement d'Emacs)
- Flexichain: An editable sequence and its gap-buffer implementation
- Text showdown: Gap Buffers vs Ropes
