Packages
fixpoint
0.8.12
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/domain/bitmap_domain.ex
defmodule CPSolver.BitmapDomain do
@spec new(Enum.t()) :: {SimpleBitmap.t(), non_neg_integer()}
def new([]) do
throw(:empty_domain)
end
def new(domain) when is_integer(domain) do
new([domain])
end
def new({%SimpleBitmap{} = _bitmap, _offset} = domain) do
domain
end
def new(domain) do
offset =
case Enum.min(domain) do
## shift values so the minimum is 1
m when m <= 0 -> -m + 1
_m -> 0
end
## Build the data and create a bitmap afterwards
value_set =
Enum.reduce(domain, MapSet.new(), fn val, acc -> MapSet.put(acc, val + offset) end)
{_, data} =
Enum.reduce(1..Enum.max(value_set), {1, 0}, fn idx, {prev, sum} ->
next = 2 * prev
{next, (idx in value_set && sum + next) || sum}
end)
{SimpleBitmap.new(data), offset}
end
def map(domain, mapper_fun) when is_function(mapper_fun) do
to_list(domain, mapper_fun)
end
def to_list({bitmap, offset} = _domain, mapper_fun \\ &Function.identity/1) do
initial_value = SimpleBitmap.lsb(bitmap)
Enum.reduce(initial_value..SimpleBitmap.msb(bitmap), [], fn i, acc ->
(SimpleBitmap.set?(bitmap, i) && [mapper_fun.(i - offset) | acc]) || acc
end)
end
def size({bitmap, _offset}) do
SimpleBitmap.popcount(bitmap)
end
def fixed?(domain) do
size(domain) == 1
end
def min({bitmap, offset}) do
SimpleBitmap.lsb(bitmap) - offset
end
def max({bitmap, offset}) do
SimpleBitmap.msb(bitmap) - offset
end
def contains?({bitmap, offset}, value) do
shifted = value + offset
shifted >= 0 && SimpleBitmap.set?(bitmap, shifted)
end
def remove({bitmap, offset} = domain, value) do
shifted = value + offset
if shifted < 0 do
:no_change
else
{SimpleBitmap.unset(bitmap, shifted), offset}
|> post_remove(domain, :domain_change)
end
end
def removeAbove({bitmap, offset} = domain, value) do
cond do
value >= max(domain) ->
:no_change
value < min(domain) ->
:fail
true ->
new_bitmap =
Enum.reduce((value + 1)..max(domain), bitmap, fn val, acc ->
SimpleBitmap.unset(acc, val + offset)
end)
{new_bitmap, offset}
|> post_remove(domain, :max_change)
end
end
def removeBelow({bitmap, offset} = domain, value) do
cond do
value <= min(domain) ->
:no_change
value > max(domain) ->
:fail
true ->
new_bitmap =
Enum.reduce((value - 1)..min(domain), bitmap, fn val, acc ->
SimpleBitmap.unset(acc, val + offset)
end)
{new_bitmap, offset}
|> post_remove(domain, :min_change)
end
end
def fix(domain, value) do
if contains?(domain, value) do
{:fixed, new(value)}
else
:fail
end
end
defp post_remove(new_domain, domain, change_kind) do
case size(new_domain) do
0 ->
:fail
new_size ->
case size(domain) do
old_size when old_size == new_size ->
:no_change
old_size when old_size > new_size ->
{(new_size == 1 && :fixed) || maybe_bound_change(change_kind, new_domain, domain),
new_domain}
end
end
end
defp maybe_bound_change(change_kind, new_domain, domain) do
(min(new_domain) > min(domain) && :min_change) ||
(max(new_domain) < max(domain) && :max_change) ||
change_kind
end
end