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