Keep sorted list of mutable elements up to date

Question

I can use sorted or list.sort in python to sort a list that was not sorted before.

If I want my list to remain sorted as I add elements in it, I can use SortedList from the sortedcontainers module.

However, I find no ready-to-use way to keep this list sorted as elements mutate within it.

from sortedcontainers import SortedList

a = SortedList([], key=len) # sort elements by their length.
a.add([3,3,3]) # add in..
a.add([1]) # .. random..
a.add([2,2]) # .. order.
print(a) # [[1], [2, 2], [3, 3, 3]] still sorted, okay.

# Now, mutate one element.
a[0].append(1)
a[0].append(1)
print(a) # [[1, 1, 1], [2, 2], [3, 3, 3]] not sorted, not okay.

I understand that SortedList is not responsible to track changes it contained items and to keep the sorting up to date.

How do I update the sorting, then?
Is there a message I can send to a so it is aware that I have made a change at index 0 and it reconsiders the location of item 0, like a.update_sorting_of(0).
Is there another data structure dedicated to this?
Should I write it and optimize it myself?
Should I work around it and a.add(a.pop(0)) instead?
How would this workaround compare to a dedicated solution?

I can safely assume that mutating a[0] has not triggered any changes in other elements in my case (or else I would just a.sort(key=len) the whole thing).

user_2243104 · Answer

There is no mechanism to do what you want. Even if you were to resort a list after mutating an element, it'd have O(nlogn) complexity. But because add() uses bisect behind the scenes, it only has O(logn). So it's better to do something like you suggested, i.e., remove the to-be-mutated element and readd it. And if there was a function that did what you wanted, it'd probably do something similar behind the scenes, because I can't think of a better way than bisect to place an element whose sorting order may have changed.

def mutate_element(sortedlist, index, value):
    temp = sortedlist.pop(index)
    temp.append(value)
    sortedlist.add(temp)

You could also further generalise the functionality for various list-mutating methods. For example getattr(mylist, 'append') is the same as mylist.append.

def mutate_element(sortedlist, index, value):
    temp = sortedlist.pop(index)
    temp.append(value)
    sortedlist.add(temp)

You could also further generalise the functionality for various list-mutating methods. For example getattr(mylist, 'append') is the same as mylist.append.

Keep sorted list of mutable elements up to date

1 Answers