I'm working on an update process which inserts items into a sorted list, and processes those items' indices in the sorted list.
To help me with this, I created a sorted list with an "insert" method which returns the index of the new element in the list. For example, given a list of
[1, 3, 5], then
insert(4) will change the list to
[1, 3, 4, 5] and return
2 (0-indexed). I then process the result with
Currently, when I need to do multiple updates, I do something like
for el in elements index = list.insert(el) beginUpdates() process(index) endUpdates()
In want to optimise update time by processing multiple indices in a single update. Of course, the following would be incorrect:
indices =  for el in elements indices.append(list.insert(el)) beginUpdates() for index in indices process(index) endUpdates()
because each insert could invalidate a previously-calculated index. For example:
list = [1, 3, 5] index1 = list.insert(4) // index of 4: 2 index2 = list.insert(2) // index of 4: 3
Now, if I
process(index1), it will process the wrong index.
So I think that, in the same way that I can batch-process indices, I should have a method to batch-insert elements and get their correct indices. Something that will allow me to do
indices = list.batchInsert(elements) beginUpdates() for index in indices process(index) endUpdates()
Is there an algorithm that can elegantly do this?