Mappage d'un ensemble d'intervalles au tampon de texte 2D avec synchronisation du changement de texte

Question

J'ai un tampon de type texte 2D (essentiellement List<List<Object>>), indexé par des coordonnées (ligne, col). Chaque rangée peut avoir une longueur arbitraire.

Soit pos = (row, col). Un intervalle est ensuite défini par (fromPos, toPos).

Le tampon de texte peut être modifié par l'insertion et la suppression de caractères:

void addRow(int rowIndex, Row<T> newRow); 

void removeRow(int rowIndex); 

void insert(int row, int col, Collection<? extends T> els); 

void delete(int row, int col, int count); 

Comment puis-je tenir compte des changements dans le texte en position d'intervalles? Les intervalles sont imbriqués, mais pas strictement.

Le problème principal est que les intervalles peuvent être vides et que l'ordre et l'imbrication des intervalles doivent être préservés.

Par exemple:

 

0 1 2 3 4  (interval number) 

[a[bcd[]][][ef]gh] (text) 

0 123  45 67 (char index) 

après insertion de X dans le 3ème intervalle (position absolue 4) devrait devenir

 

0 1 2 3 4   (interval number) 

[a[bcd[]][X][ef]ghijk] (text) 

Quelles sont quelques façons de stocker des intervalles pour être en mesure de tenir compte des changements le texte correctement et efficacement?

Answer 1

Je voudrais stocker des intervalles comme des paires de "curseurs" et ensuite maintenir l'ordre des curseurs dans un arbre splay. Plutôt que de stocker directement la ligne/colonne de chaque curseur, j'utiliserais une représentation de différence. Pour un exemple 1D, aux curseurs de magasin AE avec A = 1, B = 2, c = 3, d = 5, E = 7, l'arbre peut être maintenant

B2 
/\ 
/ \ 
/ \ 
A-1  D3 
    /\ 
     C-2 E2 

, lors de l'insertion d'un caractère à la position 4 , J'utilise l'algorithme d'insertion standard pour trouver les premiers curseurs à gauche, sommant le long du chemin lorsque je descends. C'est le curseur C, que je joue en haut, en fixant les nombres à chaque rotation.

 C3 
    /\ 
    / \ 
/ \ 
    B-1  D2 
/  \ 
A-1   E2 

Maintenant, j'en ajoute un à l'enfant droit de C. En raison de la représentation des différences, cela a pour effet d'incrémenter le sous-arbre entier d'un.

 C3 
    /\ 
    / \ 
/ \ 
    B-1  D3 
/  \ 
A-1   E2 

Les autres opérations sont des exercices simples de manipulation des arbres de coupe.