1%% 2%% %CopyrightBegin% 3%% 4%% Copyright Ericsson AB 1996-2018. All Rights Reserved. 5%% 6%% Licensed under the Apache License, Version 2.0 (the "License"); 7%% you may not use this file except in compliance with the License. 8%% You may obtain a copy of the License at 9%% 10%% http://www.apache.org/licenses/LICENSE-2.0 11%% 12%% Unless required by applicable law or agreed to in writing, software 13%% distributed under the License is distributed on an "AS IS" BASIS, 14%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15%% See the License for the specific language governing permissions and 16%% limitations under the License. 17%% 18%% %CopyrightEnd% 19%% 20-module(lists). 21 22-compile({no_auto_import,[max/2]}). 23-compile({no_auto_import,[min/2]}). 24 25-export([append/2, append/1, subtract/2, reverse/1, 26 nth/2, nthtail/2, prefix/2, suffix/2, droplast/1, last/1, 27 seq/2, seq/3, sum/1, duplicate/2, min/1, max/1, sublist/2, sublist/3, 28 delete/2, 29 unzip/1, unzip3/1, zip/2, zip3/3, zipwith/3, zipwith3/4, 30 sort/1, merge/1, merge/2, rmerge/2, merge3/3, rmerge3/3, 31 usort/1, umerge/1, umerge3/3, umerge/2, rumerge3/3, rumerge/2, 32 concat/1, flatten/1, flatten/2, flatlength/1, 33 keydelete/3, keyreplace/4, keytake/3, keystore/4, 34 keysort/2, keymerge/3, rkeymerge/3, rukeymerge/3, 35 ukeysort/2, ukeymerge/3, keymap/3]). 36 37-export([merge/3, rmerge/3, sort/2, umerge/3, rumerge/3, usort/2]). 38 39-export([all/2,any/2,map/2,flatmap/2,foldl/3,foldr/3,filter/2, 40 partition/2,zf/2,filtermap/2, 41 mapfoldl/3,mapfoldr/3,foreach/2,takewhile/2,dropwhile/2, 42 search/2, splitwith/2,split/2, 43 join/2]). 44 45%%% BIFs 46-export([keyfind/3, keymember/3, keysearch/3, member/2, reverse/2]). 47 48%% Shadowed by erl_bif_types: lists:keyfind/3 49-spec keyfind(Key, N, TupleList) -> Tuple | false when 50 Key :: term(), 51 N :: pos_integer(), 52 TupleList :: [Tuple], 53 Tuple :: tuple(). 54 55keyfind(_, _, _) -> 56 erlang:nif_error(undef). 57 58%% Shadowed by erl_bif_types: lists:keymember/3 59-spec keymember(Key, N, TupleList) -> boolean() when 60 Key :: term(), 61 N :: pos_integer(), 62 TupleList :: [Tuple], 63 Tuple :: tuple(). 64 65keymember(_, _, _) -> 66 erlang:nif_error(undef). 67 68%% Shadowed by erl_bif_types: lists:keysearch/3 69-spec keysearch(Key, N, TupleList) -> {value, Tuple} | false when 70 Key :: term(), 71 N :: pos_integer(), 72 TupleList :: [Tuple], 73 Tuple :: tuple(). 74 75keysearch(_, _, _) -> 76 erlang:nif_error(undef). 77 78%% Shadowed by erl_bif_types: lists:member/2 79-spec member(Elem, List) -> boolean() when 80 Elem :: T, 81 List :: [T], 82 T :: term(). 83 84member(_, _) -> 85 erlang:nif_error(undef). 86 87%% Shadowed by erl_bif_types: lists:reverse/2 88-spec reverse(List1, Tail) -> List2 when 89 List1 :: [T], 90 Tail :: term(), 91 List2 :: [T], 92 T :: term(). 93 94reverse(_, _) -> 95 erlang:nif_error(undef). 96 97%%% End of BIFs 98 99%% member(X, L) -> (true | false) 100%% test if X is a member of the list L 101%% Now a BIF! 102 103%member(X, [X|_]) -> true; 104%member(X, [_|Y]) -> 105% member(X, Y); 106%member(X, []) -> false. 107 108%% append(X, Y) appends lists X and Y 109 110-spec append(List1, List2) -> List3 when 111 List1 :: [T], 112 List2 :: [T], 113 List3 :: [T], 114 T :: term(). 115 116append(L1, L2) -> L1 ++ L2. 117 118%% append(L) appends the list of lists L 119 120-spec append(ListOfLists) -> List1 when 121 ListOfLists :: [List], 122 List :: [T], 123 List1 :: [T], 124 T :: term(). 125 126append([E]) -> E; 127append([H|T]) -> H ++ append(T); 128append([]) -> []. 129 130%% subtract(List1, List2) subtract elements in List2 form List1. 131 132-spec subtract(List1, List2) -> List3 when 133 List1 :: [T], 134 List2 :: [T], 135 List3 :: [T], 136 T :: term(). 137 138subtract(L1, L2) -> L1 -- L2. 139 140%% reverse(L) reverse all elements in the list L. reverse/2 is now a BIF! 141 142-spec reverse(List1) -> List2 when 143 List1 :: [T], 144 List2 :: [T], 145 T :: term(). 146 147reverse([] = L) -> 148 L; 149reverse([_] = L) -> 150 L; 151reverse([A, B]) -> 152 [B, A]; 153reverse([A, B | L]) -> 154 lists:reverse(L, [B, A]). 155 156%reverse([H|T], Y) -> 157% reverse(T, [H|Y]); 158%reverse([], X) -> X. 159 160 161%% nth(N, L) returns the N`th element of the list L 162%% nthtail(N, L) returns the N`th tail of the list L 163 164-spec nth(N, List) -> Elem when 165 N :: pos_integer(), 166 List :: [T,...], 167 Elem :: T, 168 T :: term(). 169 170nth(1, [H|_]) -> H; 171nth(N, [_|T]) when N > 1 -> 172 nth(N - 1, T). 173 174-spec nthtail(N, List) -> Tail when 175 N :: non_neg_integer(), 176 List :: [T,...], 177 Tail :: [T], 178 T :: term(). 179 180nthtail(1, [_|T]) -> T; 181nthtail(N, [_|T]) when N > 1 -> 182 nthtail(N - 1, T); 183nthtail(0, L) when is_list(L) -> L. 184 185%% prefix(Prefix, List) -> (true | false) 186 187-spec prefix(List1, List2) -> boolean() when 188 List1 :: [T], 189 List2 :: [T], 190 T :: term(). 191 192prefix([X|PreTail], [X|Tail]) -> 193 prefix(PreTail, Tail); 194prefix([], List) when is_list(List) -> true; 195prefix([_|_], List) when is_list(List) -> false. 196 197%% suffix(Suffix, List) -> (true | false) 198 199-spec suffix(List1, List2) -> boolean() when 200 List1 :: [T], 201 List2 :: [T], 202 T :: term(). 203 204suffix(Suffix, List) -> 205 Delta = length(List) - length(Suffix), 206 Delta >= 0 andalso nthtail(Delta, List) =:= Suffix. 207 208%% droplast(List) returns the list dropping its last element 209 210-spec droplast(List) -> InitList when 211 List :: [T, ...], 212 InitList :: [T], 213 T :: term(). 214 215%% This is the simple recursive implementation 216%% reverse(tl(reverse(L))) is faster on average, 217%% but creates more garbage. 218droplast([_T]) -> []; 219droplast([H|T]) -> [H|droplast(T)]. 220 221%% last(List) returns the last element in a list. 222 223-spec last(List) -> Last when 224 List :: [T,...], 225 Last :: T, 226 T :: term(). 227 228last([E|Es]) -> last(E, Es). 229 230last(_, [E|Es]) -> last(E, Es); 231last(E, []) -> E. 232 233%% seq(Min, Max) -> [Min,Min+1, ..., Max] 234%% seq(Min, Max, Incr) -> [Min,Min+Incr, ..., Max] 235%% returns the sequence Min..Max 236%% Min <= Max and Min and Max must be integers 237 238-spec seq(From, To) -> Seq when 239 From :: integer(), 240 To :: integer(), 241 Seq :: [integer()]. 242 243seq(First, Last) 244 when is_integer(First), is_integer(Last), First-1 =< Last -> 245 seq_loop(Last-First+1, Last, []). 246 247seq_loop(N, X, L) when N >= 4 -> 248 seq_loop(N-4, X-4, [X-3,X-2,X-1,X|L]); 249seq_loop(N, X, L) when N >= 2 -> 250 seq_loop(N-2, X-2, [X-1,X|L]); 251seq_loop(1, X, L) -> 252 [X|L]; 253seq_loop(0, _, L) -> 254 L. 255 256-spec seq(From, To, Incr) -> Seq when 257 From :: integer(), 258 To :: integer(), 259 Incr :: integer(), 260 Seq :: [integer()]. 261 262seq(First, Last, Inc) 263 when is_integer(First), is_integer(Last), is_integer(Inc) -> 264 if 265 Inc > 0, First - Inc =< Last; 266 Inc < 0, First - Inc >= Last -> 267 N = (Last - First + Inc) div Inc, 268 seq_loop(N, Inc*(N-1)+First, Inc, []); 269 Inc =:= 0, First =:= Last -> 270 seq_loop(1, First, Inc, []) 271 end. 272 273seq_loop(N, X, D, L) when N >= 4 -> 274 Y = X-D, Z = Y-D, W = Z-D, 275 seq_loop(N-4, W-D, D, [W,Z,Y,X|L]); 276seq_loop(N, X, D, L) when N >= 2 -> 277 Y = X-D, 278 seq_loop(N-2, Y-D, D, [Y,X|L]); 279seq_loop(1, X, _, L) -> 280 [X|L]; 281seq_loop(0, _, _, L) -> 282 L. 283 284%% sum(L) returns the sum of the elements in L 285 286-spec sum(List) -> number() when 287 List :: [number()]. 288 289sum(L) -> sum(L, 0). 290 291sum([H|T], Sum) -> sum(T, Sum + H); 292sum([], Sum) -> Sum. 293 294%% duplicate(N, X) -> [X,X,X,.....,X] (N times) 295%% return N copies of X 296 297-spec duplicate(N, Elem) -> List when 298 N :: non_neg_integer(), 299 Elem :: T, 300 List :: [T], 301 T :: term(). 302 303duplicate(N, X) when is_integer(N), N >= 0 -> duplicate(N, X, []). 304 305duplicate(0, _, L) -> L; 306duplicate(N, X, L) -> duplicate(N-1, X, [X|L]). 307 308%% min(L) -> returns the minimum element of the list L 309 310-spec min(List) -> Min when 311 List :: [T,...], 312 Min :: T, 313 T :: term(). 314 315min([H|T]) -> min(T, H). 316 317min([H|T], Min) when H < Min -> min(T, H); 318min([_|T], Min) -> min(T, Min); 319min([], Min) -> Min. 320 321%% max(L) -> returns the maximum element of the list L 322 323-spec max(List) -> Max when 324 List :: [T,...], 325 Max :: T, 326 T :: term(). 327 328max([H|T]) -> max(T, H). 329 330max([H|T], Max) when H > Max -> max(T, H); 331max([_|T], Max) -> max(T, Max); 332max([], Max) -> Max. 333 334%% sublist(List, Start, Length) 335%% Returns the sub-list starting at Start of length Length. 336 337-spec sublist(List1, Start, Len) -> List2 when 338 List1 :: [T], 339 List2 :: [T], 340 Start :: pos_integer(), 341 Len :: non_neg_integer(), 342 T :: term(). 343 344sublist(List, S, L) when is_integer(L), L >= 0 -> 345 sublist(nthtail(S-1, List), L). 346 347-spec sublist(List1, Len) -> List2 when 348 List1 :: [T], 349 List2 :: [T], 350 Len :: non_neg_integer(), 351 T :: term(). 352 353sublist(List, L) when is_integer(L), is_list(List) -> 354 sublist_2(List, L). 355 356sublist_2([H|T], L) when L > 0 -> 357 [H|sublist_2(T, L-1)]; 358sublist_2(_, 0) -> 359 []; 360sublist_2(List, L) when is_list(List), L > 0 -> 361 []. 362 363%% delete(Item, List) -> List' 364%% Delete the first occurrence of Item from the list L. 365 366-spec delete(Elem, List1) -> List2 when 367 Elem :: T, 368 List1 :: [T], 369 List2 :: [T], 370 T :: term(). 371 372delete(Item, [Item|Rest]) -> Rest; 373delete(Item, [H|Rest]) -> 374 [H|delete(Item, Rest)]; 375delete(_, []) -> []. 376 377%% Return [{X0, Y0}, {X1, Y1}, ..., {Xn, Yn}] for lists [X0, X1, ..., 378%% Xn] and [Y0, Y1, ..., Yn]. 379 380-spec zip(List1, List2) -> List3 when 381 List1 :: [A], 382 List2 :: [B], 383 List3 :: [{A, B}], 384 A :: term(), 385 B :: term(). 386 387zip([X | Xs], [Y | Ys]) -> [{X, Y} | zip(Xs, Ys)]; 388zip([], []) -> []. 389 390%% Return {[X0, X1, ..., Xn], [Y0, Y1, ..., Yn]}, for a list [{X0, Y0}, 391%% {X1, Y1}, ..., {Xn, Yn}]. 392 393-spec unzip(List1) -> {List2, List3} when 394 List1 :: [{A, B}], 395 List2 :: [A], 396 List3 :: [B], 397 A :: term(), 398 B :: term(). 399 400unzip(Ts) -> unzip(Ts, [], []). 401 402unzip([{X, Y} | Ts], Xs, Ys) -> unzip(Ts, [X | Xs], [Y | Ys]); 403unzip([], Xs, Ys) -> {reverse(Xs), reverse(Ys)}. 404 405%% Return [{X0, Y0, Z0}, {X1, Y1, Z1}, ..., {Xn, Yn, Zn}] for lists [X0, 406%% X1, ..., Xn], [Y0, Y1, ..., Yn] and [Z0, Z1, ..., Zn]. 407 408-spec zip3(List1, List2, List3) -> List4 when 409 List1 :: [A], 410 List2 :: [B], 411 List3 :: [C], 412 List4 :: [{A, B, C}], 413 A :: term(), 414 B :: term(), 415 C :: term(). 416 417zip3([X | Xs], [Y | Ys], [Z | Zs]) -> [{X, Y, Z} | zip3(Xs, Ys, Zs)]; 418zip3([], [], []) -> []. 419 420%% Return {[X0, X1, ..., Xn], [Y0, Y1, ..., Yn], [Z0, Z1, ..., Zn]}, for 421%% a list [{X0, Y0, Z0}, {X1, Y1, Z1}, ..., {Xn, Yn, Zn}]. 422 423-spec unzip3(List1) -> {List2, List3, List4} when 424 List1 :: [{A, B, C}], 425 List2 :: [A], 426 List3 :: [B], 427 List4 :: [C], 428 A :: term(), 429 B :: term(), 430 C :: term(). 431 432unzip3(Ts) -> unzip3(Ts, [], [], []). 433 434unzip3([{X, Y, Z} | Ts], Xs, Ys, Zs) -> 435 unzip3(Ts, [X | Xs], [Y | Ys], [Z | Zs]); 436unzip3([], Xs, Ys, Zs) -> 437 {reverse(Xs), reverse(Ys), reverse(Zs)}. 438 439%% Return [F(X0, Y0), F(X1, Y1), ..., F(Xn, Yn)] for lists [X0, X1, ..., 440%% Xn] and [Y0, Y1, ..., Yn]. 441 442-spec zipwith(Combine, List1, List2) -> List3 when 443 Combine :: fun((X, Y) -> T), 444 List1 :: [X], 445 List2 :: [Y], 446 List3 :: [T], 447 X :: term(), 448 Y :: term(), 449 T :: term(). 450 451zipwith(F, [X | Xs], [Y | Ys]) -> [F(X, Y) | zipwith(F, Xs, Ys)]; 452zipwith(F, [], []) when is_function(F, 2) -> []. 453 454%% Return [F(X0, Y0, Z0), F(X1, Y1, Z1), ..., F(Xn, Yn, Zn)] for lists 455%% [X0, X1, ..., Xn], [Y0, Y1, ..., Yn] and [Z0, Z1, ..., Zn]. 456 457-spec zipwith3(Combine, List1, List2, List3) -> List4 when 458 Combine :: fun((X, Y, Z) -> T), 459 List1 :: [X], 460 List2 :: [Y], 461 List3 :: [Z], 462 List4 :: [T], 463 X :: term(), 464 Y :: term(), 465 Z :: term(), 466 T :: term(). 467 468zipwith3(F, [X | Xs], [Y | Ys], [Z | Zs]) -> 469 [F(X, Y, Z) | zipwith3(F, Xs, Ys, Zs)]; 470zipwith3(F, [], [], []) when is_function(F, 3) -> []. 471 472%% sort(List) -> L 473%% sorts the list L 474 475-spec sort(List1) -> List2 when 476 List1 :: [T], 477 List2 :: [T], 478 T :: term(). 479 480sort([X, Y | L] = L0) when X =< Y -> 481 case L of 482 [] -> 483 L0; 484 [Z] when Y =< Z -> 485 L0; 486 [Z] when X =< Z -> 487 [X, Z, Y]; 488 [Z] -> 489 [Z, X, Y]; 490 _ when X == Y -> 491 sort_1(Y, L, [X]); 492 _ -> 493 split_1(X, Y, L, [], []) 494 end; 495sort([X, Y | L]) -> 496 case L of 497 [] -> 498 [Y, X]; 499 [Z] when X =< Z -> 500 [Y, X | L]; 501 [Z] when Y =< Z -> 502 [Y, Z, X]; 503 [Z] -> 504 [Z, Y, X]; 505 _ -> 506 split_2(X, Y, L, [], []) 507 end; 508sort([_] = L) -> 509 L; 510sort([] = L) -> 511 L. 512 513sort_1(X, [Y | L], R) when X == Y -> 514 sort_1(Y, L, [X | R]); 515sort_1(X, [Y | L], R) when X < Y -> 516 split_1(X, Y, L, R, []); 517sort_1(X, [Y | L], R) -> 518 split_2(X, Y, L, R, []); 519sort_1(X, [], R) -> 520 lists:reverse(R, [X]). 521 522%% merge(List) -> L 523%% merges a list of sorted lists 524 525-spec merge(ListOfLists) -> List1 when 526 ListOfLists :: [List], 527 List :: [T], 528 List1 :: [T], 529 T :: term(). 530 531merge(L) -> 532 mergel(L, []). 533 534%% merge3(X, Y, Z) -> L 535%% merges three sorted lists X, Y and Z 536 537-spec merge3(List1, List2, List3) -> List4 when 538 List1 :: [X], 539 List2 :: [Y], 540 List3 :: [Z], 541 List4 :: [(X | Y | Z)], 542 X :: term(), 543 Y :: term(), 544 Z :: term(). 545 546merge3(L1, [], L3) -> 547 merge(L1, L3); 548merge3(L1, L2, []) -> 549 merge(L1, L2); 550merge3(L1, [H2 | T2], [H3 | T3]) -> 551 lists:reverse(merge3_1(L1, [], H2, T2, H3, T3), []). 552 553%% rmerge3(X, Y, Z) -> L 554%% merges three reversed sorted lists X, Y and Z 555 556-spec rmerge3([X], [Y], [Z]) -> [(X | Y | Z)]. 557 558rmerge3(L1, [], L3) -> 559 rmerge(L1, L3); 560rmerge3(L1, L2, []) -> 561 rmerge(L1, L2); 562rmerge3(L1, [H2 | T2], [H3 | T3]) -> 563 lists:reverse(rmerge3_1(L1, [], H2, T2, H3, T3), []). 564 565%% merge(X, Y) -> L 566%% merges two sorted lists X and Y 567 568-spec merge(List1, List2) -> List3 when 569 List1 :: [X], 570 List2 :: [Y], 571 List3 :: [(X | Y)], 572 X :: term(), 573 Y :: term(). 574 575merge(T1, []) -> 576 T1; 577merge(T1, [H2 | T2]) -> 578 lists:reverse(merge2_1(T1, H2, T2, []), []). 579 580%% rmerge(X, Y) -> L 581%% merges two reversed sorted lists X and Y 582 583%% reverse(rmerge(reverse(A),reverse(B))) is equal to merge(I,A,B). 584 585-spec rmerge([X], [Y]) -> [(X | Y)]. 586 587rmerge(T1, []) -> 588 T1; 589rmerge(T1, [H2 | T2]) -> 590 lists:reverse(rmerge2_1(T1, H2, T2, []), []). 591 592%% concat(L) concatenate the list representation of the elements 593%% in L - the elements in L can be atoms, numbers of strings. 594%% Returns a list of characters. 595 596-spec concat(Things) -> string() when 597 Things :: [Thing], 598 Thing :: atom() | integer() | float() | string(). 599 600concat(List) -> 601 flatmap(fun thing_to_list/1, List). 602 603thing_to_list(X) when is_integer(X) -> integer_to_list(X); 604thing_to_list(X) when is_float(X) -> float_to_list(X); 605thing_to_list(X) when is_atom(X) -> atom_to_list(X); 606thing_to_list(X) when is_list(X) -> X. %Assumed to be a string 607 608%% flatten(List) 609%% flatten(List, Tail) 610%% Flatten a list, adding optional tail. 611 612-spec flatten(DeepList) -> List when 613 DeepList :: [term() | DeepList], 614 List :: [term()]. 615 616flatten(List) when is_list(List) -> 617 do_flatten(List, []). 618 619-spec flatten(DeepList, Tail) -> List when 620 DeepList :: [term() | DeepList], 621 Tail :: [term()], 622 List :: [term()]. 623 624flatten(List, Tail) when is_list(List), is_list(Tail) -> 625 do_flatten(List, Tail). 626 627do_flatten([H|T], Tail) when is_list(H) -> 628 do_flatten(H, do_flatten(T, Tail)); 629do_flatten([H|T], Tail) -> 630 [H|do_flatten(T, Tail)]; 631do_flatten([], Tail) -> 632 Tail. 633 634%% flatlength(List) 635%% Calculate the length of a list of lists. 636 637-spec flatlength(DeepList) -> non_neg_integer() when 638 DeepList :: [term() | DeepList]. 639 640flatlength(List) -> 641 flatlength(List, 0). 642 643flatlength([H|T], L) when is_list(H) -> 644 flatlength(H, flatlength(T, L)); 645flatlength([_|T], L) -> 646 flatlength(T, L + 1); 647flatlength([], L) -> L. 648 649%% keymember(Key, Index, [Tuple]) Now a BIF! 650%% keyfind(Key, Index, [Tuple]) A BIF! 651%% keysearch(Key, Index, [Tuple]) Now a BIF! 652%% keydelete(Key, Index, [Tuple]) 653%% keyreplace(Key, Index, [Tuple], NewTuple) 654%% keytake(Key, Index, [Tuple]) 655%% keystore(Key, Index, [Tuple], NewTuple) 656%% keysort(Index, [Tuple]) 657%% keymerge(Index, [Tuple], [Tuple]) 658%% ukeysort(Index, [Tuple]) 659%% ukeymerge(Index, [Tuple], [Tuple]) 660%% keymap(Function, Index, [Tuple]) 661%% keymap(Function, ExtraArgs, Index, [Tuple]) 662 663%keymember(K,N,L) when is_integer(N), N > 0 -> 664% keymember3(K,N,L). 665 666%keymember3(Key, N, [T|Ts]) when element(N, T) == Key -> true; 667%keymember3(Key, N, [T|Ts]) -> 668% keymember3(Key, N, Ts); 669%keymember3(Key, N, []) -> false. 670 671%keysearch(K, N, L) when is_integer(N), N > 0 -> 672% keysearch3(K, N, L). 673 674%keysearch3(Key, N, [H|T]) when element(N, H) == Key -> 675% {value, H}; 676%keysearch3(Key, N, [H|T]) -> 677% keysearch3(Key, N, T); 678%keysearch3(Key, N, []) -> false. 679 680-spec keydelete(Key, N, TupleList1) -> TupleList2 when 681 Key :: term(), 682 N :: pos_integer(), 683 TupleList1 :: [Tuple], 684 TupleList2 :: [Tuple], 685 Tuple :: tuple(). 686 687keydelete(K, N, L) when is_integer(N), N > 0 -> 688 keydelete3(K, N, L). 689 690keydelete3(Key, N, [H|T]) when element(N, H) == Key -> T; 691keydelete3(Key, N, [H|T]) -> 692 [H|keydelete3(Key, N, T)]; 693keydelete3(_, _, []) -> []. 694 695-spec keyreplace(Key, N, TupleList1, NewTuple) -> TupleList2 when 696 Key :: term(), 697 N :: pos_integer(), 698 TupleList1 :: [Tuple], 699 TupleList2 :: [Tuple], 700 NewTuple :: Tuple, 701 Tuple :: tuple(). 702 703keyreplace(K, N, L, New) when is_integer(N), N > 0, is_tuple(New) -> 704 keyreplace3(K, N, L, New). 705 706keyreplace3(Key, Pos, [Tup|Tail], New) when element(Pos, Tup) == Key -> 707 [New|Tail]; 708keyreplace3(Key, Pos, [H|T], New) -> 709 [H|keyreplace3(Key, Pos, T, New)]; 710keyreplace3(_, _, [], _) -> []. 711 712-spec keytake(Key, N, TupleList1) -> {value, Tuple, TupleList2} | false when 713 Key :: term(), 714 N :: pos_integer(), 715 TupleList1 :: [tuple()], 716 TupleList2 :: [tuple()], 717 Tuple :: tuple(). 718 719keytake(Key, N, L) when is_integer(N), N > 0 -> 720 keytake(Key, N, L, []). 721 722keytake(Key, N, [H|T], L) when element(N, H) == Key -> 723 {value, H, lists:reverse(L, T)}; 724keytake(Key, N, [H|T], L) -> 725 keytake(Key, N, T, [H|L]); 726keytake(_K, _N, [], _L) -> false. 727 728-spec keystore(Key, N, TupleList1, NewTuple) -> TupleList2 when 729 Key :: term(), 730 N :: pos_integer(), 731 TupleList1 :: [Tuple], 732 TupleList2 :: [Tuple, ...], 733 NewTuple :: Tuple, 734 Tuple :: tuple(). 735 736keystore(K, N, L, New) when is_integer(N), N > 0, is_tuple(New) -> 737 keystore2(K, N, L, New). 738 739keystore2(Key, N, [H|T], New) when element(N, H) == Key -> 740 [New|T]; 741keystore2(Key, N, [H|T], New) -> 742 [H|keystore2(Key, N, T, New)]; 743keystore2(_Key, _N, [], New) -> 744 [New]. 745 746-spec keysort(N, TupleList1) -> TupleList2 when 747 N :: pos_integer(), 748 TupleList1 :: [Tuple], 749 TupleList2 :: [Tuple], 750 Tuple :: tuple(). 751 752keysort(I, L) when is_integer(I), I > 0 -> 753 case L of 754 [] -> L; 755 [_] -> L; 756 [X, Y | T] -> 757 case {element(I, X), element(I, Y)} of 758 {EX, EY} when EX =< EY -> 759 case T of 760 [] -> 761 L; 762 [Z] -> 763 case element(I, Z) of 764 EZ when EY =< EZ -> 765 L; 766 EZ when EX =< EZ -> 767 [X, Z, Y]; 768 _EZ -> 769 [Z, X, Y] 770 end; 771 _ when X == Y -> 772 keysort_1(I, Y, EY, T, [X]); 773 _ -> 774 keysplit_1(I, X, EX, Y, EY, T, [], []) 775 end; 776 {EX, EY} -> 777 case T of 778 [] -> 779 [Y, X]; 780 [Z] -> 781 case element(I, Z) of 782 EZ when EX =< EZ -> 783 [Y, X | T]; 784 EZ when EY =< EZ -> 785 [Y, Z, X]; 786 _EZ -> 787 [Z, Y, X] 788 end; 789 _ -> 790 keysplit_2(I, X, EX, Y, EY, T, [], []) 791 end 792 end 793 end. 794 795keysort_1(I, X, EX, [Y | L], R) when X == Y -> 796 keysort_1(I, Y, EX, L, [X | R]); 797keysort_1(I, X, EX, [Y | L], R) -> 798 case element(I, Y) of 799 EY when EX =< EY -> 800 keysplit_1(I, X, EX, Y, EY, L, R, []); 801 EY -> 802 keysplit_2(I, X, EX, Y, EY, L, R, []) 803 end; 804keysort_1(_I, X, _EX, [], R) -> 805 lists:reverse(R, [X]). 806 807-spec keymerge(N, TupleList1, TupleList2) -> TupleList3 when 808 N :: pos_integer(), 809 TupleList1 :: [T1], 810 TupleList2 :: [T2], 811 TupleList3 :: [(T1 | T2)], 812 T1 :: Tuple, 813 T2 :: Tuple, 814 Tuple :: tuple(). 815 816keymerge(Index, T1, L2) when is_integer(Index), Index > 0 -> 817 case L2 of 818 [] -> 819 T1; 820 [H2 | T2] -> 821 E2 = element(Index, H2), 822 M = keymerge2_1(Index, T1, E2, H2, T2, []), 823 lists:reverse(M, []) 824 end. 825 826%% reverse(rkeymerge(I,reverse(A),reverse(B))) is equal to keymerge(I,A,B). 827 828-spec rkeymerge(pos_integer(), [X], [Y]) -> 829 [R] when X :: tuple(), Y :: tuple(), R :: tuple(). 830 831rkeymerge(Index, T1, L2) when is_integer(Index), Index > 0 -> 832 case L2 of 833 [] -> 834 T1; 835 [H2 | T2] -> 836 E2 = element(Index, H2), 837 M = rkeymerge2_1(Index, T1, E2, H2, T2, []), 838 lists:reverse(M, []) 839 end. 840 841-spec ukeysort(N, TupleList1) -> TupleList2 when 842 N :: pos_integer(), 843 TupleList1 :: [Tuple], 844 TupleList2 :: [Tuple], 845 Tuple :: tuple(). 846 847ukeysort(I, L) when is_integer(I), I > 0 -> 848 case L of 849 [] -> L; 850 [_] -> L; 851 [X, Y | T] -> 852 case {element(I, X), element(I, Y)} of 853 {EX, EY} when EX == EY -> 854 ukeysort_1(I, X, EX, T); 855 {EX, EY} when EX < EY -> 856 case T of 857 [] -> 858 L; 859 [Z] -> 860 case element(I, Z) of 861 EZ when EY == EZ -> 862 [X, Y]; 863 EZ when EY < EZ -> 864 [X, Y, Z]; 865 EZ when EZ == EX -> 866 [X, Y]; 867 EZ when EX =< EZ -> 868 [X, Z, Y]; 869 _EZ -> 870 [Z, X, Y] 871 end; 872 _ -> 873 ukeysplit_1(I, X, EX, Y, EY, T, [], []) 874 end; 875 {EX, EY} -> 876 case T of 877 [] -> 878 [Y, X]; 879 [Z] -> 880 case element(I, Z) of 881 EZ when EX == EZ -> 882 [Y, X]; 883 EZ when EX < EZ -> 884 [Y, X, Z]; 885 EZ when EY == EZ -> 886 [Y, X]; 887 EZ when EY =< EZ -> 888 [Y, Z, X]; 889 _EZ -> 890 [Z, Y, X] 891 end; 892 _ -> 893 ukeysplit_2(I, Y, EY, T, [X]) 894 end 895 end 896 end. 897 898ukeysort_1(I, X, EX, [Y | L]) -> 899 case element(I, Y) of 900 EY when EX == EY -> 901 ukeysort_1(I, X, EX, L); 902 EY when EX < EY -> 903 ukeysplit_1(I, X, EX, Y, EY, L, [], []); 904 EY -> 905 ukeysplit_2(I, Y, EY, L, [X]) 906 end; 907ukeysort_1(_I, X, _EX, []) -> 908 [X]. 909 910-spec ukeymerge(N, TupleList1, TupleList2) -> TupleList3 when 911 N :: pos_integer(), 912 TupleList1 :: [T1], 913 TupleList2 :: [T2], 914 TupleList3 :: [(T1 | T2)], 915 T1 :: Tuple, 916 T2 :: Tuple, 917 Tuple :: tuple(). 918 919ukeymerge(Index, L1, T2) when is_integer(Index), Index > 0 -> 920 case L1 of 921 [] -> 922 T2; 923 [H1 | T1] -> 924 E1 = element(Index, H1), 925 M = ukeymerge2_2(Index, T1, E1, H1, T2, []), 926 lists:reverse(M, []) 927 end. 928 929%% reverse(rukeymerge(I,reverse(A),reverse(B))) is equal to ukeymerge(I,A,B). 930 931-spec rukeymerge(pos_integer(), [X], [Y]) -> 932 [(X | Y)] when X :: tuple(), Y :: tuple(). 933 934rukeymerge(Index, T1, L2) when is_integer(Index), Index > 0 -> 935 case L2 of 936 [] -> 937 T1; 938 [H2 | T2] -> 939 E2 = element(Index, H2), 940 M = rukeymerge2_1(Index, T1, E2, T2, [], H2), 941 lists:reverse(M, []) 942 end. 943 944-spec keymap(Fun, N, TupleList1) -> TupleList2 when 945 Fun :: fun((Term1 :: term()) -> Term2 :: term()), 946 N :: pos_integer(), 947 TupleList1 :: [Tuple], 948 TupleList2 :: [Tuple], 949 Tuple :: tuple(). 950 951keymap(Fun, Index, [Tup|Tail]) -> 952 [setelement(Index, Tup, Fun(element(Index, Tup)))|keymap(Fun, Index, Tail)]; 953keymap(Fun, Index, []) when is_integer(Index), Index >= 1, 954 is_function(Fun, 1) -> []. 955 956%%% Suggestion from OTP-2948: sort and merge with Fun. 957 958-spec sort(Fun, List1) -> List2 when 959 Fun :: fun((A :: T, B :: T) -> boolean()), 960 List1 :: [T], 961 List2 :: [T], 962 T :: term(). 963 964sort(Fun, []) when is_function(Fun, 2) -> 965 []; 966sort(Fun, [_] = L) when is_function(Fun, 2) -> 967 L; 968sort(Fun, [X, Y | T]) -> 969 case Fun(X, Y) of 970 true -> 971 fsplit_1(Y, X, Fun, T, [], []); 972 false -> 973 fsplit_2(Y, X, Fun, T, [], []) 974 end. 975 976-spec merge(Fun, List1, List2) -> List3 when 977 Fun :: fun((A, B) -> boolean()), 978 List1 :: [A], 979 List2 :: [B], 980 List3 :: [(A | B)], 981 A :: term(), 982 B :: term(). 983 984merge(Fun, T1, [H2 | T2]) when is_function(Fun, 2) -> 985 lists:reverse(fmerge2_1(T1, H2, Fun, T2, []), []); 986merge(Fun, T1, []) when is_function(Fun, 2) -> 987 T1. 988 989%% reverse(rmerge(F,reverse(A),reverse(B))) is equal to merge(F,A,B). 990 991-spec rmerge(fun((X, Y) -> boolean()), [X], [Y]) -> [(X | Y)]. 992 993rmerge(Fun, T1, [H2 | T2]) when is_function(Fun, 2) -> 994 lists:reverse(rfmerge2_1(T1, H2, Fun, T2, []), []); 995rmerge(Fun, T1, []) when is_function(Fun, 2) -> 996 T1. 997 998-spec usort(Fun, List1) -> List2 when 999 Fun :: fun((T, T) -> boolean()), 1000 List1 :: [T], 1001 List2 :: [T], 1002 T :: term(). 1003 1004usort(Fun, [_] = L) when is_function(Fun, 2) -> 1005 L; 1006usort(Fun, [] = L) when is_function(Fun, 2) -> 1007 L; 1008usort(Fun, [X | L]) when is_function(Fun, 2) -> 1009 usort_1(Fun, X, L). 1010 1011usort_1(Fun, X, [Y | L]) -> 1012 case Fun(X, Y) of 1013 true -> 1014 case Fun(Y, X) of 1015 true -> % X equal to Y 1016 case L of 1017 [] -> 1018 [X]; 1019 _ -> 1020 usort_1(Fun, X, L) 1021 end; 1022 false -> 1023 ufsplit_1(Y, X, Fun, L, [], []) 1024 end; 1025 false -> 1026 ufsplit_2(Y, L, Fun, [X]) 1027 end. 1028 1029-spec umerge(Fun, List1, List2) -> List3 when 1030 Fun :: fun((A, B) -> boolean()), 1031 List1 :: [A], 1032 List2 :: [B], 1033 List3 :: [(A | B)], 1034 A :: term(), 1035 B :: term(). 1036 1037umerge(Fun, [], T2) when is_function(Fun, 2) -> 1038 T2; 1039umerge(Fun, [H1 | T1], T2) when is_function(Fun, 2) -> 1040 lists:reverse(ufmerge2_2(H1, T1, Fun, T2, []), []). 1041 1042%% reverse(rumerge(F,reverse(A),reverse(B))) is equal to umerge(F,A,B). 1043 1044-spec rumerge(fun((X, Y) -> boolean()), [X], [Y]) -> [(X | Y)]. 1045 1046rumerge(Fun, T1, []) when is_function(Fun, 2) -> 1047 T1; 1048rumerge(Fun, T1, [H2 | T2]) when is_function(Fun, 2) -> 1049 lists:reverse(rufmerge2_1(T1, H2, Fun, T2, []), []). 1050 1051%% usort(List) -> L 1052%% sorts the list L, removes duplicates 1053 1054-spec usort(List1) -> List2 when 1055 List1 :: [T], 1056 List2 :: [T], 1057 T :: term(). 1058 1059usort([X, Y | L] = L0) when X < Y -> 1060 case L of 1061 [] -> 1062 L0; 1063 [Z] when Y < Z -> 1064 L0; 1065 [Z] when Y == Z -> 1066 [X, Y]; 1067 [Z] when Z < X -> 1068 [Z, X, Y]; 1069 [Z] when Z == X -> 1070 [X, Y]; 1071 [Z] -> 1072 [X, Z, Y]; 1073 _ -> 1074 usplit_1(X, Y, L, [], []) 1075 end; 1076usort([X, Y | L]) when X > Y -> 1077 case L of 1078 [] -> 1079 [Y, X]; 1080 [Z] when X < Z -> 1081 [Y, X | L]; 1082 [Z] when X == Z -> 1083 [Y, X]; 1084 [Z] when Z < Y -> 1085 [Z, Y, X]; 1086 [Z] when Z == Y -> 1087 [Y, X]; 1088 [Z] -> 1089 [Y, Z, X]; 1090 _ -> 1091 usplit_2(X, Y, L, [], []) 1092 end; 1093usort([X, _Y | L]) -> 1094 usort_1(X, L); 1095usort([_] = L) -> 1096 L; 1097usort([]) -> 1098 []. 1099 1100usort_1(X, [Y | L]) when X == Y -> 1101 usort_1(X, L); 1102usort_1(X, [Y | L]) when X < Y -> 1103 usplit_1(X, Y, L, [], []); 1104usort_1(X, [Y | L]) -> 1105 usplit_2(X, Y, L, [], []); 1106usort_1(X, []) -> 1107 [X]. 1108 1109%% umerge(List) -> L 1110%% merges a list of sorted lists without duplicates, removes duplicates 1111 1112-spec umerge(ListOfLists) -> List1 when 1113 ListOfLists :: [List], 1114 List :: [T], 1115 List1 :: [T], 1116 T :: term(). 1117 1118umerge(L) -> 1119 umergel(L). 1120 1121%% umerge3(X, Y, Z) -> L 1122%% merges three sorted lists X, Y and Z without duplicates, 1123%% removes duplicates 1124 1125-spec umerge3(List1, List2, List3) -> List4 when 1126 List1 :: [X], 1127 List2 :: [Y], 1128 List3 :: [Z], 1129 List4 :: [(X | Y | Z)], 1130 X :: term(), 1131 Y :: term(), 1132 Z :: term(). 1133 1134umerge3(L1, [], L3) -> 1135 umerge(L1, L3); 1136umerge3(L1, L2, []) -> 1137 umerge(L1, L2); 1138umerge3(L1, [H2 | T2], [H3 | T3]) -> 1139 lists:reverse(umerge3_1(L1, [H2 | H3], T2, H2, [], T3, H3), []). 1140 1141%% rumerge3(X, Y, Z) -> L 1142%% merges three reversed sorted lists X, Y and Z without duplicates, 1143%% removes duplicates 1144 1145-spec rumerge3([X], [Y], [Z]) -> [(X | Y | Z)]. 1146 1147rumerge3(L1, [], L3) -> 1148 rumerge(L1, L3); 1149rumerge3(L1, L2, []) -> 1150 rumerge(L1, L2); 1151rumerge3(L1, [H2 | T2], [H3 | T3]) -> 1152 lists:reverse(rumerge3_1(L1, T2, H2, [], T3, H3),[]). 1153 1154%% umerge(X, Y) -> L 1155%% merges two sorted lists X and Y without duplicates, removes duplicates 1156 1157-spec umerge(List1, List2) -> List3 when 1158 List1 :: [X], 1159 List2 :: [Y], 1160 List3 :: [(X | Y)], 1161 X :: term(), 1162 Y :: term(). 1163 1164umerge([], T2) -> 1165 T2; 1166umerge([H1 | T1], T2) -> 1167 lists:reverse(umerge2_2(T1, T2, [], H1), []). 1168 1169%% rumerge(X, Y) -> L 1170%% merges two reversed sorted lists X and Y without duplicates, 1171%% removes duplicates 1172 1173%% reverse(rumerge(reverse(A),reverse(B))) is equal to umerge(I,A,B). 1174 1175-spec rumerge([X], [Y]) -> [(X | Y)]. 1176 1177rumerge(T1, []) -> 1178 T1; 1179rumerge(T1, [H2 | T2]) -> 1180 lists:reverse(rumerge2_1(T1, T2, [], H2), []). 1181 1182%% all(Predicate, List) 1183%% any(Predicate, List) 1184%% map(Function, List) 1185%% flatmap(Function, List) 1186%% foldl(Function, First, List) 1187%% foldr(Function, Last, List) 1188%% filter(Predicate, List) 1189%% zf(Function, List) 1190%% mapfoldl(Function, First, List) 1191%% mapfoldr(Function, Last, List) 1192%% foreach(Function, List) 1193%% takewhile(Predicate, List) 1194%% dropwhile(Predicate, List) 1195%% splitwith(Predicate, List) 1196%% for list programming. Function here is a 'fun'. 1197%% 1198%% The name zf is a joke! 1199%% 1200%% N.B. Unless where the functions actually needs it only foreach/2/3, 1201%% which is meant to be used for its side effects, has a defined order 1202%% of evaluation. 1203%% 1204%% There are also versions with an extra argument, ExtraArgs, which is a 1205%% list of extra arguments to each call. 1206 1207-spec all(Pred, List) -> boolean() when 1208 Pred :: fun((Elem :: T) -> boolean()), 1209 List :: [T], 1210 T :: term(). 1211 1212all(Pred, [Hd|Tail]) -> 1213 case Pred(Hd) of 1214 true -> all(Pred, Tail); 1215 false -> false 1216 end; 1217all(Pred, []) when is_function(Pred, 1) -> true. 1218 1219-spec any(Pred, List) -> boolean() when 1220 Pred :: fun((Elem :: T) -> boolean()), 1221 List :: [T], 1222 T :: term(). 1223 1224any(Pred, [Hd|Tail]) -> 1225 case Pred(Hd) of 1226 true -> true; 1227 false -> any(Pred, Tail) 1228 end; 1229any(Pred, []) when is_function(Pred, 1) -> false. 1230 1231-spec map(Fun, List1) -> List2 when 1232 Fun :: fun((A) -> B), 1233 List1 :: [A], 1234 List2 :: [B], 1235 A :: term(), 1236 B :: term(). 1237 1238map(F, [H|T]) -> 1239 [F(H)|map(F, T)]; 1240map(F, []) when is_function(F, 1) -> []. 1241 1242-spec flatmap(Fun, List1) -> List2 when 1243 Fun :: fun((A) -> [B]), 1244 List1 :: [A], 1245 List2 :: [B], 1246 A :: term(), 1247 B :: term(). 1248 1249flatmap(F, [Hd|Tail]) -> 1250 F(Hd) ++ flatmap(F, Tail); 1251flatmap(F, []) when is_function(F, 1) -> []. 1252 1253-spec foldl(Fun, Acc0, List) -> Acc1 when 1254 Fun :: fun((Elem :: T, AccIn) -> AccOut), 1255 Acc0 :: term(), 1256 Acc1 :: term(), 1257 AccIn :: term(), 1258 AccOut :: term(), 1259 List :: [T], 1260 T :: term(). 1261 1262foldl(F, Accu, [Hd|Tail]) -> 1263 foldl(F, F(Hd, Accu), Tail); 1264foldl(F, Accu, []) when is_function(F, 2) -> Accu. 1265 1266-spec foldr(Fun, Acc0, List) -> Acc1 when 1267 Fun :: fun((Elem :: T, AccIn) -> AccOut), 1268 Acc0 :: term(), 1269 Acc1 :: term(), 1270 AccIn :: term(), 1271 AccOut :: term(), 1272 List :: [T], 1273 T :: term(). 1274 1275foldr(F, Accu, [Hd|Tail]) -> 1276 F(Hd, foldr(F, Accu, Tail)); 1277foldr(F, Accu, []) when is_function(F, 2) -> Accu. 1278 1279-spec filter(Pred, List1) -> List2 when 1280 Pred :: fun((Elem :: T) -> boolean()), 1281 List1 :: [T], 1282 List2 :: [T], 1283 T :: term(). 1284 1285filter(Pred, List) when is_function(Pred, 1) -> 1286 [ E || E <- List, Pred(E) ]. 1287 1288%% Equivalent to {filter(F, L), filter(NotF, L)}, if NotF = 'fun(X) -> 1289%% not F(X) end'. 1290 1291-spec partition(Pred, List) -> {Satisfying, NotSatisfying} when 1292 Pred :: fun((Elem :: T) -> boolean()), 1293 List :: [T], 1294 Satisfying :: [T], 1295 NotSatisfying :: [T], 1296 T :: term(). 1297 1298partition(Pred, L) -> 1299 partition(Pred, L, [], []). 1300 1301partition(Pred, [H | T], As, Bs) -> 1302 case Pred(H) of 1303 true -> partition(Pred, T, [H | As], Bs); 1304 false -> partition(Pred, T, As, [H | Bs]) 1305 end; 1306partition(Pred, [], As, Bs) when is_function(Pred, 1) -> 1307 {reverse(As), reverse(Bs)}. 1308 1309-spec filtermap(Fun, List1) -> List2 when 1310 Fun :: fun((Elem) -> boolean() | {'true', Value}), 1311 List1 :: [Elem], 1312 List2 :: [Elem | Value], 1313 Elem :: term(), 1314 Value :: term(). 1315 1316filtermap(F, [Hd|Tail]) -> 1317 case F(Hd) of 1318 true -> 1319 [Hd|filtermap(F, Tail)]; 1320 {true,Val} -> 1321 [Val|filtermap(F, Tail)]; 1322 false -> 1323 filtermap(F, Tail) 1324 end; 1325filtermap(F, []) when is_function(F, 1) -> []. 1326 1327-spec zf(fun((T) -> boolean() | {'true', X}), [T]) -> [(T | X)]. 1328 1329zf(F, L) -> 1330 filtermap(F, L). 1331 1332-spec foreach(Fun, List) -> ok when 1333 Fun :: fun((Elem :: T) -> term()), 1334 List :: [T], 1335 T :: term(). 1336 1337foreach(F, [Hd|Tail]) -> 1338 F(Hd), 1339 foreach(F, Tail); 1340foreach(F, []) when is_function(F, 1) -> ok. 1341 1342-spec mapfoldl(Fun, Acc0, List1) -> {List2, Acc1} when 1343 Fun :: fun((A, AccIn) -> {B, AccOut}), 1344 Acc0 :: term(), 1345 Acc1 :: term(), 1346 AccIn :: term(), 1347 AccOut :: term(), 1348 List1 :: [A], 1349 List2 :: [B], 1350 A :: term(), 1351 B :: term(). 1352 1353mapfoldl(F, Accu0, [Hd|Tail]) -> 1354 {R,Accu1} = F(Hd, Accu0), 1355 {Rs,Accu2} = mapfoldl(F, Accu1, Tail), 1356 {[R|Rs],Accu2}; 1357mapfoldl(F, Accu, []) when is_function(F, 2) -> {[],Accu}. 1358 1359-spec mapfoldr(Fun, Acc0, List1) -> {List2, Acc1} when 1360 Fun :: fun((A, AccIn) -> {B, AccOut}), 1361 Acc0 :: term(), 1362 Acc1 :: term(), 1363 AccIn :: term(), 1364 AccOut :: term(), 1365 List1 :: [A], 1366 List2 :: [B], 1367 A :: term(), 1368 B :: term(). 1369 1370mapfoldr(F, Accu0, [Hd|Tail]) -> 1371 {Rs,Accu1} = mapfoldr(F, Accu0, Tail), 1372 {R,Accu2} = F(Hd, Accu1), 1373 {[R|Rs],Accu2}; 1374mapfoldr(F, Accu, []) when is_function(F, 2) -> {[],Accu}. 1375 1376-spec takewhile(Pred, List1) -> List2 when 1377 Pred :: fun((Elem :: T) -> boolean()), 1378 List1 :: [T], 1379 List2 :: [T], 1380 T :: term(). 1381 1382takewhile(Pred, [Hd|Tail]) -> 1383 case Pred(Hd) of 1384 true -> [Hd|takewhile(Pred, Tail)]; 1385 false -> [] 1386 end; 1387takewhile(Pred, []) when is_function(Pred, 1) -> []. 1388 1389-spec dropwhile(Pred, List1) -> List2 when 1390 Pred :: fun((Elem :: T) -> boolean()), 1391 List1 :: [T], 1392 List2 :: [T], 1393 T :: term(). 1394 1395dropwhile(Pred, [Hd|Tail]=Rest) -> 1396 case Pred(Hd) of 1397 true -> dropwhile(Pred, Tail); 1398 false -> Rest 1399 end; 1400dropwhile(Pred, []) when is_function(Pred, 1) -> []. 1401 1402-spec search(Pred, List) -> {value, Value} | false when 1403 Pred :: fun((T) -> boolean()), 1404 List :: [T], 1405 Value :: T. 1406 1407search(Pred, [Hd|Tail]) -> 1408 case Pred(Hd) of 1409 true -> {value, Hd}; 1410 false -> search(Pred, Tail) 1411 end; 1412search(Pred, []) when is_function(Pred, 1) -> 1413 false. 1414 1415-spec splitwith(Pred, List) -> {List1, List2} when 1416 Pred :: fun((T) -> boolean()), 1417 List :: [T], 1418 List1 :: [T], 1419 List2 :: [T], 1420 T :: term(). 1421 1422splitwith(Pred, List) when is_function(Pred, 1) -> 1423 splitwith(Pred, List, []). 1424 1425splitwith(Pred, [Hd|Tail], Taken) -> 1426 case Pred(Hd) of 1427 true -> splitwith(Pred, Tail, [Hd|Taken]); 1428 false -> {reverse(Taken), [Hd|Tail]} 1429 end; 1430splitwith(Pred, [], Taken) when is_function(Pred, 1) -> 1431 {reverse(Taken),[]}. 1432 1433-spec split(N, List1) -> {List2, List3} when 1434 N :: non_neg_integer(), 1435 List1 :: [T], 1436 List2 :: [T], 1437 List3 :: [T], 1438 T :: term(). 1439 1440split(N, List) when is_integer(N), N >= 0, is_list(List) -> 1441 case split(N, List, []) of 1442 {_, _} = Result -> Result; 1443 Fault when is_atom(Fault) -> 1444 erlang:error(Fault, [N,List]) 1445 end; 1446split(N, List) -> 1447 erlang:error(badarg, [N,List]). 1448 1449split(0, L, R) -> 1450 {lists:reverse(R, []), L}; 1451split(N, [H|T], R) -> 1452 split(N-1, T, [H|R]); 1453split(_, [], _) -> 1454 badarg. 1455 1456-spec join(Sep, List1) -> List2 when 1457 Sep :: T, 1458 List1 :: [T], 1459 List2 :: [T], 1460 T :: term(). 1461 1462join(_Sep, []) -> []; 1463join(Sep, [H|T]) -> [H|join_prepend(Sep, T)]. 1464 1465join_prepend(_Sep, []) -> []; 1466join_prepend(Sep, [H|T]) -> [Sep,H|join_prepend(Sep,T)]. 1467 1468%%% ================================================================= 1469%%% Here follows the implementation of the sort functions. 1470%%% 1471%%% These functions used to be in their own module (lists_sort), 1472%%% but have now been placed here to allow Dialyzer to produce better 1473%%% type information. 1474%%% ================================================================= 1475 1476-compile({inline, 1477 [{merge3_12,7}, {merge3_21,7}, {rmerge3_12,7}, {rmerge3_21,7}]}). 1478 1479-compile({inline, 1480 [{umerge3_12,8}, {umerge3_21,8}, 1481 {rumerge3_12a,7}, {rumerge3_12b,8}]}). 1482 1483-compile({inline, 1484 [{keymerge3_12,12}, {keymerge3_21,12}, 1485 {rkeymerge3_12,12}, {rkeymerge3_21,12}]}). 1486 1487-compile({inline, 1488 [{ukeymerge3_12,13}, {ukeymerge3_21,13}, 1489 {rukeymerge3_12a,11}, {rukeymerge3_21a,13}, 1490 {rukeymerge3_12b,12}, {rukeymerge3_21b,12}]}). 1491 1492%% sort/1 1493 1494%% Ascending. 1495split_1(X, Y, [Z | L], R, Rs) when Z >= Y -> 1496 split_1(Y, Z, L, [X | R], Rs); 1497split_1(X, Y, [Z | L], R, Rs) when Z >= X -> 1498 split_1(Z, Y, L, [X | R], Rs); 1499split_1(X, Y, [Z | L], [], Rs) -> 1500 split_1(X, Y, L, [Z], Rs); 1501split_1(X, Y, [Z | L], R, Rs) -> 1502 split_1_1(X, Y, L, R, Rs, Z); 1503split_1(X, Y, [], R, Rs) -> 1504 rmergel([[Y, X | R] | Rs], []). 1505 1506split_1_1(X, Y, [Z | L], R, Rs, S) when Z >= Y -> 1507 split_1_1(Y, Z, L, [X | R], Rs, S); 1508split_1_1(X, Y, [Z | L], R, Rs, S) when Z >= X -> 1509 split_1_1(Z, Y, L, [X | R], Rs, S); 1510split_1_1(X, Y, [Z | L], R, Rs, S) when S =< Z -> 1511 split_1(S, Z, L, [], [[Y, X | R] | Rs]); 1512split_1_1(X, Y, [Z | L], R, Rs, S) -> 1513 split_1(Z, S, L, [], [[Y, X | R] | Rs]); 1514split_1_1(X, Y, [], R, Rs, S) -> 1515 rmergel([[S], [Y, X | R] | Rs], []). 1516 1517%% Descending. 1518split_2(X, Y, [Z | L], R, Rs) when Z =< Y -> 1519 split_2(Y, Z, L, [X | R], Rs); 1520split_2(X, Y, [Z | L], R, Rs) when Z =< X -> 1521 split_2(Z, Y, L, [X | R], Rs); 1522split_2(X, Y, [Z | L], [], Rs) -> 1523 split_2(X, Y, L, [Z], Rs); 1524split_2(X, Y, [Z | L], R, Rs) -> 1525 split_2_1(X, Y, L, R, Rs, Z); 1526split_2(X, Y, [], R, Rs) -> 1527 mergel([[Y, X | R] | Rs], []). 1528 1529split_2_1(X, Y, [Z | L], R, Rs, S) when Z =< Y -> 1530 split_2_1(Y, Z, L, [X | R], Rs, S); 1531split_2_1(X, Y, [Z | L], R, Rs, S) when Z =< X -> 1532 split_2_1(Z, Y, L, [X | R], Rs, S); 1533split_2_1(X, Y, [Z | L], R, Rs, S) when S > Z -> 1534 split_2(S, Z, L, [], [[Y, X | R] | Rs]); 1535split_2_1(X, Y, [Z | L], R, Rs, S) -> 1536 split_2(Z, S, L, [], [[Y, X | R] | Rs]); 1537split_2_1(X, Y, [], R, Rs, S) -> 1538 mergel([[S], [Y, X | R] | Rs], []). 1539 1540%% merge/1 1541 1542mergel([[] | L], Acc) -> 1543 mergel(L, Acc); 1544mergel([T1, [H2 | T2], [H3 | T3] | L], Acc) -> 1545 mergel(L, [merge3_1(T1, [], H2, T2, H3, T3) | Acc]); 1546mergel([T1, [H2 | T2]], Acc) -> 1547 rmergel([merge2_1(T1, H2, T2, []) | Acc], []); 1548mergel([L], []) -> 1549 L; 1550mergel([L], Acc) -> 1551 rmergel([lists:reverse(L, []) | Acc], []); 1552mergel([], []) -> 1553 []; 1554mergel([], Acc) -> 1555 rmergel(Acc, []); 1556mergel([A, [] | L], Acc) -> 1557 mergel([A | L], Acc); 1558mergel([A, B, [] | L], Acc) -> 1559 mergel([A, B | L], Acc). 1560 1561rmergel([[H3 | T3], [H2 | T2], T1 | L], Acc) -> 1562 rmergel(L, [rmerge3_1(T1, [], H2, T2, H3, T3) | Acc]); 1563rmergel([[H2 | T2], T1], Acc) -> 1564 mergel([rmerge2_1(T1, H2, T2, []) | Acc], []); 1565rmergel([L], Acc) -> 1566 mergel([lists:reverse(L, []) | Acc], []); 1567rmergel([], Acc) -> 1568 mergel(Acc, []). 1569 1570%% merge3/3 1571 1572%% Take L1 apart. 1573merge3_1([H1 | T1], M, H2, T2, H3, T3) when H1 =< H2 -> 1574 merge3_12(T1, H1, H2, T2, H3, T3, M); 1575merge3_1([H1 | T1], M, H2, T2, H3, T3) -> 1576 merge3_21(T1, H1, H2, T2, H3, T3, M); 1577merge3_1([], M, H2, T2, H3, T3) when H2 =< H3 -> 1578 merge2_1(T2, H3, T3, [H2 | M]); 1579merge3_1([], M, H2, T2, H3, T3) -> 1580 merge2_2(T2, H3, T3, M, H2). 1581 1582%% Take L2 apart. 1583merge3_2(T1, H1, M, [H2 | T2], H3, T3) when H1 =< H2 -> 1584 merge3_12(T1, H1, H2, T2, H3, T3, M); 1585merge3_2(T1, H1, M, [H2 | T2], H3, T3) -> 1586 merge3_21(T1, H1, H2, T2, H3, T3, M); 1587merge3_2(T1, H1, M, [], H3, T3) when H1 =< H3 -> 1588 merge2_1(T1, H3, T3, [H1 | M]); 1589merge3_2(T1, H1, M, [], H3, T3) -> 1590 merge2_2(T1, H3, T3, M, H1). 1591 1592% H1 =< H2. Inlined. 1593merge3_12(T1, H1, H2, T2, H3, T3, M) when H1 =< H3 -> 1594 merge3_1(T1, [H1 | M], H2, T2, H3, T3); 1595merge3_12(T1, H1, H2, T2, H3, T3, M) -> 1596 merge3_12_3(T1, H1, H2, T2, [H3 | M], T3). 1597 1598% H1 =< H2, take L3 apart. 1599merge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) when H1 =< H3 -> 1600 merge3_1(T1, [H1 | M], H2, T2, H3, T3); 1601merge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) -> 1602 merge3_12_3(T1, H1, H2, T2, [H3 | M], T3); 1603merge3_12_3(T1, H1, H2, T2, M, []) -> 1604 merge2_1(T1, H2, T2, [H1 | M]). 1605 1606% H1 > H2. Inlined. 1607merge3_21(T1, H1, H2, T2, H3, T3, M) when H2 =< H3 -> 1608 merge3_2(T1, H1, [H2 | M], T2, H3, T3); 1609merge3_21(T1, H1, H2, T2, H3, T3, M) -> 1610 merge3_21_3(T1, H1, H2, T2, [H3 | M], T3). 1611 1612% H1 > H2, take L3 apart. 1613merge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) when H2 =< H3 -> 1614 merge3_2(T1, H1, [H2 | M], T2, H3, T3); 1615merge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) -> 1616 merge3_21_3(T1, H1, H2, T2, [H3 | M], T3); 1617merge3_21_3(T1, H1, H2, T2, M, []) -> 1618 merge2_2(T1, H2, T2, M, H1). 1619 1620%% rmerge/3 1621 1622%% Take L1 apart. 1623rmerge3_1([H1 | T1], M, H2, T2, H3, T3) when H1 =< H2 -> 1624 rmerge3_12(T1, H1, H2, T2, H3, T3, M); 1625rmerge3_1([H1 | T1], M, H2, T2, H3, T3) -> 1626 rmerge3_21(T1, H1, H2, T2, H3, T3, M); 1627rmerge3_1([], M, H2, T2, H3, T3) when H2 =< H3 -> 1628 rmerge2_2(T2, H3, T3, M, H2); 1629rmerge3_1([], M, H2, T2, H3, T3) -> 1630 rmerge2_1(T2, H3, T3, [H2 | M]). 1631 1632%% Take L2 apart. 1633rmerge3_2(T1, H1, M, [H2 | T2], H3, T3) when H1 =< H2 -> 1634 rmerge3_12(T1, H1, H2, T2, H3, T3, M); 1635rmerge3_2(T1, H1, M, [H2 | T2], H3, T3) -> 1636 rmerge3_21(T1, H1, H2, T2, H3, T3, M); 1637rmerge3_2(T1, H1, M, [], H3, T3) when H1 =< H3 -> 1638 rmerge2_2(T1, H3, T3, M, H1); 1639rmerge3_2(T1, H1, M, [], H3, T3) -> 1640 rmerge2_1(T1, H3, T3, [H1 | M]). 1641 1642% H1 =< H2. Inlined. 1643rmerge3_12(T1, H1, H2, T2, H3, T3, M) when H2 =< H3 -> 1644 rmerge3_12_3(T1, H1, H2, T2, [H3 | M], T3); 1645rmerge3_12(T1, H1, H2, T2, H3, T3, M) -> 1646 rmerge3_2(T1, H1, [H2 | M], T2, H3, T3). 1647 1648% H1 =< H2, take L3 apart. 1649rmerge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) when H2 =< H3 -> 1650 rmerge3_12_3(T1, H1, H2, T2, [H3 | M], T3); 1651rmerge3_12_3(T1, H1, H2, T2, M, [H3 | T3]) -> 1652 rmerge3_2(T1, H1, [H2 | M], T2, H3, T3); 1653rmerge3_12_3(T1, H1, H2, T2, M, []) -> 1654 rmerge2_2(T1, H2, T2, M, H1). 1655 1656% H1 > H2. Inlined. 1657rmerge3_21(T1, H1, H2, T2, H3, T3, M) when H1 =< H3 -> 1658 rmerge3_21_3(T1, H1, H2, T2, [H3 | M], T3); 1659rmerge3_21(T1, H1, H2, T2, H3, T3, M) -> 1660 rmerge3_1(T1, [H1 | M], H2, T2, H3, T3). 1661 1662% H1 > H2, take L3 apart. 1663rmerge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) when H1 =< H3 -> 1664 rmerge3_21_3(T1, H1, H2, T2, [H3 | M], T3); 1665rmerge3_21_3(T1, H1, H2, T2, M, [H3 | T3]) -> 1666 rmerge3_1(T1, [H1 | M], H2, T2, H3, T3); 1667rmerge3_21_3(T1, H1, H2, T2, M, []) -> 1668 rmerge2_1(T1, H2, T2, [H1 | M]). 1669 1670%% merge/2 1671 1672merge2_1([H1 | T1], H2, T2, M) when H1 =< H2 -> 1673 merge2_1(T1, H2, T2, [H1 | M]); 1674merge2_1([H1 | T1], H2, T2, M) -> 1675 merge2_2(T1, H2, T2, M, H1); 1676merge2_1([], H2, T2, M) -> 1677 lists:reverse(T2, [H2 | M]). 1678 1679merge2_2(T1, HdM, [H2 | T2], M, H1) when H1 =< H2 -> 1680 merge2_1(T1, H2, T2, [H1, HdM | M]); 1681merge2_2(T1, HdM, [H2 | T2], M, H1) -> 1682 merge2_2(T1, H2, T2, [HdM | M], H1); 1683merge2_2(T1, HdM, [], M, H1) -> 1684 lists:reverse(T1, [H1, HdM | M]). 1685 1686%% rmerge/2 1687 1688rmerge2_1([H1 | T1], H2, T2, M) when H1 =< H2 -> 1689 rmerge2_2(T1, H2, T2, M, H1); 1690rmerge2_1([H1 | T1], H2, T2, M) -> 1691 rmerge2_1(T1, H2, T2, [H1 | M]); 1692rmerge2_1([], H2, T2, M) -> 1693 lists:reverse(T2, [H2 | M]). 1694 1695rmerge2_2(T1, HdM, [H2 | T2], M, H1) when H1 =< H2 -> 1696 rmerge2_2(T1, H2, T2, [HdM | M], H1); 1697rmerge2_2(T1, HdM, [H2 | T2], M, H1) -> 1698 rmerge2_1(T1, H2, T2, [H1, HdM | M]); 1699rmerge2_2(T1, HdM, [], M, H1) -> 1700 lists:reverse(T1, [H1, HdM | M]). 1701 1702%% usort/1 1703 1704%% Ascending. 1705usplit_1(X, Y, [Z | L], R, Rs) when Z > Y -> 1706 usplit_1(Y, Z, L, [X | R], Rs); 1707usplit_1(X, Y, [Z | L], R, Rs) when Z == Y -> 1708 usplit_1(X, Y, L, R, Rs); 1709usplit_1(X, Y, [Z | L], R, Rs) when Z > X -> 1710 usplit_1(Z, Y, L, [X | R], Rs); 1711usplit_1(X, Y, [Z | L], R, Rs) when Z == X -> 1712 usplit_1(X, Y, L, R, Rs); 1713usplit_1(X, Y, [Z | L], [], Rs) -> 1714 usplit_1(X, Y, L, [Z], Rs); 1715usplit_1(X, Y, [Z | L], R, Rs) -> 1716 usplit_1_1(X, Y, L, R, Rs, Z); 1717usplit_1(X, Y, [], R, Rs) -> 1718 rumergel([[Y, X | R] | Rs], [], asc). 1719 1720usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z > Y -> 1721 usplit_1_1(Y, Z, L, [X | R], Rs, S); 1722usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z == Y -> 1723 usplit_1_1(X, Y, L, R, Rs, S); 1724usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z > X -> 1725 usplit_1_1(Z, Y, L, [X | R], Rs, S); 1726usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z == X -> 1727 usplit_1_1(X, Y, L, R, Rs, S); 1728usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z > S -> 1729 usplit_1(S, Z, L, [], [[Y, X | R] | Rs]); 1730usplit_1_1(X, Y, [Z | L], R, Rs, S) when Z == S -> 1731 usplit_1_1(X, Y, L, R, Rs, S); 1732usplit_1_1(X, Y, [Z | L], R, Rs, S) -> 1733 usplit_1(Z, S, L, [], [[Y, X | R] | Rs]); 1734usplit_1_1(X, Y, [], R, Rs, S) -> 1735 rumergel([[S], [Y, X | R] | Rs], [], asc). 1736 1737%% Descending. 1738usplit_2(X, Y, [Z | L], R, Rs) when Z < Y -> 1739 usplit_2(Y, Z, L, [X | R], Rs); 1740usplit_2(X, Y, [Z | L], R, Rs) when Z == Y -> 1741 usplit_2(X, Y, L, R, Rs); 1742usplit_2(X, Y, [Z | L], R, Rs) when Z < X -> 1743 usplit_2(Z, Y, L, [X | R], Rs); 1744usplit_2(X, Y, [Z | L], R, Rs) when Z == X -> 1745 usplit_2(X, Y, L, R, Rs); 1746usplit_2(X, Y, [Z | L], [], Rs) -> 1747 usplit_2(X, Y, L, [Z], Rs); 1748usplit_2(X, Y, [Z | L], R, Rs) -> 1749 usplit_2_1(X, Y, L, R, Rs, Z); 1750usplit_2(X, Y, [], R, Rs) -> 1751 umergel([[Y, X | R] | Rs], [], desc). 1752 1753usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z < Y -> 1754 usplit_2_1(Y, Z, L, [X | R], Rs, S); 1755usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z == Y -> 1756 usplit_2_1(X, Y, L, R, Rs, S); 1757usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z < X -> 1758 usplit_2_1(Z, Y, L, [X | R], Rs, S); 1759usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z == X -> 1760 usplit_2_1(X, Y, L, R, Rs, S); 1761usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z < S -> 1762 usplit_2(S, Z, L, [], [[Y, X | R] | Rs]); 1763usplit_2_1(X, Y, [Z | L], R, Rs, S) when Z == S -> 1764 usplit_2_1(X, Y, L, R, Rs, S); 1765usplit_2_1(X, Y, [Z | L], R, Rs, S) -> 1766 usplit_2(Z, S, L, [], [[Y, X | R] | Rs]); 1767usplit_2_1(X, Y, [], R, Rs, S) -> 1768 umergel([[S], [Y, X | R] | Rs], [], desc). 1769 1770%% umerge/1 1771 1772umergel(L) -> 1773 umergel(L, [], asc). 1774 1775umergel([[] | L], Acc, O) -> 1776 umergel(L, Acc, O); 1777umergel([T1, [H2 | T2], [H3 | T3] | L], Acc, asc) -> 1778 umergel(L, [umerge3_1(T1, [H2 | H3], T2, H2, [], T3, H3) | Acc], asc); 1779umergel([[H3 | T3], [H2 | T2], T1 | L], Acc, desc) -> 1780 umergel(L, [umerge3_1(T1, [H2 | H3], T2, H2, [], T3, H3) | Acc], desc); 1781umergel([A, [] | L], Acc, O) -> 1782 umergel([A | L], Acc, O); 1783umergel([A, B, [] | L], Acc, O) -> 1784 umergel([A, B | L], Acc, O); 1785umergel([[H1 | T1], T2 | L], Acc, asc) -> 1786 umergel(L, [umerge2_2(T1, T2, [], H1) | Acc], asc); 1787umergel([T2, [H1 | T1] | L], Acc, desc) -> 1788 umergel(L, [umerge2_2(T1, T2, [], H1) | Acc], desc); 1789umergel([L], [], _O) -> 1790 L; 1791umergel([L], Acc, O) -> 1792 rumergel([lists:reverse(L, []) | Acc], [], O); 1793umergel([], [], _O) -> 1794 []; 1795umergel([], Acc, O) -> 1796 rumergel(Acc, [], O). 1797 1798rumergel([[H3 | T3], [H2 | T2], T1 | L], Acc, asc) -> 1799 rumergel(L, [rumerge3_1(T1, T2, H2, [], T3, H3) | Acc], asc); 1800rumergel([T1, [H2 | T2], [H3 | T3] | L], Acc, desc) -> 1801 rumergel(L, [rumerge3_1(T1, T2, H2, [], T3, H3) | Acc], desc); 1802rumergel([[H2 | T2], T1 | L], Acc, asc) -> 1803 rumergel(L, [rumerge2_1(T1, T2, [], H2) | Acc], asc); 1804rumergel([T1, [H2 | T2] | L], Acc, desc) -> 1805 rumergel(L, [rumerge2_1(T1, T2, [], H2) | Acc], desc); 1806rumergel([L], Acc, O) -> 1807 umergel([lists:reverse(L, []) | Acc], [], O); 1808rumergel([], Acc, O) -> 1809 umergel(Acc, [], O). 1810 1811%% umerge3/3 1812 1813%% Take L1 apart. 1814umerge3_1([H1 | T1], HdM, T2, H2, M, T3, H3) when H1 =< H2 -> 1815 umerge3_12(T1, H1, T2, H2, M, T3, H3, HdM); 1816umerge3_1([H1 | T1], HdM, T2, H2, M, T3, H3) when H2 == HdM -> 1817 umerge3_2(T1, H1, T2, H2, M, T3, H3); 1818umerge3_1([H1 | T1], HdM, T2, H2, M, T3, H3) -> 1819 umerge3_21(T1, H1, T2, H2, M, T3, H3, HdM); 1820umerge3_1([], HdM, T2, H2, M, T3, H3) when H2 == HdM -> 1821 umerge2_1(T2, T3, M, HdM, H3); 1822umerge3_1([], _HdM, T2, H2, M, T3, H3) when H2 =< H3 -> 1823 umerge2_1(T2, T3, [H2 | M], H2, H3); 1824umerge3_1([], HdM, T2, H2, M, T3, H3) when H3 == HdM -> 1825 umerge2_2(T2, T3, M, H2); 1826umerge3_1([], _HdM, T2, H2, M, T3, H3) -> 1827 umerge2_2(T2, T3, [H3 | M], H2). 1828 1829%% Take L2 apart. 1830umerge3_2(T1, H1, [H2 | T2], HdM, M, T3, H3) when H1 =< H2 -> 1831 umerge3_12(T1, H1, T2, H2, M, T3, H3, HdM); 1832umerge3_2(T1, H1, [H2 | T2], HdM, M, T3, H3) -> 1833 umerge3_21(T1, H1, T2, H2, M, T3, H3, HdM); 1834umerge3_2(T1, H1, [], _HdM, M, T3, H3) when H1 =< H3 -> 1835 umerge2_1(T1, T3, [H1 | M], H1, H3); 1836umerge3_2(T1, H1, [], HdM, M, T3, H3) when H3 == HdM -> 1837 umerge2_2(T1, T3, M, H1); 1838umerge3_2(T1, H1, [], _HdM, M, T3, H3) -> 1839 umerge2_2(T1, T3, [H3 | M], H1). 1840 1841% H1 =< H2. Inlined. 1842umerge3_12(T1, H1, T2, H2, M, T3, H3, _HdM) when H1 =< H3 -> 1843 umerge3_1(T1, H1, T2, H2, [H1 | M], T3, H3); 1844umerge3_12(T1, H1, T2, H2, M, T3, H3, HdM) when H3 == HdM -> 1845 umerge3_12_3(T1, H1, T2, H2, M, T3); 1846umerge3_12(T1, H1, T2, H2, M, T3, H3, _HdM) -> 1847 umerge3_12_3(T1, H1, T2, H2, [H3 | M], T3). 1848 1849% H1 =< H2, take L3 apart. 1850umerge3_12_3(T1, H1, T2, H2, M, [H3 | T3]) when H1 =< H3 -> 1851 umerge3_1(T1, H1, T2, H2, [H1 | M], T3, H3); 1852umerge3_12_3(T1, H1, T2, H2, M, [H3 | T3]) -> 1853 umerge3_12_3(T1, H1, T2, H2, [H3 | M], T3); 1854umerge3_12_3(T1, H1, T2, H2, M, []) -> 1855 umerge2_1(T1, T2, [H1 | M], H1, H2). 1856 1857% H1 > H2. Inlined. 1858umerge3_21(T1, H1, T2, H2, M, T3, H3, _HdM) when H2 =< H3 -> 1859 umerge3_2(T1, H1, T2, H2, [H2 | M], T3, H3); 1860umerge3_21(T1, H1, T2, H2, M, T3, H3, HdM) when H3 == HdM -> 1861 umerge3_21_3(T1, H1, T2, H2, M, T3); 1862umerge3_21(T1, H1, T2, H2, M, T3, H3, _HdM) -> 1863 umerge3_21_3(T1, H1, T2, H2, [H3 | M], T3). 1864 1865% H1 > H2, take L3 apart. 1866umerge3_21_3(T1, H1, T2, H2, M, [H3 | T3]) when H2 =< H3 -> 1867 umerge3_2(T1, H1, T2, H2, [H2 | M], T3, H3); 1868umerge3_21_3(T1, H1, T2, H2, M, [H3 | T3]) -> 1869 umerge3_21_3(T1, H1, T2, H2, [H3 | M], T3); 1870umerge3_21_3(T1, H1, T2, H2, M, []) -> 1871 umerge2_2(T1, T2, [H2 | M], H1). 1872 1873%% Take L1 apart. 1874rumerge3_1([H1 | T1], T2, H2, M, T3, H3) when H1 =< H2 -> 1875 rumerge3_12a(T1, H1, T2, H2, M, T3, H3); 1876rumerge3_1([H1 | T1], T2, H2, M, T3, H3) when H1 =< H3 -> 1877 rumerge3_21_3(T1, T2, H2, M, T3, H3, H1); 1878rumerge3_1([H1 | T1], T2, H2, M, T3, H3) -> 1879 rumerge3_1(T1, T2, H2, [H1 | M], T3, H3); 1880rumerge3_1([], T2, H2, M, T3, H3) when H2 =< H3 -> 1881 rumerge2_2(T2, T3, M, H3, H2); 1882rumerge3_1([], T2, H2, M, T3, H3) -> 1883 rumerge2_1(T2, T3, [H2 | M], H3). 1884 1885% H1 =< H2. Inlined. 1886rumerge3_12a(T1, H1, T2, H2, M, T3, H3) when H2 =< H3 -> 1887 rumerge3_12_3(T1, T2, H2, M, T3, H3, H1); 1888rumerge3_12a(T1, H1, T2, H2, M, T3, H3) -> 1889 rumerge3_2(T1, T2, H2, M, T3, H3, H1). 1890 1891%% Take L2 apart. H2M > H3. H2M > H2. 1892rumerge3_2(T1, [H2 | T2], H2M, M, T3, H3, H1) when H1 =< H2 -> 1893 % H2M > H1. 1894 rumerge3_12b(T1, H1, T2, H2, M, T3, H3, H2M); 1895rumerge3_2(T1, [H2 | T2], H2M, M, T3, H3, H1) when H1 == H2M -> 1896 rumerge3_1(T1, T2, H2, [H1 | M], T3, H3); 1897rumerge3_2(T1, [H2 | T2], H2M, M, T3, H3, H1) when H1 =< H3 -> 1898 % H2M > H1. 1899 rumerge3_21_3(T1, T2, H2, [H2M | M], T3, H3, H1); 1900rumerge3_2(T1, [H2 | T2], H2M, M, T3, H3, H1) -> 1901 % H2M > H1. 1902 rumerge3_1(T1, T2, H2, [H1, H2M | M], T3, H3); 1903rumerge3_2(T1, [], H2M, M, T3, H3, H1) when H1 == H2M -> 1904 rumerge2_1(T1, T3, [H1 | M], H3); 1905rumerge3_2(T1, [], H2M, M, T3, H3, H1) when H1 =< H3 -> 1906 rumerge2_2(T1, T3, [H2M | M], H3, H1); 1907rumerge3_2(T1, [], H2M, M, T3, H3, H1) -> 1908 rumerge2_1(T1, T3, [H1, H2M | M], H3). 1909 1910% H1 =< H2. Inlined. 1911rumerge3_12b(T1, H1, T2, H2, M, T3, H3, H2M) when H2 =< H3 -> 1912 rumerge3_12_3(T1, T2, H2, [H2M | M], T3, H3, H1); 1913rumerge3_12b(T1, H1, T2, H2, M, T3, H3, H2M) -> 1914 rumerge3_2(T1, T2, H2, [H2M | M], T3, H3, H1). 1915 1916% H1 =< H2, take L3 apart. 1917rumerge3_12_3(T1, T2, H2, M, [H3 | T3], H3M, H1) when H2 =< H3 -> 1918 rumerge3_12_3(T1, T2, H2, [H3M | M], T3, H3, H1); 1919rumerge3_12_3(T1, T2, H2, M, [H3 | T3], H3M, H1) when H2 == H3M -> 1920 rumerge3_2(T1, T2, H2, M, T3, H3, H1); 1921rumerge3_12_3(T1, T2, H2, M, [H3 | T3], H3M, H1) -> 1922 rumerge3_2(T1, T2, H2, [H3M | M], T3, H3, H1); 1923rumerge3_12_3(T1, T2, H2, M, [], H3M, H1) when H2 == H3M -> 1924 rumerge2_2(T1, T2, M, H2, H1); 1925rumerge3_12_3(T1, T2, H2, M, [], H3M, H1) -> 1926 rumerge2_2(T1, T2, [H3M | M], H2, H1). 1927 1928% H1 > H2, take L3 apart. 1929rumerge3_21_3(T1, T2, H2, M, [H3 | T3], H3M, H1) when H1 =< H3 -> 1930 rumerge3_21_3(T1, T2, H2, [H3M | M], T3, H3, H1); 1931rumerge3_21_3(T1, T2, H2, M, [H3 | T3], H3M, H1) when H1 == H3M -> 1932 rumerge3_1(T1, T2, H2, [H1 | M], T3, H3); 1933rumerge3_21_3(T1, T2, H2, M, [H3 | T3], H3M, H1) -> 1934 rumerge3_1(T1, T2, H2, [H1, H3M | M], T3, H3); 1935rumerge3_21_3(T1, T2, H2, M, [], H3M, H1) when H1 == H3M -> 1936 rumerge2_1(T1, T2, [H1 | M], H2); 1937rumerge3_21_3(T1, T2, H2, M, [], H3M, H1) -> 1938 rumerge2_1(T1, T2, [H1, H3M | M], H2). 1939 1940%% umerge/2 1941 1942%% Elements from the first list are kept and prioritized. 1943umerge2_1([H1 | T1], T2, M, _HdM, H2) when H1 =< H2 -> 1944 umerge2_1(T1, T2, [H1 | M], H1, H2); 1945umerge2_1([H1 | T1], T2, M, HdM, H2) when H2 == HdM -> 1946 umerge2_2(T1, T2, M, H1); 1947umerge2_1([H1 | T1], T2, M, _HdM, H2) -> 1948 umerge2_2(T1, T2, [H2 | M], H1); 1949umerge2_1([], T2, M, HdM, H2) when H2 == HdM -> 1950 lists:reverse(T2, M); 1951umerge2_1([], T2, M, _HdM, H2) -> 1952 lists:reverse(T2, [H2 | M]). 1953 1954umerge2_2(T1, [H2 | T2], M, H1) when H1 =< H2 -> 1955 umerge2_1(T1, T2, [H1 | M], H1, H2); 1956umerge2_2(T1, [H2 | T2], M, H1) -> 1957 umerge2_2(T1, T2, [H2 | M], H1); 1958umerge2_2(T1, [], M, H1) -> 1959 lists:reverse(T1, [H1 | M]). 1960 1961%% rumerge/2 1962 1963%% Elements from the first list are kept and prioritized. 1964rumerge2_1([H1 | T1], T2, M, H2) when H1 =< H2 -> 1965 rumerge2_2(T1, T2, M, H2, H1); 1966rumerge2_1([H1 | T1], T2, M, H2) -> 1967 rumerge2_1(T1, T2, [H1 | M], H2); 1968rumerge2_1([], T2, M, H2) -> 1969 lists:reverse(T2, [H2 | M]). 1970 1971% H1 =< H2M. 1972rumerge2_2(T1, [H2 | T2], M, H2M, H1) when H1 =< H2 -> 1973 rumerge2_2(T1, T2, [H2M | M], H2, H1); 1974rumerge2_2(T1, [H2 | T2], M, H2M, H1) when H1 == H2M -> 1975 rumerge2_1(T1, T2, [H1 | M], H2); 1976rumerge2_2(T1, [H2 | T2], M, H2M, H1) -> 1977 rumerge2_1(T1, T2, [H1, H2M | M], H2); 1978rumerge2_2(T1, [], M, H2M, H1) when H1 == H2M -> 1979 lists:reverse(T1, [H1 | M]); 1980rumerge2_2(T1, [], M, H2M, H1) -> 1981 lists:reverse(T1, [H1, H2M | M]). 1982 1983%% keysort/2 1984 1985%% Ascending. 1986keysplit_1(I, X, EX, Y, EY, [Z | L], R, Rs) -> 1987 case element(I, Z) of 1988 EZ when EY =< EZ -> 1989 keysplit_1(I, Y, EY, Z, EZ, L, [X | R], Rs); 1990 EZ when EX =< EZ -> 1991 keysplit_1(I, Z, EZ, Y, EY, L, [X | R], Rs); 1992 _EZ when R == [] -> 1993 keysplit_1(I, X, EX, Y, EY, L, [Z], Rs); 1994 EZ -> 1995 keysplit_1_1(I, X, EX, Y, EY, EZ, R, Rs, Z, L) 1996 end; 1997keysplit_1(I, X, _EX, Y, _EY, [], R, Rs) -> 1998 rkeymergel(I, [[Y, X | R] | Rs], [], asc). 1999 2000keysplit_1_1(I, X, EX, Y, EY, ES, R, Rs, S, [Z | L]) -> 2001 case element(I, Z) of 2002 EZ when EY =< EZ -> 2003 keysplit_1_1(I, Y, EY, Z, EZ, ES, [X | R], Rs, S, L); 2004 EZ when EX =< EZ -> 2005 keysplit_1_1(I, Z, EZ, Y, EY, ES, [X | R], Rs, S, L); 2006 EZ when ES =< EZ -> 2007 keysplit_1(I, S, ES, Z, EZ, L, [], [[Y, X | R] | Rs]); 2008 EZ -> 2009 keysplit_1(I, Z, EZ, S, ES, L, [], [[Y, X | R] | Rs]) 2010 end; 2011keysplit_1_1(I, X, _EX, Y, _EY, _ES, R, Rs, S, []) -> 2012 rkeymergel(I, [[S], [Y, X | R] | Rs], [], asc). 2013 2014%% Descending. 2015keysplit_2(I, X, EX, Y, EY, [Z | L], R, Rs) -> 2016 case element(I, Z) of 2017 EZ when EY > EZ -> 2018 keysplit_2(I, Y, EY, Z, EZ, L, [X | R], Rs); 2019 EZ when EX > EZ -> 2020 keysplit_2(I, Z, EZ, Y, EY, L, [X | R], Rs); 2021 _EZ when R == [] -> 2022 keysplit_2(I, X, EX, Y, EY, L, [Z], Rs); 2023 EZ -> 2024 keysplit_2_1(I, X, EX, Y, EY, EZ, R, Rs, Z, L) 2025 end; 2026keysplit_2(I, X, _EX, Y, _EY, [], R, Rs) -> 2027 keymergel(I, [[Y, X | R] | Rs], [], desc). 2028 2029keysplit_2_1(I, X, EX, Y, EY, ES, R, Rs, S, [Z | L]) -> 2030 case element(I, Z) of 2031 EZ when EY > EZ -> 2032 keysplit_2_1(I, Y, EY, Z, EZ, ES, [X | R], Rs, S, L); 2033 EZ when EX > EZ -> 2034 keysplit_2_1(I, Z, EZ, Y, EY, ES, [X | R], Rs, S, L); 2035 EZ when ES > EZ -> 2036 keysplit_2(I, S, ES, Z, EZ, L, [], [[Y, X | R] | Rs]); 2037 EZ -> 2038 keysplit_2(I, Z, EZ, S, ES, L, [], [[Y, X | R] | Rs]) 2039 end; 2040keysplit_2_1(I, X, _EX, Y, _EY, _ES, R, Rs, S, []) -> 2041 keymergel(I, [[S], [Y, X | R] | Rs], [], desc). 2042 2043keymergel(I, [T1, [H2 | T2], [H3 | T3] | L], Acc, O) when O == asc -> 2044 M = keymerge3_1(I, T1, [],O,element(I,H2), H2, T2, element(I,H3), H3, T3), 2045 keymergel(I, L, [M | Acc], O); 2046keymergel(I, [[H3 | T3], [H2 | T2], T1 | L], Acc, O) when O == desc -> 2047 M = keymerge3_1(I, T1, [],O,element(I,H2), H2, T2, element(I,H3), H3, T3), 2048 keymergel(I, L, [M | Acc], O); 2049keymergel(I, [T1, [H2 | T2] | L], Acc, asc) -> 2050 keymergel(I, L, [keymerge2_1(I, T1, element(I,H2),H2,T2,[]) | Acc], asc); 2051keymergel(I, [[H2 | T2], T1 | L], Acc, desc) -> 2052 keymergel(I, L, [keymerge2_1(I, T1, element(I,H2),H2,T2,[]) | Acc], desc); 2053keymergel(_I, [L], [], _O) -> 2054 L; 2055keymergel(I, [L], Acc, O) -> 2056 rkeymergel(I, [lists:reverse(L, []) | Acc], [], O); 2057keymergel(I, [], Acc, O) -> 2058 rkeymergel(I, Acc, [], O). 2059 2060rkeymergel(I, [[H3 | T3], [H2 | T2], T1 | L], Acc, O) when O == asc -> 2061 M = rkeymerge3_1(I, T1, [],O,element(I,H2), H2, T2, element(I,H3), H3,T3), 2062 rkeymergel(I, L, [M | Acc], O); 2063rkeymergel(I, [T1, [H2 | T2], [H3 | T3] | L], Acc, O) when O == desc -> 2064 M = rkeymerge3_1(I, T1, [],O,element(I,H2), H2, T2, element(I,H3), H3,T3), 2065 rkeymergel(I, L, [M | Acc], O); 2066rkeymergel(I, [[H2 | T2], T1 | L], Acc, asc) -> 2067 rkeymergel(I, L, [rkeymerge2_1(I, T1, element(I,H2),H2,T2,[]) | Acc],asc); 2068rkeymergel(I, [T1, [H2 | T2] | L], Acc, desc) -> 2069 rkeymergel(I, L, [rkeymerge2_1(I,T1, element(I,H2),H2,T2,[]) | Acc],desc); 2070rkeymergel(I, [L], Acc, O) -> 2071 keymergel(I, [lists:reverse(L, []) | Acc], [], O); 2072rkeymergel(I, [], Acc, O) -> 2073 keymergel(I, Acc, [], O). 2074 2075%%% An extra argument, D, just to avoid some move instructions. 2076 2077%% Take L1 apart. 2078keymerge3_1(I, [H1 | T1], M, D, E2, H2, T2, E3, H3, T3) -> 2079 case element(I, H1) of 2080 E1 when E1 =< E2 -> 2081 keymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D); 2082 E1 -> 2083 keymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, T2) 2084 end; 2085keymerge3_1(I, [], M, _D, E2, H2, T2, E3, H3, T3) when E2 =< E3 -> 2086 keymerge2_1(I, T2, E3, H3, T3, [H2 | M]); 2087keymerge3_1(I, [], M, _D, E2, H2, T2, _E3, H3, T3) -> 2088 keymerge2_2(I, T2, E2, H3, T3, M, H2). 2089 2090%% Take L2 apart. 2091keymerge3_2(I, E1, H1, T1, [H2 | T2], M, D, E3, H3, T3) -> 2092 case element(I, H2) of 2093 E2 when E1 =< E2 -> 2094 keymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, T1); 2095 E2 -> 2096 keymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D) 2097 end; 2098keymerge3_2(I, E1, H1, T1, [], M, _D, E3, H3, T3) when E1 =< E3 -> 2099 keymerge2_1(I, T1, E3, H3, T3, [H1 | M]); 2100keymerge3_2(I, E1, H1, T1, [], M, _D, _E3, H3, T3) -> 2101 keymerge2_2(I, T1, E1, H3, T3, M, H1). 2102 2103% E1 =< E2. Inlined. 2104keymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D) when E1 =< E3 -> 2105 keymerge3_1(I, T1, [H1 | M], D, E2, H2, T2, E3, H3, T3); 2106keymerge3_12(I, E1, H1, T1, E2, H2, T2, _E3, H3, T3, M, _D) -> 2107 keymerge3_12_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]). 2108 2109% E1 =< E2, take L3 apart. 2110keymerge3_12_3(I, E1, H1, T1, E2, H2, T2, [H3 | T3], M) -> 2111 case element(I, H3) of 2112 E3 when E1 =< E3 -> 2113 keymerge3_1(I, T1, [H1 | M], T1, E2, H2, T2, E3, H3, T3); 2114 _E3 -> 2115 keymerge3_12_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]) 2116 end; 2117keymerge3_12_3(I, _E1, H1, T1, E2, H2, T2, [], M) -> 2118 keymerge2_1(I, T1, E2, H2, T2, [H1 | M]). 2119 2120% E1 > E2. Inlined. 2121keymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D) when E2 =< E3 -> 2122 keymerge3_2(I, E1, H1, T1, T2, [H2 | M], D, E3, H3, T3); 2123keymerge3_21(I, E1, H1, T1, E2, H2, T2, _E3, H3, T3, M, _D) -> 2124 keymerge3_21_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]). 2125 2126% E1 > E2, take L3 apart. 2127keymerge3_21_3(I, E1, H1, T1, E2, H2, T2, [H3 | T3], M) -> 2128 case element(I, H3) of 2129 E3 when E2 =< E3 -> 2130 keymerge3_2(I, E1, H1, T1, T2, [H2 | M], T2, E3, H3, T3); 2131 _E3 -> 2132 keymerge3_21_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]) 2133 end; 2134keymerge3_21_3(I, E1, H1, T1, _E2, H2, T2, [], M) -> 2135 keymerge2_2(I, T1, E1, H2, T2, M, H1). 2136 2137%% Take L1 apart. 2138rkeymerge3_1(I, [H1 | T1], M, D, E2, H2, T2, E3, H3, T3) -> 2139 case element(I, H1) of 2140 E1 when E1 =< E2 -> 2141 rkeymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, T2); 2142 E1 -> 2143 rkeymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D) 2144 end; 2145rkeymerge3_1(I, [], M, _D, E2, H2, T2, E3, H3, T3) when E2 =< E3 -> 2146 rkeymerge2_2(I, E2, T2, H3, T3, M, H2); 2147rkeymerge3_1(I, [], M, _D, _E2, H2, T2, E3, H3, T3) -> 2148 rkeymerge2_1(I, T2, E3, H3, T3, [H2 | M]). 2149 2150%% Take L2 apart. 2151rkeymerge3_2(I, E1, H1, T1, [H2 | T2], M, D, E3, H3, T3) -> 2152 case element(I, H2) of 2153 E2 when E1 =< E2 -> 2154 rkeymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D); 2155 E2 -> 2156 rkeymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, T1) 2157 end; 2158rkeymerge3_2(I, E1, H1, T1, [], M, _D, E3, H3, T3) when E1 =< E3 -> 2159 rkeymerge2_2(I, E1, T1, H3, T3, M, H1); 2160rkeymerge3_2(I, _E1, H1, T1, [], M, _D, E3, H3, T3) -> 2161 rkeymerge2_1(I, T1, E3, H3, T3, [H1 | M]). 2162 2163% E1 =< E2. Inlined. 2164rkeymerge3_12(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, _D) when E2 =< E3 -> 2165 rkeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]); 2166rkeymerge3_12(I, E1, H1, T1, _E2, H2, T2, E3, H3, T3, M, D) -> 2167 rkeymerge3_2(I, E1, H1, T1, T2, [H2 | M], D, E3, H3, T3). 2168 2169% E1 =< E2, take L3 apart. 2170rkeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, [H3 | T3], M) -> 2171 case element(I, H3) of 2172 E3 when E2 =< E3 -> 2173 rkeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]); 2174 E3 -> 2175 rkeymerge3_2(I, E1, H1, T1, T2, [H2 | M], T2, E3, H3, T3) 2176 end; 2177rkeymerge3_12_3(I, E1, H1, T1, _E2, H2, T2, [], M) -> 2178 rkeymerge2_2(I, E1, T1, H2, T2, M, H1). 2179 2180% E1 > E2. Inlined. 2181rkeymerge3_21(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, _D) when E1 =< E3 -> 2182 rkeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]); 2183rkeymerge3_21(I, _E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D) -> 2184 rkeymerge3_1(I, T1, [H1 | M], D, E2, H2, T2, E3, H3, T3). 2185 2186% E1 > E2, take L3 apart. 2187rkeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, [H3 | T3], M) -> 2188 case element(I, H3) of 2189 E3 when E1 =< E3 -> 2190 rkeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, T3, [H3 | M]); 2191 E3 -> 2192 rkeymerge3_1(I, T1, [H1 | M], T1, E2, H2, T2, E3, H3, T3) 2193 end; 2194rkeymerge3_21_3(I, _E1, H1, T1, E2, H2, T2, [], M) -> 2195 rkeymerge2_1(I, T1, E2, H2, T2, [H1 | M]). 2196 2197%% keymerge/3 2198 2199%% Elements from the first list are prioritized. 2200keymerge2_1(I, [H1 | T1], E2, H2, T2, M) -> 2201 case element(I, H1) of 2202 E1 when E1 =< E2 -> 2203 keymerge2_1(I, T1, E2, H2, T2, [H1 | M]); 2204 E1 -> 2205 keymerge2_2(I, T1, E1, H2, T2, M, H1) 2206 end; 2207keymerge2_1(_I, [], _E2, H2, T2, M) -> 2208 lists:reverse(T2, [H2 | M]). 2209 2210keymerge2_2(I, T1, E1, HdM, [H2 | T2], M, H1) -> 2211 case element(I, H2) of 2212 E2 when E1 =< E2 -> 2213 keymerge2_1(I, T1, E2, H2, T2, [H1, HdM | M]); 2214 _E2 -> 2215 keymerge2_2(I, T1, E1, H2, T2, [HdM | M], H1) 2216 end; 2217keymerge2_2(_I, T1, _E1, HdM, [], M, H1) -> 2218 lists:reverse(T1, [H1, HdM | M]). 2219 2220%% rkeymerge/3 2221 2222rkeymerge2_1(I, [H1 | T1], E2, H2, T2, M) -> 2223 case element(I, H1) of 2224 E1 when E1 =< E2 -> 2225 rkeymerge2_2(I, E1, T1, H2, T2, M, H1); 2226 _E1 -> 2227 rkeymerge2_1(I, T1, E2, H2, T2, [H1 | M]) 2228 end; 2229rkeymerge2_1(_I, [], _E2, H2, T2, M) -> 2230 lists:reverse(T2, [H2 | M]). 2231 2232rkeymerge2_2(I, E1, T1, HdM, [H2 | T2], M, H1) -> 2233 case element(I, H2) of 2234 E2 when E1 =< E2 -> 2235 rkeymerge2_2(I, E1, T1, H2, T2, [HdM | M], H1); 2236 E2 -> 2237 rkeymerge2_1(I, T1, E2, H2, T2, [H1, HdM | M]) 2238 end; 2239rkeymerge2_2(_I, _E1, T1, HdM, [], M, H1) -> 2240 lists:reverse(T1, [H1, HdM | M]). 2241 2242%% ukeysort/2 2243 2244%% Ascending. 2245ukeysplit_1(I, X, EX, Y, EY, [Z | L], R, Rs) -> 2246 case element(I, Z) of 2247 EZ when EY == EZ -> 2248 ukeysplit_1(I, X, EX, Y, EY, L, R, Rs); 2249 EZ when EY < EZ -> 2250 ukeysplit_1(I, Y, EY, Z, EZ, L, [X | R], Rs); 2251 EZ when EX == EZ -> 2252 ukeysplit_1(I, X, EX, Y, EY, L, R, Rs); 2253 EZ when EX < EZ -> 2254 ukeysplit_1(I, Z, EZ, Y, EY, L, [X | R], Rs); 2255 _EZ when R == [] -> 2256 ukeysplit_1(I, X, EX, Y, EY, L, [Z], Rs); 2257 EZ -> 2258 ukeysplit_1_1(I, X, EX, Y, EY, L, R, Rs, Z, EZ) 2259 end; 2260ukeysplit_1(I, X, _EX, Y, _EY, [], R, Rs) -> 2261 rukeymergel(I, [[Y, X | R] | Rs], []). 2262 2263ukeysplit_1_1(I, X, EX, Y, EY, [Z | L], R, Rs, S, ES) -> 2264 case element(I, Z) of 2265 EZ when EY == EZ -> 2266 ukeysplit_1_1(I, X, EX, Y, EY, L, R, Rs, S, ES); 2267 EZ when EY < EZ -> 2268 ukeysplit_1_1(I, Y, EY, Z, EZ, L, [X | R], Rs, S, ES); 2269 EZ when EX == EZ -> 2270 ukeysplit_1_1(I, X, EX, Y, EY, L, R, Rs, S, ES); 2271 EZ when EX < EZ -> 2272 ukeysplit_1_1(I, Z, EZ, Y, EY, L, [X | R], Rs, S, ES); 2273 EZ when ES == EZ -> 2274 ukeysplit_1_1(I, X, EX, Y, EY, L, R, Rs, S, ES); 2275 EZ when ES < EZ -> 2276 ukeysplit_1(I, S, ES, Z, EZ, L, [], [[Y, X | R] | Rs]); 2277 EZ -> 2278 ukeysplit_1(I, Z, EZ, S, ES, L, [], [[Y, X | R] | Rs]) 2279 end; 2280ukeysplit_1_1(I, X, _EX, Y, _EY, [], R, Rs, S, _ES) -> 2281 rukeymergel(I, [[S], [Y, X | R] | Rs], []). 2282 2283%% Descending. 2284ukeysplit_2(I, Y, EY, [Z | L], R) -> 2285 case element(I, Z) of 2286 EZ when EY == EZ -> 2287 ukeysplit_2(I, Y, EY, L, R); 2288 EZ when EY < EZ -> 2289 ukeysplit_1(I, Y, EY, Z, EZ, L, [], [lists:reverse(R, [])]); 2290 EZ -> 2291 ukeysplit_2(I, Z, EZ, L, [Y | R]) 2292 end; 2293ukeysplit_2(_I, Y, _EY, [], R) -> 2294 [Y | R]. 2295 2296-dialyzer({no_improper_lists, ukeymergel/3}). 2297 2298ukeymergel(I, [T1, [H2 | T2], [H3 | T3] | L], Acc) -> 2299 %% The fourth argument, [H2 | H3] (=HdM), may confuse type 2300 %% checkers. Its purpose is to ensure that the tests H2 == HdM 2301 %% and H3 == HdM in ukeymerge3_1 will always fail as long as M == []. 2302 M = ukeymerge3_1(I, T1, Acc, [H2 | H3], element(I, H2), H2, T2, [], 2303 element(I, H3), H3, T3), 2304 ukeymergel(I, L, [M | Acc]); 2305ukeymergel(I, [[H1 | T1], T2 | L], Acc) -> 2306 ukeymergel(I, L, [ukeymerge2_2(I, T1, element(I, H1), H1, T2, []) | Acc]); 2307ukeymergel(_I, [L], []) -> 2308 L; 2309ukeymergel(I, [L], Acc) -> 2310 rukeymergel(I, [lists:reverse(L, []) | Acc], []); 2311ukeymergel(I, [], Acc) -> 2312 rukeymergel(I, Acc, []). 2313 2314rukeymergel(I, [[H3 | T3], [H2 | T2], T1 | L], Acc) -> 2315 M = rukeymerge3_1(I, T1, Acc, [], element(I, H2), H2, T2, [], 2316 element(I, H3), H3, T3), 2317 rukeymergel(I, L, [M | Acc]); 2318rukeymergel(I, [[H2 | T2], T1 | L], Acc) -> 2319 rukeymergel(I, L, [rukeymerge2_1(I, T1, element(I,H2), T2, [], H2)|Acc]); 2320rukeymergel(I, [L], Acc) -> 2321 ukeymergel(I, [lists:reverse(L, []) | Acc], []); 2322rukeymergel(I, [], Acc) -> 2323 ukeymergel(I, Acc, []). 2324 2325%%% An extra argument, D, just to avoid some move instructions. 2326 2327%% Take L1 apart. 2328ukeymerge3_1(I, [H1 | T1], D, HdM, E2, H2, T2, M, E3, H3, T3) -> 2329 case element(I, H1) of 2330 E1 when E1 =< E2 -> 2331 ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, HdM, D); 2332 E1 when E2 == HdM -> 2333 ukeymerge3_2(I, E1, T1, H1, T2, HdM, T2, M, E3, H3, T3); 2334 E1 -> 2335 ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, HdM, T2) 2336 end; 2337ukeymerge3_1(I, [], _D, HdM, E2, _H2, T2, M, E3, H3, T3) when E2 == HdM -> 2338 ukeymerge2_1(I, T2, E3, HdM, T3, M, H3); 2339ukeymerge3_1(I, [], _D, _HdM, E2, H2, T2, M, E3, H3, T3) when E2 =< E3 -> 2340 ukeymerge2_1(I, T2, E3, E2, T3, [H2 | M], H3); 2341ukeymerge3_1(I, [], _D, HdM, E2, H2, T2, M, E3, _H3, T3) when E3 == HdM -> 2342 ukeymerge2_2(I, T2, E2, H2, T3, M); 2343ukeymerge3_1(I, [], _D, _HdM, E2, H2, T2, M, _E3, H3, T3) -> 2344 ukeymerge2_2(I, T2, E2, H2, T3, [H3 | M]). 2345 2346%% Take L2 apart. 2347ukeymerge3_2(I, E1, T1, H1, [H2 | T2], HdM, D, M, E3, H3, T3) -> 2348 case element(I, H2) of 2349 E2 when E1 =< E2 -> 2350 ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, HdM, T1); 2351 E2 -> 2352 ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, HdM, D) 2353 end; 2354ukeymerge3_2(I, E1, T1, H1, [], _HdM, _D, M, E3, H3, T3) when E1 =< E3 -> 2355 ukeymerge2_1(I, T1, E3, E1, T3, [H1 | M], H3); 2356ukeymerge3_2(I, E1, T1, H1, [], HdM, _D, M, E3, _H3, T3) when E3 == HdM -> 2357 ukeymerge2_2(I, T1, E1, H1, T3, M); 2358ukeymerge3_2(I, E1, T1, H1, [], _HdM, _D, M, _E3, H3, T3) -> 2359 ukeymerge2_2(I, T1, E1, H1, T3, [H3 | M]). 2360 2361% E1 =< E2. Inlined. 2362ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, _HdM, D) 2363 when E1 =< E3 -> 2364 ukeymerge3_1(I, T1, D, E1, E2, H2, T2, [H1 | M], E3, H3, T3); 2365ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, E3, _H3, T3, M, HdM, _D) 2366 when E3 == HdM -> 2367 ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, M, T3); 2368ukeymerge3_12(I, E1, T1, H1, E2, H2, T2, _E3, H3, T3, M, _HdM, _D) -> 2369 ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, [H3 | M], T3). 2370 2371% E1 =< E2, take L3 apart. 2372ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, M, [H3 | T3]) -> 2373 case element(I, H3) of 2374 E3 when E1 =< E3 -> 2375 ukeymerge3_1(I, T1, T1, E1, E2, H2, T2, [H1 | M], E3, H3, T3); 2376 _E3 -> 2377 ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, [H3 | M], T3) 2378 end; 2379ukeymerge3_12_3(I, E1, T1, H1, E2, H2, T2, M, []) -> 2380 ukeymerge2_1(I, T1, E2, E1, T2, [H1 | M], H2). 2381 2382% E1 > E2. Inlined. 2383ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, E3, H3, T3, M, _HdM, D) 2384 when E2 =< E3 -> 2385 ukeymerge3_2(I, E1, T1, H1, T2, E2, D, [H2 | M], E3, H3, T3); 2386ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, E3, _H3, T3, M, HdM, _D) 2387 when E3 == HdM -> 2388 ukeymerge3_21_3(I, E1, T1, H1, E2, H2, T2, M, T3); 2389ukeymerge3_21(I, E1, T1, H1, E2, H2, T2, _E3, H3, T3, M, _HdM, _D) -> 2390 ukeymerge3_21_3(I, E1, T1, H1, E2, H2, T2, [H3 | M], T3). 2391 2392% E1 > E2, take L3 apart. 2393ukeymerge3_21_3(I, E1, T1, H1, E2, H2, T2, M, [H3 | T3]) -> 2394 case element(I, H3) of 2395 E3 when E2 =< E3 -> 2396 ukeymerge3_2(I, E1, T1, H1, T2, E2, T2, [H2 | M], E3, H3, T3); 2397 _E3 -> 2398 ukeymerge3_21_3(I, E1, T1, H1, E2, H2, T2, [H3 | M], T3) 2399 end; 2400ukeymerge3_21_3(I, E1, T1, H1, _E2, H2, T2, M, []) -> 2401 ukeymerge2_2(I, T1, E1, H1, T2, [H2 | M]). 2402 2403%%% Two extra arguments, D1 and D2, just to avoid some move instructions. 2404 2405%% Take L1 apart. 2406rukeymerge3_1(I, [H1 | T1], D1, D2, E2, H2, T2, M, E3, H3, T3) -> 2407 case element(I, H1) of 2408 E1 when E1 =< E2 -> 2409 rukeymerge3_12a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M); 2410 E1 -> 2411 rukeymerge3_21a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D1, D2) 2412 end; 2413rukeymerge3_1(I, [], _D1, _D2, E2, H2, T2, M, E3, H3, T3) when E2 =< E3 -> 2414 rukeymerge2_2(I, T2, E2, T3, M, E3, H3, H2); 2415rukeymerge3_1(I, [], _D1, _D2, _E2, H2, T2, M, E3, H3, T3) -> 2416 rukeymerge2_1(I, T2, E3, T3, [H2 | M], H3). 2417 2418% E1 =< E2. Inlined. 2419rukeymerge3_12a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M) when E2 =< E3 -> 2420 rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, M, E3, H3, T3); 2421rukeymerge3_12a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M) -> 2422 rukeymerge3_2(I, E1, H1, T1, T2, H2, E2, M, E3, H3, T3). 2423 2424% E1 > E2. Inlined 2425rukeymerge3_21a(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, _D1, _D2) 2426 when E1 =< E3 -> 2427 rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, M, E3, H3, T3); 2428rukeymerge3_21a(I, _E1, H1, T1, E2, H2, T2, E3, H3, T3, M, D1, D2) -> 2429 rukeymerge3_1(I, T1, D1, D2, E2, H2, T2, [H1 | M], E3, H3, T3). 2430 2431%% Take L2 apart. E2M > E3. E2M > E2. 2432rukeymerge3_2(I, E1, H1, T1, [H2 | T2], H2M, E2M, M, E3, H3, T3) -> 2433 case element(I, H2) of 2434 E2 when E1 =< E2 -> 2435 % E2M > E1. 2436 rukeymerge3_12b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M); 2437 E2 when E1 == E2M -> 2438 rukeymerge3_1(I, T1, H1, T1, E2, H2, T2, [H1 | M], E3, H3, T3); 2439 E2 -> 2440 % E2M > E1. 2441 rukeymerge3_21b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M) 2442 end; 2443rukeymerge3_2(I, E1, H1, T1, [], _H2M, E2M, M, E3, H3, T3) when E1 == E2M -> 2444 rukeymerge2_1(I, T1, E3, T3, [H1 | M], H3); 2445rukeymerge3_2(I, E1, H1, T1, [], H2M, _E2M, M, E3, H3, T3) when E1 =< E3 -> 2446 rukeymerge2_2(I, T1, E1, T3, [H2M | M], E3, H3, H1); 2447rukeymerge3_2(I, _E1, H1, T1, [], H2M, _E2M, M, E3, H3, T3) -> 2448 rukeymerge2_1(I, T1, E3, T3, [H1, H2M | M], H3). 2449 2450% E1 =< E2. Inlined. 2451rukeymerge3_12b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M) 2452 when E2 =< E3 -> 2453 rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, [H2M | M], E3, H3, T3); 2454rukeymerge3_12b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M) -> 2455 rukeymerge3_2(I, E1, H1, T1, T2, H2, E2, [H2M | M], E3, H3, T3). 2456 2457% E1 > E2. Inlined 2458rukeymerge3_21b(I, E1, H1, T1, E2, H2, T2, E3, H3, T3, M,H2M) when E1 =< E3 -> 2459 rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, [H2M | M], E3, H3, T3); 2460rukeymerge3_21b(I, _E1, H1, T1, E2, H2, T2, E3, H3, T3, M, H2M) -> 2461 rukeymerge3_1(I, T1, H1, T1, E2, H2, T2, [H1, H2M | M], E3, H3, T3). 2462 2463% E1 =< E2, take L3 apart. 2464rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, M, E3M, H3M, [H3 | T3]) -> 2465 case element(I, H3) of 2466 E3 when E2 =< E3 -> 2467 rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, [H3M | M], E3, H3, T3); 2468 E3 when E2 == E3M -> 2469 rukeymerge3_2(I, E1, H1, T1, T2, H2, E2, M, E3, H3, T3); 2470 E3 -> 2471 rukeymerge3_2(I, E1, H1, T1, T2, H2, E2, [H3M | M], E3, H3, T3) 2472 end; 2473rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, M, E3M, _H3M, []) when E2 == E3M -> 2474 rukeymerge2_2(I, T1, E1, T2, M, E2, H2, H1); 2475rukeymerge3_12_3(I, E1, H1, T1, E2, H2, T2, M, _E3M, H3M, []) -> 2476 rukeymerge2_2(I, T1, E1, T2, [H3M | M], E2, H2, H1). 2477 2478% E1 > E2, take L3 apart. 2479rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, M, E3M, H3M, [H3 | T3]) -> 2480 case element(I, H3) of 2481 E3 when E1 =< E3 -> 2482 rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, [H3M | M], E3, H3, T3); 2483 E3 when E1 == E3M -> 2484 rukeymerge3_1(I, T1, H1, T1, E2, H2, T2, [H1 | M], E3, H3, T3); 2485 E3 -> 2486 rukeymerge3_1(I, T1, H1, T1, E2, H2, T2, [H1,H3M | M], E3, H3, T3) 2487 end; 2488rukeymerge3_21_3(I, E1, H1, T1, E2, H2, T2, M, E3M, _H3M, []) when E1 == E3M -> 2489 rukeymerge2_1(I, T1, E2, T2, [H1 | M], H2); 2490rukeymerge3_21_3(I, _E1, H1, T1, E2, H2, T2, M, _E3M, H3M, []) -> 2491 rukeymerge2_1(I, T1, E2, T2, [H1, H3M | M], H2). 2492 2493%% ukeymerge/3 2494 2495%% Elements from the first list are kept and prioritized. 2496ukeymerge2_1(I, [H1 | T1], E2, HdM, T2, M, H2) -> 2497 case element(I, H1) of 2498 E1 when E1 =< E2 -> 2499 ukeymerge2_1(I, T1, E2, E1, T2, [H1 | M], H2); 2500 E1 when E2 == HdM -> 2501 ukeymerge2_2(I, T1, E1, H1, T2, M); 2502 E1 -> 2503 ukeymerge2_2(I, T1, E1, H1, T2, [H2 | M]) 2504 end; 2505ukeymerge2_1(_I, [], E2, HdM, T2, M, _H2) when E2 == HdM -> 2506 lists:reverse(T2, M); 2507ukeymerge2_1(_I, [], _E2, _HdM, T2, M, H2) -> 2508 lists:reverse(T2, [H2 | M]). 2509 2510ukeymerge2_2(I, T1, E1, H1, [H2 | T2], M) -> 2511 case element(I, H2) of 2512 E2 when E1 =< E2 -> 2513 ukeymerge2_1(I, T1, E2, E1, T2, [H1 | M], H2); 2514 _E2 -> 2515 ukeymerge2_2(I, T1, E1, H1, T2, [H2 | M]) 2516 end; 2517ukeymerge2_2(_I, T1, _E1, H1, [], M) -> 2518 lists:reverse(T1, [H1 | M]). 2519 2520%% rukeymerge/3 2521 2522rukeymerge2_1(I, [H1 | T1], E2, T2, M, H2) -> 2523 case element(I, H1) of 2524 E1 when E1 =< E2 -> 2525 rukeymerge2_2(I, T1, E1, T2, M, E2, H2, H1); 2526 _E1 -> 2527 rukeymerge2_1(I, T1, E2, T2, [H1 | M], H2) 2528 end; 2529rukeymerge2_1(_I, [], _E2, T2, M, H2) -> 2530 lists:reverse(T2, [H2 | M]). 2531 2532rukeymerge2_2(I, T1, E1, [H2 | T2], M, E2M, H2M, H1) -> 2533 case element(I, H2) of 2534 E2 when E1 =< E2 -> 2535 rukeymerge2_2(I, T1, E1, T2, [H2M | M], E2, H2, H1); 2536 E2 when E1 == E2M -> 2537 rukeymerge2_1(I, T1, E2, T2, [H1 | M], H2); 2538 E2 -> 2539 rukeymerge2_1(I, T1, E2, T2, [H1, H2M | M], H2) 2540 end; 2541rukeymerge2_2(_I, T1, E1, [], M, E2M, _H2M, H1) when E1 == E2M -> 2542 lists:reverse(T1, [H1 | M]); 2543rukeymerge2_2(_I, T1, _E1, [], M, _E2M, H2M, H1) -> 2544 lists:reverse(T1, [H1, H2M | M]). 2545 2546%% sort/2 2547 2548%% Ascending. 2549fsplit_1(Y, X, Fun, [Z | L], R, Rs) -> 2550 case Fun(Y, Z) of 2551 true -> 2552 fsplit_1(Z, Y, Fun, L, [X | R], Rs); 2553 false -> 2554 case Fun(X, Z) of 2555 true -> 2556 fsplit_1(Y, Z, Fun, L, [X | R], Rs); 2557 false when R == [] -> 2558 fsplit_1(Y, X, Fun, L, [Z], Rs); 2559 false -> 2560 fsplit_1_1(Y, X, Fun, L, R, Rs, Z) 2561 end 2562 end; 2563fsplit_1(Y, X, Fun, [], R, Rs) -> 2564 rfmergel([[Y, X | R] | Rs], [], Fun, asc). 2565 2566fsplit_1_1(Y, X, Fun, [Z | L], R, Rs, S) -> 2567 case Fun(Y, Z) of 2568 true -> 2569 fsplit_1_1(Z, Y, Fun, L, [X | R], Rs, S); 2570 false -> 2571 case Fun(X, Z) of 2572 true -> 2573 fsplit_1_1(Y, Z, Fun, L, [X | R], Rs, S); 2574 false -> 2575 case Fun(S, Z) of 2576 true -> 2577 fsplit_1(Z, S, Fun, L, [], [[Y, X | R] | Rs]); 2578 false -> 2579 fsplit_1(S, Z, Fun, L, [], [[Y, X | R] | Rs]) 2580 end 2581 end 2582 end; 2583fsplit_1_1(Y, X, Fun, [], R, Rs, S) -> 2584 rfmergel([[S], [Y, X | R] | Rs], [], Fun, asc). 2585 2586%% Descending. 2587fsplit_2(Y, X, Fun, [Z | L], R, Rs) -> 2588 case Fun(Y, Z) of 2589 false -> 2590 fsplit_2(Z, Y, Fun, L, [X | R], Rs); 2591 true -> 2592 case Fun(X, Z) of 2593 false -> 2594 fsplit_2(Y, Z, Fun, L, [X | R], Rs); 2595 true when R == [] -> 2596 fsplit_2(Y, X, Fun, L, [Z], Rs); 2597 true -> 2598 fsplit_2_1(Y, X, Fun, L, R, Rs, Z) 2599 end 2600 end; 2601fsplit_2(Y, X, Fun, [], R, Rs) -> 2602 fmergel([[Y, X | R] | Rs], [], Fun, desc). 2603 2604fsplit_2_1(Y, X, Fun, [Z | L], R, Rs, S) -> 2605 case Fun(Y, Z) of 2606 false -> 2607 fsplit_2_1(Z, Y, Fun, L, [X | R], Rs, S); 2608 true -> 2609 case Fun(X, Z) of 2610 false -> 2611 fsplit_2_1(Y, Z, Fun, L, [X | R], Rs, S); 2612 true -> 2613 case Fun(S, Z) of 2614 false -> 2615 fsplit_2(Z, S, Fun, L, [], [[Y, X | R] | Rs]); 2616 true -> 2617 fsplit_2(S, Z, Fun, L, [], [[Y, X | R] | Rs]) 2618 end 2619 end 2620 end; 2621fsplit_2_1(Y, X, Fun, [], R, Rs, S) -> 2622 fmergel([[S], [Y, X | R] | Rs], [], Fun, desc). 2623 2624fmergel([T1, [H2 | T2] | L], Acc, Fun, asc) -> 2625 fmergel(L, [fmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun, asc); 2626fmergel([[H2 | T2], T1 | L], Acc, Fun, desc) -> 2627 fmergel(L, [fmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun, desc); 2628fmergel([L], [], _Fun, _O) -> 2629 L; 2630fmergel([L], Acc, Fun, O) -> 2631 rfmergel([lists:reverse(L, []) | Acc], [], Fun, O); 2632fmergel([], Acc, Fun, O) -> 2633 rfmergel(Acc, [], Fun, O). 2634 2635rfmergel([[H2 | T2], T1 | L], Acc, Fun, asc) -> 2636 rfmergel(L, [rfmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun, asc); 2637rfmergel([T1, [H2 | T2] | L], Acc, Fun, desc) -> 2638 rfmergel(L, [rfmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun, desc); 2639rfmergel([L], Acc, Fun, O) -> 2640 fmergel([lists:reverse(L, []) | Acc], [], Fun, O); 2641rfmergel([], Acc, Fun, O) -> 2642 fmergel(Acc, [], Fun, O). 2643 2644%% merge/3 2645 2646%% Elements from the first list are prioritized. 2647fmerge2_1([H1 | T1], H2, Fun, T2, M) -> 2648 case Fun(H1, H2) of 2649 true -> 2650 fmerge2_1(T1, H2, Fun, T2, [H1 | M]); 2651 false -> 2652 fmerge2_2(H1, T1, Fun, T2, [H2 | M]) 2653 end; 2654fmerge2_1([], H2, _Fun, T2, M) -> 2655 lists:reverse(T2, [H2 | M]). 2656 2657fmerge2_2(H1, T1, Fun, [H2 | T2], M) -> 2658 case Fun(H1, H2) of 2659 true -> 2660 fmerge2_1(T1, H2, Fun, T2, [H1 | M]); 2661 false -> 2662 fmerge2_2(H1, T1, Fun, T2, [H2 | M]) 2663 end; 2664fmerge2_2(H1, T1, _Fun, [], M) -> 2665 lists:reverse(T1, [H1 | M]). 2666 2667%% rmerge/3 2668 2669rfmerge2_1([H1 | T1], H2, Fun, T2, M) -> 2670 case Fun(H1, H2) of 2671 true -> 2672 rfmerge2_2(H1, T1, Fun, T2, [H2 | M]); 2673 false -> 2674 rfmerge2_1(T1, H2, Fun, T2, [H1 | M]) 2675 end; 2676rfmerge2_1([], H2, _Fun, T2, M) -> 2677 lists:reverse(T2, [H2 | M]). 2678 2679rfmerge2_2(H1, T1, Fun, [H2 | T2], M) -> 2680 case Fun(H1, H2) of 2681 true -> 2682 rfmerge2_2(H1, T1, Fun, T2, [H2 | M]); 2683 false -> 2684 rfmerge2_1(T1, H2, Fun, T2, [H1 | M]) 2685 end; 2686rfmerge2_2(H1, T1, _Fun, [], M) -> 2687 lists:reverse(T1, [H1 | M]). 2688 2689%% usort/2 2690 2691%% Ascending. X < Y 2692ufsplit_1(Y, X, Fun, [Z | L], R, Rs) -> 2693 case Fun(Y, Z) of 2694 true -> 2695 case Fun(Z, Y) of 2696 true -> % Z equal to Y 2697 ufsplit_1(Y, X, Fun, L, R, Rs); 2698 false -> 2699 ufsplit_1(Z, Y, Fun, L, [X | R], Rs) 2700 end; 2701 false -> 2702 case Fun(X, Z) of 2703 true -> 2704 case Fun(Z, X) of 2705 true -> % Z equal to X 2706 ufsplit_1(Y, X, Fun, L, R, Rs); 2707 false -> 2708 ufsplit_1(Y, Z, Fun, L, [X | R], Rs) 2709 end; 2710 false when R == [] -> 2711 ufsplit_1(Y, X, Fun, L, [Z], Rs); 2712 false -> 2713 ufsplit_1_1(Y, X, Fun, L, R, Rs, Z) 2714 end 2715 end; 2716ufsplit_1(Y, X, Fun, [], R, Rs) -> 2717 rufmergel([[Y, X | R] | Rs], [], Fun). 2718 2719%% X < Y 2720ufsplit_1_1(Y, X, Fun, [Z | L], R, Rs, S) -> 2721 case Fun(Y, Z) of 2722 true -> 2723 case Fun(Z, Y) of 2724 true -> % Z equal to Y 2725 ufsplit_1_1(Y, X, Fun, L, R, Rs, S); 2726 false -> 2727 ufsplit_1_1(Z, Y, Fun, L, [X | R], Rs, S) 2728 end; 2729 false -> 2730 case Fun(X, Z) of 2731 true -> 2732 case Fun(Z, X) of 2733 true -> % Z equal to X 2734 ufsplit_1_1(Y, X, Fun, L, R, Rs, S); 2735 false -> 2736 ufsplit_1_1(Y, Z, Fun, L, [X | R], Rs, S) 2737 end; 2738 false -> 2739 case Fun(S, Z) of 2740 true -> 2741 case Fun(Z, S) of 2742 true -> % Z equal to S 2743 ufsplit_1_1(Y, X, Fun, L, R, Rs, S); 2744 false -> 2745 ufsplit_1(Z, S, Fun, L, [], [[Y, X | R] | Rs]) 2746 end; 2747 false -> 2748 ufsplit_1(S, Z, Fun, L, [], [[Y, X | R] | Rs]) 2749 end 2750 end 2751 end; 2752ufsplit_1_1(Y, X, Fun, [], R, Rs, S) -> 2753 rufmergel([[S], [Y, X | R] | Rs], [], Fun). 2754 2755%% Descending. 2756ufsplit_2(Y, [Z | L], Fun, R) -> 2757 case Fun(Y, Z) of 2758 true -> 2759 case Fun(Z, Y) of 2760 true -> % Z equal to Y 2761 ufsplit_2(Y, L, Fun, R); 2762 false -> 2763 ufsplit_1(Z, Y, Fun, L, [], [lists:reverse(R, [])]) 2764 end; 2765 false -> 2766 ufsplit_2(Z, L, Fun, [Y | R]) 2767 end; 2768ufsplit_2(Y, [], _Fun, R) -> 2769 [Y | R]. 2770 2771ufmergel([[H1 | T1], T2 | L], Acc, Fun) -> 2772 ufmergel(L, [ufmerge2_2(H1, T1, Fun, T2, []) | Acc], Fun); 2773ufmergel([L], [], _Fun) -> 2774 L; 2775ufmergel([L], Acc, Fun) -> 2776 rufmergel([lists:reverse(L, []) | Acc], [], Fun); 2777ufmergel([], Acc, Fun) -> 2778 rufmergel(Acc, [], Fun). 2779 2780rufmergel([[H2 | T2], T1 | L], Acc, Fun) -> 2781 rufmergel(L, [rufmerge2_1(T1, H2, Fun, T2, []) | Acc], Fun); 2782rufmergel([L], Acc, Fun) -> 2783 ufmergel([lists:reverse(L, []) | Acc], [], Fun); 2784rufmergel([], Acc, Fun) -> 2785 ufmergel(Acc, [], Fun). 2786 2787%% umerge/3 2788 2789%% Elements from the first list are kept and prioritized. 2790%% HdM before H2. 2791ufmerge2_1([H1 | T1], H2, Fun, T2, M, HdM) -> 2792 case Fun(H1, H2) of 2793 true -> 2794 ufmerge2_1(T1, H2, Fun, T2, [H1 | M], H1); 2795 false -> 2796 case Fun(H2, HdM) of 2797 true -> % HdM equal to H2 2798 ufmerge2_2(H1, T1, Fun, T2, M); 2799 false -> 2800 ufmerge2_2(H1, T1, Fun, T2, [H2 | M]) 2801 end 2802 end; 2803ufmerge2_1([], H2, Fun, T2, M, HdM) -> 2804 case Fun(H2, HdM) of 2805 true -> % HdM equal to H2 2806 lists:reverse(T2, M); 2807 false -> 2808 lists:reverse(T2, [H2 | M]) 2809 end. 2810 2811ufmerge2_2(H1, T1, Fun, [H2 | T2], M) -> 2812 case Fun(H1, H2) of 2813 true -> 2814 ufmerge2_1(T1, H2, Fun, T2, [H1 | M], H1); 2815 false -> 2816 ufmerge2_2(H1, T1, Fun, T2, [H2 | M]) 2817 end; 2818ufmerge2_2(H1, T1, _Fun, [], M) -> 2819 lists:reverse(T1, [H1 | M]). 2820 2821%% rumerge/3 2822 2823rufmerge2_1([H1 | T1], H2, Fun, T2, M) -> 2824 case Fun(H1, H2) of 2825 true -> 2826 rufmerge2_2(H1, T1, Fun, T2, M, H2); 2827 false -> 2828 rufmerge2_1(T1, H2, Fun, T2, [H1 | M]) 2829 end; 2830rufmerge2_1([], H2, _Fun, T2, M) -> 2831 lists:reverse(T2, [H2 | M]). 2832 2833%% H1 before H2M 2834rufmerge2_2(H1, T1, Fun, [H2 | T2], M, H2M) -> 2835 case Fun(H1, H2) of 2836 true -> 2837 rufmerge2_2(H1, T1, Fun, T2, [H2M | M], H2); 2838 false -> 2839 case Fun(H2M, H1) of 2840 true -> % H2M equal to H1 2841 rufmerge2_1(T1, H2, Fun, T2, [H1 | M]); 2842 false -> 2843 rufmerge2_1(T1, H2, Fun, T2, [H1, H2M | M]) 2844 end 2845 end; 2846rufmerge2_2(H1, T1, Fun, [], M, H2M) -> 2847 case Fun(H2M, H1) of 2848 true -> 2849 lists:reverse(T1, [H1 | M]); 2850 false -> 2851 lists:reverse(T1, [H1, H2M | M]) 2852 end. 2853 2854