% <PRE>
% Amzi! inc. list.pro library
%
% This file contains library predicates that perform
% various list utilities.  The .plm file must be loaded
% or linked with the project, and the module must be
% imported.
%
% To use from the listener:
% ?- load(list).
% ?- import(list).
%
% To use in a compiled application, link list.plm with the
% project and put the directive
% :- import(list).
% in the modules that use the list predicates.

:- module(list).
:- export( [
     append/3,            % join or split lists
     compare_lists/3,     % returns difference of two lists
     deleteN/4,           % delete the Nth element of a list
     flatten/2,           % flatten a list of nested lists
     insert/3,            % insert an item in a sorted list
     last_item/2,         % get last element of a list
     length/2,            % get the length of a list
     length_lte/2,        % compare lengths of lists
     length_gte/2,        % compare lengths of lists
     length_lt/2,         % compare lengths of lists
     length_gt/2,         % compare lengths of lists
     member/2,            % find or generate members of list
     nth_elem/3,          % find the nth element of a list
     permutation/3,       % permute elements of a list
     random_elem/2,       % pick a random element from a list
     remove/3,            % remove an element from a list
     remove_dups/2,       % remove duplicate elements from a list
     replace_elem/4,      % replace one occurence of element in a list
     replace_all_elem/4,  % replaces all occurrences of element in a list
     reverse/2,           % reverse a list
     shuffle/2,           % randomly shuffle a list
     sub_list/4,          % find a sub list in a list
     write_formatted/1,   % write a formatted list
     write_formatted/2,   % write a formatted list
     write_list/2,        % write separated list elements
     write_list/3,        % write separated list elements
     writeq_list/2,       % writeq separated list elements
     writeq_list/3        % writeq separated list elements
     ]).


%-----------------------------------------
% append(?L1, ?L2, ?L12)
%
% append/3 defines the relationship that lists L1 and L2,
% appended together, equal list L12.
%
% append/3 can be used in a number of different ways, depending
% on which arguments are instantiated.  If the first two are, it
% simply joins the two lists.  If just the third argument is, it
% generates all possible splittings of the list on backtracking.
%

append([], X, X).
append([A|X], Y, [A|Z]) :- append(X,Y,Z).

%-------------------------------------------
% compare_lists(+L1, +L2, -L3)
%
% compare_lists/3 returns, in L3, the elements that are in
% the first list, L1, and not in the second list, L2.
%

compare_lists([], _, []).
compare_lists([H|T], L, D) :-
  is_member(H, L), !,
  compare_lists(T, L, D).
compare_lists([H|T], L, [H|D]) :-
  compare_lists(T, L, D).

%-----------------------------------------
% deleteN(+NTH, -ELEM, +IN_LIST, -OUT_LIST)
%
% Delete the NTH elem of the list IN_LIST.  ELEM is bound
% to the deleted element and OUT_LIST is bound to the remaining
% list.
%

deleteN(1, H, [H|Z], Z).
deleteN(_, _, [], []) :- !, fail.
deleteN(N, H, [X|Z], [X|Z2]) :-
  NN is N - 1,
  deleteN(NN, H, Z, Z2).


%-----------------------------------------
% flatten(+L1, -L2)
%
% Take a list L1, that might have nested lists in it,
% and flatten it into list L2, that does not have any
% lists as elements.
%

/* The slow way.
flatten(X, X):-
	var(X).
flatten([], []).
flatten([H|T],L):-
	flatten(H,H1),
	flatten(T,T1),!,
	append(H1,T1,L).
flatten(H,[H]).
*/

% The fast way from Clocksin's Clause & Effect
flatten(In,Flat) :- flatpair(In,Flat-[]).

flatpair([],L-L) :- !.
flatpair([H|T], L1-L3) :- !, flatpair(H,L1-L2), flatpair(T,L2-L3).
flatpair(X,[X|Z]-Z).


%-----------------------------------------
% insert(+A, +L1, -L2)
% 
% Insert an item, A, in sorted order in a list L1, with
% resulting list L2.
%

insert(A, [A|Z], [A|Z]) :-
   !.
insert(A, [], [A]) :-
   !.
insert(A, [B|Z], [A,B|Z]) :-
   A @< B,
   !.
insert(B, [A|Y], [A|Z]) :-
   insert(B,Y,Z).

%-----------------------------------------
% last_item(+List, ?Elem)
%
% Find or test the last item of a list.
%

last_item([], _) :-
   !,
   fail.
last_item([X], X) :-
   !.
last_item([_|Z], X) :-
   last_item(Z, X).
   
%-----------------------------------------
% length(+L, -LENGTH)
% 
% Return the length of input list L.
%

