Java – RLE sequence, set a value

Say I have an arbitrary RLE sequence (for those who don't know, RLE compresses an array like [4,4,6,1] into [(5,4) (2,6) (2,1)] First is the specific integer in the operation of number a, and then the number itself.)

How to determine the algorithm to set the value at a given index without decompressing the whole thing? For example, if (0,1) is set, RLE will become [(1,1) (4,1)] (in set, the first value is the index and the second value is the value)

In addition, I have divided this compressed sequence into ArrayList In other words, each entry is one of the following: (1,1) it has amount and value

I'm trying to find an effective way to do this, and now I can think of too many methods if the statement is considered clean There are many possible changes: for example, if a given value splits an existing entry, or it has the same value as an existing entry, and so on

Any help would be appreciated I am now studying an algorithm. Here are some:

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, it's getting sloppy

thank you!

Solution

RLE is usually poorly updated for the above reasons Changing ArrayList to LinkedList won't help much, because LinkedList is very slow in everything except insertion (even with insertion, you must use, for example, listiterator to save references to specific locations)

However, when it comes to the original problem, it is not necessary to decompress all the problems All you need is to find the correct location (total count), which is linear time (consider skipping the list to make it faster), after which you will have only four options:

>You are in a block that is the same as the number you want to save. > You are in a block, the number is different. > If you are at the beginning or end of a block, the number is different from that of the block, but the same as the neighbor. > If you are at the beginning or end of a block, the number is neither a block nor a neighbor's number

The action is the same, obviously:

>Do nothing > change counter in block, add two blocks > change counter in two blocks > change counter in one block, insert a new area

(note that if you have skip lists, you must also update them.)

Update: it is more interesting if the length of the block to be updated is 1 Nevertheless, it is still insignificant: in any case, the change is limited to a maximum of three blocks