Processing a sequence of additions and deletions

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 li

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:

• Make two lists. One of operations, one of indexes.

• zip lists together.

• 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.

StackExchange Code Review Q#129025, answer score: 4