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 thatvaluesandsorted_indexrepresent a sorted list ofvalues. 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

Summary

Functions

get(order_rec, index)

Get value by index in sorted array

new(values)

Creates an order structure from (unsorted) array

to_sorted(order_rec, order \\ :asc)

to_sorted(values, sort_index, order)

update(order_rec, change)

update(values, positions, sort_index, change)

valid?(order_rec, order \\ :asc)