CPSolver.Utils.MutableOrder (Fixpoint v0.14.4)

'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

Link to this section Summary

Link to this section Functions

Link to this function

get(order_rec, index)

Get value by index in sorted array

Creates an order structure from (unsorted) array

Link to this function

to_sorted(order_rec, order \\ :asc)

Link to this function

to_sorted(values, sort_index, order)

Link to this function

update(order_rec, change)

Link to this function

update(values, positions, sort_index, change)

Link to this function

valid?(order_rec, order \\ :asc)