Structure de données Zipper pour éditeur de modèle graphique

Question

J'écris un éditeur graphique pour un "modèle" (c'est-à-dire une collection de boîtes et de lignes avec une sorte de sémantique, comme UML, dont les détails n'ont pas d'importance ici) . Je veux donc avoir une structure de données représentant le modèle, et un diagramme où une modification apportée au diagramme provoque une modification correspondante dans le modèle. Donc, si, par exemple, un élément de modèle a du texte dans un attribut et que je modifie le texte dans le diagramme, je veux que l'élément de modèle soit mis à jour.

Le modèle sera probablement représenté sous forme d'arborescence, mais je souhaite que l'éditeur de diagramme en sache le moins possible sur la représentation du modèle. (J'utilise le framework diagrams, donc l'association d'informations arbitraires avec un élément graphique est facile). Il y aura probablement une classe "model" pour encoder l'interface, si je peux juste comprendre ce que cela devrait être. Si je faisais cela dans un langage impératif, ce serait simple: je voudrais juste avoir une référence de l'élément graphique dans le diagramme à l'élément de modèle. En théorie, je pourrais encore le faire en construisant le modèle à partir d'une collection massive de IORefs, mais cela serait l'écriture d'un programme Java dans Haskell. De toute évidence, chaque élément graphique doit être associé à un cookie qui lui permettra d'effectuer la mise à jour du modèle. Une réponse simple serait de donner à chaque élément de modèle un identifiant unique et de stocker le modèle dans une table de recherche Data.Map. Mais cela nécessite une comptabilité importante pour s'assurer qu'aucun élément du modèle ne reçoive le même identifiant. Cela me semble également être une solution "stringly typed"; vous devez gérer les cas où un objet est supprimé mais il y a une référence qui se balade ailleurs, et il est difficile de dire quoi que ce soit sur la structure interne du modèle dans vos types.

D'autre part Oleg's writings sur les fermetures à glissière avec des trous multiples et des curseurs avec le partage transactionnel clair semble être une meilleure option, si seulement je pouvais le comprendre. J'ai l'idée de base des fermetures à glissière de liste et d'arbre et de la différenciation d'une structure de données. Serait-il possible pour chaque élément d'un diagramme de contenir un curseur dans une fermeture à glissière du modèle? Alors que si un changement est fait, il peut alors être engagé à tous les autres curseurs? Y compris les opérations arborescentes (telles que le déplacement d'un sous-arbre d'un endroit à un autre)? Cela m'aiderait particulièrement s'il existait une sorte de tutoriel sur les continuations délimitées, et une explication de la façon dont fonctionnent les fermetures multi-curseurs d'Oleg, un peu moins abruptes que les publications d'Oleg?

Answer 1

Je pense que vous travaillez actuellement à partir d'une conception dans laquelle chaque nœud de l'arbre du modèle est représenté par un widget graphique distinct, et chacun de ces widgets peut mettre à jour le modèle indépendamment. Si oui, je ne crois pas qu'une fermeture à glissière multi-trous sera très pratique. Le problème est que la complexité de la fermeture à glissière se développe rapidement avec le nombre de trous que vous souhaitez soutenir. Comme vous obtenez beaucoup au-delà de 2 termes, la taille de la fermeture éclair deviendra assez grande. Du point de vue de la différenciation, une fermeture à glissière à 2 trous est une fermeture à glissière sur les fermetures à glissière à un trou, de sorte que la complexité augmente en fonction de la règle de la chaîne. Au lieu de cela, vous pouvez emprunter une idée à MVC. Chaque nœud est toujours associé à un widget, mais ne communique pas directement. Au contraire, ils passent par un contrôleur intermédiaire, qui maintient une fermeture à glissière unique. Lorsque les widgets sont mis à jour, ils avertissent le contrôleur, qui sérialise toutes les mises à jour et modifie la fermeture à glissière en conséquence.

Les widgets auront toujours besoin d'une sorte d'identifiant pour référencer les nœuds du modèle. J'ai trouvé qu'il est souvent plus facile d'utiliser le chemin du nœud, par exemple. [0] pour la racine, [1,0] pour le second enfant de la racine, etc. Ceci a quelques avantages. Il est facile de déterminer le nœud auquel un chemin se réfère, et il est également facile pour une fermeture à glissière de calculer le chemin le plus court entre l'emplacement actuel et un nœud donné.Pour une structure arborescente, ils sont également uniques jusqu'à la suppression et la réinsertion. Même cela n'est généralement pas un problème car, lorsque le contrôleur est averti que les nœuds doivent être supprimés, il peut supprimer les widgets correspondants et ne pas tenir compte des mises à jour associées. Tant que la durée de vie du widget est liée à la durée de vie de chaque nœud, le chemin sera suffisamment unique pour identifier les modifications.

Pour les opérations d'arborescence, je détruirais probablement puis recréerais des widgets graphiques. Par exemple, j'ai un code does this sort of thing. Dans ce modèle, il n'y a pas de widgets séparés pour chaque nœud, mais je rends tout à l'aide de diagrammes, puis interroge le diagramme en fonction de la position du clic pour obtenir le chemin dans le modèle de données. C'est loin d'être terminé, et je ne l'ai pas regardé depuis un moment, donc ça pourrait ne pas se construire, mais le code peut vous donner quelques idées.