Processing a sequence of additions and deletions

Question

I am working on a program which manages a list, and must be able to insert new items, and delete ranges of items. I want the user to be able to specify the insertions and deletions in terms of the current state of the list, and not have to worry about how later operations will need an offset index in order to work on the correct items.
eg:

delete: 4-5
insert: 2,6

will insert an element before index 2, and another element before what was originally element 6, and delete the items originally at 4 and 5.

I want to convert these instructions into a list of deletions followed by insertions, which can be performed consecutively, ie the operations above would become:

delete 4, delete 4, insert 2, insert 4

as the deletion at 4 shifts the following operations left, so the next deletion also acts at 4. The insertion of 2 shifts the insertion of 6 right, but the previous 2 subtractions shift it left.

I'm looking for a (hopefully readable) formula for converting the indices of these insertions and deletions into the form they will be in in the delete and insert lists.

So far, I have a rather unreadable python function, which would be difficult to maintain, but which seems to output the correct values:

ii = jj = kk = 0 # list indices
plus = minus = 0 # plus / minus offset
while ii < len(dellist) or jj < len(addlist):
    if jj < len(addlist): # in the list
        if addlist[jj] == kk: # at the specified index
            addlist[jj] -= minus # deletions happen first, so shift it back
            addlist[jj] += plus # then additions happen, so shift it forward
            jj += 1 # next addition
            plus += 1 # one more item inserted before the others
    if ii < len(dellist): # in the list
        if dellist[ii] == kk: # at the specified index
            dellist[ii] -= minus # previous deletions, so shift back
            ii += 1 # next deletion
            minus += 1 # one more item removed from before the others
    kk += 1 # next list element

I'm mainly concerned with having readable code, that I can easily modify later; and, ideally, something more modular, although I'm not sure how that would be achieved in this case.

Answer 1

Not really a code-review, but an alternative suggestion:

Why not make the processor process the list in reverse. Given the 'modifications' suggested, order them by position with largest position first. Then, the processor can just walk down the line, not having to deal with modifications to the list at an earlier step.

So the logic would be more as follows:

for (pos, mod) in sorted(modifications, reverse=True):
    if mod == 'del':
        del lst[pos]
    elif mod == 'ins':
        lst.insert(pos, "some item")
    else:
        raise ValueError("unknown action")  # Or some other handling.

Answer 2

So I made your code a function and then ran it on the example you gave. I got to the following code:

def shift_indexes(dellist, addlist):
    ii = jj = kk = 0
    plus = minus = 0
    while ii < len(dellist) or jj < len(addlist):
        if jj < len(addlist):
            if addlist[jj] == kk:
                addlist[jj] -= minus
                addlist[jj] += plus
                jj += 1
                plus += 1
        if ii < len(dellist):
            if dellist[ii] == kk:
                dellist[ii] -= minus
                ii += 1
                minus += 1
        kk += 1
    return dellist, addlist

dellist = [4, 5]
addlist = [2, 6]
print('del: {}\nadd: {}'.format(*shift_indexes(dellist, addlist)))

It works fine with the input you gave, but it doesn't when I change addlist to 6, 2 not 2, 6. And so I'll 'white box' test your code:

if addlist[0] == 0: # 6 == 0 : False
kk += 1             # kk = 1
if addlist[0] == 1: # 6 == 1 : False
kk += 1             # kk = 2
if addlist[0] == 2: # 6 == 2 : False
kk += 1             # kk = 3
if addlist[0] == 3: # 6 == 3 : False
kk += 1             # kk = 4
if addlist[0] == 4: # 6 == 4 : False
kk += 1             # kk = 5
if addlist[0] == 5: # 6 == 5 : False
kk += 1             # kk = 6
if addlist[0] == 6: # 6 == 6 : True
jj += 1             # jj = 1
kk += 1             # kk = 7
if addlist[1] == 7: # 2 == 7 : False
kk += 1             # kk = 8
if addlist[1] == 8: # 2 == 8 : False
...                 # loop for ever

The error is clear!

Ok, so lets change this. We know that the deletes and the adds are in an order, and that order is important! We should be able to guess that inserts and removals should be able to happen anywhere. We need the algorithm to work with numbers in any order.

And so honestly I'd recommend a new algorithm.

To make all the code easier I'd highly recommend that you change the input, this input should be a list in the order you want to add and remove. The items in this list should be (operation, index).

To save you figuring out how to change your current input to this form. You want to:

1. Make two lists. One of operations, one of indexes.
2. zip lists together.
3. Change list to list of list, from list of tuples (Python2) or iterator of tuples (Python3).

And so:

list_ = [list(i) for i in
         zip(['del'] * len(dellist) + ['add'] * len(addlist), dellist + addlist)]

Not too nice to read, but it makes the algorithm much nicer! Your plus minus method doesn't work, and so I'm not going to talk about modifying it.

And so the simplest method from this is to transform the list_ whilst iterating through it. When iterating we will want to pass it through enumerate this is to get the index in list_, we also want the operator and the index that we want to shift relative to. This results in:

for i, (operation, curr_index) in enumerate(list_):

From this we want to skip any operations that we don't know. If you later decide to remove the horrible zip list comprehension stuff. This is a simple if ...: continue:

if operation not in ('add', 'del'):
    continue

And now the main part of the algorithm. You want to change the indexes after that item by +1 if the operator is add otherwise -1.

change = 1 if operation == 'add' else -1

You then want to add the change to all the items following the current item if the index is greater than the current one. And so:

i += 1
for j, (_, index) in enumerate(list_[i:], i):
    if index >= curr_index:
        list_[j][1] += change

If we merge this all together, you should get:

def shift_indexes(dellist, addlist):
    # Transform input to better format
    list_ = [list(i) for i in
             zip(['del'] * len(dellist) + ['add'] * len(addlist), dellist + addlist)]
    for i, (operation, curr_index) in enumerate(list_, 1):
        if operation not in ('add', 'del'):
            continue
        change = 1 if operation == 'add' else -1
        for j, (_, index) in enumerate(list_[i:], i):
            if index >= curr_index:
                list_[j][1] += change
    return list_

If you have more than just add and del then you may want to use a dictionary.
The current 'dictionary' we have is:

d = {
    'add': 1,
    'del': -1
}

To use this dictionary you'd change the if and how to get change. Using dict.get to get the change or None if it's not a valid item then we can use:

change = d.get(operator, None)
if change is None:
    continue

Either way this is much simpler to what you were doing.