Algorithme de rendu de texte long dans un éditeur de texte

Question

Je pensais écrire un contrôle d'éditeur de texte capable d'éditer du texte de longueur arbitraire (disons des centaines de mégaoctets), similaire à l'éditeur Scintilla. Le but étant de lire le fichier paresseux, l'utilisateur n'a pas besoin de lire cinq cents mégaoctets de données pour n'en afficher qu'une petite partie. Je vais avoir deux problèmes:

1. Il me semble impossible de mettre en œuvre une fonction de défilement raisonnable pour un tel éditeur, à moins que je prélecture le fichier entier une fois, afin de déterminer la ligne pauses. Est-ce vraiment vrai? Ou y a-t-il un moyen d'approximer les choses auxquelles je ne pense pas? En raison de divers problèmes avec Unicode (par exemple, il permet à plusieurs octets de représenter un seul caractère, non seulement en raison de l'encodage de longueur variable, mais aussi en raison des accents et autres), il semble presque impossible de déterminer exactement s'adaptera à l'écran - je devrais utiliser TextOut() ou quelque chose pour dessiner un personnage, mesurer sa taille, puis dessiner le personnage suivant. Et même dans ce cas, cela ne dit toujours pas comment je retrouverais les clics de l'utilisateur à la bonne position du texte.

Y at-il quelque chose que je pourrais lire sur le web concernant les algorithmes pour gérer ces problèmes? J'ai cherché, mais je n'ai rien trouvé.

Merci!

Answer 1

Vous pouvez définir une position "grossière" en fonction de la taille des données plutôt que des lignes. La position "fine" de votre fenêtre de texte peut être basée sur un scan local autour d'un point d'entrée arbitraire. Cela signifie que vous aurez besoin d'écrire des fonctions qui peuvent scanner localement (en avant et en arrière) pour trouver les départs de lignes, compter les caractères Unicode, etc. Cela ne devrait pas être trop difficile. UTF8 est conçu pour être facile à analyser de cette manière.

Vous voudrez peut-être accorder une attention particulière à ce qu'il faut faire pour les très longues lignes. Comme il n'y a pas de limite supérieure sur la longueur d'une ligne, cela fait de trouver le début (ou la fin) d'une ligne comme une tâche illimitée; Je crois que tout ce dont vous avez besoin pour un affichage d'éditeur d'écran devrait être local.

Enfin, si vous voulez un texte général éditeur, vous devez savoir ce que vous allez faire lorsque vous souhaitez enregistrer un fichier dans lequel vous avez inséré/supprimé des choses. La chose la plus simple est de réécrire le fichier; Cependant, cela va évidemment prendre plus de temps avec un énorme fichier. Vous pouvez vous attendre à ce que l'utilisateur rencontre des problèmes s'il n'y a pas assez de place pour une copie modifiée, donc à tout le moins, vous voudrez vérifier s'il y a assez de place sur le système de fichiers.

Answer 2

@comingstorm est fondamentalement correct. Pour l'affichage, vous commencez par le curseur et balayez en arrière jusqu'à ce que vous soyez sûr que vous avez dépassé le haut de l'écran. Ensuite, vous revenez en arrière jusqu'à la fin d'une ligne, en supposant que vous pouvez identifier une extrémité de ligne en arrière. Maintenant, vous numérisez en avant, en calculant et en sauvegardant les positions de départ de la ligne d'écran jusqu'à ce que vous soyez allé assez loin. Enfin, vous choisissez la ligne que vous voulez commencer à afficher et vous partez.

Pour un texte simple, cela peut être fait sur un processeur archaïque assez rapidement pour redessiner un affichage vidéo mappé en mémoire à chaque frappe. [J'ai inventé cette technologie il y a 30 ans]. La bonne façon de faire est de fixer le curseur sur la ligne médiane de l'écran.

Pour modifier réellement les fichiers, vous pouvez utiliser les cordes de Gnu. Une corde est essentiellement une liste chaînée de tampons.L'idée est que toutes les modifications locales peuvent être effectuées dans un seul petit tampon, en ajoutant de temps en temps un nouveau tampon, et parfois en fusionnant les tampons adjacents.

Je considérerais combiner cette technologie avec le stockage différentiel: le genre de chose que font tous les systèmes modernes de contrôle de source. Vous avez pour utiliser ce type d'édition basée sur les transactions si vous souhaitez implémenter la fonction undo.

La clé de cette transaction est les transactions inversibles, c'est-à-dire celles qui contiennent suffisamment d'informations pour être appliquées à rebours pour annuler ce qu'elles ont fait lorsqu'elles ont été appliquées. L'opération de l'éditeur de base est:

at pos p replace old with new 

qui a inverse

at pos p replace new with old 

Cet insert poignées (ancien est vide) et supprimer (nouveau est vide), ainsi que remplacer. Étant donné une liste de transactions, vous pouvez annuler les modifications apportées à une chaîne en appliquant l'inverse de la liste des transactions inverses. Maintenant, vous utilisez l'ancien concept de point de contrôle: vous stockez une image modifiée du fichier assez récente avec quelques transactions récentes qui n'ont pas encore été appliquées. Pour afficher, vous appliquez les transactions à la volée. Pour annuler, vous venez de jeter certaines transactions. De temps en temps, vous appliquez réellement les transactions, en faisant une image "checkpoint". Cela accélère l'affichage, au prix de ralentir l'annulation. Enfin: pour réécrire un énorme fichier texte séquentiel, vous devez normalement réécrire le texte entier, ce qui est horrible. Si vous pouvez tricher un peu et autoriser des caractères arbitraires de 0 dans le texte et que vous avez accès au gestionnaire de page du système de mémoire virtuelle et à l'accès au disque, vous pouvez faire beaucoup mieux en conservant toutes les pages de texte inchangées. Autrement dit, l'idée de cordes sur le disque.