length(L, N) :- length(L, 0, N).

  length([], N, N) :- !.
  length([_|Y], X, N) :-
    XX is X + 1,
    length(Y, XX, N).


%-----------------------------------------
% length_x(+L1, +L2)
%
% These predicates compare list lengths according to
% the pattern 'x', so length_lte(L1, L2) tests if the
% length of L1 is less than or equal the length of L2.
%

length_lte([], _).
length_lte([X1|Z1], [X2|Z2]) :-
  length_lte(Z1, Z2).

length_gte(L1, L2) :-
  length_lte(L2, L1).

length_lt([], [_|_]).
length_lt([X1|Z1], [X2|Z2]) :-
  length_lt(Z1, Z2).

length_gt(L1, L2) :-
  length_lt(L2, L1).


%-----------------------------------------
% member(?ITEM, ?LIST)
% 
% Find a member of a list, or generate all members
% of a list.
%

member(A, [A|_]).
member(A, [_|Z]) :- member(A, Z).


%-----------------------------------------
% nth_elem(+L, ?X, ?N)
% 
% Given a list, L, nth_elem finds either the position,
% starting at 1, of the elem X, or the elem at position
% N.
%

nth_elem(L, X, N) :-
  nth_elem(L, X, 1, N).

  nth_elem([X|Z], X, N, N).
  nth_elem([_|Z], X, A, N) :-
    AA is A + 1,
    nth_elem(Z, X, AA, N).  


%-----------------------------------------
% permutation(ListOfVars, List, LV)
% 
% permutation/3 assigns different values to the variables in the first
% list from the values in the second.  The third list is the list of
% unassigned values.  It works by simply deleting elements from the
% list using remove/3.  Because it is deleting an element which is an
% unbound variable, remove/3 simply deletes the next element and binds
% its value to the variable, thus providing a simple way to assign
% permuted values to a list of variables.  On backtracking, of course,
% delete simply binds the variable to the next element of the list and
% deletes it, thus eventually generating all permutations of a list.
%
% Example
% 
% ?- permutation([X,Y,Z], [a,b,c,d,e], L).
% 
% X = a
% Y = b
% Z = c
% L = [d, e] ;
% 
% X = a
% Y = b
% Z = d
% L = [c, e] ;
% ....
%

permutation([],L,L).
permutation([A|X],Y,L) :- atomic(A), permutation(X,Y,L).
permutation([A|X],Y,L) :- remove(A,Y,Y1), permutation(X,Y1,L).

%-----------------------------------------
% random_elem(+LIST, -ITEM)
%
% Pick a random element, ITEM, from a list, LIST.
%

random_elem(L, A) :-
   length(L, N),
   R is 1 + integer( random * N ),
   nth_elem(L, A, R).
   
%-----------------------------------------
% remove(?ITEM, +L1, -L2)
%
% Remove ITEM from list L1, leaving list L2.  Fails if
% no item to remove.
%

remove(A,[A|X],X).
remove(A,[B|X],[B|Y]) :- remove(A,X,Y).


%-----------------------------------------
% remove_duplicates(+L1, -L2)
% 
% remove_duplicates removes all the duplicates from L1 and
% returns the list of unique elements L2.  It is implemented
% to keep the first instance of each repeated element.
%

remove_dups(Lin, Lout) :-
   remove_dups(Lin, [], Lout).
   
remove_dups([], ACC, OUT) :-
   reverse(ACC, OUT).
remove_dups([X|Z], ACC, OUT) :-
   is_member(X, ACC),
   !,
   remove_dups(Z, ACC, OUT).
remove_dups([X|Z], ACC, OUT) :-
   remove_dups(Z, [X|ACC], OUT).

%-----------------------------------------
% replace_elem(+OldElem, +NewElem, +Lin, -Lout)
% 
% Replace first OldElem in list Lin, with NewElem, returning the new
% list in Lout.  Fails if nothing to replace.
%

replace_elem(_, _, [], _) :- !, fail.
replace_elem(Old, New, [Old|Z], [New|Z]) :- !.
replace_elem(Old, New, [X|Z], [X|Z2]) :-
  replace_elem(Old, New, Z, Z2).

%-----------------------------------------
% replace_all_elem(+OldElem, +NewElem, +Lin, -Lout)
% 
% Replace OldElem in list Lin, with NewElem, returning the new list
% in Lout.  Succeeds if nothing to replace.
%

replace_all_elem(_, _, [], []) :- !.
replace_all_elem(Old, New, [Old|Z], [New|Z2]) :-
  !,
  replace_all_elem(Old, New, Z, Z2).
replace_all_elem(Old, New, [X|Z], [X|Z2]) :-
  !,
  replace_all_elem(Old, New, Z, Z2).


