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