Rechecking contiguous characters (as in run length encoding)

Question

So I have a fun little problem. It will take a minute to explain, but the situation is conceptually very simple. Suppose you have a string of characters, which is interpreted as groups of one or more contiguous characters. This is for run length encoding or something. For example:

zz22344a is two z's, two 2's, one 3, two 4's, and one a.

Once you've parsed the original string, you retain only the characters and sizes in an array.

struct Run { char whatChar; int length; }

Run* runArrayVar;

void parseIntoArray(char* sourceChars);   // creates runArrayVar

I won't put the implementation of parseIntoArray() here because it's trivial to do with a loop, but I'll assume that arrays are null-terminated, although in the problem they don't have to be. Here is the problem part. I want to implement a function like this:

void alterArray(char* newSourceChars, int changedOffset,
                int changedLength, int changedCharsAdded);

This responds to a change in the source text. Included is the new text, the beginning and length of the altered area, and for reference, how many extra characters were added. For example, take the original zz22344a. If the substring 223 was pasted over with 23_44, then the new string would be zz23_4444a and the new array would be two z's, one 2, one 3, one _, four 4's, and one a.

I could get the new runArrayVar naively by just calling parseIntoArray, but I want to be less naive: I want to step through and only change the parts of runArrayVar that need to be changed. Finding the first changed element is pretty easy; skip through until you find one that overlaps changedOffset (you need to test one extra char after the element). After that it gets dicey and I can't figure it out. Take the above example:

zz needs to be re-checked because the character right after it might have been changed to a z. It wasn't, so it remains zz. Now we're at offset 2.

22 is rechecked, and it turned into 2. So OK. Now we're at offset 3.

3 is rechecked, and it's the same. So we're at offset 4.

44 is rechecked, and apparently turned into an underscore. So we're at offset 5.

At this point we're still looking at characters that have changed, and we're at 4444. According to the previous logic, a turned into 4444. OK. Now we're past the characters that have changed, and our array still has an element with one a left over. I can keep parsing and terminate the array when I hit the end of the string, but suppose that a was actually a million as in a row. The algorithm should be able to reason that it doesn't have to do any more work and terminate. If you look at the example, there is nothing you could have changed that particular section into that would influence the a.

This is difficult. I've tried it a lot of different ways and I can't figure out exactly when the algorithm needs to terminate. Please let me know if you have any ideas!

Answer 1

If a Run only retains characters and sizes in an array, it seems as though you only need to find the indices corresponding to changedOffset and changedOffset + changedLength, and then potentially change the sizes of the characters in the indices to the right and left by simple addition. That is, if you have an array of Runs: $$[(x,1),(y,2),(a,2),(b,1),(c,1),(z,2),(x,1)]$$ for alterArray("ac_zz",3,4), it is first determined that the $a$ and $c$ are the beginning and ending characters (the $b$ is eliminated). This is done by simply adding: $1+2=3$ (from the $1x$ and $2y$) and $2+1+1=4$ (from the $2a,1b,$ and $1c$).

Then you check whether either side has to be combined: on the left side, the $y$ is not affected; on the right side, the $z$ is affected and so we add $2+2=4z$. The $x$'s are never checked.