Mise en œuvre de la fonction Annuler/Refaire

Question

Donnez-moi quelques idées sur la façon d'implémenter la fonctionnalité undo/redo - comme nous avons dans les éditeurs de texte. Quels algorithmes devrais-je utiliser et ce que je pourrais lire. Merci.

Answer 1

Je connais deux grandes divisions des types d'annulation.

• SAUVER L'ÉTAT : Une catégorie d'annulation permet de sauvegarder les états de l'historique. Dans ce cas, à chaque instant, vous continuez à sauvegarder l'état dans un emplacement de la mémoire. Lorsque vous voulez faire une annulation, il vous suffit d'échanger l'état actuel et d'échanger l'état qui était déjà présent dans la mémoire. C'est ainsi que l'on procède avec l'historique dans Adobe Photoshop ou la réouverture des onglets fermés dans Google Chrome, par exemple.

• GÉNÉRER L'ÉTAT : L'autre catégorie est celle où, au lieu de maintenir les états eux-mêmes, vous vous souvenez simplement de ce que les actions étaient. Lorsque vous avez besoin d'annuler, vous devez faire une inversion logique de cette action particulière. Pour un exemple simple, lorsque vous faites un Ctrl + B dans un éditeur de texte qui prend en charge les annulations, elle est mémorisée en tant qu'une Gras action. Maintenant, avec chaque action, il y a un mapping de ses inverses logiques. Ainsi, lorsque vous faites une Ctrl + Z il consulte un tableau d'actions inverses et constate que l'action d'annulation est une Ctrl + B à nouveau. Cette opération est effectuée et vous obtenez votre état précédent. Donc, ici, votre état précédent n'a pas été stocké en mémoire mais généré lorsque vous en avez eu besoin.

Pour les éditeurs de texte, la génération de l'état de cette manière n'est pas trop exigeante en termes de calcul, mais pour des programmes comme Adobe Photoshop, cela peut être trop exigeant en termes de calcul ou tout simplement impossible. Par exemple, pour un Flou vous spécifierez un de-Blur mais cela ne vous ramènera jamais à l'état initial car les données sont déjà perdues. Ainsi, en fonction de la situation - possibilité d'une action inverse logique et faisabilité de celle-ci, vous devez choisir entre ces deux grandes catégories, puis les mettre en œuvre comme vous le souhaitez. Bien sûr, il est possible d'avoir une stratégie hybride qui fonctionne pour vous.

De plus, parfois, comme dans Gmail, une annulation limitée dans le temps est possible parce que l'action (l'envoi du courrier) n'est jamais effectuée en premier lieu. Ainsi, vous n'êtes pas en train d'"annuler", mais simplement de "ne pas faire" l'action elle-même.

Answer 2

J'ai écrit deux éditeurs de texte à partir de rien, et ils utilisent tous deux une forme très primitive de la fonctionnalité annuler/refaire. Par "primitif", je veux dire que la fonctionnalité a été très facile à mettre en œuvre, mais qu'elle n'est pas rentable pour les très gros fichiers (disons >> 10 Mo). Cependant, le système est très flexible ; par exemple, il supporte un nombre illimité de niveaux d'annulation.

En gros, je définis une structure comme

type
  TUndoDataItem = record
    text: /array of/ string;
    selBegin: integer;
    selEnd: integer;
    scrollPos: TPoint;
  end;

et ensuite définir un tableau

var
  UndoData: array of TUndoDataItem;

