Packages
fixpoint
0.10.3
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
lib/utils/mutable_order.ex
defmodule CPSolver.Utils.MutableOrder do
import CPSolver.Utils.MutableArray
@moduledoc """
'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 `values` and `sorted_index` represent 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
"""
@doc """
Creates an order structure from (unsorted) array
"""
def new(values) when is_list(values) do
n = length(values)
values_ref = make_array(values)
sort_index_ref = make_array(n)
values
|> Enum.with_index()
|> Enum.sort()
|> Enum.reduce(0, fn {_val, idx}, pos_acc ->
array_update(sort_index_ref, pos_acc, idx)
pos_acc + 1
end)
%{values: values_ref, sort_index: sort_index_ref}
end
@doc "Get value by index in sorted array"
def get(order_rec, index) do
array_get(order_rec.values, array_get(order_rec.sort_index, index))
end
def update(%{values: values_ref, sort_index: sort_index_ref} = _order_rec, change) do
update(values_ref, sort_index_ref, change)
end
def update(values, sort_index, {change_index, new_value} = _change)
when is_reference(values) and is_reference(sort_index) and is_integer(change_index) and
is_integer(new_value) do
updated_pos = array_get(sort_index, change_index)
current_value = array_get(values, change_index)
update_order_impl(
updated_pos,
values,
sort_index,
new_value,
(current_value > new_value && 0) || array_size(values) - 1
)
array_update(values, change_index, new_value)
end
defp update_order_impl(current_pos, _values, _sort_index, _new_value, last_pos)
when current_pos == last_pos do
:ok
end
defp update_order_impl(pos, values, sort_index, new_value, 0) do
if array_get(values, pos - 1) > new_value do
swap(sort_index, pos, pos - 1)
update_order_impl(pos - 1, values, sort_index, new_value, 0)
else
:ok
end
end
defp update_order_impl(pos, values, sort_index, new_value, last_index) do
if array_get(values, pos + 1) < new_value do
swap(sort_index, pos, pos + 1)
update_order_impl(pos + 1, values, sort_index, new_value, last_index)
else
:ok
end
end
def to_sorted(%{values: values, sort_index: sort_index} = _order_rec, order \\ :asc) do
to_sorted(values, sort_index, order)
end
def to_sorted(values, sort_index, order) do
Enum.reduce(1..array_size(sort_index), [], fn idx, acc ->
[array_get(values, array_get(sort_index, idx - 1)) | acc]
end)
|> then(fn desc -> (order == :asc && Enum.reverse(desc)) || desc end)
end
def test() do
values = make_array([2, 8, 3, 5, 2])
sort_index = make_array([0, 4, 2, 3, 1])
update(values, sort_index, {2, 10})
to_sorted(values, sort_index, :asc)
end
end