Smarter union for dense and sparse bisect.
diff --git a/src/hyper.erl b/src/hyper.erl
index 7c43629..ea16549 100644
--- a/src/hyper.erl
+++ b/src/hyper.erl
@@ -311,6 +311,25 @@
sets:intersection(LeftDistinct, RightDistinct)))
< 200).
+small_big_union_test() ->
+ random:seed(1, 2, 3),
+ SmallCard = 100,
+ BigCard = 15000, % switches to dense at 10922 items
+
+ SmallSet = sets:from_list(generate_unique(SmallCard)),
+ BigSet = sets:from_list(generate_unique(BigCard)),
+
+ SmallHyper = insert_many(sets:to_list(SmallSet), new(15, hyper_bisect)),
+ BigHyper = insert_many(sets:to_list(BigSet), new(15, hyper_bisect)),
+ ?assertMatch({hyper_bisect, {sparse, _, _, _}}, SmallHyper#hyper.registers),
+ ?assertMatch({hyper_bisect, {dense, _}}, BigHyper#hyper.registers),
+
+ UnionHyper = union(SmallHyper, BigHyper),
+ TrueUnion = sets:size(sets:union(SmallSet, BigSet)),
+ ?assert(abs(card(UnionHyper) - TrueUnion) < TrueUnion * 0.01).
+
+
+
intersect_card_test() ->
random:seed(1, 2, 3),
diff --git a/src/hyper_bisect.erl b/src/hyper_bisect.erl
index e9b4cf0..520fa30 100644
--- a/src/hyper_bisect.erl
+++ b/src/hyper_bisect.erl
@@ -72,10 +72,12 @@
lists:reverse(
do_dense_merge(Left, Right)))};
-max_merge({dense, Left}, {sparse, Right, P, _}) ->
- {dense, iolist_to_binary(
- lists:reverse(
- do_dense_merge(Left, bisect2dense(Right, P))))}.
+max_merge({dense, Dense}, {sparse, Sparse, _, _}) ->
+ do_dense_sparse_merge({dense, Dense}, bisect:to_orddict(Sparse));
+
+max_merge({sparse, Sparse, _, _}, {dense, Dense}) ->
+ do_dense_sparse_merge({dense, Dense}, bisect:to_orddict(Sparse)).
+
%%
@@ -87,6 +89,12 @@
do_dense_merge(<<Left, LeftRest/binary>>, <<Right, RightRest/binary>>) ->
[max(Left, Right) | do_dense_merge(LeftRest, RightRest)].
+do_dense_sparse_merge({dense, Dense}, []) ->
+ {dense, Dense};
+do_dense_sparse_merge({dense, Dense}, [{<<Index:?KEY_SIZE/integer>>,
+ <<Value:?VALUE_SIZE/integer>>} | Rest]) ->
+ do_dense_sparse_merge(set(Index, Value, {dense, Dense}), Rest).
+
do_dense_fold(F, Acc, B) ->
do_dense_fold(F, Acc, B, 0).
