Packages
fixpoint
0.6.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/solver/store/store.ex
defmodule CPSolver.ConstraintStore do
@moduledoc """
Constraint store is a key-value store, where `key` is a variable id,
and `value` is a implementation-dependent structure that allows to
update and keep track of variables' domains.
"""
#################
alias CPSolver.{Common, Variable}
alias CPSolver.DefaultDomain, as: Domain
require Logger
@type get_operation :: Common.domain_get_operation() | nil
@type update_operation :: Common.domain_update_operation()
@unfixed Common.unfixed()
def default_store() do
CPSolver.Store.ETS
end
### Callbacks
## Tell basic constraints (a.k.a, domains) to a constraint store
@callback create(variables :: Enum.t(), opts :: Keyword.t()) ::
{:ok, any()} | {:error, any()}
## Get variable details
@callback get(store :: any(), variable :: Variable.t(), get_operation(), [any()]) ::
{:ok, any()} | {:error, any()}
@callback update(store :: any(), variable :: Variable.t(), update_operation(), [any()]) ::
any()
@callback update_domain(store :: any(), variable :: Variable.t(), update_operation(), [any()]) ::
any()
@callback dispose(store :: any(), variables :: [Variable.t()]) :: :ok | :not_found
@callback domain(store :: any(), variable :: Variable.t()) :: {:ok, any()} | {:error, any()}
@callback on_fail(store :: any(), variable :: Variable.t()) :: any()
@callback on_no_change(store :: any(), variable :: Variable.t()) :: any()
@callback on_change(
store :: any(),
variable :: Variable.t(),
change :: Common.domain_change()
) :: any()
@callback on_fix(store :: any(), variable :: Variable.t(), value :: any()) :: any()
@callback get_variables(store :: any()) :: [any()]
### API
defmacro __using__(_) do
quote do
@behaviour CPSolver.ConstraintStore
@domain_events CPSolver.Common.domain_events()
alias CPSolver.ConstraintStore
require Logger
def update(store, variable, operation, args) do
update_domain(store, variable, operation, args)
|> tap(fn
:fail ->
on_fail(store, variable)
{:fixed, value} ->
on_fix(store, variable, value)
:no_change ->
on_no_change(store, variable)
change when change in @domain_events ->
on_change(store, variable, change)
end)
end
defoverridable update: 4
end
end
def default_store_opts() do
[space: self(), store_impl: default_store()]
end
def create_store(variables, opts \\ [])
def create_store(variables, opts) do
opts = Keyword.merge(default_store_opts(), opts)
space = Keyword.get(opts, :space)
store_impl = Keyword.get(opts, :store_impl)
{:ok, store_handle} = store_impl.create(variables, opts)
fixed_variables_store = create_fixed_vars_store(variables)
store = %{
space: space,
handle: store_handle,
store_impl: store_impl,
fixed_variables: fixed_variables_store
}
{:ok,
variables
|> Enum.with_index(1)
|> Enum.map(fn {%{domain: domain} = var, index} = _indexed_var ->
var
|> Map.put(:index, index)
|> Map.put(:name, var.name)
|> Map.put(:store, store)
|> Map.put(:fixed?, Domain.fixed?(domain))
|> tap(fn v -> register_fixed(v) end)
end), store}
end
def domain(variable) do
domain(variable.store, variable)
end
def domain(%{handle: handle, store_impl: store_impl} = _store, variable) do
store_impl.domain(handle, variable)
end
def get(%{handle: handle, store_impl: store_impl} = _store, variable, operation, args \\ []) do
store_impl.get(handle, variable, operation, args)
end
def update(
%{handle: handle, store_impl: store_impl} = _store,
variable,
operation,
args \\ []
) do
store_impl.update(handle, variable, operation, args)
|> then(fn
{:fixed, value} ->
# :fail
update_fixed(variable, value)
result ->
result
end)
end
def get_variables(%{handle: handle, store_impl: store_impl} = _store) do
store_impl.get_variables(handle)
end
def dispose(%{handle: handle, store_impl: store_impl} = _store, variables) do
store_impl.dispose(handle, variables)
end
def variable_id(%Variable{id: id}) do
id
end
def variable_id(id) do
id
end
## There is a possible race condition for the updates that fix a variable.
## It goes like this:
## Propagators P1 and P2 run concurrently,
## and the filtering for each of them results
## in fixing the same variable.
## Filter calls for both P1 and P2 read the domain of the variable,
## but the updates are unaware that the domain may have already been fixed by
## another propagator.
##
## The fix: use :atomics to enforce sequential operations when updating variables to
## :fixed state.
## In the scenario above, the code checks if the variable has already been fixed
## by looking up variable index in :atomics list.
def create_fixed_vars_store(variables) do
:atomics.new(length(variables), signed: true)
end
## Note: if index is not supplied, this operation is not thread-safe
def update_fixed(%{index: nil} = variable, fixed_value) do
domain = domain(variable)
(Domain.fixed?(domain) && Domain.min(domain) != fixed_value && :fail) || :fixed
end
def update_fixed(
%{index: index, store: %{fixed_variables: fixed_vars}} = _variable,
fixed_value
) do
case :atomics.exchange(fixed_vars, index, fixed_value) do
prev_value when prev_value == @unfixed -> :fixed
prev_value when prev_value != fixed_value -> :fail
_same -> :fixed
end
end
def register_fixed(
%{index: index, domain: domain, store: %{fixed_variables: fixed_vars}} = _variable
) do
value = (Domain.fixed?(domain) && Domain.min(domain)) || @unfixed
:atomics.put(fixed_vars, index, value)
end
def fixed?(%{store: %{fixed_variables: fixed_vars}, index: index} = _var) do
:atomics.get(fixed_vars, index) != @unfixed
end
end