Packages
fixpoint
0.8.17
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/bitvector_domain.ex
defmodule CPSolver.BitVectorDomain do
import Bitwise
def new([]) do
throw(:empty_domain)
end
def new(value) when is_integer(value) do
new([value])
end
def new(domain) when is_integer(domain) do
new([domain])
end
def new({{:bit_vector, _size, _ref} = _bitmap, _offset} = domain) do
domain
end
def new(domain) do
offset = -Enum.min(domain)
domain_size = Enum.max(domain) + offset + 1
bv = :bit_vector.new(domain_size)
Enum.each(domain, fn idx -> :bit_vector.set(bv, idx + offset) end)
{bv, offset}
end
def map(domain, mapper_fun) when is_function(mapper_fun) do
to_list(domain, mapper_fun)
end
def to_list(domain, mapper_fun \\ &Function.identity/1) do
Enum.reduce(min(domain)..max(domain), [], fn i, acc ->
(contains?(domain, i) && [mapper_fun.(i) | acc]) || acc
end)
end
def size({{:bit_vector, _size, ref} = bit_vector, _offset}) do
Enum.reduce(1..last_index(bit_vector), 0, fn idx, acc ->
n = :atomics.get(ref, idx)
(n == 0 && acc) ||
acc + (for(<<bit::1 <- :binary.encode_unsigned(n)>>, do: bit) |> Enum.sum())
end)
end
def fixed?(domain) do
size(domain) == 1
end
def fail?(domain) do
size(domain) == 0
end
def min({{:bit_vector, _zero_based_max, atomics_ref} = bit_vector, offset}) do
## Skip to a first non-zero element of atomics
min_value =
Enum.reduce_while(1..last_index(bit_vector), nil, fn idx, _acc ->
case :atomics.get(atomics_ref, idx) do
0 -> {:cont, nil}
non_zero_block -> {:halt, (idx - 1) * 64 + lsb(non_zero_block) - offset}
end
end)
(min_value && min_value) || :fail
end
def max({{:bit_vector, _zero_based_max, atomics_ref} = bit_vector, offset}) do
## Skip to a last non-zero element of atomics
max_value =
Enum.reduce_while(1..last_index(bit_vector) |> Enum.reverse(), nil, fn idx, _acc ->
case :atomics.get(atomics_ref, idx) do
0 -> {:cont, nil}
non_zero_block -> {:halt, (idx - 1) * 64 + msb(non_zero_block) - offset}
end
end)
(max_value && max_value) || :fail
end
def contains?({{:bit_vector, zero_based_max, _ref} = bit_vector, offset}, value) do
vector_value = value + offset
vector_value >= 0 && vector_value < zero_based_max &&
:bit_vector.get(bit_vector, vector_value) == 1
end
def remove({bitmap, offset} = domain, value) do
cond do
!contains?(domain, value) ->
:no_change
true ->
min? = min(domain) == value
max? = max(domain) == value
cond do
## Attempt to remove fixed value
min? && max? ->
:fail
true ->
vector_value = value + offset
{:bit_vector.clear(bitmap, vector_value), offset}
## What kind of domain change happened?
domain_change =
cond do
fixed?(domain) -> :fixed
min? -> :min_change
max? -> :max_change
true -> :domain_change
end
{domain_change, domain}
end
end
end
def removeAbove({{:bit_vector, _zero_based_max, ref} = bit_vector, offset} = domain, value) do
cond do
value >= max(domain) ->
:no_change
value < min(domain) ->
:fail
true ->
vector_value = value + offset
block_index = block_index(vector_value)
last_index = last_index(bit_vector)
## Clear up all blocks that follow the block the value is in
last_index > block_index &&
Enum.each((block_index + 1)..last_index, fn idx -> :atomics.put(ref, idx, 0) end)
block_value = :atomics.get(ref, block_index)
## Find position for the value within the block
pos = rem(vector_value, 64)
# mask = (:math.pow(2, pos + 1) - 1) |> floor()
mask = (1 <<< (pos + 1)) - 1
## Remove all significant bits in the block above the value position
# msb = msb(block_value)
# shift = msb - pos
new_value = block_value &&& mask
:atomics.put(ref, block_index, new_value)
domain_change =
cond do
fail?(domain) -> :fail
fixed?(domain) -> :fixed
true -> :max_change
end
{domain_change, domain}
end
end
def removeBelow({{:bit_vector, _zero_based_max, ref} = _bit_vector, offset} = domain, value) do
cond do
value <= min(domain) ->
:no_change
value > max(domain) ->
:fail
true ->
vector_value = value + offset
block_index = block_index(vector_value)
## Clear up all blocks on the left of the block the value is in
block_index > 1 &&
Enum.each(1..(block_index - 1), fn idx -> :atomics.put(ref, idx, 0) end)
block_value = :atomics.get(ref, block_index)
## Find position for the value within the block
pos = rem(vector_value, 64)
msb = msb(block_value)
mask = ((1 <<< msb) - 1) <<< pos
## Remove all significant bits in the block below the value position
new_value = block_value &&& mask
:atomics.put(ref, block_index, new_value)
domain_change =
cond do
fail?(domain) -> :fail
fixed?(domain) -> :fixed
true -> :min_change
end
{domain_change, domain}
end
end
def fix(domain, value) do
if contains?(domain, value) do
{:fixed, new(value)}
else
:fail
end
end
## Find the index of atomics where the n-value resides
def block_index(n) do
div(n, 64) + 1
end
## Last 2 bytes of bit_vector are min and max
def last_index({:bit_vector, _zero_based_max, ref} = _bit_vector) do
:atomics.info(ref).size - 2
end
## Find least significant bit
def lsb(0) do
nil
end
def lsb(n) do
lsb(n, 0)
end
defp lsb(1, idx) do
idx
end
defp lsb(n, idx) do
((n &&& 1) == 1 && idx) ||
lsb(n >>> 1, idx + 1)
end
def msb(0) do
nil
end
def msb(n) do
msb = floor(:math.log2(n))
## Check if there is no precision loss.
## We really want to throw away the fraction part even if it may
## get very close to 1.
if floor(:math.pow(2, msb)) > n do
msb - 1
else
msb
end
end
end