Packages
fixpoint
0.8.49
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/solver/constraints/propagators/element_var.ex
defmodule CPSolver.Propagator.ElementVar do
use CPSolver.Propagator
@moduledoc """
The propagator for Element constraint.
array[index] = value,
where array is an array of variables.
"""
def new(var_array, var_index, var_value) do
new([var_array, var_index, var_value])
end
@impl true
def arguments([var_array, var_index, var_value]) do
[Arrays.new(var_array, implementation: Aja.Vector), var_index, var_value]
end
@impl true
def bind(%{args: [var_array, var_index, var_value] = _args} = propagator, source, var_field) do
bound_args =
[
Arrays.map(var_array, fn var -> Propagator.bind_to_variable(var, source, var_field) end),
Propagator.bind_to_variable(var_index, source, var_field),
Propagator.bind_to_variable(var_value, source, var_field)
]
Map.put(propagator, :args, bound_args)
end
@impl true
def variables([var_array, var_index, var_value]) do
Enum.map(var_array, fn var ->
set_propagate_on(var, :fixed)
end) ++
[
set_propagate_on(var_index, :domain_change),
set_propagate_on(var_value, :domain_change)
]
end
defp initial_reduction([], _var_index, _var_value, _state, _changes) do
throw(:fail)
end
defp initial_reduction(var_array, var_index, var_value, state, changes) do
# var_index is an index in array2d,
# so we trim D(var_index) to the size of array (0-based).
removeBelow(var_index, 0)
removeAbove(var_index, Arrays.size(var_array) - 1)
reduction(var_array, var_index, var_value, state, changes)
end
@impl true
def filter([var_array, var_index, var_value] = _args, state, changes) do
new_state = state || %{var_index_position: Arrays.size(var_array)}
res = state && filter_impl(var_array, var_index, var_value, new_state, changes)
|| initial_reduction(var_array, var_index, var_value, new_state, changes)
res == :passive && :passive || {:state, new_state}
end
defp filter_impl(var_array, var_index, var_value, %{var_index_position: idx_position} = state, changes) do
## Run reduction when either of index or value variables are fixed
map_size(changes) > 0 && (Map.has_key?(changes, idx_position) || Map.has_key?(changes, idx_position + 1))
&& reduction(var_array, var_index, var_value, state, changes)
end
defp reduction(var_array, var_index, var_value, _state, _changes) do
index_domain = domain(var_index) |> Domain.to_list()
# Step 1
## For all variables in var_array, if no values in D(var_value)
## present in their domains, then the corresponding index has to be removed.
value_domain = domain(var_value) |> Domain.to_list()
total_value_intersection =
Enum.reduce(index_domain, MapSet.new(), fn idx, intersection_acc ->
case Arrays.get(var_array, idx) do
nil ->
IO.inspect("Unexpected: no element at #{idx}")
throw(:unexpected_no_element)
elem_var ->
elem_var_domain = domain(elem_var) |> Domain.to_list()
intersection = MapSet.intersection(value_domain, elem_var_domain)
(MapSet.size(intersection) == 0 && remove(var_index, idx) && intersection_acc) ||
MapSet.union(intersection, intersection_acc)
end
end)
## Step 2
## `total_value_intersection` has domain values from D(var_value)
## such that each of them is present in at least one domain of variables
## of `var_array`
## Hence, we can remove values that are not in `total_value_intersection` from
## D(var_value)
Enum.each(value_domain, fn val ->
!MapSet.member?(total_value_intersection, val) && remove(var_value, val)
end)
end
end