%-----------------------------------------
% reverse(L1, L2)
% 
% Reverses L1 to L2.
%

reverse(A, Z) :- reverse(A, [], Z).

   reverse([], Z, Z).
   reverse([A|X], SoFar, Z) :- reverse(X, [A|SoFar], Z).


%-----------------------------------------
% shuffle(+L1, -L2)
% 
% Randomly shuffles the list L1 and returns L2, the
% shuffled list.  To get the same shuffling each time,
% use the built-in predicate seed_random/1 to provide an
% integer starting seed for random.
%

shuffle(Tin, Tout) :-
  shuffle1(Tin, [], Tout).

  shuffle1([], A, A).
  shuffle1(Tin, A, Tout) :-
    length(Tin, L),
    N is 1 + integer( random * L ),
    deleteN(N, Elem, Tin, Tx),
    shuffle1(Tx, [Elem|A], Tout).

%----------------------------------------
% sublist(Lin, Start, Finish, Lout)
%
% Either finds the sublist or returns it.
%

sub_list(List, Start, Finish, SubList) :-
   find_sublist(List, 1, Start, Finish, SubList).

find_sublist([X|Xs], S, S, F, [X|Ys]) :-
   find_finish(Xs, S, F, Ys).
find_sublist([X|Xs], Si, S, F, Sub) :-
   Sii is Si + 1,
   find_sublist(Xs, Sii, S, F, Sub).

find_finish(Xs, F, F, []) :-
   !.
find_finish([X|Xs], Fi, F, [X|Ys]) :-
   Fii is Fi + 1,
   find_finish(Xs, Fii, F, Ys).

%----------------------------------------
% write_formatted(+Formatted_List)
%
% write_formatted/1 writes a formatted list, allowing the
% format specifications in the form {Format}.  Formats
% can be nl, tab(N), quote, noquote, precision(N).
%

write_formatted(List) :-
   current_output(Out),
   write_formatted(Out, List).

write_formatted(Out, List) :-
   write_formatted(Out, List, []).

write_formatted(H, [], Formats) :-
   clear_formats(Formats).
write_formatted(H, [{F}|Z], InFormats) :-
   apply_format(H, F, InFormats, OutFormats),
   !, write_formatted(H, Z, OutFormats).
write_formatted(H, [A|Z], Formats) :-
   (member(quote, Formats) -> writeq(H,A); write(H,A)),
   write_formatted(H, Z, Formats).

apply_format(H, nl, Formats, Formats) :-
   !, nl(H).
apply_format(H, tab(N), Formats, Formats) :-
   !, tab(H,N).
apply_format(H, quote, InFormats, [quote|InCleared]) :-
   !,
   (remove(quote, InFormats, InCleared) -> true; InCleared = InFormats).
apply_format(H, noquote, InFormats, InCleared) :-
   !,
   (remove(quote, InFormats, InCleared) -> true; InCleared = InFormats).
apply_format(H, precision(N), InFormats, OutFormats) :-
   ( member(old_precision(_), InFormats) ->
       OutFormats = InFormats
       ;
       current_prolog_flag(decimal_places, DP),
       OutFormats = [old_precision(DP)|InFormats] ),
   set_prolog_flag(decimal_places, N).
   
clear_formats([]).
clear_formats([old_precision(P)|Z]) :-
   set_prolog_flag(decimal_places, P),
   !, clear_formats(Z).
clear_formats([_|Z]) :-
   clear_formats(Z).
   

%-----------------------------------------
% write_list(+L, +Separator)
% 
% write_list/2 writes each of the elements of a list, writing the
% Separator between elements.  For example, write_list(L, `\n  `),
% will write the elements of list L on newlines, indented two spaces.
%

write_list(List, Separator) :-
   current_output(Out),
   write_list(Out, List, Separator).
  
write_list(H, [], _).
write_list(H, [X], _) :-
  !, write(H, X).
write_list(H, [X|Y], Separator) :-
  write(H, X),
  write(H, Separator),
  write_list(H, Y, Separator).
  

%-----------------------------------------
% writeq_list(L, Separator)
% 
% writeq_list/2 writeqs each of the elements of a list, writing the
% Separator between elements.  For example, writeq_list(L, `\n  `),
% will writeq the elements of list L on newlines, indented two spaces.
%

writeq_list(List, Separator) :-
  current_output(Out),
  writeq_list(Out, List, Separator).

writeq_list(H, [X], _) :-
  !, writeq(H, X).
writeq_list(H, [X|Y], Separator) :-
  writeq(H, X),
  write(H, Separator),
  writeq_list(H, Y, Separator).


:- end_module(list).