RLE sequence, setting a value

Question

Say I have an arbitrary RLE Sequence. (For those who don't know, RLE compresses an array like [4 4 4 4 4 6 6 1 1] into [(5,4) (2,6) (2,1)]. First comes the number of a particular integer in a run, then the number itself.)

How can I determine an algorithm to set a value at a given index without decompressing the whole thing? For example, if you do set(0,1) the RLE would become [(1,1) (4,4) (2,6) (2,1)]. (In set, the first value is the index, the second is the value)

Also, I've divided this compressed sequence into an ArrayList of Entries. That is, each Entry is one of these: (1,1) where it has an amount and value.

I'm trying to find an efficient way to do this, right now I can just think of methods that have WAY too many if statements to be considered clean. There are so many possible variations: for example, if the given value splits an existing entry, or if it has the same value as an existing entry, etc...

Any help would be much appreciated. I'm working on an algorithm now, here is some of it:

while(i<rleAL.size() && count != index)
    {
        indexToStop=0;
        while(count<index || indexToStop == rleAL.get(i).getAmount())
        {
            count++;
            indexToStop++;
        }

        if(count != index)
        {
            i++;
        }
    }

As you can see this is getting increasingly sloppy...

Thanks!

Answer 1

RLE is generally bad at updates, exactly for the reason stated. Changing ArrayList to LinkedList won't help much, as LinkedList is awfully slow in everything but inserts (and even with inserts you must already hold a reference to a specific location using e.g. ListIterator).

Talking about the original question, though, there's no need to decompress all. All you need is find the right place (summing up the counts), which is linear-time (consider skip list to make it faster) after which you'll have just four options:

1. You're in a block, and this block is the same as a number you're trying to save.
2. You're inside a block, and the number is different.
3. You're in the beginning or the end of the block, the number differs from the block's but same as neighbour has.
4. You're in the beginning or the end of the block, the number is neither the same as block's nor the one of neighbour's.

The actions are the same, obviously:

1. Do nothing
2. Change counter in the block, add two blocks
3. Change counters in two blocks
4. Change counter in one block, insert a new one

(Note though if you have skip lists, you must update those as well.)

Update: it gets more interesting if the block to update is of length 1, true. Still, it all stays as trivial: in any case, the changes are limited to maximum of three blocks.