% Author: Alex Roque
% Assignment #: 2
% Due Date: 09/25/01
% Program Title: Assignment 2
% Program Description: This assignment writes the following prolog predicates
% integer_list(List), subsequence(List1, List2), flatten(List1, List2), add_multi(Multi1, Multi2, Sum)
%
% I certify that this is my work and have not consulted with anyone else.
%
%
%

% integer_List gives is satisfied if every member of the list is an integer
integer_list([]).		 % base case
integer_list([Head|Tail]) :-
	integer(Head),
	integer_list(Tail).

% subsequence(List1,List2) is satisfied if all members of List1 occur in List2 in 
% the order in which they occur in List1.
subsequence([],[]).		% base case
subsequence([Head|Tail],[Head1|Tail1]) :-
	Head==Head1,
	reduceListUntilX(Head1,[Head1|Tail1],List1),
	reduceListUntilX(Head,[Head|Tail],List),
	subsequence(List,List1);
	del(Head1, [Head1|Tail1], List1),
	subsequence([Head|Tail],List1).

% flatten(List1,List2) takes as input a list. Flatten copies all atoms that occur 
% in List1 onto List2, in the order in which they occur in List1.
flatten([Head|Tail],List) :-
	flatten(Head,FlatHeadList),
	flatten(Tail,FlatTailList),
	conc(FlatHeadList,FlatTailList,List).
flatten([],[]).			%base [] case
flatten(X,[X]).			%base non-list case

% if X/p is in Multi1 and X/Q is in Multi2, the X/R is in Multi, where R is the 
% sum of P and Q.
% if X/P is a member of one of the lists Multi1 and Multi2, but the other one  
% does not contain an element X/Q, then X/P is in Multi.
add_multi([],[],[]).
add_multi([Head1|Tail1],[Head2|Tail2],List) :-
	member(Head1, [Head2|Tail2]),
	add_multi([Head1|Tail1],Tail2,List);
	member(Head1, [Head2|Tail2]),
	add(Head1,Head2,List),
	del(Head1,[Head2|Tail2],deletedList),
	add_multi(Tail1,deletedList,List);
	add_all(Head2,List,List).

%adds all elements from one list to another
add_all(X,[],[X]).	
add_all([Head|Tail], List, NewList):-
	add_all(Tail,[Head|List],NewList).

% X is a member of List
member(X, [X|_Tail]).
member(X, [_Head|Tail] ) :-
	member(X,Tail).

% conc(List1,List2,List3) concates List1 and List 2 into List3.
conc([X|L1],L2,[X|L3]) :-
	conc(L1,L2,L3).

% performs addition onto list
add(X,[],[X]).
add(X,List, [X|List]).

% deletes from list
del(X,[X|Tail],Tail).
del(X,[Y|Tail],[Y|Tail1]) :-
	del(X,Tail,Tail1).

% reduces List until X
reduceListUntilX(X,[Head|Tail], NewList) :-
	X==Head,
	del(X,[Head|Tail], NewList);
	del(Head,[Head|Tail],List),	
	reduceListUntilX(X,List,NewList).	

% included from Handout 2b
reduce([],[]).
reduce([Head | Tail], [Head | R_Tail]) :-
	delete_all(Head, Tail, Tail1),
	reduce(Tail1, R_Tail).

delete_all(_X,[],[]).
delete_all(X,[X|Tail], R_Tail) :-
        % eliminate the Head and reduce the tail
        delete_all(X,Tail,R_Tail).
delete_all(X,[Y|Tail],[Y|R_Tail]) :-
        %Item1 is not equal to Item, so it's not eliminated
        delete_all(X,Tail,R_Tail).


% Individual Test

integer_list_test(L) :- 
	nl,tab(10),write('testing integer_test '),
	write(L), nl, test_integer_list(L).

test_integer_list(L) :- integer_list(L),
	nl,tab(10),write(L), write(' is a list of integers'),nl.
test_integer_list(L) :- 
        nl,tab(10),write(L), write(' is not a list of integers'),nl.

subsequence_test(L1,L2) :-
	nl,tab(10),write('testing subsequences '),
        write(L1),tab(5), write(L2), nl, test_subsequence(L1,L2).

test_subsequence(L1,L2) :- subsequence(L1,L2),
        nl,tab(10),write(L1),tab(5),write(L2), write(' L1 is subsequence of 
L2'),nl.
test_subsequence(L1,L2) :-
        nl,tab(10),write(L1),tab(5),write(L2), write(' L1 is not a 
subsequence of L2'),nl.	

flatten_test(L1,L2) :-
        nl,tab(10),write('flattening L1 '),
        write(L1),tab(5), nl, test_flatten(L1,L2).
      
test_flatten(L1,L2) :- flatten(L1,L2),
        nl,tab(10),write(L1), write(' L1 flatten is '),tab(5),write(L2),nl.

add_multi_test(L1,L2,L3) :-
        nl,tab(10),write('performing add_mult on '),
        write(L1),tab(5),write(L2), nl, test_add_multi(L1,L2,L3).

test_add_multi(L1,L2,L3) :- add_multi(L1,L2,L3),
        nl,tab(10),write(L3), write(' is add_multi of'),
	tab(5),write(L1),tab(5),write(L2),nl.

% Entire tests
go :- nl, tab(20), write('SOME TESTS'),
      nl, tab(20), write('=========='),nl,nl,
      integer_list_test([]),
      integer_list_test([1,3,a, 2.3]),
      integer_list_test([1,2,3]),
      integer_list_test([2,2.3,5]),
      subsequence_test([],[]),
      subsequence_test([a],[]),
      subsequence_test([a,b,b],[b,a,c,b,c,b]),
      subsequence_test([a,b,b],[b,a,b,a,b]),
      subsequence_test([b,a,b],[a,b,b,a,a]),
      flatten_test([],L),
      flatten_test([a,[],[[b,[c,a]],c],[[[b]],c],[[a],[[]]]],L),
      flatten_test([a,[b],c,[b]],L),
      add_multi_test([a/2,b/3,c/1],[a/1,c/5,d/2],L),
      add_multi_test([a/2,b/3],[],L).