Packages
fixpoint
0.7.10
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
src/bitmap.erl
%%%-------------------------------------------------------------------
%%% @author Heinz N. Gies <heinz@licenser.net>
%%% @copyright (C) 2016, Heinz N. Gies
%%% @doc Library for dealing with bitmaps in erlang.
%%%
%%% @end
%%% Created : 5 Dec 2016 by Heinz N. Gies <heinz@licenser.net>
%%%-------------------------------------------------------------------
-module(bitmap).
%% API exports
-export([
new/1,
from_list/2,
to_list/1,
from_flags/2,
from_flags/3,
to_flags/2,
union/2,
intersection/2,
invert/1,
set/2,
set_many/2,
unset/2,
test/2,
diff/2,
size/1,
bytes/1,
display_diff/3,
display/2
]).
%% Options only valid for newly created bitmaps
-type create_opt() ::
full.
%% options valid for other (i.e. converted) bitmaps
-type general_opt() ::
{size, pos_integer()}.
-type flags() :: [atom()].
-type bitmap() :: <<_:64, _:_*8>>.
-type diff_set() :: [pos_integer()].
-type diff() :: {OnlyA :: diff_set(), OnlyB :: diff_set()}.
%%====================================================================
%% API functions
%%====================================================================
%%--------------------------------------------------------------------
%% @doc Generates a new bitmap with the given options. The total size
%% will always be a multiople of 8, prefixed with a size..
%%
%% possible options are:
%% - full - the bitmap gets created with all bit s set.
%% - {size, Size} - Size of the bitmap (required)
%% @end
%%--------------------------------------------------------------------
-spec new([create_opt() | general_opt()]) ->
{ok, bitmap()} |
{error, size_needed | bad_size}.
new(Opts) ->
%% bytes gives us the total bytes of a bitmap, including the
%% 8 byte size prefix, so we need to substract that.
R1 = case proplists:get_value(size, Opts) of
undefined ->
{error, size_needed};
Size when Size =< 0 ->
{error, bad_size};
Size ->
Bytes = bitmap:bytes(Size) - 8,
Bits = Bytes * 8,
{ok, <<Size:64/unsigned, 0:Bits/unsigned>>}
end,
case {proplists:get_bool(full, Opts), R1} of
{false, R1} ->
R1;
{true, {ok, B}} ->
{ok, invert(B)};
{_, R1} ->
R1
end.
%%--------------------------------------------------------------------
%% @doc Creates a bitmap from a list of set bits.
%% @end
%%--------------------------------------------------------------------
-spec from_list([non_neg_integer()], [general_opt()]) ->
{ok, bitmap()} |
{error, size_needed | bad_size}.
from_list(Elements, Opts) ->
Size = proplists:get_value(size, Opts),
case lists:sort(Elements) of
[Min | _] = Sorted ->
Max = lists:last(Sorted),
from_list_(Size, Min, Max, Sorted);
Sorted ->
from_list_(Size, 0, 0, Sorted)
end.
from_list_(undefined, _Min, _Max, _Sorted) ->
{error, size_needed};
from_list_(Size, Min, Max, Sorted)
when Sorted =/= []
andalso (Max < 0 orelse Min < 0 orelse Max > Size) ->
{error, bad_points};
from_list_(Size, _, _, Sorted) ->
R = from_list_(0, Sorted, <<>>),
Bytes = bitmap:bytes(Size) - 8,
Bits = Bytes * 8,
Missing = Bits - bit_size(R),
{ok, <<Size:64/unsigned, R/bitstring, 0:Missing>>}.
%%--------------------------------------------------------------------
%% @doc Creates a bitmap to a list of set bits.
%% @end
%%--------------------------------------------------------------------
to_list(<<Size:64/unsigned, Bitmap:Size/bitstring, _/bitstring>>) ->
to_list(Bitmap, 0, []).
to_list(<<>>, _, Acc) ->
lists:reverse(Acc);
to_list(<<0:1, R/bitstring>>, N, Acc) ->
to_list(R, N + 1, Acc);
to_list(<<1:1, R/bitstring>>, N, Acc) ->
to_list(R, N + 1, [N | Acc]).
%%--------------------------------------------------------------------
%% @doc Converts a bitmap into flags given a set of flag options.
%% @end
%%--------------------------------------------------------------------
-spec to_flags(bitmap(), flags()) -> flags().
to_flags(Bitmap = <<Size:64/unsigned, _/bitstring>>, Flags)
when length(Flags) =< Size ->
[lists:nth(N + 1, Flags) || N <- to_list(Bitmap)].
%%--------------------------------------------------------------------
%% @doc Creates a new bitmap from a set of flags and a list of all
%% available flags. The size of the resulting bitmap equals the
%% total number of flags.
%% @end
%%--------------------------------------------------------------------
from_flags(Set, Flags) ->
Size = length(Flags),
from_flags(Set, Flags, [{size, Size}]).
%%--------------------------------------------------------------------
%% @doc Creates a new bitmap from a set of flags and a list of all
%% available flags. With custom options.
%% @end
%%--------------------------------------------------------------------
from_flags(Set, Flags, Opts) ->
Map = flag_map(Flags, 0, #{}),
from_list([maps:get(F, Map) || F <- Set], Opts).
%%--------------------------------------------------------------------
%% @doc Inverts all set items on the bitmap
%% @end
%%--------------------------------------------------------------------
-spec invert(bitmap()) -> bitmap().
invert(<<Size:64/unsigned, V:Size/unsigned, P/bitstring>>) ->
<<Size:64/unsigned, (bnot V):Size/unsigned, P/bitstring>>.
%%--------------------------------------------------------------------
%% @doc Sets a position in the bitmap.
%% @end
%%--------------------------------------------------------------------
-spec set(Position :: non_neg_integer(), bitmap()) ->
{ok, bitmap()}.
set(Position, <<Size:64/unsigned, Bitmap/binary>>)
when Position >= 0,
Position < Size ->
<<Head:Position/bitstring, _:1, Tail/bitstring>> = Bitmap,
Bitmap1 = <<Size:64/unsigned,
Head/bitstring,
1:1,
Tail/bitstring>>,
{ok, Bitmap1}.
%%--------------------------------------------------------------------
%% @doc Sets many psoitions in a bitmap (significantly faster then
%% using set multiple times!)
%% @end
%%--------------------------------------------------------------------
-spec set_many([non_neg_integer()], bitmap()) ->
{ok, bitmap()}.
set_many(Positions, <<Size:64/unsigned, _/binary>> = Bitmap) ->
{ok, Mask} = from_list(Positions, [{size, Size}]),
{ok, union(Bitmap, Mask)}.
%%--------------------------------------------------------------------
%% @doc Unsets a position in the bitmap.
%% @end
%%--------------------------------------------------------------------
-spec unset(Position :: pos_integer(), bitmap()) ->
{ok, bitmap()}.
unset(Position, <<Size:64/unsigned, Bitmap/binary>>)
when Position >= 0,
Position < Size ->
<<Head:Position/bitstring, _:1, Tail/bitstring>> = Bitmap,
Bitmap1 = <<Size:64/unsigned,
Head/bitstring,
0:1,
Tail/bitstring>>,
{ok, Bitmap1}.
%%--------------------------------------------------------------------
%% @doc Tests weather a position is set in the bitmap.
%% @end
%%--------------------------------------------------------------------
-spec test(Position :: pos_integer(), bitmap()) ->
boolean() |
{error, out_of_range}.
test(Position, <<Size:64/unsigned, Bitmap/binary>>)
when Position >= 0,
Position < Size ->
<<_Head:Position/bitstring, R:1, _Tail/bitstring>> = Bitmap,
R =:= 1.
%%--------------------------------------------------------------------
%% @doc Returns a diff of bitmaps or an error if they have a different
%% size.
%% @end
%%--------------------------------------------------------------------
-spec diff(bitmap(), bitmap()) ->
{ok, diff()} |
{error, bad_size}.
diff(Bitmap, Bitmap) ->
{ok, {[], []}};
diff(<<Size:64/unsigned, BitmapL/binary>>,
<<Size:64/unsigned, BitmapR/binary>>) ->
diff_(0, BitmapL, BitmapR, [], []).
diff_(_N, _Bitmap, _Bitmap, L, R) ->
{ok, {lists:reverse(L), lists:reverse(R)}};
diff_(N,
<<X:1, BitmapL/bitstring>>,
<<X:1, BitmapR/bitstring>>, L, R) ->
diff_(N + 1, BitmapL, BitmapR, L, R);
diff_(N,
<<1:1, BitmapL/bitstring>>,
<<0:1, BitmapR/bitstring>>, L, R) ->
diff_(N + 1, BitmapL, BitmapR, [N | L], R);
diff_(N,
<<0:1, BitmapL/bitstring>>,
<<1:1, BitmapR/bitstring>>, L, R) ->
diff_(N + 1, BitmapL, BitmapR, L, [N | R]).
%%--------------------------------------------------------------------
%% @doc Size in bytes the bitmap will take up.
%% @end
%%--------------------------------------------------------------------
-spec bytes(pos_integer()) ->
pos_integer().
bytes(Size) ->
ceiling(Size / 8) + 8.
%%--------------------------------------------------------------------
%% @doc returns the size of a bitmap.,
%% @end
%%--------------------------------------------------------------------
-spec size(bitmap()) ->
pos_integer().
size(<<Size:64/unsigned, _/binary>>) ->
Size.
%%--------------------------------------------------------------------
%% @doc Visualizes the difference between to bitmaps.
%% @end
%%--------------------------------------------------------------------
display_diff(<<Size:64, _/binary>> = LB, <<Size:64, _/binary>> = RB, Width) ->
{ok, {L, R}} = diff(LB, RB),
D = diff_view(Size, L, R),
print_grid(D, Width).
%%--------------------------------------------------------------------
%% @doc Visualizes a bitmap.
%% @end
%%--------------------------------------------------------------------
display(<<Size:64, X/binary>>, Width) ->
{V, _} = lists:split(Size, to_view(X, [])),
print_grid(V, Width).
%%--------------------------------------------------------------------
%% @doc Creates the intersection of two bitmaps (binary and)
%% @end
%%--------------------------------------------------------------------
-spec intersection(bitmap(), bitmap()) -> bitmap().
intersection(<<Size:64/unsigned, L:Size/unsigned, P/bitstring>>,
<<Size:64/unsigned, R:Size/unsigned, _/bitstring>>) ->
<<Size:64/unsigned, (L band R):Size/unsigned, P/bitstring>>.
%%--------------------------------------------------------------------
%% @doc Creates the union of two bitmaps (binary or)
%% @end
%%--------------------------------------------------------------------
-spec union(bitmap(), bitmap()) -> bitmap().
union(<<Size:64/unsigned, L:Size/unsigned, P/bitstring>>,
<<Size:64/unsigned, R:Size/unsigned, _/bitstring>>) ->
<<Size:64/unsigned, (L bor R):Size/unsigned, P/bitstring>>.
%%====================================================================
%% Internal functions
%%====================================================================
diff_view(Size, L, R) ->
diff_to_view(0, Size, L, R, []).
diff_to_view(_Size, _Size, _L, _R, Acc) ->
lists:reverse(Acc);
diff_to_view(P, Size, [P | L], R, Acc) ->
diff_to_view(P + 1, Size, L, R, [cf:format("~!r<") | Acc]);
diff_to_view(P, Size, L, [P | R], Acc) ->
diff_to_view(P + 1, Size, L, R, [cf:format("~!r>") | Acc]);
diff_to_view(P, Size, L, R, Acc) ->
diff_to_view(P + 1, Size, L, R, [cf:format("~!g*") | Acc]).
to_view(<<>>, Acc) ->
lists:reverse(Acc);
to_view(<<1:1, R/bitstring>>, Acc) ->
to_view(R, [cf:format("~!g*") | Acc]);
to_view(<<0:1, R/bitstring>>, Acc) ->
to_view(R, [cf:format("~!y_") | Acc]).
print_grid(List, Width) ->
Log = trunc(math:log10(length(List))) + 1,
Space = integer_to_list(Log),
header(Space, Width),
S = "~n~" ++ Space ++ "b ~s",
print_grid(S, List, 0, Width).
print_grid(_S, [], _N, _Count) ->
ok;
print_grid(S, List, N, Count) when length(List) > Count ->
{H, T} = lists:split(Count, List),
io:format(S, [Count * N, H]),
print_grid(S, T, N + 1, Count);
print_grid(S, List, N, Count) ->
io:format(S, [Count * N, List]).
header(Space, Width) ->
Log = trunc(math:log10(Width - 1)),
Pfx = io_lib:format("~" ++ Space ++ "c", [$\s]),
Idx = lists:seq(0, Width-1),
print_hdrs(Log, Idx, Pfx).
print_hdrs(0, Idx, Pfx) ->
io:format("~s ~s", [Pfx, [integer_to_list(X rem 10) || X <- Idx]]);
print_hdrs(N, Idx, Pfx) ->
io:format("~s ~s~n", [Pfx, remove_zero([to_s(N, X) || X <- Idx])]),
print_hdrs(N - 1, Idx, Pfx).
to_s(N, X) ->
R = (X div round(math:pow(10, N))) rem 10,
integer_to_list(R).
remove_zero(["0" | R]) ->
[$\s | remove_zero(R)];
remove_zero(R) ->
R.
ceiling(X) when X < 0 ->
trunc(X);
ceiling(X) ->
T = trunc(X),
case X - T == 0 of
true -> T;
false -> T + 1
end.
from_list_(Pos, [X | R], Acc) when X > Pos ->
Missing = X - Pos,
from_list_(X + 1, R, <<Acc/bitstring, 0:Missing, 1:1>>);
from_list_(Pos, [Pos | R], Acc) ->
from_list_(Pos + 1, R, <<Acc/bitstring, 1:1>>);
from_list_(_, [], R) ->
R.
flag_map([], _I, Map) ->
Map;
flag_map([K | R], I, Map) ->
flag_map(R, I + 1, maps:put(K, I, Map)).