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 process(2)
.
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?
process()
method took the actual object as a parameter rather than an index into a list?process
doesn't care about the object, just the index. The real-world context is an iOS collection view update, where I tell a controller that the data source changed, and which items are new. It then queries the data source for the data at the indices I provided.list.getIndexOf(element)
function?