Remove bisect implementation
We're not using this backend, and it requires R17 (we are still
supporting R16 as of this writing).
diff --git a/rebar-test.config b/rebar-test.config
index 170844e..160b729 100644
--- a/rebar-test.config
+++ b/rebar-test.config
@@ -2,8 +2,6 @@
{deps, [
{basho_stats, "",
{git, "https://github.com/knutin/basho_stats.git", {branch, "master"}}},
- {bisect, "",
- {git, "https://github.com/knutin/bisect.git", {branch, "master"}}},
{proper, "",
{git,"https://github.com/manopapad/proper.git", "master"}},
{stdlib2, "",
diff --git a/rebar.config b/rebar.config
index 5cf51a1..0382632 100644
--- a/rebar.config
+++ b/rebar.config
@@ -1,9 +1,4 @@
{cover_enabled, true}.
-{deps, [
- {bisect, "",
- {git, "https://github.com/knutin/bisect.git", {branch, "master"}}}
- ]}.
-
{port_specs, [
{"priv/hyper_carray.so", ["c_src/hyper_carray.c"]}
diff --git a/src/hyper_bisect.erl b/src/hyper_bisect.erl
deleted file mode 100644
index 2c31521..0000000
--- a/src/hyper_bisect.erl
+++ /dev/null
@@ -1,250 +0,0 @@
--module(hyper_bisect).
--include_lib("eunit/include/eunit.hrl").
--behaviour(hyper_register).
-
--export([new/1,
- set/3,
- max_merge/1,
- max_merge/2,
- reduce_precision/2,
- bytes/1,
- register_sum/1,
- zero_count/1,
- encode_registers/1,
- decode_registers/2,
- compact/1]).
-
-
--define(KEY_SIZE, 16).
--define(VALUE_SIZE, 8).
-
-%%
-%% BEHAVIOUR
-%%
-
-new(P) ->
- DenseSize = trunc(math:pow(2, P)),
- EntrySize = (?KEY_SIZE + ?VALUE_SIZE) div 8,
- Threshold = DenseSize div EntrySize,
- {sparse, bisect:new(?KEY_SIZE div 8, ?VALUE_SIZE div 8), P, Threshold}.
-
-
-set(Index, Value, {sparse, B, P, Threshold}) ->
- V = <<Value:?VALUE_SIZE/integer>>,
- UpdateF = fun (OldValue) when OldValue >= V -> OldValue;
- (OldValue) when OldValue < V -> V
- end,
- NewB = bisect:update(B, <<Index:?KEY_SIZE/integer>>, V, UpdateF),
-
- case bisect:num_keys(NewB) < Threshold of
- true ->
- {sparse, NewB, P, Threshold};
- false ->
- {dense, bisect2dense(NewB, P)}
- end;
-
-set(Index, Value, {dense, B} = D) ->
- case binary:at(B, Index) of
- R when R > Value ->
- D;
- _ ->
- <<Left:Index/binary, _:?VALUE_SIZE, Right/binary>> = B,
- {dense, iolist_to_binary([Left, <<Value:?VALUE_SIZE/integer>>, Right])}
- end.
-
-
-
-fold(F, Acc, {sparse, B, _, _}) ->
- InterfaceF = fun (<<Index:?KEY_SIZE/integer>>,
- <<Value:?VALUE_SIZE/integer>>,
- A) ->
- F(Index, Value, A)
- end,
- bisect:foldl(B, InterfaceF, Acc);
-fold(F, Acc, {dense, B}) ->
- do_dense_fold(F, Acc, B).
-
-
-max_merge(Registers) ->
- [First | Rest] = Registers,
- lists:foldl(fun max_merge/2, First, Rest).
-
-
-
-max_merge({sparse, Small, P, T}, {sparse, Big, P, T}) ->
- ToInsert = bisect:foldl(Small,
- fun (Index, Value, Acc) ->
- case bisect:find(Big, Index) of
- not_found ->
- [{Index, Value} | Acc];
- V when V >= Value ->
- Acc;
- V when V < Value ->
- [{Index, Value} | Acc]
- end
- end,
- []),
- Merged = bisect:bulk_insert(Big, lists:sort(ToInsert)),
- {sparse, Merged, P, T};
-
-
-max_merge({dense, Left}, {dense, Right}) ->
- Merged = iolist_to_binary(
- do_dense_merge(Left, Right)),
- {dense, Merged};
-
-max_merge({dense, Dense}, {sparse, Sparse, P, _}) ->
- {dense, iolist_to_binary(
- do_dense_merge(Dense, bisect2dense(Sparse, P)))};
-
-max_merge({sparse, Sparse, P, _}, {dense, Dense}) ->
- {dense, iolist_to_binary(
- do_dense_merge(Dense, bisect2dense(Sparse, P)))}.
-
-reduce_precision(_NewP, _B) ->
- throw(not_implemented).
-
-compact(B) ->
- B.
-
-bytes({sparse, Sparse, _, _}) -> bisect:size(Sparse);
-bytes({dense, Dense}) -> erlang:byte_size(Dense).
-
-
-register_sum(B) ->
- M = case B of
- {dense, Bytes} -> erlang:byte_size(Bytes);
- {sparse, _, P, _} -> trunc(math:pow(2, P))
- end,
-
- {MaxI, Sum} = fold(fun (Index, Value, {I, Acc}) ->
- Zeros = Index - I - 1,
- {Index, Acc + math:pow(2, -Value)
- + (math:pow(2, -0) * Zeros)}
- end, {-1, 0}, B),
- Sum + (M - 1 - MaxI) * math:pow(2, -0).
-
-zero_count({dense, _} = B) ->
- fold(fun (_, 0, Acc) -> Acc + 1;
- (_, _, Acc) -> Acc
- end, 0, B);
-zero_count({sparse, B, P, _}) ->
- M = trunc(math:pow(2, P)),
- M - bisect:num_keys(B).
-
-encode_registers({dense, B}) ->
- B;
-encode_registers({sparse, B, P, _}) ->
- M = trunc(math:pow(2, P)),
- iolist_to_binary(
- do_encode_registers(M-1, B, [])).
-
-
-
-decode_registers(AllBytes, P) ->
- M = DenseSize = trunc(math:pow(2, P)),
- EntrySize = (?KEY_SIZE + ?VALUE_SIZE) div 8,
- Threshold = DenseSize div EntrySize,
-
- Bytes = case AllBytes of
- <<B:M/binary>> -> B;
- <<B:M/binary, 0>> -> B
- end,
-
- L = do_decode_registers(Bytes, 0),
- case length(L) < Threshold of
- true ->
- New = bisect:new(?KEY_SIZE div 8, ?VALUE_SIZE div 8),
- {sparse, bisect:from_orddict(New, L), P, Threshold};
- false ->
- {dense, Bytes}
- end.
-
-
-%%
-%% INTERNAL
-%%
-
-do_dense_merge(<<>>, <<>>) ->
- [];
-do_dense_merge(<<Left:?VALUE_SIZE/integer, LeftRest/binary>>,
- <<Right:?VALUE_SIZE/integer, RightRest/binary>>) ->
- [max(Left, Right) | do_dense_merge(LeftRest, RightRest)].
-
-
-
-do_dense_fold(F, Acc, B) ->
- do_dense_fold(F, Acc, B, 0).
-
-do_dense_fold(_, Acc, <<>>, _) ->
- Acc;
-do_dense_fold(F, Acc, <<Value, Rest/binary>>, Index) ->
- do_dense_fold(F, F(Index, Value, Acc), Rest, Index+1).
-
-
-
-bisect2dense(B, P) ->
- M = trunc(math:pow(2, P)),
- {LastI, L} = lists:foldl(fun ({<<Index:?KEY_SIZE/integer>>, V}, {I, Acc}) ->
- Index < M orelse throw(index_too_high),
-
- Fill = case Index - I of
- 0 ->
- [];
- ToFill ->
- binary:copy(<<0>>, ToFill - 1)
- end,
-
- {Index, [V, Fill | Acc]}
-
- end, {-1, []}, bisect:to_orddict(B)),
- %% Fill last
- Filled = [binary:copy(<<0>>, M - LastI - 1) | L],
-
- iolist_to_binary(lists:reverse(Filled)).
-
-do_encode_registers(I, _B, ByteEncoded) when I < 0 ->
- ByteEncoded;
-do_encode_registers(I, B, ByteEncoded) when I >= 0 ->
- Byte = case bisect:find(B, <<I:?KEY_SIZE/integer>>) of
- not_found ->
- <<0>>;
- V ->
- V % already encoded
- end,
- do_encode_registers(I - 1, B, [Byte | ByteEncoded]).
-
-
-do_decode_registers(<<>>, _) ->
- [];
-do_decode_registers(<<0, Rest/binary>>, I) ->
- do_decode_registers(Rest, I+1);
-do_decode_registers(<<Value:?VALUE_SIZE, Rest/binary>>, I) ->
- [{<<I:?KEY_SIZE/integer>>, <<Value:?VALUE_SIZE/integer>>}
- | do_decode_registers(Rest, I+1)].
-
-
-
-%%
-%% TESTS
-%%
-
-bisect2dense_test() ->
- P = 4,
- M = 16, % pow(2, P)
-
- {sparse, B, _, _} =
- lists:foldl(fun ({I, V}, Acc) ->
- set(I, V, Acc)
- end, new(P), [{2, 1}, {1, 1}, {4, 4}, {15, 5}]),
-
- Dense = bisect2dense(B, P),
- ?assertEqual(M, size(Dense)),
-
-
- Expected = <<0, 1, 1, 0,
- 4, 0, 0, 0,
- 0, 0, 0, 0,
- 0, 0, 0, 5>>,
- ?assertEqual(M, size(Expected)),
- ?assertEqual(Expected, Dense).