aboutsummaryrefslogtreecommitdiffstats
path: root/lib/stdlib/test
diff options
context:
space:
mode:
authorPatrik Nyblom <[email protected]>2010-04-23 18:53:51 +0200
committerBjörn Gustavsson <[email protected]>2010-05-17 15:51:50 +0200
commit9d2fe9d9af19ab94ff3feb1e7b9ffd83fa6927ff (patch)
treeb419b5ab967fbc781463d6ab92e1b7539cccd1d8 /lib/stdlib/test
parenta6c89679cd6006b3e9839b426159fd4302321528 (diff)
downloadotp-9d2fe9d9af19ab94ff3feb1e7b9ffd83fa6927ff.tar.gz
otp-9d2fe9d9af19ab94ff3feb1e7b9ffd83fa6927ff.tar.bz2
otp-9d2fe9d9af19ab94ff3feb1e7b9ffd83fa6927ff.zip
Add binary:longest_common_prefix/longest_common_suffix
Add allcoator parameter to erts_get_aligned_binary_bytes_extra. Add testcases for the functions above. Add reference implementation for the functions above.
Diffstat (limited to 'lib/stdlib/test')
-rw-r--r--lib/stdlib/test/binary_module_SUITE.erl82
-rw-r--r--lib/stdlib/test/binref.erl74
2 files changed, 155 insertions, 1 deletions
diff --git a/lib/stdlib/test/binary_module_SUITE.erl b/lib/stdlib/test/binary_module_SUITE.erl
index 24545f296a..5ab9bb7b25 100644
--- a/lib/stdlib/test/binary_module_SUITE.erl
+++ b/lib/stdlib/test/binary_module_SUITE.erl
@@ -179,6 +179,88 @@ do_interesting(Module) ->
[<<4,5>>,<<7>>,<<8>>],<<>>,
[global,{scope,{0,5}},
{insert_replaced,1}])),
+ ?line 2 = Module:longest_common_prefix([<<1,2,4>>,<<1,2,3>>]),
+ ?line 2 = Module:longest_common_prefix([<<1,2,4>>,<<1,2>>]),
+ ?line 1 = Module:longest_common_prefix([<<1,2,4>>,<<1>>]),
+ ?line 0 = Module:longest_common_prefix([<<1,2,4>>,<<>>]),
+ ?line 1 = Module:longest_common_prefix([<<1,2,4>>,<<1,2,3>>,<<1,3,3>>]),
+ ?line 1 = Module:longest_common_prefix([<<1,2,4>>,<<1,2,3>>,<<1,3,3>>,<<1,2,4>>]),
+ ?line 1251 = Module:longest_common_prefix([<<0:10000,1,2,4>>,
+ <<0:10000,1,2,3>>,
+ <<0:10000,1,3,3>>,
+ <<0:10000,1,2,4>>]),
+ ?line 12501 = Module:longest_common_prefix([<<0:100000,1,2,4>>,
+ <<0:100000,1,2,3>>,
+ <<0:100000,1,3,3>>,
+ <<0:100000,1,2,4>>]),
+ ?line 1251 = Module:longest_common_prefix(
+ [make_unaligned(<<0:10000,1,2,4>>),
+ <<0:10000,1,2,3>>,
+ make_unaligned(<<0:10000,1,3,3>>),
+ <<0:10000,1,2,4>>]),
+ ?line 12501 = Module:longest_common_prefix(
+ [<<0:100000,1,2,4>>,
+ make_unaligned(<<0:100000,1,2,3>>),
+ <<0:100000,1,3,3>>,
+ make_unaligned(<<0:100000,1,2,4>>)]),
+ ?line 1250001 = Module:longest_common_prefix([<<0:10000000,1,2,4>>,
+ <<0:10000000,1,2,3>>,
+ <<0:10000000,1,3,3>>,
+ <<0:10000000,1,2,4>>]),
+ if % Too cruel for the reference implementation
+ Module =:= binary ->
+ ?line 125000001 = Module:longest_common_prefix(
+ [<<0:1000000000,1,2,4>>,
+ <<0:1000000000,1,2,3>>,
+ <<0:1000000000,1,3,3>>,
+ <<0:1000000000,1,2,4>>]);
+ true ->
+ ok
+ end,
+ ?line 1 = Module:longest_common_suffix([<<0:1000000000,1,2,4,5>>,
+ <<0:1000000000,1,2,3,5>>,
+ <<0:1000000000,1,3,3,5>>,
+ <<0:1000000000,1,2,4,5>>]),
+ ?line 1 = Module:longest_common_suffix([<<1,2,4,5>>,
+ <<0:1000000000,1,2,3,5>>,
+ <<0:1000000000,1,3,3,5>>,
+ <<0:1000000000,1,2,4,5>>]),
+ ?line 1 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<5,5>>,
+ <<0:1000000000,1,3,3,5,5>>,
+ <<0:1000000000,1,2,4,5>>]),
+ ?line 0 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<5,5>>,
+ <<0:1000000000,1,3,3,5,5>>,
+ <<0:1000000000,1,2,4>>]),
+ ?line 2 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<5,5>>,
+ <<0:1000000000,1,3,3,5,5>>,
+ <<0:1000000000,1,2,4,5,5>>]),
+ ?line 1 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<5>>,
+ <<0:1000000000,1,3,3,5,5>>,
+ <<0:1000000000,1,2,4,5,5>>]),
+ ?line 0 = Module:longest_common_suffix([<<1,2,4,5,5>>,<<>>,
+ <<0:1000000000,1,3,3,5,5>>,
+ <<0:1000000000,1,2,4,5,5>>]),
+ ?line 0 = Module:longest_common_suffix([<<>>,<<0:1000000000,1,3,3,5,5>>,
+ <<0:1000000000,1,2,4,5,5>>]),
+ ?line 0 = Module:longest_common_suffix([<<>>,<<0:1000000000,1,3,3,5,5>>,
+ <<0:1000000000,1,2,4,5,5>>]),
+ ?line 2 = Module:longest_common_suffix([<<5,5>>,<<0:1000000000,1,3,3,5,5>>,
+ <<0:1000000000,1,2,4,5,5>>]),
+ ?line 2 = Module:longest_common_suffix([<<5,5>>,<<5,5>>,<<4,5,5>>]),
+ ?line 2 = Module:longest_common_suffix([<<5,5>>,<<5,5>>,<<5,5>>]),
+ ?line 3 = Module:longest_common_suffix([<<4,5,5>>,<<4,5,5>>,<<4,5,5>>]),
+ ?line 0 = Module:longest_common_suffix([<<>>]),
+ ?line badarg = ?MASK_ERROR(Module:longest_common_suffix([])),
+ ?line badarg = ?MASK_ERROR(Module:longest_common_suffix([apa])),
+ ?line badarg = ?MASK_ERROR(Module:longest_common_suffix([[<<>>]])),
+ ?line badarg = ?MASK_ERROR(Module:longest_common_suffix([[<<0>>,
+ <<1:9>>]])),
+ ?line 0 = Module:longest_common_prefix([<<>>]),
+ ?line badarg = ?MASK_ERROR(Module:longest_common_prefix([])),
+ ?line badarg = ?MASK_ERROR(Module:longest_common_prefix([apa])),
+ ?line badarg = ?MASK_ERROR(Module:longest_common_prefix([[<<>>]])),
+ ?line badarg = ?MASK_ERROR(Module:longest_common_prefix([[<<0>>,
+ <<1:9>>]])),
ok.
parts(doc) ->
diff --git a/lib/stdlib/test/binref.erl b/lib/stdlib/test/binref.erl
index 484112428c..e98b1b2bc8 100644
--- a/lib/stdlib/test/binref.erl
+++ b/lib/stdlib/test/binref.erl
@@ -3,7 +3,8 @@
-export([compile_pattern/1,match/2,match/3,matches/2,matches/3,
split/2,split/3,replace/3,replace/4,first/1,last/1,at/2,
part/2,part/3,copy/1,copy/2,encode_unsigned/1,encode_unsigned/2,
- decode_unsigned/1,decode_unsigned/2,referenced_byte_size/1]).
+ decode_unsigned/1,decode_unsigned/2,referenced_byte_size/1,
+ longest_common_prefix/1,longest_common_suffix/1 ]).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -319,6 +320,77 @@ at(Subject,X) ->
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% longest_common_prefix
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+longest_common_prefix(LB) ->
+ try
+ true = is_list(LB) and (length(LB) > 0), % Make badarg instead of function clause
+ do_longest_common_prefix(LB,0)
+ catch
+ _:_ ->
+ erlang:error(badarg)
+ end.
+
+do_longest_common_prefix(LB,X) ->
+ case do_lcp(LB,X,no) of
+ true ->
+ do_longest_common_prefix(LB,X+1);
+ false ->
+ X
+ end.
+do_lcp([],_,_) ->
+ true;
+do_lcp([Bin|_],X,_) when byte_size(Bin) =< X ->
+ false;
+do_lcp([Bin|T],X,no) ->
+ Ch = at(Bin,X),
+ do_lcp(T,X,Ch);
+do_lcp([Bin|T],X,Ch) ->
+ Ch2 = at(Bin,X),
+ if
+ Ch =:= Ch2 ->
+ do_lcp(T,X,Ch);
+ true ->
+ false
+ end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% longest_common_suffix
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+longest_common_suffix(LB) ->
+ try
+ true = is_list(LB) and (length(LB) > 0), % Make badarg instead of function clause
+ do_longest_common_suffix(LB,0)
+ catch
+ _:_ ->
+ erlang:error(badarg)
+ end.
+
+do_longest_common_suffix(LB,X) ->
+ case do_lcs(LB,X,no) of
+ true ->
+ do_longest_common_suffix(LB,X+1);
+ false ->
+ X
+ end.
+do_lcs([],_,_) ->
+ true;
+do_lcs([Bin|_],X,_) when byte_size(Bin) =< X ->
+ false;
+do_lcs([Bin|T],X,no) ->
+ Ch = at(Bin,byte_size(Bin) - 1 - X),
+ do_lcs(T,X,Ch);
+do_lcs([Bin|T],X,Ch) ->
+ Ch2 = at(Bin,byte_size(Bin) - 1 - X),
+ if
+ Ch =:= Ch2 ->
+ do_lcs(T,X,Ch);
+ true ->
+ false
+ end.
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% part
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
part(Subject,Part) ->