Ensuite, chaque membre de ce tableau spécifie un état sauvegardé du texte. Maintenant, à chaque édition du texte (touche de caractère enfoncée, retour arrière enfoncé, touche d'effacement enfoncée, couper/coller, sélection déplacée par la souris, etc.), je (re)lance une minuterie de (disons) une seconde. ), je (re)lance une minuterie d'une seconde (par exemple). Lorsqu'elle est déclenchée, la minuterie enregistre l'état actuel comme un nouveau membre de la classe UndoData le tableau.

En cas d'annulation (Ctrl+Z), je rétablis l'éditeur dans l'état suivant UndoData[UndoLevel - 1] et diminuer le UndoLevel par un. Par défaut, UndoLevel est égal à l'indice du dernier membre de l'élément UndoData réseau. Lors du redo (Ctrl+Y ou Shift+Ctrl+Z), je rétablis l'éditeur dans l'état suivant UndoData[UndoLevel + 1] et augmenter le UndoLevel par un. Bien entendu, si la minuterie d'édition est déclenchée lorsque UndoLevel n'est pas égale à la longueur (moins un) de l'élément UndoData j'efface tous les éléments de ce tableau après que UndoLevel L'inconvénient de l'approche de Microsoft Windows est que, si vous annulez beaucoup de changements et que vous modifiez accidentellement le tampon, le contenu précédent (qui a été annulé) est définitivement perdu. Vous pourriez vouloir sauter cette réduction du tableau.

Dans un autre type de programme, par exemple un éditeur d'images, la même technique peut être appliquée, mais, bien sûr, avec une toute autre méthode. UndoDataItem structure. Une approche plus avancée, qui ne nécessite pas autant de mémoire, consiste à ne sauvegarder que le fichier cambia entre les niveaux d'annulation (c'est-à-dire qu'au lieu de sauvegarder "alpha \nbeta\gamma "et "alpha \nbeta\ngamma\ndelta "vous pourriez enregistrer "alpha \nbeta\ngamma "et "ADD \ndelta ", si vous voyez ce que je veux dire). Dans les très gros fichiers où chaque modification est petite par rapport à la taille du fichier, cela diminuera considérablement l'utilisation de la mémoire des données d'annulation, mais c'est plus délicat à mettre en œuvre, et peut-être plus sujet aux erreurs.

Answer 3

Il y a plusieurs façons de procéder, mais vous pouvez commencer par examiner l'élément suivant Modèle de commande . Utilisez une liste de commandes pour revenir en arrière (Undo) ou avancer (redo) dans vos actions. Un exemple en C# peut être trouvé aquí .

Answer 4

Mon seul avis est que vous devriez utiliser deux piles pour suivre les opérations. Chaque fois que l'utilisateur effectue des opérations, votre programme devrait placer ces opérations sur une pile "effectuée". Lorsque l'utilisateur souhaite annuler ces opérations, il suffit de transférer les opérations de la pile "exécutée" vers une pile "rappel". Lorsque l'utilisateur souhaite refaire ces opérations, il doit extraire les éléments de la pile "rappel" et les remettre dans la pile "effectuée".

J'espère que cela vous aidera.

Answer 5

Un peu tard, mais c'est parti : Vous faites spécifiquement référence aux éditeurs de texte, ce qui suit explique un algorithme qui peut être adapté à tout ce que vous éditez. Le principe est de garder une liste d'actions/instructions qui peuvent être automatisées pour recréer chaque changement que vous avez fait. Ne modifiez pas le fichier original (s'il n'est pas vide), gardez-le comme sauvegarde.

Conservez une liste de liens avant-arrière des modifications que vous apportez au fichier d'origine. Cette liste est sauvegardée par intermittence dans un fichier temporaire, jusqu'à ce que l'utilisateur fasse effectivement des modifications. Économisez les changements : lorsque cela se produit, vous appliquez les changements à un nouveau fichier, en copiant l'ancien et en appliquant simultanément les changements ; puis vous renommez le fichier original en une sauvegarde, et changez le nom du nouveau fichier pour le nom correct. (Vous pouvez soit conserver la liste de modifications sauvegardée, soit la supprimer et la remplacer par une liste de modifications ultérieure).

Chaque nœud de la liste liée contient les informations suivantes :.

• le type de modification : soit vous insérez des données, soit vous les supprimez : "modifier" des données signifie une modification de l'information. delete suivi d'un insert
• position dans le fichier : peut être un décalage ou une paire de lignes/colonnes
• tampon de données : ce sont les données impliquées dans l'action ; si insert il s'agit des données qui ont été insérées ; si delete les données qui ont été supprimées.

Pour mettre en œuvre Undo vous travaillez à rebours à partir de la fin de la liste chaînée, en utilisant un pointeur ou un index 'current-node' : où le changement a été effectué insert vous effectuez une suppression mais sans mettre à jour la liste liée ; et lorsque c'était un delete vous insérez les données à partir des données dans le tampon de la liste liée. Faites cela pour chaque commande "Undo" de l'utilisateur. Redo déplace le pointeur 'current-node' vers l'avant et exécute le changement selon le nœud. Si l'utilisateur apporte une modification au code après l'annulation, il supprime tous les noeuds après l'indicateur 'current-node' jusqu'à la queue, et met la queue égale à l'indicateur 'current-node'. Les nouvelles modifications de l'utilisateur sont alors insérées après la queue. Et c'est à peu près tout.