diff options
Diffstat (limited to 'lib/stdlib/test/lists_SUITE.erl')
| -rw-r--r-- | lib/stdlib/test/lists_SUITE.erl | 2657 |
1 files changed, 2657 insertions, 0 deletions
diff --git a/lib/stdlib/test/lists_SUITE.erl b/lib/stdlib/test/lists_SUITE.erl new file mode 100644 index 0000000000..0089e874c8 --- /dev/null +++ b/lib/stdlib/test/lists_SUITE.erl @@ -0,0 +1,2657 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 1997-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +%%%---------------------------------------------------------------- +%%% Purpose: Test suite for the 'lists' module. +%%%----------------------------------------------------------------- + +-module(lists_SUITE). +-include("test_server.hrl"). + + +% Default timetrap timeout (set in init_per_testcase). +% This should be set relatively high (10-15 times the expected +% max testcasetime). +-define(default_timeout, ?t:minutes(4)). + +% Test server specific exports +-export([all/1]). +-export([init_per_testcase/2, fin_per_testcase/2]). + +% Test cases must be exported. +-export([member/1, reverse/1, + keymember/1, keysearch_keyfind/1, + keystore/1, keytake/1, + append/1, append_1/1, append_2/1, + seq/1, seq_loop/1, seq_2/1, seq_3/1, seq_2_e/1, seq_3_e/1, + sublist/1, flatten/1, + sublist_2/1, sublist_3/1, sublist_2_e/1, sublist_3_e/1, + flatten_1/1, flatten_2/1, flatten_1_e/1, flatten_2_e/1, + dropwhile/1, + sort/1, sort_1/1, sort_stable/1, merge/1, rmerge/1, sort_rand/1, + usort/1, usort_1/1, usort_stable/1, umerge/1, rumerge/1,usort_rand/1, + keymerge/1, rkeymerge/1, + keysort/1, keysort_1/1, keysort_i/1, keysort_stable/1, + keysort_rand/1, keysort_error/1, + ukeymerge/1, rukeymerge/1, + ukeysort/1, ukeysort_1/1, ukeysort_i/1, ukeysort_stable/1, + ukeysort_rand/1, ukeysort_error/1, + funmerge/1, rfunmerge/1, + funsort/1, funsort_1/1, funsort_stable/1, funsort_rand/1, + funsort_error/1, + ufunmerge/1, rufunmerge/1, + ufunsort/1, ufunsort_1/1, ufunsort_stable/1, ufunsort_rand/1, + ufunsort_error/1, + zip_unzip/1, zip_unzip3/1, zipwith/1, zipwith3/1, + filter_partition/1, + tickets/1, otp_5939/1, otp_6023/1, otp_6606/1, otp_7230/1, + suffix/1, subtract/1]). + +%% Sort randomized lists until stopped. +%% +%% If you update some of the sort or merge functions, you should +%% definitely let sort_loop work for a couple of hours or days. Try +%% both sort_loop/0 and sort_loop/1 with a small argument (30-50 say). + +-export([sort_loop/0, sort_loop/1, sloop/1]). + +%% Internal export. +-export([make_fun/1]). + +%% +%% all/1 +%% +all(doc) -> + []; +all(suite) -> + [append, reverse, member, keymember, keysearch_keyfind, keystore, keytake, + dropwhile, + sort, usort, keysort, ukeysort, + funsort, ufunsort, sublist, flatten, seq, + zip_unzip, zip_unzip3, zipwith, zipwith3, + filter_partition, tickets, suffix, subtract]. + +init_per_testcase(_Case, Config) -> + ?line Dog=test_server:timetrap(?default_timeout), + [{watchdog, Dog}|Config]. + +fin_per_testcase(_Case, Config) -> + Dog=?config(watchdog, Config), + test_server:timetrap_cancel(Dog), + ok. + +% +% Test cases starts here. +% +append(doc) -> + ["Tests lists:append/1 & lists:append/2"]; +append(suite) -> + [append_1, append_2]. + +append_1(doc) -> []; +append_1(suite) -> []; +append_1(Config) when is_list(Config) -> + ?line "abcdef"=lists:append(["abc","def"]), + ?line [hej, du,[glade, [bagare]]]= + lists:append([[hej], [du], [[glade, [bagare]]]]), + ?line [10, [elem]]=lists:append([[10], [[elem]]]), + ok. + +append_2(doc) -> []; +append_2(suite) -> []; +append_2(Config) when is_list(Config) -> + ?line "abcdef"=lists:append("abc", "def"), + ?line [hej, du]=lists:append([hej], [du]), + ?line [10, [elem]]=lists:append([10], [[elem]]), + ok. + +reverse(suite) -> + []; +reverse(doc) -> + ["Tests the lists:reverse() implementation. The function is " + "`non-blocking', and only processes a fixed number of elements " + "at a time."]; +reverse(Config) when is_list(Config) -> + ?line reverse_test(0), + ?line reverse_test(1), + ?line reverse_test(2), + ?line reverse_test(128), + ?line reverse_test(256), + ?line reverse_test(1000), + ?line reverse_test(1998), + ?line reverse_test(1999), + ?line reverse_test(2000), + ?line reverse_test(2001), + ?line reverse_test(3998), + ?line reverse_test(3999), + ?line reverse_test(4000), + ?line reverse_test(4001), + ?line reverse_test(60001), + ?line reverse_test(100007), + ok. + +reverse_test(0) -> + case lists:reverse([]) of + [] -> + ok; + _Other -> + error + end; +reverse_test(Num) -> + List0 = ['The Element'|lists:duplicate(Num, 'Ele')], + List = lists:reverse(List0), + ['Ele'|_] = List, + 'The Element' = lists:last(List), + List0 = lists:reverse(List), + ok. + +member(doc) -> + ["Tests the lists:member() implementation." + "This test case depends on lists:reverse() to work, " + "wich is tested in a separate test case."]; +member(Config) when is_list(Config) -> + ?line {'EXIT',{badarg,_}} = (catch lists:member(45, {a,b,c})), + ?line {'EXIT',{badarg,_}} = (catch lists:member(45, [0|non_list_tail])), + ?line false = lists:member(4233, []), + ?line member_test(1), + ?line member_test(100), + ?line member_test(256), + ?line member_test(1000), + ?line member_test(1998), + ?line member_test(1999), + ?line member_test(2000), + ?line member_test(2001), + ?line member_test(3998), + ?line member_test(3999), + ?line member_test(4000), + ?line member_test(4001), + ?line member_test(100008), + ok. + +member_test(Num) -> + List0 = ['The Element'|lists:duplicate(Num, 'Elem')], + true = lists:member('The Element', List0), + true = lists:member('Elem', List0), + false = lists:member(arne_anka, List0), + false = lists:member({a,b,c}, List0), + List = lists:reverse(List0), + true = lists:member('The Element', List), + true = lists:member('Elem', List), + false = lists:member(arne_anka, List), + false = lists:member({a,b,c}, List). + +keymember(Config) when is_list(Config) -> + ?line false = lists:keymember(anything_goes, 1, []), + ?line {'EXIT',{badarg,_}} = (catch lists:keymember(anything_goes, -1, [])), + ?line {'EXIT',{badarg,_}} = (catch lists:keymember(anything_goes, 0, [])), + ?line {'EXIT',{badarg,_}} = (catch lists:keymember(anything_goes, 1, {1,2,3})), + List = [{52.0,a},{-19,b,c},{37.5,d},an_atom,42.0,{39},{45,{x,y,z}}], + + ?line false = lists:keymember(333, 5, List), + ?line false = lists:keymember(333, 999, List), + ?line false = lists:keymember(37, 1, List), + + ?line true = lists:keymember(52.0, 1, List), + ?line true = lists:keymember(52, 1, List), + ?line true = lists:keymember(-19, 1, List), + ?line true = lists:keymember(-19.0, 1, List), + ?line true = lists:keymember(37.5, 1, List), + ?line true = lists:keymember(39, 1, List), + ?line true = lists:keymember(39.0, 1, List), + ?line true = lists:keymember(45, 1, List), + ?line true = lists:keymember(45.0, 1, List), + + ?line true = lists:keymember(a, 2, List), + ?line true = lists:keymember(b, 2, List), + ?line true = lists:keymember(c, 3, List), + ?line true = lists:keymember(d, 2, List), + ?line true = lists:keymember({x,y,z}, 2, List), + + ?line Long0 = lists:seq(1, 100007), + ?line false = lists:keymember(kalle, 1, Long0), + ?line Long = lists:foldl(fun(E, A) -> [{1/E,E}|A] end, [], Long0), + ?line true = lists:keymember(1, 2, Long), + ?line true = lists:keymember(2, 2, Long), + ?line true = lists:keymember(1.0, 2, Long), + ?line true = lists:keymember(2.0, 2, Long), + ?line true = lists:keymember(100006, 2, Long), + ok. + +keysearch_keyfind(Config) when is_list(Config) -> + ?line false = key_search_find(anything_goes, 1, []), + ?line {'EXIT',{badarg,_}} = (catch key_search_find(anything_goes, -1, [])), + ?line {'EXIT',{badarg,_}} = (catch key_search_find(anything_goes, 0, [])), + ?line {'EXIT',{badarg,_}} = (catch key_search_find(anything_goes, 1, {1,2,3})), + + First = {x,42.0}, + Second = {y,-77}, + Third = {z,[a,b,c],{5.0}}, + List = [First,Second,Third], + + ?line false = key_search_find(333, 1, []), + ?line false = key_search_find(333, 5, List), + ?line false = key_search_find(333, 999, List), + ?line false = key_search_find(37, 1, List), + + ?line {value,First} = key_search_find(42, 2, List), + ?line {value,First} = key_search_find(42.0, 2, List), + + ?line {value,Second} = key_search_find(-77, 2, List), + ?line {value,Second} = key_search_find(-77.0, 2, List), + + ?line {value,Third} = key_search_find(z, 1, List), + ?line {value,Third} = key_search_find([a,b,c], 2, List), + ?line {value,Third} = key_search_find({5}, 3, List), + ?line {value,Third} = key_search_find({5.0}, 3, List), + + ?line Long0 = lists:seq(1, 100007), + ?line false = key_search_find(kalle, 1, Long0), + ?line Long = lists:foldl(fun(E, A) -> [{1/E,float(E)}|A] end, [], Long0), + ?line {value,{_,1.0}} = key_search_find(1, 2, Long), + ?line {value,{_,1.0}} = key_search_find(1.0, 2, Long), + ?line {value,{_,2.0}} = key_search_find(2, 2, Long), + ?line {value,{_,2.0}} = key_search_find(2.0, 2, Long), + ?line {value,{_,33988.0}} = key_search_find(33988, 2, Long), + ?line {value,{_,33988.0}} = key_search_find(33988.0, 2, Long), + ok. + +%% Test both lists:keysearch/3 and lists:keyfind/3. The only +%% difference between these two functions is that lists:keysearch/3 +%% wraps a successfully returned tuple in a value tuple. +%% +key_search_find(Key, Pos, List) -> + case lists:keyfind(Key, Pos, List) of + false -> + false = lists:keysearch(Key, Pos, List); + Tuple when is_tuple(Tuple) -> + {value,Tuple} = lists:keysearch(Key, Pos, List) + end. + +dropwhile(Config) when is_list(Config) -> + ?line F = fun(C) -> C =:= $@ end, + + ?line [] = lists:dropwhile(F, []), + ?line [a] = lists:dropwhile(F, [a]), + ?line [a,b] = lists:dropwhile(F, [a,b]), + ?line [a,b,c] = lists:dropwhile(F, [a,b,c]), + + ?line [] = lists:dropwhile(F, [$@]), + ?line [] = lists:dropwhile(F, [$@,$@]), + ?line [a,$@] = lists:dropwhile(F, [$@,a,$@]), + + ?line [$k] = lists:dropwhile(F, [$@,$k]), + ?line [$k,$l] = lists:dropwhile(F, [$@,$@,$k,$l]), + ?line [a] = lists:dropwhile(F, [$@,$@,$@,a]), + + ?line [a,$@,b] = lists:dropwhile(F, [$@,a,$@,b]), + ?line [a,$@,b] = lists:dropwhile(F, [$@,$@,a,$@,b]), + ?line [a,$@,b] = lists:dropwhile(F, [$@,$@,$@,a,$@,b]), + + Long = lists:seq(1, 1024), + Shorter = lists:seq(800, 1024), + + ?line Shorter = lists:dropwhile(fun(E) -> E < 800 end, Long), + + ok. + +keystore(doc) -> + ["OTP-XXX."]; +keystore(suite) -> []; +keystore(Config) when is_list(Config) -> + ?line {'EXIT',_} = (catch lists:keystore(key, 0, [], {1})), + ?line {'EXIT',_} = (catch lists:keystore(key, 1, {}, {})), + ?line {'EXIT',_} = (catch lists:keystore(key, 1, {a,b}, {})), + ?line {'EXIT', _} = (catch lists:keystore(a, 2, [{1,a}], b)), + T = {k,17}, + ?line [T] = lists:keystore(a, 2, [], T), + ?line [{1,a},{2,b},{k,17}] = lists:keystore(c, 2, [{1,a},{2,b}],T), + L = [{1,a},{2,b},{3,c}], + ?line [{k,17},{2,b},{3,c}] = lists:keystore(a, 2, L, T), + ?line [{1,a},{k,17},{3,c}] = lists:keystore(b, 2, L, T), + ?line [{1,a},{2,b},{k,17}] = lists:keystore(c, 2, L, T), + ?line [{2,b}] = lists:keystore(a, 2, [{1,a}], {2,b}), + ?line [{1,a}] = lists:keystore(foo, 1, [], {1,a}), + ok. + +keytake(doc) -> + ["OTP-XXX."]; +keytake(suite) -> []; +keytake(Config) when is_list(Config) -> + ?line {'EXIT',_} = (catch lists:keytake(key, 0, [])), + ?line {'EXIT',_} = (catch lists:keytake(key, 1, {})), + ?line {'EXIT',_} = (catch lists:keytake(key, 1, {a,b})), + ?line false = lists:keytake(key, 2, [{a}]), + ?line false = lists:keytake(key, 1, [a]), + ?line false = lists:keytake(k, 1, []), + ?line false = lists:keytake(k, 1, [{a},{b},{c}]), + L = [{a,1},{b,2},{c,3}], + ?line {value,{a,1},[{b,2},{c,3}]} = lists:keytake(1, 2, L), + ?line {value,{b,2},[{a,1},{c,3}]} = lists:keytake(2, 2, L), + ?line {value,{c,3},[{a,1},{b,2}]} = lists:keytake(3, 2, L), + ?line false = lists:keytake(4, 2, L), + ok. + +sort(doc) -> + ["Tests merge functions and lists:sort/1"]; +sort(suite) -> + %% [merge, rmerge, sort_1, sort_rand, sort_stable]. + [merge, rmerge, sort_1, sort_rand]. + +merge(doc) -> ["merge functions"]; +merge(suite) -> []; +merge(Config) when is_list(Config) -> + + %% merge list of lists + ?line [] = lists:merge([]), + ?line [] = lists:merge([[]]), + ?line [] = lists:merge([[],[]]), + ?line [] = lists:merge([[],[],[]]), + ?line [1] = lists:merge([[1]]), + ?line [1,1,2,2] = lists:merge([[1,2],[1,2]]), + ?line [1] = lists:merge([[1],[],[]]), + ?line [1] = lists:merge([[],[1],[]]), + ?line [1] = lists:merge([[],[],[1]]), + ?line [1,2] = lists:merge([[1],[2],[]]), + ?line [1,2] = lists:merge([[1],[],[2]]), + ?line [1,2] = lists:merge([[],[1],[2]]), + ?line [1,2,3,4,5,6] = lists:merge([[1,2],[],[5,6],[],[3,4],[]]), + ?line [1,2,3,4] = lists:merge([[4],[3],[2],[1]]), + ?line [1,2,3,4,5] = lists:merge([[1],[2],[3],[4],[5]]), + ?line [1,2,3,4,5,6] = lists:merge([[1],[2],[3],[4],[5],[6]]), + ?line [1,2,3,4,5,6,7,8,9] = + lists:merge([[1],[2],[3],[4],[5],[6],[7],[8],[9]]), + Seq = lists:seq(1,100), + ?line true = Seq == lists:merge(lists:map(fun(E) -> [E] end, Seq)), + + Two = [1,2], + Six = [1,2,3,4,5,6], + + %% 2-way merge + ?line [] = lists:merge([], []), + ?line Two = lists:merge(Two, []), + ?line Two = lists:merge([], Two), + ?line Six = lists:merge([1,3,5], [2,4,6]), + ?line Six = lists:merge([2,4,6], [1,3,5]), + ?line Six = lists:merge([1,2,3], [4,5,6]), + ?line Six = lists:merge([4,5,6], [1,2,3]), + ?line Six = lists:merge([1,2,5],[3,4,6]), + ?line [1,2,3,5,7] = lists:merge([1,3,5,7], [2]), + ?line [1,2,3,4,5,7] = lists:merge([1,3,5,7], [2,4]), + ?line [1,2,3,4,5,6,7] = lists:merge([1,3,5,7], [2,4,6]), + ?line [1,2,3,5,7] = lists:merge([2], [1,3,5,7]), + ?line [1,2,3,4,5,7] = lists:merge([2,4], [1,3,5,7]), + ?line [1,2,3,4,5,6,7] = lists:merge([2,4,6], [1,3,5,7]), + + %% 3-way merge + ?line [] = lists:merge3([], [], []), + ?line Two = lists:merge3([], [], Two), + ?line Two = lists:merge3([], Two, []), + ?line Two = lists:merge3(Two, [], []), + ?line Six = lists:merge3([], [1,3,5], [2,4,6]), + ?line Six = lists:merge3([1,3,5], [], [2,4,6]), + ?line Six = lists:merge3([1,3,5], [2,4,6], []), + ?line Nine = lists:merge3([1,4,7],[2,5,8],[3,6,9]), + ?line Nine = lists:merge3([1,4,7],[3,6,9],[2,5,8]), + ?line Nine = lists:merge3([3,6,9],[1,4,7],[2,5,8]), + ?line Nine = lists:merge3([4,5,6],[1,2,3],[7,8,9]), + ?line Nine = lists:merge3([1,2,3],[4,5,6],[7,8,9]), + ?line Nine = lists:merge3([7,8,9],[4,5,6],[1,2,3]), + ?line Nine = lists:merge3([4,5,6],[7,8,9],[1,2,3]), + + ok. + +rmerge(doc) -> ["reverse merge functions"]; +rmerge(suite) -> []; +rmerge(Config) when is_list(Config) -> + + Two = [2,1], + Six = [6,5,4,3,2,1], + + %% 2-way reversed merge + ?line [] = lists:rmerge([], []), + ?line Two = lists:rmerge(Two, []), + ?line Two = lists:rmerge([], Two), + ?line Six = lists:rmerge([5,3,1], [6,4,2]), + ?line Six = lists:rmerge([6,4,2], [5,3,1]), + ?line Six = lists:rmerge([3,2,1], [6,5,4]), + ?line Six = lists:rmerge([6,5,4], [3,2,1]), + ?line Six = lists:rmerge([4,3,2],[6,5,1]), + ?line [7,6,5,3,1] = lists:rmerge([7,5,3,1], [6]), + ?line [7,6,5,4,3,1] = lists:rmerge([7,5,3,1], [6,4]), + ?line [7,6,5,4,3,2,1] = lists:rmerge([7,5,3,1], [6,4,2]), + ?line [7,5,3,2,1] = lists:rmerge([2], [7,5,3,1]), + ?line [7,5,4,3,2,1] = lists:rmerge([4,2], [7,5,3,1]), + ?line [7,6,5,4,3,2,1] = lists:rmerge([6,4,2], [7,5,3,1]), + + Nine = [9,8,7,6,5,4,3,2,1], + + %% 3-way reversed merge + ?line [] = lists:rmerge3([], [], []), + ?line Two = lists:rmerge3([], [], Two), + ?line Two = lists:rmerge3([], Two, []), + ?line Two = lists:rmerge3(Two, [], []), + ?line Six = lists:rmerge3([], [5,3,1], [6,4,2]), + ?line Six = lists:rmerge3([5,3,1], [], [6,4,2]), + ?line Six = lists:rmerge3([5,3,1], [6,4,2], []), + ?line Nine = lists:rmerge3([7,4,1],[8,5,2],[9,6,3]), + ?line Nine = lists:rmerge3([7,4,1],[9,6,3],[8,5,2]), + ?line Nine = lists:rmerge3([9,6,3],[7,4,1],[8,5,2]), + ?line Nine = lists:rmerge3([6,5,4],[3,2,1],[9,8,7]), + ?line Nine = lists:rmerge3([3,2,1],[6,5,4],[9,8,7]), + ?line Nine = lists:rmerge3([9,8,7],[6,5,4],[3,2,1]), + ?line Nine = lists:rmerge3([6,5,4],[9,8,7],[3,2,1]), + + ok. + +sort_1(doc) -> ["sort/1"]; +sort_1(suite) -> []; +sort_1(Config) when is_list(Config) -> + ?line [] = lists:sort([]), + ?line [a] = lists:sort([a]), + ?line [a,a] = lists:sort([a,a]), + ?line [a,b] = lists:sort([a,b]), + ?line [a,b] = lists:sort([b,a]), + ?line [1,1] = lists:sort([1,1]), + ?line [1,1,2,3] = lists:sort([1,1,3,2]), + ?line [1,2,3,3] = lists:sort([3,3,1,2]), + ?line [1,1,1,1] = lists:sort([1,1,1,1]), + ?line [1,1,1,2,2,2,3,3,3] = lists:sort([3,3,3,2,2,2,1,1,1]), + ?line [1,1,1,2,2,2,3,3,3] = lists:sort([1,1,1,2,2,2,3,3,3]), + + ?line lists:foreach(fun check/1, perms([1,2,3])), + ?line lists:foreach(fun check/1, perms([1,2,3,4,5,6,7,8])), + ok. + +sort_rand(doc) -> ["sort/1 on big randomized lists"]; +sort_rand(suite) -> []; +sort_rand(Config) when is_list(Config) -> + ?line ok = check(biglist(10)), + ?line ok = check(biglist(100)), + ?line ok = check(biglist(1000)), + ?line ok = check(biglist(10000)), + ok. + +%% sort/1 was really stable for a while - the order of equal elements +%% was kept - but since the performance suffered a bit, this "feature" +%% was removed. +sort_stable(doc) -> ["sort/1 should be stable for equal terms."]; +sort_stable(suite) -> []; +sort_stable(Config) when is_list(Config) -> + ?line ok = check_stability(bigfunlist(10)), + ?line ok = check_stability(bigfunlist(100)), + ?line ok = check_stability(bigfunlist(1000)), + ?line case erlang:system_info(modified_timing_level) of + undefined -> ok = check_stability(bigfunlist(10000)); + _ -> ok + end, + ok. + +check([]) -> + ok; +check(L) -> + S = lists:sort(L), + case {length(L) == length(S), check(hd(S), tl(S))} of + {true,ok} -> + ok; + _ -> + io:format("~w~n", [L]), + erlang:error(check) + end. + +check(_A, []) -> + ok; +check(A, [B | L]) when A =< B -> + check(B, L); +check(_A, _L) -> + no. + +%% The check that sort/1 is stable is no longer used. +%% Equal elements are no longer always kept in order. +check_stability(L) -> + S = lists:sort(L), + LP = explicit_pid(L), + SP = explicit_pid(S), + check_sorted(1, 2, LP, SP). + +explicit_pid(L) -> + lists:reverse(expl_pid(L, [])). + +expl_pid([{I,F} | T], L) when is_function(F) -> + expl_pid(T, [{I,fun_pid(F)} | L]); +expl_pid([], L) -> + L. + +usort(doc) -> + ["Tests unique merge functions and lists:usort/1"]; +usort(suite) -> + [umerge, rumerge, usort_1, usort_rand, usort_stable]. + +usort_1(suite) -> []; +usort_1(doc) -> [""]; +usort_1(Conf) when is_list(Conf) -> + ?line [] = lists:usort([]), + ?line [1] = lists:usort([1]), + ?line [1] = lists:usort([1,1]), + ?line [1] = lists:usort([1,1,1,1,1]), + ?line [1,2] = lists:usort([1,2]), + ?line [1,2] = lists:usort([1,2,1]), + ?line [1,2] = lists:usort([1,2,2]), + ?line [1,2,3] = lists:usort([1,3,2]), + ?line [1,3] = lists:usort([3,1,3]), + ?line [0,1,3] = lists:usort([3,1,0]), + ?line [1,2,3] = lists:usort([3,1,2]), + ?line [1,2] = lists:usort([2,1,1]), + ?line [1,2] = lists:usort([2,1]), + ?line [0,3,4,8,9] = lists:usort([3,8,9,0,9,4]), + + ?line lists:foreach(fun ucheck/1, perms([1,2,3])), + ?line lists:foreach(fun ucheck/1, perms([1,2,3,4,5,6,2,1])), + + ok. + +umerge(suite) -> []; +umerge(doc) -> [""]; +umerge(Conf) when is_list(Conf) -> + %% merge list of lists + ?line [] = lists:umerge([]), + ?line [] = lists:umerge([[]]), + ?line [] = lists:umerge([[],[]]), + ?line [] = lists:umerge([[],[],[]]), + ?line [1] = lists:umerge([[1]]), + ?line [1,2] = lists:umerge([[1,2],[1,2]]), + ?line [1] = lists:umerge([[1],[],[]]), + ?line [1] = lists:umerge([[],[1],[]]), + ?line [1] = lists:umerge([[],[],[1]]), + ?line [1,2] = lists:umerge([[1],[2],[]]), + ?line [1,2] = lists:umerge([[1],[],[2]]), + ?line [1,2] = lists:umerge([[],[1],[2]]), + ?line [1,2,3,4,5,6] = lists:umerge([[1,2],[],[5,6],[],[3,4],[]]), + ?line [1,2,3,4] = lists:umerge([[4],[3],[2],[1]]), + ?line [1,2,3,4,5] = lists:umerge([[1],[2],[3],[4],[5]]), + ?line [1,2,3,4,5,6] = lists:umerge([[1],[2],[3],[4],[5],[6]]), + ?line [1,2,3,4,5,6,7,8,9] = + lists:umerge([[1],[2],[3],[4],[5],[6],[7],[8],[9]]), + ?line [1,2,4,6,8] = lists:umerge([[1,2],[2,4,6,8]]), + Seq = lists:seq(1,100), + ?line true = Seq == lists:umerge(lists:map(fun(E) -> [E] end, Seq)), + + Two = [1,2], + Six = [1,2,3,4,5,6], + + %% 2-way unique merge + ?line [] = lists:umerge([], []), + ?line Two = lists:umerge(Two, []), + ?line Two = lists:umerge([], Two), + ?line Six = lists:umerge([1,3,5], [2,4,6]), + ?line Six = lists:umerge([2,4,6], [1,3,5]), + ?line Six = lists:umerge([1,2,3], [4,5,6]), + ?line Six = lists:umerge([4,5,6], [1,2,3]), + ?line Six = lists:umerge([1,2,5],[3,4,6]), + ?line [1,2,3,5,7] = lists:umerge([1,3,5,7], [2]), + ?line [1,2,3,4,5,7] = lists:umerge([1,3,5,7], [2,4]), + ?line [1,2,3,4,5,6,7] = lists:umerge([1,3,5,7], [2,4,6]), + ?line [1,2,3,5,7] = lists:umerge([2], [1,3,5,7]), + ?line [1,2,3,4,5,7] = lists:umerge([2,4], [1,3,5,7]), + ?line [1,2,3,4,5,6,7] = lists:umerge([2,4,6], [1,3,5,7]), + + ?line [1,2,3,5,7] = lists:umerge([1,2,3,5,7], [2]), + ?line [1,2,3,4,5,7] = lists:umerge([1,2,3,4,5,7], [2,4]), + ?line [1,2,3,4,5,6,7] = lists:umerge([1,2,3,4,5,6,7], [2,4,6]), + ?line [1,2,3,5,7] = lists:umerge([2], [1,2,3,5,7]), + ?line [1,2,3,4,5,7] = lists:umerge([2,4], [1,2,3,4,5,7]), + ?line [1,2,3,4,5,6,7] = lists:umerge([2,4,6], [1,2,3,4,5,6,7]), + + %% 3-way unique merge + ?line [] = lists:umerge3([], [], []), + ?line Two = lists:umerge3([], [], Two), + ?line Two = lists:umerge3([], Two, []), + ?line Two = lists:umerge3(Two, [], []), + ?line Six = lists:umerge3([], [1,3,5], [2,4,6]), + ?line Six = lists:umerge3([1,3,5], [], [2,4,6]), + ?line Six = lists:umerge3([1,3,5], [2,4,6], []), + ?line Nine = lists:umerge3([1,4,7],[2,5,8],[3,6,9]), + ?line Nine = lists:umerge3([1,4,7],[3,6,9],[2,5,8]), + ?line Nine = lists:umerge3([3,6,9],[1,4,7],[2,5,8]), + ?line Nine = lists:umerge3([4,5,6],[1,2,3],[7,8,9]), + ?line Nine = lists:umerge3([1,2,3],[4,5,6],[7,8,9]), + ?line Nine = lists:umerge3([7,8,9],[4,5,6],[1,2,3]), + ?line Nine = lists:umerge3([4,5,6],[7,8,9],[1,2,3]), + + ?line [1,2,3] = lists:umerge3([1,2,3],[1,2,3],[1,2,3]), + ?line [1,2,3,4] = lists:umerge3([2,3,4],[1,2,3],[2,3,4]), + ?line [1,2,3] = lists:umerge3([1,2,3],[2,3],[1,2,3]), + ?line [1,2,3,4] = lists:umerge3([2,3,4],[3,4],[1,2,3]), + + ok. + +rumerge(suite) -> []; +rumerge(doc) -> [""]; +rumerge(Conf) when is_list(Conf) -> + Two = [2,1], + Six = [6,5,4,3,2,1], + + %% 2-way reversed unique merge + ?line [] = lists:rumerge([], []), + ?line Two = lists:rumerge(Two, []), + ?line Two = lists:rumerge([], Two), + ?line Six = lists:rumerge([5,3,1], [6,4,2]), + ?line Six = lists:rumerge([6,4,2], [5,3,1]), + ?line Six = lists:rumerge([3,2,1], [6,5,4]), + ?line Six = lists:rumerge([6,5,4], [3,2,1]), + ?line Six = lists:rumerge([4,3,2],[6,5,1]), + ?line [7,6,5,3,1] = lists:rumerge([7,5,3,1], [6]), + ?line [7,6,5,4,3,1] = lists:rumerge([7,5,3,1], [6,4]), + ?line [7,6,5,4,3,2,1] = lists:rumerge([7,5,3,1], [6,4,2]), + ?line [7,5,3,2,1] = lists:rumerge([2], [7,5,3,1]), + ?line [7,5,4,3,2,1] = lists:rumerge([4,2], [7,5,3,1]), + ?line [7,6,5,4,3,2,1] = lists:rumerge([6,4,2], [7,5,3,1]), + + ?line [7,6,5,3,1] = lists:rumerge([7,6,5,3,1], [6]), + ?line [7,6,5,4,3,1] = lists:rumerge([7,6,5,4,3,1], [6,4]), + ?line [7,6,5,4,3,2,1] = lists:rumerge([7,6,5,4,3,2,1], [6,4,2]), + ?line [7,5,3,2,1] = lists:rumerge([2], [7,5,3,2,1]), + ?line [7,5,4,3,2,1] = lists:rumerge([4,2], [7,5,4,3,2,1]), + ?line [7,6,5,4,3,2,1] = lists:rumerge([6,4,2], [7,6,5,4,3,2,1]), + + Nine = [9,8,7,6,5,4,3,2,1], + + %% 3-way reversed unique merge + ?line [] = lists:rumerge3([], [], []), + ?line Two = lists:rumerge3([], [], Two), + ?line Two = lists:rumerge3([], Two, []), + ?line Two = lists:rumerge3(Two, [], []), + ?line Six = lists:rumerge3([], [5,3,1], [6,4,2]), + ?line Six = lists:rumerge3([5,3,1], [], [6,4,2]), + ?line Six = lists:rumerge3([5,3,1], [6,4,2], []), + ?line Nine = lists:rumerge3([7,4,1],[8,5,2],[9,6,3]), + ?line Nine = lists:rumerge3([7,4,1],[9,6,3],[8,5,2]), + ?line Nine = lists:rumerge3([9,6,3],[7,4,1],[8,5,2]), + ?line Nine = lists:rumerge3([6,5,4],[3,2,1],[9,8,7]), + ?line Nine = lists:rumerge3([3,2,1],[6,5,4],[9,8,7]), + ?line Nine = lists:rumerge3([9,8,7],[6,5,4],[3,2,1]), + ?line Nine = lists:rumerge3([6,5,4],[9,8,7],[3,2,1]), + + ?line [3,2,1] = lists:rumerge3([3,2,1],[3,2,1],[3,2,1]), + ?line [4,3,2,1] = lists:rumerge3([4,3,2],[3,2,1],[3,2,1]), + ?line [5,4,3,2,1] = lists:rumerge3([4,3,2],[5,4,3,2],[5,4,3,2,1]), + ?line [6,5,4,3,2] = lists:rumerge3([4,3,2],[5,4,3,2],[6,5,4,3]), + + L1 = [c,d,e], + L2 = [b,c,d], + ?line true = + lists:umerge(L1, L2) == + lists:reverse(lists:rumerge(lists:reverse(L1), lists:reverse(L2))), + ok. + +usort_rand(doc) -> ["usort/1 on big randomized lists"]; +usort_rand(suite) -> []; +usort_rand(Config) when is_list(Config) -> + ?line ok = ucheck(biglist(10)), + ?line ok = ucheck(biglist(100)), + ?line ok = ucheck(biglist(1000)), + ?line ok = ucheck(biglist(10000)), + + ?line ok = ucheck(ubiglist(10)), + ?line ok = ucheck(ubiglist(100)), + ?line ok = ucheck(ubiglist(1000)), + ?line ok = ucheck(ubiglist(10000)), + ok. + +usort_stable(doc) -> ["usort/1 should keep the first duplicate."]; +usort_stable(suite) -> []; +usort_stable(Config) when is_list(Config) -> + ?line ok = ucheck_stability(bigfunlist(3)), + ?line ok = ucheck_stability(bigfunlist(10)), + ?line ok = ucheck_stability(bigfunlist(100)), + ?line ok = ucheck_stability(bigfunlist(1000)), + ?line case erlang:system_info(modified_timing_level) of + undefined -> ok = ucheck_stability(bigfunlist(10000)); + _ -> ok + end, + ok. + +ucheck([]) -> + ok; +ucheck(L) -> + S = lists:usort(L), + case ucheck(hd(S), tl(S)) of + ok -> + ok; + _ -> + io:format("~w~n", [L]), + erlang:error(ucheck) + end. + +ucheck(_A, []) -> + ok; +ucheck(A, [B | L]) when A < B -> + ucheck(B, L); +ucheck(_A, _L) -> + no. + +%% Check that usort/1 is stable and correct relative ukeysort/2. +ucheck_stability(L) -> + S = no_dups(lsort(L)), + U = lists:usort(L), + check_stab(L, U, S, "usort/1", "ukeysort/2"). + +keysort(doc) -> + ["Tests lists:keysort/2"]; +keysort(suite) -> + [keymerge, rkeymerge, + keysort_1, keysort_rand, keysort_i, keysort_stable, keysort_error]. + +keymerge(doc) -> ["Key merge two lists."]; +keymerge(suite) -> []; +keymerge(Config) when is_list(Config) -> + + Two = [{1,a},{2,b}], + Six = [{1,a},{2,b},{3,c},{4,d},{5,e},{6,f}], + + %% 2-way keymerge + ?line [] = lists:keymerge(1, [], []), + ?line Two = lists:keymerge(1, Two, []), + ?line Two = lists:keymerge(1, [], Two), + ?line Six = lists:keymerge(1, [{1,a},{3,c},{5,e}], [{2,b},{4,d},{6,f}]), + ?line Six = lists:keymerge(1, [{2,b},{4,d},{6,f}], [{1,a},{3,c},{5,e}]), + ?line Six = lists:keymerge(1, [{1,a},{2,b},{3,c}], [{4,d},{5,e},{6,f}]), + ?line Six = lists:keymerge(1, [{4,d},{5,e},{6,f}], [{1,a},{2,b},{3,c}]), + ?line Six = lists:keymerge(1, [{1,a},{2,b},{5,e}],[{3,c},{4,d},{6,f}]), + ?line [{1,a},{2,b},{3,c},{5,e},{7,g}] = + lists:keymerge(1, [{1,a},{3,c},{5,e},{7,g}], [{2,b}]), + ?line [{1,a},{2,b},{3,c},{4,d},{5,e},{7,g}] = + lists:keymerge(1, [{1,a},{3,c},{5,e},{7,g}], [{2,b},{4,d}]), + ?line [{1,a},{2,b},{3,c},{4,d},{5,e},{6,f},{7,g}] = + lists:keymerge(1, [{1,a},{3,c},{5,e},{7,g}], [{2,b},{4,d},{6,f}]), + ?line [{1,a},{2,b},{3,c},{5,e},{7,g}] = + lists:keymerge(1, [{2,b}], [{1,a},{3,c},{5,e},{7,g}]), + ?line [{1,a},{2,b},{3,c},{4,d},{5,e},{7,g}] = + lists:keymerge(1, [{2,b},{4,d}], [{1,a},{3,c},{5,e},{7,g}]), + ?line [{1,a},{2,b},{3,c},{4,d},{5,e},{6,f},{7,g}] = + lists:keymerge(1, [{2,b},{4,d},{6,f}], [{1,a},{3,c},{5,e},{7,g}]), + + ?line [{b,2},{c,11},{c,12},{c,21},{c,22},{e,5}] = + lists:keymerge(1,[{c,11},{c,12},{e,5}], [{b,2},{c,21},{c,22}]), + + ok. + +rkeymerge(doc) -> ["Reverse key merge two lists."]; +rkeymerge(suite) -> []; +rkeymerge(Config) when is_list(Config) -> + + Two = [{2,b},{1,a}], + Six = [{6,f},{5,e},{4,d},{3,c},{2,b},{1,a}], + + %% 2-way reversed keymerge + ?line [] = lists:rkeymerge(1, [], []), + ?line Two = lists:rkeymerge(1, Two, []), + ?line Two = lists:rkeymerge(1, [], Two), + ?line Six = lists:rkeymerge(1, [{5,e},{3,c},{1,a}], [{6,f},{4,d},{2,b}]), + ?line Six = lists:rkeymerge(1, [{6,f},{4,d},{2,b}], [{5,e},{3,c},{1,a}]), + ?line Six = lists:rkeymerge(1, [{3,c},{2,b},{1,a}], [{6,f},{5,e},{4,d}]), + ?line Six = lists:rkeymerge(1, [{6,f},{5,e},{4,d}], [{3,c},{2,b},{1,a}]), + ?line Six = lists:rkeymerge(1, [{4,d},{3,c},{2,b}],[{6,f},{5,e},{1,a}]), + ?line [{7,g},{6,f},{5,e},{3,c},{1,a}] = + lists:rkeymerge(1, [{7,g},{5,e},{3,c},{1,a}], [{6,f}]), + ?line [{7,g},{6,f},{5,e},{4,d},{3,c},{1,a}] = + lists:rkeymerge(1, [{7,g},{5,e},{3,c},{1,a}], [{6,f},{4,d}]), + ?line [{7,g},{6,f},{5,e},{4,d},{3,c},{2,b},{1,a}] = + lists:rkeymerge(1, [{7,g},{5,e},{3,c},{1,a}], [{6,f},{4,d},{2,b}]), + ?line [{7,g},{5,e},{3,c},{2,b},{1,a}] = + lists:rkeymerge(1, [{2,b}], [{7,g},{5,e},{3,c},{1,a}]), + ?line [{7,g},{5,e},{4,d},{3,c},{2,b},{1,a}] = + lists:rkeymerge(1, [{4,d},{2,b}], [{7,g},{5,e},{3,c},{1,a}]), + ?line [{7,g},{6,f},{5,e},{4,d},{3,c},{2,b},{1,a}] = + lists:rkeymerge(1, [{6,f},{4,d},{2,b}], [{7,g},{5,e},{3,c},{1,a}]), + + L1 = [{c,11},{c,12},{e,5}], + L2 = [{b,2},{c,21},{c,22}], + ?line true = + lists:keymerge(1, L1, L2) == + lists:reverse(lists:rkeymerge(1,lists:reverse(L1), + lists:reverse(L2))), + + ok. + +keysort_1(doc) -> ["keysort"]; +keysort_1(suite) -> []; +keysort_1(Config) when is_list(Config) -> + ?line ok = keysort_check(1, [], []), + ?line ok = keysort_check(1, [{a,b}], [{a,b}]), + ?line ok = keysort_check(1, [{a,b},{a,b}], [{a,b},{a,b}]), + ?line ok = keysort_check(1, [{a,b},{b,c}], [{a,b},{b,c}]), + ?line ok = keysort_check(1, [{b,c},{a,b}], [{a,b},{b,c}]), + ?line ok = keysort_check(1, + [{1,e},{3,f},{2,y},{0,z},{x,14}], + [{0,z},{1,e},{2,y},{3,f},{x,14}]), + ?line ok = keysort_check(1, + [{1,a},{1,a},{1,a},{1,a}], + [{1,a},{1,a},{1,a},{1,a}]), + + ?line [{b,1},{c,1}] = lists:keysort(1, [{c,1},{b,1}]), + ?line [{a,0},{b,2},{c,3},{d,4}] = + lists:keysort(1, [{d,4},{c,3},{b,2},{a,0}]), + ?line [{a,0},{b,1},{b,2},{c,1}] = + lists:keysort(1, [{c,1},{b,1},{b,2},{a,0}]), + ?line [{a,0},{b,1},{b,2},{c,1},{d,4}] = + lists:keysort(1, [{c,1},{b,1},{b,2},{a,0},{d,4}]), + + SFun = fun(L) -> fun(X) -> keysort_check(1, X, L) end end, + L1 = [{1,a},{2,b},{3,c}], + ?line lists:foreach(SFun(L1), perms(L1)), + L2 = [{1,a},{1,a},{2,b}], + ?line lists:foreach(SFun(L2), perms(L2)), + L3 = [{1,a},{1,a},{1,a},{2,b}], + ?line lists:foreach(SFun(L3), perms(L3)), + L4 = [{a,1},{a,1},{b,2},{b,2},{c,3},{d,4},{e,5},{f,6}], + ?line lists:foreach(SFun(L4), perms(L4)), + + ok. + +keysort_stable(doc) -> ["keysort should be stable"]; +keysort_stable(suite) -> []; +keysort_stable(Config) when is_list(Config) -> + ?line ok = keysort_check(1, [{1,b},{1,c}], [{1,b},{1,c}]), + ?line ok = keysort_check(1, [{1,c},{1,b}], [{1,c},{1,b}]), + ?line ok = keysort_check(1, + [{1,c},{1,b},{2,x},{3,p},{2,a}], + [{1,c},{1,b},{2,x},{2,a},{3,p}]), + ?line ok = keysort_check(1, + [{1,a},{1,b},{1,a},{1,a}], + [{1,a},{1,b},{1,a},{1,a}]), + ok. + +keysort_error(doc) -> ["keysort should exit when given bad arguments"]; +keysort_error(suite) -> []; +keysort_error(Config) when is_list(Config) -> + ?line {'EXIT', _} = (catch lists:keysort(0, [{1,b},{1,c}])), + ?line {'EXIT', _} = (catch lists:keysort(3, [{1,b},{1,c}])), + ?line {'EXIT', _} = (catch lists:keysort(1.5, [{1,b},{1,c}])), + ?line {'EXIT', _} = (catch lists:keysort(x, [{1,b},{1,c}])), + ?line {'EXIT', _} = (catch lists:keysort(x, [])), + ?line {'EXIT', _} = (catch lists:keysort(x, [{1,b}])), + ?line {'EXIT', _} = (catch lists:keysort(1, [a,b])), + ?line {'EXIT', _} = (catch lists:keysort(1, [{1,b} | {1,c}])), + ok. + +keysort_i(doc) -> ["keysort with other key than first element"]; +keysort_i(suite) -> []; +keysort_i(Config) when is_list(Config) -> + ?line ok = keysort_check(2, [{a,2},{b,1},{c,3}], [{b,1},{a,2},{c,3}]), + ok. + +keysort_rand(doc) -> ["keysort on big randomized lists"]; +keysort_rand(suite) -> []; +keysort_rand(Config) when is_list(Config) -> + ?line ok = keysort_check3(1, biglist(10)), + ?line ok = keysort_check3(1, biglist(100)), + ?line ok = keysort_check3(1, biglist(1000)), + ?line ok = keysort_check3(1, biglist(10000)), + + ?line ok = keysort_check3(2, biglist(10)), + ?line ok = keysort_check3(2, biglist(100)), + ?line ok = keysort_check3(2, biglist(1000)), + ?line ok = keysort_check3(2, biglist(10000)), + ok. + +%%% Keysort a list, check that the returned list is what we expected, +%%% and that it is actually sorted. +keysort_check(I, Input, Expected) -> + ?line Expected = lists:keysort(I, Input), + check_sorted(I, Input, Expected). + +keysort_check3(I, Input) -> + check_sorted(I, 3, Input, lists:keysort(I, Input)). + +check_sorted(I, Input, L) -> + check_sorted(I, I, Input, L). + +%%% Check that a list is keysorted by element I. Elements comparing equal +%%% should be sorted according to element J. +check_sorted(_I, _J, _Input, []) -> + ok; +check_sorted(I, J, Input, [A | Rest]) -> + case catch check_sorted1(I, J, A, Rest) of + {'EXIT', _} -> + io:format("~w~n", [Input]), + erlang:error(check_sorted); + Reply -> + Reply + end. + +check_sorted1(_I, _J, _A, []) -> + ok; +check_sorted1(I, J, A, [B | Rest]) -> + ok = keycompare(I, J, A, B), + check_sorted1(I, J, B, Rest). + +keycompare(I, _J, A, B) when element(I, A) < element(I, B) -> + ok; +keycompare(I, J, A, B) when element(I, A) == element(I, B), + element(J, A) =< element(J, B) -> + ok. + +ukeysort(doc) -> + ["Tests lists:ukeysort/2"]; +ukeysort(suite) -> + [ukeymerge, rukeymerge, + ukeysort_1, ukeysort_rand, ukeysort_i, ukeysort_stable, ukeysort_error]. + +ukeymerge(suite) -> []; +ukeymerge(doc) -> ["Merge two lists while removing duplicates."]; +ukeymerge(Conf) when is_list(Conf) -> + + Two = [{1,a},{2,b}], + Six = [{1,a},{2,b},{3,c},{4,d},{5,e},{6,f}], + + %% 2-way unique keymerge + ?line [] = lists:ukeymerge(1, [], []), + ?line Two = lists:ukeymerge(1, Two, []), + ?line Two = lists:ukeymerge(1, [], Two), + ?line [] = lists:ukeymerge(1, [], []), + ?line Two = lists:ukeymerge(1, Two, []), + ?line Two = lists:ukeymerge(1, [], Two), + ?line Six = lists:ukeymerge(1, [{1,a},{3,c},{5,e}], [{2,b},{4,d},{6,f}]), + ?line Six = lists:ukeymerge(1, [{2,b},{4,d},{6,f}], [{1,a},{3,c},{5,e}]), + ?line Six = lists:ukeymerge(1, [{1,a},{2,b},{3,c}], [{4,d},{5,e},{6,f}]), + ?line Six = lists:ukeymerge(1, [{4,d},{5,e},{6,f}], [{1,a},{2,b},{3,c}]), + ?line Six = lists:ukeymerge(1, [{1,a},{2,b},{5,e}],[{3,c},{4,d},{6,f}]), + ?line [{1,a},{2,b},{3,c},{5,e},{7,g}] = + lists:ukeymerge(1, [{1,a},{3,c},{5,e},{7,g}], [{2,b}]), + ?line [{1,a},{2,b},{3,c},{4,d},{5,e},{7,g}] = + lists:ukeymerge(1, [{1,a},{3,c},{5,e},{7,g}], [{2,b},{4,d}]), + ?line [{1,a},{2,b},{3,c},{4,d},{5,e},{6,f},{7,g}] = + lists:ukeymerge(1, [{1,a},{3,c},{5,e},{7,g}], [{2,b},{4,d},{6,f}]), + ?line [{1,a},{2,b},{3,c},{5,e},{7,g}] = + lists:ukeymerge(1, [{2,b}], [{1,a},{3,c},{5,e},{7,g}]), + ?line [{1,a},{2,b},{3,c},{4,d},{5,e},{7,g}] = + lists:ukeymerge(1, [{2,b},{4,d}], [{1,a},{3,c},{5,e},{7,g}]), + ?line [{1,a},{2,b},{3,c},{4,d},{5,e},{6,f},{7,g}] = + lists:ukeymerge(1, [{2,b},{4,d},{6,f}], [{1,a},{3,c},{5,e},{7,g}]), + + ?line [{1,a},{2,b},{3,c},{5,e},{7,g}] = + lists:ukeymerge(1, [{1,a},{2,b},{3,c},{5,e},{7,g}], [{2,b}]), + ?line [{1,a},{2,b},{3,c},{4,d},{5,e},{7,g}] = + lists:ukeymerge(1, [{1,a},{2,b},{3,c},{4,d},{5,e},{7,g}], + [{2,b},{4,d}]), + ?line [{1,a},{2,b},{3,c},{4,d},{5,e},{6,f},{7,g}] = + lists:ukeymerge(1, [{1,a},{3,c},{5,e},{6,f},{7,g}], + [{2,b},{4,d},{6,f}]), + ?line [{1,a},{2,b},{3,c},{5,e},{7,g}] = + lists:ukeymerge(1, [{2,b}], [{1,a},{2,b},{3,c},{5,e},{7,g}]), + ?line [{1,a},{2,b},{3,c},{4,d},{5,e},{7,g}] = + lists:ukeymerge(1, [{2,b},{4,d}], + [{1,a},{2,b},{3,c},{4,d},{5,e},{7,g}]), + ?line [{1,a},{2,b},{3,c},{4,d},{5,e},{6,f},{7,g}] = + lists:ukeymerge(1, [{2,b},{4,d},{6,f}], + [{1,a},{2,b},{3,c},{4,d},{5,e},{6,f},{7,g}]), + + L1 = [{a,1},{a,3},{a,5},{a,7}], + L2 = [{b,1},{b,3},{b,5},{b,7}], + ?line L1 = lists:ukeymerge(2, L1, L2), + + ok. + +rukeymerge(suite) -> []; +rukeymerge(doc) -> + ["Reverse merge two lists while removing duplicates."]; +rukeymerge(Conf) when is_list(Conf) -> + + Two = [{2,b},{1,a}], + Six = [{6,f},{5,e},{4,d},{3,c},{2,b},{1,a}], + + %% 2-way reversed unique keymerge + ?line [] = lists:rukeymerge(1, [], []), + ?line Two = lists:rukeymerge(1, Two, []), + ?line Two = lists:rukeymerge(1, [], Two), + ?line Six = lists:rukeymerge(1, [{5,e},{3,c},{1,a}], [{6,f},{4,d},{2,b}]), + ?line Six = lists:rukeymerge(1, [{6,f},{4,d},{2,b}], [{5,e},{3,c},{1,a}]), + ?line Six = lists:rukeymerge(1, [{3,c},{2,b},{1,a}], [{6,f},{5,e},{4,d}]), + ?line Six = lists:rukeymerge(1, [{6,f},{5,e},{4,d}], [{3,c},{2,b},{1,a}]), + ?line Six = lists:rukeymerge(1, [{4,d},{3,c},{2,b}],[{6,f},{5,e},{1,a}]), + ?line [{7,g},{6,f},{5,e},{3,c},{1,a}] = + lists:rukeymerge(1, [{7,g},{5,e},{3,c},{1,a}], [{6,f}]), + ?line [{7,g},{6,f},{5,e},{4,d},{3,c},{1,a}] = + lists:rukeymerge(1, [{7,g},{5,e},{3,c},{1,a}], [{6,f},{4,d}]), + ?line [{7,g},{6,f},{5,e},{4,d},{3,c},{2,b},{1,a}] = + lists:rukeymerge(1, [{7,g},{5,e},{3,c},{1,a}], [{6,f},{4,d},{2,b}]), + ?line [{7,g},{5,e},{3,c},{2,b},{1,a}] = + lists:rukeymerge(1, [{2,b}], [{7,g},{5,e},{3,c},{1,a}]), + ?line [{7,g},{5,e},{4,d},{3,c},{2,b},{1,a}] = + lists:rukeymerge(1, [{4,d},{2,b}], [{7,g},{5,e},{3,c},{1,a}]), + ?line [{7,g},{6,f},{5,e},{4,d},{3,c},{2,b},{1,a}] = + lists:rukeymerge(1, [{6,f},{4,d},{2,b}], [{7,g},{5,e},{3,c},{1,a}]), + + ?line [{7,g},{6,f},{5,e},{3,c},{1,a}] = + lists:rukeymerge(1, [{7,g},{6,f},{5,e},{3,c},{1,a}], [{6,f}]), + ?line [{7,g},{6,f},{5,e},{4,d},{3,c},{1,a}] = + lists:rukeymerge(1, [{7,g},{6,f},{5,e},{4,d},{3,c},{1,a}], + [{6,f},{4,d}]), + ?line [{7,g},{6,f},{5,e},{4,d},{3,c},{2,b},{1,a}] = + lists:rukeymerge(1, [{7,g},{6,f},{5,e},{4,d},{3,c},{2,b},{1,a}], + [{6,f},{4,d},{2,b}]), + ?line [{7,g},{5,e},{3,c},{2,b},{1,a}] = + lists:rukeymerge(1, [{2,b}], [{7,g},{5,e},{3,c},{2,b},{1,a}]), + ?line [{7,g},{5,e},{4,d},{3,c},{2,b},{1,a}] = + lists:rukeymerge(1, [{4,d},{2,b}], + [{7,g},{5,e},{4,d},{3,c},{2,b},{1,a}]), + ?line [{7,g},{6,f},{5,e},{4,d},{3,c},{2,b},{1,a}] = + lists:rukeymerge(1, [{6,f},{4,d},{2,b}], + [{7,g},{6,f},{5,e},{4,d},{3,c},{2,b},{1,a}]), + + L1 = [{a,1},{a,3},{a,5},{a,7}], + L2 = [{b,1},{b,3},{b,5},{b,7}], + ?line true = + lists:ukeymerge(2, L1, L2) == + lists:reverse(lists:rukeymerge(2, lists:reverse(L1), + lists:reverse(L2))), + + ok. + +ukeysort_1(doc) -> ["ukeysort"]; +ukeysort_1(suite) -> []; +ukeysort_1(Config) when is_list(Config) -> + ?line ok = ukeysort_check(1, [], []), + ?line ok = ukeysort_check(1, [{a,b}], [{a,b}]), + ?line ok = ukeysort_check(1, [{a,b},{a,b}], [{a,b}]), + ?line ok = ukeysort_check(1, [{a,b},{b,c}], [{a,b},{b,c}]), + ?line ok = ukeysort_check(1, [{b,c},{a,b}], [{a,b},{b,c}]), + ?line ok = ukeysort_check(1, + [{1,e},{3,f},{2,y},{0,z},{x,14}], + [{0,z},{1,e},{2,y},{3,f},{x,14}]), + ?line ok = ukeysort_check(1, [{1,a},{1,a},{1,a},{1,a}], [{1,a}]), + + L1 = [{1,a},{1,b},{1,a}], + L1u = lists:ukeysort(1, L1), + L2 = [{1,a},{1,b},{1,a}], + L2u = lists:ukeysort(1, L2), + ?line ok = ukeysort_check(1, lists:keymerge(1, L1, L2), + lists:ukeymerge(1, L1u, L2u)), + L3 = [{1,a},{1,b},{1,a},{2,a}], + L3u = lists:ukeysort(1, L3), + ?line ok = ukeysort_check(1, lists:keymerge(1, L3, L2), + lists:ukeymerge(1, L3u, L2u)), + L4 = [{1,b},{1,a}], + L4u = lists:ukeysort(1, L4), + ?line ok = ukeysort_check(1, lists:keymerge(1, L1, L4), + lists:ukeymerge(1, L1u, L4u)), + L5 = [{1,a},{1,b},{1,a},{2,a}], + L5u = lists:ukeysort(1, L5), + ?line ok = ukeysort_check(1, lists:keymerge(1, [], L5), + lists:ukeymerge(1, [], L5u)), + ?line ok = ukeysort_check(1, lists:keymerge(1, L5, []), + lists:ukeymerge(1, L5u, [])), + L6 = [{3,a}], + L6u = lists:ukeysort(1, L6), + ?line ok = ukeysort_check(1, lists:keymerge(1, L5, L6), + lists:ukeymerge(1, L5u, L6u)), + + ?line [{b,1},{c,1}] = lists:ukeysort(1, [{c,1},{c,1},{c,1},{c,1},{b,1}]), + ?line [{a,0},{b,2},{c,3},{d,4}] = + lists:ukeysort(1, [{d,4},{c,3},{b,2},{b,2},{a,0}]), + ?line [{a,0},{b,1},{c,1}] = + lists:ukeysort(1, [{c,1},{b,1},{b,1},{b,2},{b,2},{a,0}]), + ?line [{a,0},{b,1},{c,1},{d,4}] = + lists:ukeysort(1, [{c,1},{b,1},{b,2},{a,0},{a,0},{d,4},{d,4}]), + + SFun = fun(L) -> fun(X) -> ukeysort_check(2, X, L) end end, + PL = [{a,1},{b,2},{c,3},{d,4},{e,5},{f,6}], + Ps = perms([{a,1},{b,2},{c,3},{d,4},{e,5},{f,6},{b,2},{a,1}]), + ?line lists:foreach(SFun(PL), Ps), + + M1L = [{1,a},{1,a},{2,b}], + M1s = [{1,a},{2,b}], + ?line lists:foreach(SFun(M1s), perms(M1L)), + M2L = [{1,a},{2,b},{2,b}], + M2s = [{1,a},{2,b}], + ?line lists:foreach(SFun(M2s), perms(M2L)), + M3 = [{1,a},{2,b},{3,c}], + ?line lists:foreach(SFun(M3), perms(M3)), + + ok. + +ukeysort_stable(doc) -> ["ukeysort should keep the first duplicate"]; +ukeysort_stable(suite) -> []; +ukeysort_stable(Config) when is_list(Config) -> + ?line ok = ukeysort_check(1, [{1,b},{1,c}], [{1,b}]), + ?line ok = ukeysort_check(1, [{1,c},{1,b}], [{1,c}]), + ?line ok = ukeysort_check(1, + [{1,c},{1,b},{2,x},{3,p},{2,a}], + [{1,c},{2,x},{3,p}]), + + ?line ok = ukeysort_check(1, [{1,a},{1,b},{1,b}], [{1,a}]), + ?line ok = ukeysort_check(1, [{2,a},{1,b},{2,a}], [{1,b},{2,a}]), + + ?line ok = ukeysort_check_stability(bigfunlist(3)), + ?line ok = ukeysort_check_stability(bigfunlist(10)), + ?line ok = ukeysort_check_stability(bigfunlist(100)), + ?line ok = ukeysort_check_stability(bigfunlist(1000)), + ?line case erlang:system_info(modified_timing_level) of + undefined -> ok = ukeysort_check_stability(bigfunlist(10000)); + _ -> ok + end, + ok. + +ukeysort_error(doc) -> ["ukeysort should exit when given bad arguments"]; +ukeysort_error(suite) -> []; +ukeysort_error(Config) when is_list(Config) -> + ?line {'EXIT', _} = (catch lists:ukeysort(0, [{1,b},{1,c}])), + ?line {'EXIT', _} = (catch lists:ukeysort(3, [{1,b},{1,c}])), + ?line {'EXIT', _} = (catch lists:ukeysort(1.5, [{1,b},{1,c}])), + ?line {'EXIT', _} = (catch lists:ukeysort(x, [{1,b},{1,c}])), + ?line {'EXIT', _} = (catch lists:ukeysort(x, [])), + ?line {'EXIT', _} = (catch lists:ukeysort(x, [{1,b}])), + ?line {'EXIT', _} = (catch lists:ukeysort(1, [a,b])), + ?line {'EXIT', _} = (catch lists:ukeysort(1, [{1,b} | {1,c}])), + ok. + +ukeysort_i(doc) -> ["ukeysort with other key than first element"]; +ukeysort_i(suite) -> []; +ukeysort_i(Config) when is_list(Config) -> + ?line ok = ukeysort_check(2, [{a,2},{b,1},{c,3}], [{b,1},{a,2},{c,3}]), + ok. + +ukeysort_rand(doc) -> ["ukeysort on big randomized lists"]; +ukeysort_rand(suite) -> []; +ukeysort_rand(Config) when is_list(Config) -> + ?line ok = ukeysort_check3(2, biglist(10)), + ?line ok = ukeysort_check3(2, biglist(100)), + ?line ok = ukeysort_check3(2, biglist(1000)), + ?line ok = ukeysort_check3(2, biglist(10000)), + + ?line ok = gen_ukeysort_check(1, ubiglist(10)), + ?line ok = gen_ukeysort_check(1, ubiglist(100)), + ?line ok = gen_ukeysort_check(1, ubiglist(1000)), + ?line ok = gen_ukeysort_check(1, ubiglist(10000)), + ok. + +%% Check that ukeysort/2 is stable and correct relative keysort/2. +%% (this is not affected by the fact that keysort/2 is no longer really +%% stable; ucheck_stability/1 checks ukeysort/2 (and usort/1, of course)) +gen_ukeysort_check(I, Input) -> + U = lists:ukeysort(I, Input), + S = lists:keysort(I, Input), + case U == no_dups_keys(S, I) of + true -> + ok; + false -> + io:format("~w~n", [Input]), + erlang:error(gen_ukeysort_check) + end. + +%% Used for checking that the first copy is kept. +ukeysort_check_stability(L) -> + I = 1, + U = lists:ukeysort(I, L), + S = no_dups_keys(lkeysort(I, L), I), + check_stab(L, U, S, "ukeysort/2", "usort/2"). + +%%% Uniquely keysort a list, check that the returned list is what we +%%% expected, and that it is actually sorted. +ukeysort_check(I, Input, Expected) -> + ?line Expected = lists:ukeysort(I, Input), + ucheck_sorted(I, Input, Expected). + +ukeysort_check3(I, Input) -> + ucheck_sorted(I, 3, Input, lists:ukeysort(I, Input)). + +ucheck_sorted(I, Input, L) -> + ucheck_sorted(I, I, Input, L). + +%%% Check that a list is ukeysorted by element I. Elements comparing +%%% equal should be sorted according to element J. +ucheck_sorted(_I, _J, _Input, []) -> + ok; +ucheck_sorted(I, J, Input, [A | Rest]) -> + case catch ucheck_sorted1(I, J, A, Rest) of + {'EXIT', _} -> + io:format("~w~n", [Input]), + erlang:error(ucheck_sorted); + Reply -> + Reply + end. + +ucheck_sorted1(_I, _J, _A, []) -> + ok; +ucheck_sorted1(I, J, A, [B | Rest]) -> + ok = ukeycompare(I, J, A, B), + ucheck_sorted1(I, J, B, Rest). + +ukeycompare(I, _J, A, B) when element(I, A) < element(I, B) -> + ok; +ukeycompare(I, J, A, B) when A =/= B, + element(I, A) == element(I, B), + element(J, A) =< element(J, B) -> + ok. + + +funsort(doc) -> + ["Tests lists:sort/2"]; +funsort(suite) -> + [funmerge, rfunmerge, + funsort_1, funsort_stable, funsort_error, funsort_rand]. + +funmerge(doc) -> ["Merge two lists using a fun."]; +funmerge(suite) -> []; +funmerge(Config) when is_list(Config) -> + + Two = [1,2], + Six = [1,2,3,4,5,6], + F = fun(X, Y) -> X =< Y end, + + %% 2-way merge + ?line [] = lists:merge(F, [], []), + ?line Two = lists:merge(F, Two, []), + ?line Two = lists:merge(F, [], Two), + ?line Six = lists:merge(F, [1,3,5], [2,4,6]), + ?line Six = lists:merge(F, [2,4,6], [1,3,5]), + ?line Six = lists:merge(F, [1,2,3], [4,5,6]), + ?line Six = lists:merge(F, [4,5,6], [1,2,3]), + ?line Six = lists:merge(F, [1,2,5],[3,4,6]), + ?line [1,2,3,5,7] = lists:merge(F, [1,3,5,7], [2]), + ?line [1,2,3,4,5,7] = lists:merge(F, [1,3,5,7], [2,4]), + ?line [1,2,3,4,5,6,7] = lists:merge(F, [1,3,5,7], [2,4,6]), + ?line [1,2,3,5,7] = lists:merge(F, [2], [1,3,5,7]), + ?line [1,2,3,4,5,7] = lists:merge(F, [2,4], [1,3,5,7]), + ?line [1,2,3,4,5,6,7] = lists:merge(F, [2,4,6], [1,3,5,7]), + + F2 = fun(X,Y) -> element(1,X) =< element(1,Y) end, + ?line [{b,2},{c,11},{c,12},{c,21},{c,22},{e,5}] = + lists:merge(F2,[{c,11},{c,12},{e,5}], [{b,2},{c,21},{c,22}]), + + ok. + +rfunmerge(doc) -> ["Reverse merge two lists using a fun."]; +rfunmerge(suite) -> []; +rfunmerge(Config) when is_list(Config) -> + + Two = [2,1], + Six = [6,5,4,3,2,1], + F = fun(X, Y) -> X =< Y end, + + %% 2-way reversed merge + ?line [] = lists:rmerge(F, [], []), + ?line Two = lists:rmerge(F, Two, []), + ?line Two = lists:rmerge(F, [], Two), + ?line Six = lists:rmerge(F, [5,3,1], [6,4,2]), + ?line Six = lists:rmerge(F, [6,4,2], [5,3,1]), + ?line Six = lists:rmerge(F, [3,2,1], [6,5,4]), + ?line Six = lists:rmerge(F, [6,5,4], [3,2,1]), + ?line Six = lists:rmerge(F, [4,3,2],[6,5,1]), + ?line [7,6,5,3,1] = lists:rmerge(F, [7,5,3,1], [6]), + ?line [7,6,5,4,3,1] = lists:rmerge(F, [7,5,3,1], [6,4]), + ?line [7,6,5,4,3,2,1] = lists:rmerge(F, [7,5,3,1], [6,4,2]), + ?line [7,5,3,2,1] = lists:rmerge(F, [2], [7,5,3,1]), + ?line [7,5,4,3,2,1] = lists:rmerge(F, [4,2], [7,5,3,1]), + ?line [7,6,5,4,3,2,1] = lists:rmerge(F, [6,4,2], [7,5,3,1]), + + F2 = fun(X,Y) -> element(1,X) =< element(1,Y) end, + L1 = [{c,11},{c,12},{e,5}], + L2 = [{b,2},{c,21},{c,22}], + ?line true = + lists:merge(F2, L1, L2) == + lists:reverse(lists:rmerge(F2,lists:reverse(L1), lists:reverse(L2))), + + ok. + + +funsort_1(doc) -> ["sort/2"]; +funsort_1(suite) -> []; +funsort_1(Config) when is_list(Config) -> + ?line ok = funsort_check(1, [], []), + ?line ok = funsort_check(1, [{a,b}], [{a,b}]), + ?line ok = funsort_check(1, [{a,b},{a,b}], [{a,b},{a,b}]), + ?line ok = funsort_check(1, [{a,b},{b,c}], [{a,b},{b,c}]), + ?line ok = funsort_check(1, [{b,c},{a,b}], [{a,b},{b,c}]), + ?line ok = funsort_check(1, + [{1,e},{3,f},{2,y},{0,z},{x,14}], + [{0,z},{1,e},{2,y},{3,f},{x,14}]), + F = funsort_fun(1), + + ?line [{b,1},{c,1}] = lists:sort(F, [{c,1},{b,1}]), + ?line [{a,0},{b,2},{c,3},{d,4}] = + lists:sort(F, [{d,4},{c,3},{b,2},{a,0}]), + ?line [{a,0},{b,1},{b,2},{c,1}] = + lists:sort(F, [{c,1},{b,1},{b,2},{a,0}]), + ?line [{a,0},{b,1},{b,2},{c,1},{d,4}] = + lists:sort(F, [{c,1},{b,1},{b,2},{a,0},{d,4}]), + + SFun = fun(L) -> fun(X) -> funsort_check(1, X, L) end end, + L1 = [{1,a},{1,a},{2,b},{2,b},{3,c},{4,d},{5,e},{6,f}], + ?line lists:foreach(SFun(L1), perms(L1)), + + ok. + +funsort_stable(doc) -> ["sort/2 should be stable"]; +funsort_stable(suite) -> []; +funsort_stable(Config) when is_list(Config) -> + ?line ok = funsort_check(1, [{1,b},{1,c}], [{1,b},{1,c}]), + ?line ok = funsort_check(1, [{1,c},{1,b}], [{1,c},{1,b}]), + ?line ok = funsort_check(1, + [{1,c},{1,b},{2,x},{3,p},{2,a}], + [{1,c},{1,b},{2,x},{2,a},{3,p}]), + ok. + +funsort_error(doc) -> ["sort/2 should exit when given bad arguments"]; +funsort_error(suite) -> []; +funsort_error(Config) when is_list(Config) -> + ?line {'EXIT', _} = (catch lists:sort(1, [{1,b} , {1,c}])), + ?line {'EXIT', _} = (catch lists:sort(fun(X,Y) -> X =< Y end, + [{1,b} | {1,c}])), + ok. + +funsort_rand(doc) -> ["sort/2 on big randomized lists"]; +funsort_rand(suite) -> []; +funsort_rand(Config) when is_list(Config) -> + ?line ok = funsort_check3(1, biglist(10)), + ?line ok = funsort_check3(1, biglist(100)), + ?line ok = funsort_check3(1, biglist(1000)), + ?line ok = funsort_check3(1, biglist(10000)), + ok. + +% Do a keysort +funsort(I, L) -> + lists:sort(funsort_fun(I), L). + +funsort_check3(I, Input) -> + check_sorted(I, 3, Input, funsort(I, Input)). + +%%% Keysort a list, check that the returned list is what we expected, +%%% and that it is actually sorted. +funsort_check(I, Input, Expected) -> + ?line Expected = funsort(I, Input), + check_sorted(I, Input, Expected). + +ufunsort(doc) -> + ["Tests lists:usort/2"]; +ufunsort(suite) -> + [ufunmerge, rufunmerge, + ufunsort_1, ufunsort_stable, ufunsort_error, ufunsort_rand]. + +ufunmerge(suite) -> []; +ufunmerge(doc) -> ["Merge two lists while removing duplicates using a fun."]; +ufunmerge(Conf) when is_list(Conf) -> + + Two = [1,2], + Six = [1,2,3,4,5,6], + F = fun(X, Y) -> X =< Y end, + + %% 2-way unique merge + ?line [] = lists:umerge(F, [], []), + ?line Two = lists:umerge(F, Two, []), + ?line Two = lists:umerge(F, [], Two), + ?line Six = lists:umerge(F, [1,3,5], [2,4,6]), + ?line Six = lists:umerge(F, [2,4,6], [1,3,5]), + ?line Six = lists:umerge(F, [1,2,3], [4,5,6]), + ?line Six = lists:umerge(F, [4,5,6], [1,2,3]), + ?line Six = lists:umerge(F, [1,2,5],[3,4,6]), + ?line [1,2,3,5,7] = lists:umerge(F, [1,3,5,7], [2]), + ?line [1,2,3,4,5,7] = lists:umerge(F, [1,3,5,7], [2,4]), + ?line [1,2,3,4,5,6,7] = lists:umerge(F, [1,3,5,7], [2,4,6]), + ?line [1,2,3,5,7] = lists:umerge(F, [2], [1,3,5,7]), + ?line [1,2,3,4,5,7] = lists:umerge(F, [2,4], [1,3,5,7]), + ?line [1,2,3,4,5,6,7] = lists:umerge(F, [2,4,6], [1,3,5,7]), + + ?line [1,2,3,5,7] = lists:umerge(F, [1,2,3,5,7], [2]), + ?line [1,2,3,4,5,7] = lists:umerge(F, [1,2,3,4,5,7], [2,4]), + ?line [1,2,3,4,5,6,7] = lists:umerge(F, [1,3,5,6,7], [2,4,6]), + ?line [1,2,3,5,7] = lists:umerge(F, [2], [1,2,3,5,7]), + ?line [1,2,3,4,5,7] = lists:umerge(F, [2,4], [1,2,3,4,5,7]), + ?line [1,2,3,4,5,6,7] = lists:umerge(F, [2,4,6], [1,2,3,4,5,6,7]), + + L1 = [{a,1},{a,3},{a,5},{a,7}], + L2 = [{b,1},{b,3},{b,5},{b,7}], + F2 = fun(X,Y) -> element(2,X) =< element(2,Y) end, + ?line L1 = lists:umerge(F2, L1, L2), + ?line [{b,2},{e,5},{c,11},{c,12},{c,21},{c,22}] = + lists:umerge(F2, [{e,5},{c,11},{c,12}], [{b,2},{c,21},{c,22}]), + + ok. + +rufunmerge(suite) -> []; +rufunmerge(doc) -> + ["Reverse merge two lists while removing duplicates using a fun."]; +rufunmerge(Conf) when is_list(Conf) -> + Two = [2,1], + Six = [6,5,4,3,2,1], + F = fun(X, Y) -> X =< Y end, + + %% 2-way reversed unique merge + ?line [] = lists:rumerge(F, [], []), + ?line Two = lists:rumerge(F, Two, []), + ?line Two = lists:rumerge(F, [], Two), + ?line Six = lists:rumerge(F, [5,3,1], [6,4,2]), + ?line Six = lists:rumerge(F, [6,4,2], [5,3,1]), + ?line Six = lists:rumerge(F, [3,2,1], [6,5,4]), + ?line Six = lists:rumerge(F, [6,5,4], [3,2,1]), + ?line Six = lists:rumerge(F, [4,3,2],[6,5,1]), + ?line [7,6,5,3,1] = lists:rumerge(F, [7,5,3,1], [6]), + ?line [7,6,5,4,3,1] = lists:rumerge(F, [7,5,3,1], [6,4]), + ?line [7,6,5,4,3,2,1] = lists:rumerge(F, [7,5,3,1], [6,4,2]), + ?line [7,5,3,2,1] = lists:rumerge(F, [2], [7,5,3,1]), + ?line [7,5,4,3,2,1] = lists:rumerge(F, [4,2], [7,5,3,1]), + ?line [7,6,5,4,3,2,1] = lists:rumerge(F, [6,4,2], [7,5,3,1]), + + ?line [7,6,5,3,1] = lists:rumerge(F, [7,6,5,3,1], [6]), + ?line [7,6,5,4,3,1] = lists:rumerge(F, [7,6,5,4,3,1], [6,4]), + ?line [7,6,5,4,3,2,1] = lists:rumerge(F, [7,6,5,4,3,2,1], [6,4,2]), + ?line [7,5,3,2,1] = lists:rumerge(F, [2], [7,5,3,2,1]), + ?line [7,5,4,3,2,1] = lists:rumerge(F, [4,2], [7,5,4,3,2,1]), + ?line [7,6,5,4,3,2,1] = lists:rumerge(F, [6,4,2], [7,6,5,4,3,2,1]), + + F2 = fun(X,Y) -> element(1,X) =< element(1,Y) end, + L1 = [{1,a},{1,b},{1,a}], + L2 = [{1,a},{1,b},{1,a}], + ?line true = lists:umerge(F2, L1, L2) == + lists:reverse(lists:rumerge(F, lists:reverse(L2), lists:reverse(L1))), + + L3 = [{c,11},{c,12},{e,5}], + L4 = [{b,2},{c,21},{c,22}], + ?line true = + lists:umerge(F2, L3, L4) == + lists:reverse(lists:rumerge(F2,lists:reverse(L3), lists:reverse(L4))), + + ok. + +ufunsort_1(doc) -> ["usort/2"]; +ufunsort_1(suite) -> []; +ufunsort_1(Config) when is_list(Config) -> + ?line ok = ufunsort_check(1, [], []), + ?line ok = ufunsort_check(1, [{a,b}], [{a,b}]), + ?line ok = ufunsort_check(1, [{a,b},{a,b}], [{a,b}]), + ?line ok = ufunsort_check(1, [{a,b},{b,c}], [{a,b},{b,c}]), + ?line ok = ufunsort_check(1, [{b,c},{a,b}], [{a,b},{b,c}]), + ?line ok = ufunsort_check(1, + [{1,e},{3,f},{2,y},{0,z},{x,14}], + [{0,z},{1,e},{2,y},{3,f},{x,14}]), + ?line ok = ufunsort_check(1, + [{1,a},{2,b},{3,c},{2,b},{1,a},{2,b},{3,c}, + {2,b},{1,a}], + [{1,a},{2,b},{3,c}]), + ?line ok = ufunsort_check(1, + [{1,a},{1,a},{1,b},{1,b},{1,a},{2,a}], + [{1,a},{2,a}]), + + F = funsort_fun(1), + L1 = [{1,a},{1,b},{1,a}], + L2 = [{1,a},{1,b},{1,a}], + ?line ok = ufunsort_check(1, lists:keymerge(1, L1, L2), + lists:umerge(F, lists:usort(F, L1), + lists:usort(F, L2))), + L3 = [{1,a},{1,b},{1,a},{2,a}], + ?line ok = ufunsort_check(1, lists:keymerge(1, L3, L2), + lists:umerge(F, lists:usort(F, L3), + lists:usort(F, L2))), + L4 = [{1,b},{1,a}], + ?line ok = ufunsort_check(1, lists:keymerge(1, L1, L4), + lists:umerge(F, lists:usort(F, L1), + lists:usort(F, L4))), + L5 = [{1,a},{1,b},{1,a},{2,a}], + ?line ok = ufunsort_check(1, lists:keymerge(1, L5, []), + lists:umerge(F, lists:usort(F, L5), [])), + L6 = [{3,a}], + ?line ok = ufunsort_check(1, lists:keymerge(1, L5, L6), + lists:umerge(F, lists:usort(F, L5), + lists:usort(F, L6))), + + ?line [{b,1},{c,1}] = lists:usort(F, [{c,1},{c,1},{b,1}]), + ?line [{a,0},{b,2},{c,3},{d,4}] = + lists:usort(F, [{d,4},{c,3},{b,2},{b,2},{a,0}]), + ?line [{a,0},{b,1},{c,1}] = + lists:usort(F, [{c,1},{b,1},{b,1},{b,2},{b,2},{a,0}]), + ?line [{a,0},{b,1},{c,1},{d,4}] = + lists:usort(F, [{c,1},{b,1},{b,2},{a,0},{a,0},{d,4},{d,4}]), + + SFun = fun(L) -> fun(X) -> ufunsort_check(1, X, L) end end, + PL = [{1,a},{2,b},{3,c},{4,d},{5,e},{6,f}], + Ps = perms([{1,a},{2,b},{3,c},{4,d},{5,e},{6,f},{2,b},{1,a}]), + ?line lists:foreach(SFun(PL), Ps), + + ok. + +ufunsort_stable(doc) -> ["usort/2 should be stable"]; +ufunsort_stable(suite) -> []; +ufunsort_stable(Config) when is_list(Config) -> + ?line ok = ufunsort_check(1, [{1,b},{1,c}], [{1,b}]), + ?line ok = ufunsort_check(1, [{1,c},{1,b}], [{1,c}]), + ?line ok = ufunsort_check(1, + [{1,c},{1,b},{2,x},{3,p},{2,a}], + [{1,c},{2,x},{3,p}]), + + ?line ok = ufunsort_check_stability(bigfunlist(10)), + ?line ok = ufunsort_check_stability(bigfunlist(100)), + ?line ok = ufunsort_check_stability(bigfunlist(1000)), + ?line case erlang:system_info(modified_timing_level) of + undefined -> ok = ufunsort_check_stability(bigfunlist(10000)); + _ -> ok + end, + ok. + +ufunsort_error(doc) -> ["usort/2 should exit when given bad arguments"]; +ufunsort_error(suite) -> []; +ufunsort_error(Config) when is_list(Config) -> + ?line {'EXIT', _} = (catch lists:usort(1, [{1,b} , {1,c}])), + ?line {'EXIT', _} = (catch lists:usort(fun(X,Y) -> X =< Y end, + [{1,b} | {1,c}])), + ok. + +ufunsort_rand(doc) -> ["usort/2 on big randomized lists"]; +ufunsort_rand(suite) -> []; +ufunsort_rand(Config) when is_list(Config) -> + ?line ok = ufunsort_check3(1, biglist(10)), + ?line ok = ufunsort_check3(1, biglist(100)), + ?line ok = ufunsort_check3(1, biglist(1000)), + ?line ok = ufunsort_check3(1, biglist(10000)), + + ?line ok = gen_ufunsort_check(1, ubiglist(100)), + ?line ok = gen_ufunsort_check(1, ubiglist(1000)), + ?line ok = gen_ufunsort_check(1, ubiglist(10000)), + ok. + +%% Check that usort/2 is stable and correct relative sort/2. +gen_ufunsort_check(I, Input) -> + U = ufunsort(I, Input), + S = funsort(I, Input), + case U == no_dups_keys(S, I) of + true -> + ok; + false -> + io:format("~w~n", [Input]), + erlang:error(gen_ufunsort_check) + end. + +%% Used for checking that the first copy is kept. +ufunsort_check_stability(L) -> + I = 1, + U = ufunsort(I, L), + S = no_dups(funsort(I, L)), + check_stab(L, U, S, "usort/2", "sort/2"). + +ufunsort_check3(I, Input) -> + ucheck_sorted(I, 3, Input, ufunsort(I, Input)). + +%%% Keysort a list, check that the returned list is what we expected, +%%% and that it is actually sorted. +ufunsort_check(I, Input, Expected) -> + ?line Expected = ufunsort(I, Input), + ucheck_sorted(I, Input, Expected). + +% Do a keysort +ufunsort(I, L) -> + lists:usort(funsort_fun(I), L). + +funsort_fun(I) -> + fun(A, B) when tuple_size(A) >= I, tuple_size(B) >= I -> + element(I, A) =< element(I, B) + end. + +check_stab(L, U, S, US, SS) -> + UP = explicit_pid(U), + SP = explicit_pid(S), + case UP == SP of + true -> + ok; + false -> + io:format("In: ~w~n", [explicit_pid(L)]), + io:format("~s: ~w~n", [US, UP]), + io:format("~s: ~w~n", [SS, SP]), + erlang:error(unstable) + end. + +%%%------------------------------------------------------------ +%%% Generate lists of given length, containing 3-tuples with +%%% random integer elements in the range 0..44 as elements 1 and 2. +%%% Element 3 in the tuple is the position of the tuple in the list. + +biglist(N) -> + {A, B, C} = get_seed(), + random:seed(A, B, C), + biglist(N, []). + +biglist(0, L) -> + L; +biglist(N, L) -> + E = random_tuple(45, N), + biglist(N-1, [E|L]). + +%%%------------------------------------------------------------ +%%% Generate lists of given length, containing 2-tuples with +%%% random integer elements in the range 0..10 as element 1. +%%% Element 2 in the tuple is a random integer in the range 0..5. +%%% No sequence number. + +ubiglist(N) -> + {A, B, C} = get_seed(), + random:seed(A, B, C), + ubiglist(N, []). + +ubiglist(0, L) -> + L; +ubiglist(N, L) -> + E = urandom_tuple(11, 6), + ubiglist(N-1, [E|L]). + +urandom_tuple(N, I) -> + R1 = randint(N), + R2 = randint(I), + {R1, R2}. + +%%%------------------------------------------------------------ +%%% Generate lists of given length, containing 2-tuples with random +%%% integer elements in the range 0..10 as elements 1. All tuples have +%%% the same function as element 2, but every function is created in a +%%% unique process. ==/2 will return 'true' for any pair of functions, +%%% but erlang:fun_info(Fun, pid) can be used for distinguishing +%%% functions created in different processes. The pid acts like a +%%% sequence number. + +bigfunlist(N) -> + {A, B, C} = get_seed(), + random:seed(A, B, C), + bigfunlist_1(N). + +bigfunlist_1(N) when N < 30000 -> % Now (R8) max 32000 different pids. + case catch bigfunlist(N, 0, []) of + {'EXIT', _} -> + bigfunlist_1(N); + Reply -> + Reply + end. + +bigfunlist(0, _P, L) -> + lists:reverse(L); +bigfunlist(N, P, L) -> + {E, NP} = random_funtuple(P, 11), + bigfunlist(N-1, NP, [E | L]). + +random_funtuple(P, N) -> + R = randint(N), + F = make_fun(), + NP = fun_pid(F), + true = NP > P, + {{R, F}, NP}. + +make_fun() -> + Pid = spawn(?MODULE, make_fun, [self()]), + receive {Pid, Fun} -> Fun end. + +make_fun(Pid) -> + Pid ! {self(), fun make_fun/1}. + +fun_pid(Fun) -> + erlang:fun_info(Fun, pid). + +get_seed() -> + case random:seed() of + undefined -> + now(); + Tuple -> + Tuple + end. + +random_tuple(N, Seq) -> + R1 = randint(N), + R2 = randint(N), + {R1, R2, Seq}. + +randint(N) -> + trunc(random:uniform() * N). + +%% The first "duplicate" is kept. +no_dups([]) -> + []; +no_dups([H | T]) -> + no_dups(H, T, []). + +no_dups(H, [H1 | T], L) when H == H1 -> + no_dups(H, T, L); +no_dups(H, [H1 | T], L) -> + no_dups(H1, T, [H | L]); +no_dups(H, [], L) -> + lists:reverse([H | L]). + +%% The first "duplicate" is kept. +no_dups_keys([], _I) -> + []; +no_dups_keys([H | T], I) -> + no_dups_keys(H, T, [], I). + +no_dups_keys(H, [H1 | T], L, I) when element(I, H) == element(I, H1) -> + no_dups_keys(H, T, L, I); +no_dups_keys(H, [H1 | T], L, I) -> + no_dups_keys(H1, T, [H | L], I); +no_dups_keys(H, [], L, _I) -> + lists:reverse([H | L]). + +perms([]) -> + [[]]; +perms(L) -> + [[H|T] || H <- L, T <- perms(L--[H])]. + +%%%------------------------------------------------------------ +%%% Test the sort routines with randomly generated lists. + +-record(state, {sort = 0, usort = 0, stable = 0}). + +%% Run it interactively. 'stop' or 'info' recognized commands. +sort_loop() -> + sort_loop(5000). + +sort_loop(N) when is_integer(N), N > 0 -> + Pid = spawn_link(?MODULE, sloop, [N]), + sort_loop_1(Pid). + +sort_loop_1(Pid) -> + case io:get_line('? ') of + eof -> + ok; + "stop\n" -> + Pid ! {self(), stop}, + receive {Pid, S} -> display_state(S) end; + "info\n" -> + Pid ! {self(), info}, + receive {Pid, S} -> display_state(S) end, + sort_loop_1(Pid); + _Other -> + sort_loop_1(Pid) + end. + +sloop(N) -> + {A, B, C} = get_seed(), + random:seed(A, B, C), + sloop(N, #state{}). + +sloop(N, S) -> + receive + {From, stop} -> + From ! {self(), S}; + {From, info} -> + From ! {self(), S}, + sloop(N, S) + after 0 -> + Len = randint(N), + NS = case randint(3) of + 0 -> + BL = biglist(Len, []), + ok = check(BL), + ok = keysort_check3(1, BL), + ok = funsort_check3(1, BL), + S#state{sort = S#state.sort + 1}; + 1 -> + BL = ubiglist(Len, []), + ok = ucheck(BL), + ok = gen_ukeysort_check(1, BL), + ok = gen_ufunsort_check(1, BL), + S#state{usort = S#state.usort + 1}; + 2 -> + BL = bigfunlist(Len), + %% ok = check_stability(BL), + ok = ucheck_stability(BL), + ok = ukeysort_check_stability(BL), + ok = ufunsort_check_stability(BL), + S#state{stable = S#state.stable + 1} + end, + sloop(N, NS) + end. + +display_state(S) -> + io:format("sort: ~p~n", [S#state.sort]), + io:format("usort: ~p~n", [S#state.usort]), + io:format("stable: ~p~n", [S#state.stable]). + +%% This version of sort/1 is really stable; the order of equal +%% elements is kept. It is used for checking the current +%% implementation of usort/1 etc. + +lsort([X, Y | L] = L0) when X =< Y -> + case L of + [] -> + L0; + [Z] when Y =< Z -> + L0; + [Z] when X =< Z -> + [X, Z, Y]; + [Z] -> + [Z, X, Y]; + _ -> + split_1(X, Y, L, [], []) + end; +lsort([X, Y | L]) -> + case L of + [] -> + [Y, X]; + [Z] when X =< Z -> + [Y, X | L]; + [Z] when Y =< Z -> + [Y, Z, X]; + [Z] -> + [Z, Y, X]; + _ -> + split_2(X, Y, L, [], []) + end; +lsort([_] = L) -> + L; +lsort([] = L) -> + L. + +split_1(X, Y, [Z | L], R, Rs) when Z >= Y -> + split_1(Y, Z, L, [X | R], Rs); +split_1(X, Y, [Z | L], R, Rs) when Z >= X -> + split_1(Z, Y, L, [X | R], Rs); +split_1(X, Y, [Z | L], [], Rs) -> + split_1(X, Y, L, [Z], Rs); +split_1(X, Y, [Z | L], R, Rs) -> + split_1_1(X, Y, L, R, Rs, Z); +split_1(X, Y, [], R, Rs) -> + rmergel([[Y, X | R] | Rs], [], asc). + +split_1_1(X, Y, [Z | L], R, Rs, S) when Z >= Y -> + split_1_1(Y, Z, L, [X | R], Rs, S); +split_1_1(X, Y, [Z | L], R, Rs, S) when Z >= X -> + split_1_1(Z, Y, L, [X | R], Rs, S); +split_1_1(X, Y, [Z | L], R, Rs, S) when S =< Z -> + split_1(S, Z, L, [], [[Y, X | R] | Rs]); +split_1_1(X, Y, [Z | L], R, Rs, S) -> + split_1(Z, S, L, [], [[Y, X | R] | Rs]); +split_1_1(X, Y, [], R, Rs, S) -> + rmergel([[S], [Y, X | R] | Rs], [], asc). + +split_2(X, Y, [Z | L], R, Rs) when Z < Y -> + split_2(Y, Z, L, [X | R], Rs); +split_2(X, Y, [Z | L], R, Rs) when Z < X -> + split_2(Z, Y, L, [X | R], Rs); +split_2(X, Y, [Z | L], [], Rs) -> + split_2(X, Y, L, [Z], Rs); +split_2(X, Y, [Z | L], R, Rs) -> + split_2_1(X, Y, L, R, Rs, Z); +split_2(X, Y, [], R, Rs) -> + mergel([[Y, X | R] | Rs], [], desc). + +split_2_1(X, Y, [Z | L], R, Rs, S) when Z < Y -> + split_2_1(Y, Z, L, [X | R], Rs, S); +split_2_1(X, Y, [Z | L], R, Rs, S) when Z < X -> + split_2_1(Z, Y, L, [X | R], Rs, S); +split_2_1(X, Y, [Z | L], R, Rs, S) when S > Z -> + split_2(S, Z, L, [], [[Y, X | R] | Rs]); +split_2_1(X, Y, [Z | L], R, Rs, S) -> + split_2(Z, S, L, [], [[Y, X | R] | Rs]); +split_2_1(X, Y, [], R, Rs, S) -> + mergel([[S], [Y, X | R] | Rs], [], desc). + +mergel([[] | L], Acc, O) -> + mergel(L, Acc, O); +mergel([T1, [H2 | T2] | L], Acc, asc) -> + mergel(L, [merge2_1(T1, H2, T2, []) | Acc], asc); +mergel([[H2 | T2], T1 | L], Acc, desc) -> + mergel(L, [merge2_1(T1, H2, T2, []) | Acc], desc); +mergel([L], [], _O) -> + L; +mergel([L], Acc, O) -> + rmergel([lists:reverse(L, []) | Acc], [], O); +mergel([], [], _O) -> + []; +mergel([], Acc, O) -> + rmergel(Acc, [], O); +mergel([A, [] | L], Acc, O) -> + mergel([A | L], Acc, O); +mergel([A, B, [] | L], Acc, O) -> + mergel([A, B | L], Acc, O). + +rmergel([[H2 | T2], T1 | L], Acc, asc) -> + rmergel(L, [rmerge2_1(T1, H2, T2, []) | Acc], asc); +rmergel([T1, [H2 | T2] | L], Acc, desc) -> + rmergel(L, [rmerge2_1(T1, H2, T2, []) | Acc], desc); +rmergel([L], Acc, O) -> + mergel([lists:reverse(L, []) | Acc], [], O); +rmergel([], Acc, O) -> + mergel(Acc, [], O). + +merge2_1([H1 | T1], H2, T2, M) when H1 =< H2 -> + merge2_1(T1, H2, T2, [H1 | M]); +merge2_1([H1 | T1], H2, T2, M) -> + merge2_2(T1, H1, T2, [H2 | M]); +merge2_1([], H2, T2, M) -> + lists:reverse(T2, [H2 | M]). + +merge2_2(T1, H1, [H2 | T2], M) when H1 =< H2 -> + merge2_1(T1, H2, T2, [H1 | M]); +merge2_2(T1, H1, [H2 | T2], M) -> + merge2_2(T1, H1, T2, [H2 | M]); +merge2_2(T1, H1, [], M) -> + lists:reverse(T1, [H1 | M]). + +rmerge2_1([H1 | T1], H2, T2, M) when H1 =< H2 -> + rmerge2_2(T1, H1, T2, [H2 | M]); +rmerge2_1([H1 | T1], H2, T2, M) -> + rmerge2_1(T1, H2, T2, [H1 | M]); +rmerge2_1([], H2, T2, M) -> + lists:reverse(T2, [H2 | M]). + +rmerge2_2(T1, H1, [H2 | T2], M) when H1 =< H2 -> + rmerge2_2(T1, H1, T2, [H2 | M]); +rmerge2_2(T1, H1, [H2 | T2], M) -> + rmerge2_1(T1, H2, T2, [H1 | M]); +rmerge2_2(T1, H1, [], M) -> + lists:reverse(T1, [H1 | M]). + + + +%% This version of keysort/2 is really stable; the order of equal +%% elements is kept. It is used for checking the current +%% implementation of ukeysort/2 etc. + +lkeysort(Index, L) when is_integer(Index), Index > 0 -> + case L of + [] -> L; + [_] -> L; + [X, Y | T] -> + EX = element(Index, X), + EY = element(Index, Y), + if + EX =< EY -> + keysplit_1(Index, X, EX, Y, EY, T, [], []); + true -> + keysplit_2(Index, Y, EY, T, [X]) + end + end. + +keysplit_1(I, X, EX, Y, EY, [Z | L], R, Rs) -> + EZ = element(I, Z), + if + EY =< EZ -> + keysplit_1(I, Y, EY, Z, EZ, L, [X | R], Rs); + EX =< EZ -> + keysplit_1(I, Z, EZ, Y, EY, L, [X | R], Rs); + true, R == [] -> + keysplit_1(I, X, EX, Y, EY, L, [Z], Rs); + true -> + keysplit_1_1(I, X, EX, Y, EY, L, R, Rs, Z, EZ) + end; +keysplit_1(I, X, _EX, Y, _EY, [], R, Rs) -> + rkeymergel(I, [[Y, X | R] | Rs], []). + +%% One out-of-order element, S. +keysplit_1_1(I, X, EX, Y, EY, [Z | L], R, Rs, S, ES) -> + EZ = element(I, Z), + if + EY =< EZ -> + keysplit_1_1(I, Y, EY, Z, EZ, L, [X | R], Rs, S, ES); + EX =< EZ -> + keysplit_1_1(I, Z, EZ, Y, EY, L, [X | R], Rs, S, ES); + ES =< EZ -> + keysplit_1(I, S, ES, Z, EZ, L, [], [[Y, X | R] | Rs]); + true -> + keysplit_1(I, Z, EZ, S, ES, L, [], [[Y, X | R] | Rs]) + end; +keysplit_1_1(I, X, _EX, Y, _EY, [], R, Rs, S, _ES) -> + rkeymergel(I, [[S], [Y, X | R] | Rs], []). + +%% Descending. +keysplit_2(I, Y, EY, [Z | L], R) -> + EZ = element(I, Z), + if + EY =< EZ -> + keysplit_1(I, Y, EY, Z, EZ, L, [], [lists:reverse(R, [])]); + true -> + keysplit_2(I, Z, EZ, L, [Y | R]) + end; +keysplit_2(_I, Y, _EY, [], R) -> + [Y | R]. + +keymergel(I, [T1, [H2 | T2] | L], Acc) -> + keymergel(I, L, [keymerge2_1(I, T1, element(I, H2), H2, T2, []) | Acc]); +keymergel(_I, [L], []) -> + L; +keymergel(I, [L], Acc) -> + rkeymergel(I, [lists:reverse(L, []) | Acc], []); +keymergel(I, [], Acc) -> + rkeymergel(I, Acc, []). + +rkeymergel(I, [[H2 | T2], T1 | L], Acc) -> + rkeymergel(I, L, [rkeymerge2_1(I, T1, element(I, H2), H2, T2, []) | Acc]); +rkeymergel(I, [L], Acc) -> + keymergel(I, [lists:reverse(L, []) | Acc], []); +rkeymergel(I, [], Acc) -> + keymergel(I, Acc, []). + +keymerge2_1(I, [H1 | T1], E2, H2, T2, M) -> + E1 = element(I, H1), + if + E1 =< E2 -> + keymerge2_1(I, T1, E2, H2, T2, [H1 | M]); + true -> + keymerge2_2(I, T1, E1, H1, T2, [H2 | M]) + end; +keymerge2_1(_I, [], _E2, H2, T2, M) -> + lists:reverse(T2, [H2 | M]). + +keymerge2_2(I, T1, E1, H1, [H2 | T2], M) -> + E2 = element(I, H2), + if + E1 =< E2 -> + keymerge2_1(I, T1, E2, H2, T2, [H1 | M]); + true -> + keymerge2_2(I, T1, E1, H1, T2, [H2 | M]) + end; +keymerge2_2(_I, T1, _E1, H1, [], M) -> + lists:reverse(T1, [H1 | M]). + +rkeymerge2_1(I, [H1 | T1], E2, H2, T2, M) -> + E1 = element(I, H1), + if + E1 =< E2 -> + rkeymerge2_2(I, T1, E1, T2, [H2 | M], H1); + true -> + rkeymerge2_1(I, T1, E2, H2, T2, [H1 | M]) + end; +rkeymerge2_1(_I, [], _E2, H2, T2, M) -> + lists:reverse(T2, [H2 | M]). + +rkeymerge2_2(I, T1, E1, [H2 | T2], M, H1) -> + E2 = element(I, H2), + if + E1 =< E2 -> + rkeymerge2_2(I, T1, E1, T2, [H2 | M], H1); + true -> + rkeymerge2_1(I, T1, E2, H2, T2, [H1 | M]) + end; +rkeymerge2_2(_I, T1, _E1, [], M, H1) -> + lists:reverse(T1, [H1 | M]). + + +%%%------------------------------------------------------------ + +seq(doc) -> + ["Tests lists:seq/3"]; +seq(suite) -> + [ + seq_loop, + seq_2, seq_3, seq_2_e, seq_3_e]. + +seq_loop(doc) -> + ["Test for infinite loop (OTP-2404)."]; +seq_loop(suite) -> + []; +seq_loop(Config) when is_list(Config) -> + ?line _ = (catch lists:seq(1, 5, -1)), + ok. + +seq_2(doc) -> + ["Non-error cases for seq/2"]; +seq_2(suite) -> + []; +seq_2(Config) when is_list(Config) -> + ?line [1,2,3] = lists:seq(1,3), + ?line [1] = lists:seq(1,1), + ?line Big = 748274827583793785928592859, + ?line Big1 = Big+1, + ?line Big2 = Big+2, + ?line [Big, Big1, Big2] = lists:seq(Big, Big+2), + ok. + +seq_2_e(doc) -> + ["Error cases for seq/2"]; +seq_2_e(suite) -> + []; +seq_2_e(Config) when is_list(Config) -> + ?line seq_error([4, 2]), + ?line seq_error([1, a]), + ?line seq_error([1.0, 2.0]), + ok. + +seq_error(Args) -> + {'EXIT', _} = (catch apply(lists, seq, Args)). + +seq_3(doc) -> + ["Non-error cases for seq/3"]; +seq_3(suite) -> + []; +seq_3(Config) when is_list(Config) -> + ?line [1,2,3] = lists:seq(1,3,1), + ?line [1] = lists:seq(1,1,1), + ?line Big = 748274827583793785928592859, + ?line Big1 = Big+1, + ?line Big2 = Big+2, + ?line [Big, Big1, Big2] = lists:seq(Big, Big+2,1), + + ?line [3,2,1] = lists:seq(3,1,-1), + ?line [1] = lists:seq(1,1,-1), + + ?line [3,1] = lists:seq(3,1,-2), + ?line [1] = lists:seq(1, 10, 10), + ?line [1, 4, 7, 10, 13, 16, 19] = lists:seq(1, 19, 3), + ?line [1, 4, 7, 10, 13, 16, 19] = lists:seq(1, 20, 3), + ?line [1, 4, 7, 10, 13, 16, 19] = lists:seq(1, 21, 3), + + ?line [1] = lists:seq(1, 1, 0), %OTP-2613 + ok. + +seq_3_e(doc) -> + ["Error cases for seq/3"]; +seq_3_e(suite) -> + []; +seq_3_e(Config) when is_list(Config) -> + ?line seq_error([4, 2, 1]), + ?line seq_error([3, 5, -1]), + ?line seq_error([1, a, 1]), + ?line seq_error([1.0, 2.0, 1]), + + ?line seq_error([1, 3, 1.0]), + ?line seq_error([1, 3, a]), + ?line seq_error([1, 3, 0]), + + ?line seq_error([a, a, 0]), + ok. + +otp_7230(doc) -> + ["OTP-7230. seq/1,2 returns the empty list"]; +otp_7230(suite) -> + []; +otp_7230(Config) when is_list(Config) -> + From = -10, + To = 10, + StepFrom = -10, + StepTo = 10, + + L = lists:seq(From, To), + SL = lists:seq(StepFrom, StepTo), + ?line [] = + [{F, T, S} || + F <- L, T <- L, S <- SL, + not check_seq(F, T, S, catch lists:seq(F, T, S)) + orelse + S =:= 1 andalso not check_seq(F, T, S, catch lists:seq(F, T)) + ]. + +check_seq(From, To, 0, R) -> + From =:= To andalso R =:= [From] + orelse + From =/= To andalso is_tuple(R) andalso element(1, R) =:= 'EXIT'; +check_seq(From, To, Step, []) when Step =/= 0 -> + 0 =:= property(From, To, Step) + andalso + ( + Step > 0 andalso To < From andalso From-To =< Step + orelse + Step < 0 andalso To > From andalso To-From =< -Step + ); +check_seq(From, To, Step, R) when R =/= [], To < From, Step > 0 -> + is_tuple(R) andalso element(1, R) =:= 'EXIT'; +check_seq(From, To, Step, R) when R =/= [], To > From, Step < 0 -> + is_tuple(R) andalso element(1, R) =:= 'EXIT'; +check_seq(From, To, Step, L) when is_list(L), L =/= [], Step =/= 0 -> + First = hd(L), + Last = lists:last(L), + Min = lists:min(L), + Max = lists:max(L), + + [] =:= [E || E <- L, not is_integer(E)] + andalso + %% The difference between two consecutive elements is Step: + begin + LS = [First-Step]++L, + LR = L++[Last+Step], + [Step] =:= lists:usort([B-A || {A,B} <- lists:zip(LS, LR)]) + end + andalso + %% The first element of L is From: + From =:= First + andalso + %% No element outside the given interval: + Min >= lists:min([From, To]) + andalso + Max =< lists:max([From, To]) + andalso + %% All elements are present: + abs(To-Last) < abs(Step) + andalso + length(L) =:= property(From, To, Step); +check_seq(_From, _To, _Step, _R) -> + false. + +property(From, To, Step) -> + ((To-From+Step) div Step). + +%%%------------------------------------------------------------ + +sublist(doc) -> + ["Tests lists:sublist/[2,3]"]; +sublist(suite) -> + [sublist_2, sublist_3, sublist_2_e, sublist_3_e]. + +-define(sublist_error2(X,Y), ?line {'EXIT', _} = (catch lists:sublist(X,Y))). +-define(sublist_error3(X,Y,Z), ?line {'EXIT', _} = (catch lists:sublist(X,Y,Z))). + +sublist_2(doc) -> ["sublist/2"]; +sublist_2(suite) -> []; +sublist_2(Config) when is_list(Config) -> + ?line [] = lists:sublist([], 0), + ?line [] = lists:sublist([], 1), + ?line [] = lists:sublist([a], 0), + ?line [a] = lists:sublist([a], 1), + ?line [a] = lists:sublist([a], 2), + ?line [a] = lists:sublist([a|b], 1), + + ?line [a,b] = lists:sublist([a,b|c], 2), + + ok. + +sublist_2_e(doc) -> ["sublist/2 error cases"]; +sublist_2_e(suite) -> []; +sublist_2_e(Config) when is_list(Config) -> + ?sublist_error2([], -1), + ?sublist_error2(a, -1), + ?sublist_error2(a, 0), + ?sublist_error2([a|b], 2), + ?sublist_error2([a], x), + ?sublist_error2([a], 1.5), + ?sublist_error2([], x), + ?sublist_error2([], 1.5), + ok. + +sublist_3(doc) -> ["sublist/3"]; +sublist_3(suite) -> []; +sublist_3(Config) when is_list(Config) -> + ?line [] = lists:sublist([], 1, 0), + ?line [] = lists:sublist([], 1, 1), + ?line [] = lists:sublist([a], 1, 0), + ?line [a] = lists:sublist([a], 1, 1), + ?line [a] = lists:sublist([a], 1, 2), + ?line [a] = lists:sublist([a|b], 1, 1), + + ?line [] = lists:sublist([], 1, 0), + ?line [] = lists:sublist([], 1, 1), + ?line [] = lists:sublist([a], 1, 0), + ?line [a] = lists:sublist([a], 1, 1), + ?line [a] = lists:sublist([a], 1, 2), + ?line [] = lists:sublist([a], 2, 1), + ?line [] = lists:sublist([a], 2, 2), + ?line [] = lists:sublist([a], 2, 79), + ?line [] = lists:sublist([a,b|c], 1, 0), + ?line [] = lists:sublist([a,b|c], 2, 0), + ?line [a] = lists:sublist([a,b|c], 1, 1), + ?line [b] = lists:sublist([a,b|c], 2, 1), + ?line [a,b] = lists:sublist([a,b|c], 1, 2), + + ?line [] = lists:sublist([a], 2, 0), + + ok. + +sublist_3_e(doc) -> ["sublist/3 error cases"]; +sublist_3_e(suite) -> []; +sublist_3_e(Config) when is_list(Config) -> + ?sublist_error3([], 1, -1), + ?sublist_error3(a, 1, -1), + ?sublist_error3(a, 1, 0), + ?sublist_error3([a|b], 1, 2), + ?sublist_error3([a], 1, x), + ?sublist_error3([a], 1, 1.5), + ?sublist_error3([], 1, x), + ?sublist_error3([], 1, 1.5), + + ?sublist_error3([], -1, 0), + ?sublist_error3(a, x, -1), + ?sublist_error3([a,b], 0.5, 1), + ?sublist_error3([a,b], 1.5, 1), + ?sublist_error3([a], 1, x), + ?sublist_error3([a], 1, 1.5), + ?sublist_error3([], 1, x), + ?sublist_error3([], 1, 1.5), + + ?sublist_error3([a], 0, -1), + ?sublist_error3([a], 1, -1), + ?sublist_error3([a], 2, -1), + ?sublist_error3([a], 0, 0), + ?sublist_error3([a], 0, 1), + + ?sublist_error3([a,b|c], 2, 2), + ?sublist_error3([a,b|c], 3, 0), + ?sublist_error3([a,b|c], 3, 1), + ok. + +%%%------------------------------------------------------------ + +flatten(doc) -> + ["Tests lists:flatten/[1,2]"]; +flatten(suite) -> + [flatten_1, flatten_2, flatten_1_e, flatten_2_e]. + +-define(flatten_error1(X), ?line {'EXIT', _} = (catch lists:flatten(X))). +-define(flatten_error2(X,Y), ?line {'EXIT', _} = (catch lists:flatten(X,Y))). + +flatten_1(doc) -> ["flatten/1"]; +flatten_1(suite) -> []; +flatten_1(Config) when is_list(Config) -> + ?line [] = lists:flatten([]), + ?line [1,2] = lists:flatten([1,2]), + ?line [1,2] = lists:flatten([1,[2]]), + ?line [1,2] = lists:flatten([[1],2]), + ?line [1,2] = lists:flatten([[1],[2]]), + ?line [1,2] = lists:flatten([[1,2]]), + ?line [a,b,c,d] = lists:flatten([[a],[b,c,[d]]]), + + ok. + +flatten_1_e(doc) -> ["flatten/1 error cases"]; +flatten_1_e(suite) -> []; +flatten_1_e(Config) when is_list(Config) -> + ?flatten_error1(a), + ?flatten_error1([a|b]), + ?flatten_error1([[a],[b|c],[d]]), + ok. + +%%% [arndt] What if second arg isn't a proper list? This issue isn't +%%% clear-cut. Right now, I think that any term should be allowed. +%%% But I also wish this function didn't exist at all. + +flatten_2(doc) -> ["flatten/2"]; +flatten_2(suite) -> []; +flatten_2(Config) when is_list(Config) -> + ?line [] = lists:flatten([]), + ?line [a] = lists:flatten([a]), + ok. + +flatten_2_e(doc) -> ["flatten/2 error cases"]; +flatten_2_e(suite) -> []; +flatten_2_e(Config) when is_list(Config) -> + ok. + +%% Test lists:zip/2, lists:unzip/1. +zip_unzip(Config) when is_list(Config) -> + ?line [] = lists:zip([], []), + ?line [{a,b}] = lists:zip([a], [b]), + ?line [{42.0,{kalle,nisse}},{a,b}] = lists:zip([42.0,a], [{kalle,nisse},b]), + + %% Longer lists. + ?line SeqA = lists:seq(45, 200), + ?line SeqB = [A*A || A <- SeqA], + ?line AB = lists:zip(SeqA, SeqB), + ?line SeqA = [A || {A,_} <- AB], + ?line SeqB = [B || {_,B} <- AB], + ?line {SeqA,SeqB} = lists:unzip(AB), + + %% Some more unzip/1. + ?line {[],[]} = lists:unzip([]), + ?line {[a],[b]} = lists:unzip([{a,b}]), + ?line {[a,c],[b,d]} = lists:unzip([{a,b},{c,d}]), + + %% Error cases. + ?line {'EXIT',{function_clause,_}} = (catch lists:zip([], [b])), + ?line {'EXIT',{function_clause,_}} = (catch lists:zip([a], [])), + ?line {'EXIT',{function_clause,_}} = (catch lists:zip([a], [b,c])), + ?line {'EXIT',{function_clause,_}} = (catch lists:zip([a], [b,c])), + ok. + +%% Test lists:zip3/3, lists:unzip3/1. +zip_unzip3(Config) when is_list(Config) -> + ?line [] = lists:zip3([], [], []), + ?line [{a,b,c}] = lists:zip3([a], [b], [c]), + + %% Longer lists. + ?line SeqA = lists:seq(45, 200), + ?line SeqB = [2*A || A <- SeqA], + ?line SeqC = [A*A || A <- SeqA], + ?line ABC = lists:zip3(SeqA, SeqB, SeqC), + ?line SeqA = [A || {A,_,_} <- ABC], + ?line SeqB = [B || {_,B,_} <- ABC], + ?line SeqC = [C || {_,_,C} <- ABC], + ?line {SeqA,SeqB,SeqC} = lists:unzip3(ABC), + + %% Some more unzip3/1. + ?line {[],[],[]} = lists:unzip3([]), + ?line {[a],[b],[c]} = lists:unzip3([{a,b,c}]), + + %% Error cases. + ?line {'EXIT',{function_clause,_}} = (catch lists:zip3([], [], [c])), + ?line {'EXIT',{function_clause,_}} = (catch lists:zip3([], [b], [])), + ?line {'EXIT',{function_clause,_}} = (catch lists:zip3([a], [], [])), + + ok. + +%% Test lists:zipwith/3. +zipwith(Config) when is_list(Config) -> + Zip = fun(A, B) -> [A|B] end, + + ?line [] = lists:zipwith(Zip, [], []), + ?line [[a|b]] = lists:zipwith(Zip, [a], [b]), + + %% Longer lists. + ?line SeqA = lists:seq(77, 300), + ?line SeqB = [A*A || A <- SeqA], + ?line AB = lists:zipwith(Zip, SeqA, SeqB), + ?line SeqA = [A || [A|_] <- AB], + ?line SeqB = [B || [_|B] <- AB], + + %% Error cases. + ?line {'EXIT',{function_clause,_}} = (catch lists:zipwith(badfun, [], [])), + ?line {'EXIT',{function_clause,_}} = (catch lists:zipwith(Zip, [], [b])), + ?line {'EXIT',{function_clause,_}} = (catch lists:zipwith(Zip, [a], [])), + ?line {'EXIT',{function_clause,_}} = (catch lists:zipwith(Zip, [a], [b,c])), + ?line {'EXIT',{function_clause,_}} = (catch lists:zipwith(Zip, [a], [b,c])), + ok. + +%% Test lists:zipwith3/4. +zipwith3(Config) when is_list(Config) -> + Zip = fun(A, B, C) -> [A,B,C] end, + + ?line [] = lists:zipwith3(Zip, [], [], []), + ?line [[a,b,c]] = lists:zipwith3(Zip, [a], [b], [c]), + + %% Longer lists. + ?line SeqA = lists:seq(45, 200), + ?line SeqB = [2*A || A <- SeqA], + ?line SeqC = [A*A || A <- SeqA], + ?line ABC = lists:zipwith3(Zip, SeqA, SeqB, SeqC), + ?line SeqA = [A || [A,_,_] <- ABC], + ?line SeqB = [B || [_,B,_] <- ABC], + ?line SeqC = [C || [_,_,C] <- ABC], + + %% Error cases. + ?line {'EXIT',{function_clause,_}} = (catch lists:zipwith3(badfun, [], [], [])), + ?line {'EXIT',{function_clause,_}} = (catch lists:zipwith3(Zip, [], [], [c])), + ?line {'EXIT',{function_clause,_}} = (catch lists:zipwith3(Zip, [], [b], [])), + ?line {'EXIT',{function_clause,_}} = (catch lists:zipwith3(Zip, [a], [], [])), + + ok. + +%% Test lists:filter/2, lists:partition/2. +filter_partition(Config) when is_list(Config) -> + F = fun(I) -> I rem 2 =:= 0 end, + ?line filpart(F, [], []), + ?line filpart(F, [1], []), + ?line filpart(F, [1,3,17], []), + ?line filpart(F, [1,2,3,17], [2]), + ?line filpart(F, [6,8,1,2,3,17], [6,8,2]), + ?line filpart(F, [6,8,1,2,42,3,17], [6,8,2,42]), + + %% Error cases. + ?line {'EXIT',{function_clause,_}} = (catch lists:filter(badfun, [])), + ?line {'EXIT',{function_clause,_}} = (catch lists:partition(badfun, [])), + ok. + +filpart(F, All, Exp) -> + Exp = lists:filter(F, All), + Other = lists:filter(fun(E) -> not F(E) end, All), + {Exp,Other} = lists:partition(F, All). + +tickets(doc) -> + ["Ticktes."]; +tickets(suite) -> + [otp_5939, otp_6023, otp_6606, otp_7230]. + +otp_5939(doc) -> ["OTP-5939. Guard tests added."]; +otp_5939(suite) -> []; +otp_5939(Config) when is_list(Config) -> + Fun1 = fun(A) -> A end, + Fun2 = fun(A, B) -> {A,B} end, + Fun3 = fun(A, B, C) -> {A,B,C} end, + Pred = fun(_A) -> true end, + Fold = fun(_E, A) -> A end, + MapFold = fun(E, A) -> {E,A} end, + + ?line {'EXIT', _} = (catch lists:usort( [asd], [qwe])), + + ?line {'EXIT', _} = (catch lists:zipwith(func, [], [])), + ?line [] = lists:zipwith(Fun2, [], []), + ?line {'EXIT', _} = (catch lists:zipwith3(func, [], [], [])), + ?line [] = lists:zipwith3(Fun3, [], [], []), + ?line {'EXIT', _} = (catch lists:keymap(func, 1, [])), + ?line {'EXIT', _} = (catch lists:keymap(Fun1, 0, [])), + ?line [] = lists:keymap(Fun1, 1, []), + ?line {'EXIT', _} = (catch lists:merge(func, [], [1])), + ?line {'EXIT', _} = (catch lists:merge(func, [1], [])), + ?line [] = lists:merge(Fun2, [], []), + ?line {'EXIT', _} = (catch lists:rmerge(func, [], [1])), + ?line {'EXIT', _} = (catch lists:rmerge(func, [1], [])), + ?line [] = lists:rmerge(Fun2, [], []), + ?line {'EXIT', _} = (catch lists:usort(func, [])), + ?line {'EXIT', _} = (catch lists:usort(func, [a])), + ?line {'EXIT', _} = (catch lists:usort(func, [a, b])), + ?line [] = lists:usort(Fun2, []), + ?line {'EXIT', _} = (catch lists:umerge(func, [], [1])), + ?line {'EXIT', _} = (catch lists:merge(func, [1], [])), + ?line [] = lists:umerge(Fun2, [], []), + ?line {'EXIT', _} = (catch lists:rumerge(func, [], [1])), + ?line {'EXIT', _} = (catch lists:rumerge(func, [1], [])), + ?line [] = lists:rumerge(Fun2, [], []), + ?line {'EXIT', _} = (catch lists:all(func, [])), + ?line true = lists:all(Pred, []), + ?line {'EXIT', _} = (catch lists:any(func, [])), + ?line false = lists:any(Pred, []), + ?line {'EXIT', _} = (catch lists:map(func, [])), + ?line [] = lists:map(Fun1, []), + ?line {'EXIT', _} = (catch lists:flatmap(func, [])), + ?line [] = lists:flatmap(Fun1, []), + ?line {'EXIT', _} = (catch lists:foldl(func, [], [])), + ?line [] = lists:foldl(Fold, [], []), + ?line {'EXIT', _} = (catch lists:foldr(func, [], [])), + ?line [] = lists:foldr(Fold, [], []), + ?line {'EXIT', _} = (catch lists:filter(func, [])), + ?line [] = lists:filter(Pred, []), + ?line {'EXIT', _} = (catch lists:partition(func, [])), + ?line {[],[]} = lists:partition(Pred, []), + ?line {'EXIT', _} = (catch lists:zf(func, [])), + ?line [] = lists:zf(Fun1, []), + ?line {'EXIT', _} = (catch lists:foreach(func, [])), + ?line ok = lists:foreach(Fun1, []), + ?line {'EXIT', _} = (catch lists:mapfoldl(func, [], [])), + ?line {[],[]} = lists:mapfoldl(MapFold, [], []), + ?line {'EXIT', _} = (catch lists:mapfoldr(func, [], [])), + ?line {[],[]} = lists:mapfoldr(MapFold, [], []), + ?line {'EXIT', _} = (catch lists:takewhile(func, [])), + ?line [] = lists:takewhile(Pred, []), + ?line {'EXIT', _} = (catch lists:dropwhile(func, [])), + ?line [] = lists:dropwhile(Pred, []), + ?line {'EXIT', _} = (catch lists:splitwith(func, [])), + ?line {[],[]} = lists:splitwith(Pred, []), + + ok. + +otp_6023(doc) -> ["OTP-6023. lists:keyreplace/4, a typecheck."]; +otp_6023(suite) -> []; +otp_6023(Config) when is_list(Config) -> + ?line {'EXIT', _} = (catch lists:keyreplace(a, 2, [{1,a}], b)), + ?line [{2,b}] = lists:keyreplace(a, 2, [{1,a}], {2,b}), + + ok. + +otp_6606(doc) -> ["OTP-6606. sort and keysort bug"]; +otp_6606(suite) -> []; +otp_6606(Config) when is_list(Config) -> + I = 1, + F = float(1), + L1 = [{F,I},{F,F},{I,I},{I,F}], + ?line L1 = lists:keysort(1, L1), + ?line L1 = lists:sort(L1), + L2 = [{I,I},{I,F},{F,I},{F,F}], + ?line L2 = lists:keysort(1, L2), + ?line L2 = lists:sort(L2), + ok. + +%% Test lists:suffix/2. +suffix(Config) when is_list(Config) -> + ?line true = lists:suffix([], []), + ?line true = lists:suffix([], [a]), + ?line true = lists:suffix([], [a,b]), + ?line true = lists:suffix([], [a,b,c]), + ?line true = lists:suffix([a], lists:duplicate(200000, a)), + ?line true = lists:suffix(lists:seq(1, 1024), + lists:seq(2, 64000) ++ lists:seq(1, 1024)), + ?line true = lists:suffix(lists:duplicate(20000, a), + lists:duplicate(200000, a)), + ?line true = lists:suffix([2.0,3.0], [1.0,2.0,3.0]), + + %% False cases. + ?line false = lists:suffix([a], []), + ?line false = lists:suffix([a,b,c], []), + ?line false = lists:suffix([a,b,c], [b,c]), + ?line false = lists:suffix([a,b,c], [a,b,c,a,b]), + ?line false = lists:suffix(lists:duplicate(199999, a)++[b], + lists:duplicate(200000, a)), + ?line false = lists:suffix([2.0,3.0], [1,2,3]), + + %% Error cases. + ?line {'EXIT',_} = (catch lists:suffix({a,b,c}, [])), + ?line {'EXIT',_} = (catch lists:suffix([], {a,b})), + ?line {'EXIT',_} = (catch lists:suffix([a|b], [])), + ?line {'EXIT',_} = (catch lists:suffix([a,b|c], [a|b])), + ?line {'EXIT',_} = (catch lists:suffix([a|b], [a,b|c])), + ?line {'EXIT',_} = (catch lists:suffix([a|b], [a|b])), + + ok. + +%% Test lists:subtract/2 and the '--' operator. +subtract(Config) when is_list(Config) -> + ?line [] = sub([], []), + ?line [] = sub([], [a]), + ?line [] = sub([], lists:seq(1, 1024)), + ?line sub_non_matching([a], []), + ?line sub_non_matching([1,2], [make_ref()]), + ?line sub_non_matching(lists:seq(1, 1024), [make_ref(),make_ref()]), + + %% Matching subtracts. + ?line [] = sub([a], [a]), + ?line [a] = sub([a,b], [b]), + ?line [a] = sub([a,b], [b,c]), + ?line [a] = sub([a,b,c], [b,c]), + ?line [a] = sub([a,b,c], [b,c]), + ?line [d,a,a] = sub([a,b,c,d,a,a], [a,b,c]), + ?line [d,x,a] = sub([a,b,c,d,a,x,a], [a,b,c,a]), + ?line [1,2,3,4,5,6,7,8,9,9999,10000,20,21,22] = + sub(lists:seq(1, 10000)++[20,21,22], lists:seq(10, 9998)), + + %% Floats/integers. + ?line [42.0,42.0] = sub([42.0,42,42.0], [42,42,42]), + ?line [1,2,3,4,43.0] = sub([1,2,3,4,5,42.0,43.0], [42.0,5]), + + %% Crashing subtracts. + ?line {'EXIT',_} = (catch sub([], [a|b])), + ?line {'EXIT',_} = (catch sub([a], [a|b])), + ?line {'EXIT',_} = (catch sub([a|b], [])), + ?line {'EXIT',_} = (catch sub([a|b], [])), + ?line {'EXIT',_} = (catch sub([a|b], [a])), + + ok. + +sub_non_matching(A, B) -> + A = sub(A, B). + +sub(A, B) -> + Res = A -- B, + Res = lists:subtract(A, B). + |