Updating a SortedMultiDict

[Azzaare]

Hi there!

I know there are a lot of things ongoing before v1, so maybe there are no solutions yet to my problem, but I am trying to update the keys of a SortedMultiDict.
For the current application, it happens that the order of the elements won't change, so I am okay with a dirty solution for a while.

As for a MWE, assume we have

# initial keys (sorted)
[1, 2, 2, 3]

# values
["a", "b", "c", "d"]

# The SMD should be 
smd = SortedMultiDict([
       1 => "a",
       2 => "b",
       2 => "c",
       3 => "d",
])

# after update, keys
[2, 2, 2, 3]
# values
["a", "b", "c", "d"]

One costly approach would be to store, delete! the 3 first elements, and insert! them again (to preserve the original order). I couldn't make the delete! method work with SMD and the associated token. It seems the documentation is still in progress regarding this.

Any way I could get through it? (if I drop dict structures, I can probably do something with mutable linked list, but most likely the insertion of sorted elements dynamically won't be efficient)

[StephenVavasis]

This operation is not supported in SortedMultiDict. I would say that it is unlikely to get supported because it is an unusual operation that would be difficult to test and document (although not too difficult to implement). Here are some possible workarounds for the functionality you are looking for.

(1) If you are changing many of the keys simultaneously, say, a constant fraction of all the keys, then you can rebuild the SortedMultiDict from scratch with the updated keys. In the current implementation of SortedMultiDict, this requires O(n log n) operations. In the updated version in pull request #787 the time requirement is reduced to O(n) because the update has a SortedMultiDict constructor that runs in O(n) time if the keys are already sorted. This pull request is currently under review and awaiting merging.

(2) This and the next suggestion assume the case that you are modifying only a few keys. The next possibility is for you to hack the needed functionality into data structure yourself. First, in case you are not already familiar, take a look at the description of 2-3 trees on Wikipedia to understand the structure. To change a key in-place, first change the key of the entry of the data record of the item (a Vector indexed by the semitoken). Then go to the parent node in the tree Vector (the index of the parent node is stored in the parent field of the data record) and see if this data record is either the 2nd or 3rd child of the parent. If so, then the key stored in splitkey1 or splitkey2 of the parent also needs to be updated. And then in this case, the grandparent also needs to be checked, and so on. If you want to muck around with this, you can use the checkcorrectness routine in test_sorted_containers, which verifies the correctness of the index structure of the 2-3 tree.

(3) Another approach is to build a two-level data structure. The outer level would be a SortedDict that would store, for each "new" key, a 2-tuple of semitokens of an underlying SortedMultiDict that is indexed by the original keys. These two semitokens index the starting and ending position of records that correspond to this new key. For example, in your MWE, the SortedMultiDict would not change. The outer SortedDict would be initially 1=>(t(1,"a"),t(1,"a")), 2=>(t(2,"b"),t(2,"c")), 3=>(t(3,"d"),t(3,"d")), where t(x,y) is shorthand for the semitoken of x=>y in the SortedMultiDIct. Then to update a key in a way that preserves the order, you would just need to change the two records corresponding to the old and new keys in the outer SortedDict, so in your MWE you would delete the record for 1 and update: 2=>(t(1,"a"),t(2,"c")).

[Azzaare]

Thanks @StephenVavasis

For the current problem, I update keys only a few at a time (during an iteration over the whole SMD).
I like both approaches, 2) and 3), and will give it a go later.

I am closing the issue then :)