CPSolver.Utils.MutableOrder (Fixpoint v0.10.6)
'mutable order' structure.
Currently being used by AllDifferent.BC The motivation: every time the filtering happens, it needs to update some already sorted lists of lower and/or upper bounds.
Doing sorting from scratch is expensive, so the goal is to update and keep the array sorted based only on the incoming changes.
values
is a list of (unsorted) values - this would be a list of variables' lower or upper bounds
sorted_index is a list, s.t. sorted_index[i] holds the position of values[i] in the sorted list. The upshot is that
valuesand
sorted_indexrepresent a sorted list of
values.
updated_index
- the index of the changed value in values
updated_value
- the new value for values[updated_index]
For instance: values = [2, 8, 3, 5, 2] The sorted index would be: sorted_index = [0, 4, 2, 3, 1]
updated_index = 1, updated_value = 2 means that values[1] (that had value 8) had been updated to 2
Note: value
and sorted_index
are represented by :atomics
in order to facilitate fast access and updates in place