%% lists.pl
%%
%% Login(s):
%%
%% CS 60 Hw 4, part 1
%%
%%
%% Some "nice" prolog settings:
%% See www.swi-prolog.org/pldoc/man?predicate=current_prolog_flag/2
%% This one prompts only when there are variables:
:- set_prolog_flag( prompt_alternatives_on, groundness ).
% This one sets some reasonable display defaults:
:- set_prolog_flag(toplevel_print_options,
	  [quoted(true),
	   portray(true),
	   attributes(portray),
	   max_depth(999),
	   priority(699)]).


%% a couple of example predicates that might be helpful...

%
% member( E, L ) should be true if
%         E is a top-level member of the list L
% member should work when E is a variable or bound to a value;
%         L should only be bound to a value
%
member( E, [E|_] ).
member( E, [_|R] ) :- member( E, R ).

% The following tests can be run by typing:
% run_tests(member)
:- begin_tests(member).
test(memberT1) :- member(1, [1, 2, 3]), !.
test(memberT2) :- member(2, [1, 2, 3]), !.
test(memberT3) :- member(3, [1, 2, 3]), !.
test(memberT4) :- member(b, [a, b, c]), !.
test(memberT5) :-
	setof(One, member(One, [1,2,3,4]), All),
	All == [1,2,3,4].
test(memberT6) :- \+member(5, [1,2,3]).
% no additional tests needed for member
:- end_tests(member).

%
% reverse( L, Rev ) should be true if Rev is the reverse of L
% reverse should work when Rev is a variable or bound;
%          L should only be bound to a value
%
reverse( [], [] ).   % base case ~ though they don't always involve [] in Prolog!
reverse( [F|R], Rev ) :- reverse( R, Tmp ), append( Tmp, [F], Rev ).

% The following tests can be run by typing:
% run_tests(reverse)
:- begin_tests(reverse).
test(reverseT1) :- reverse([1]    , [1])    , !.
test(reverseT2) :- reverse([1,2]  , [2,1])  , !.
test(reverseT3) :- reverse([3,2,1], [1,2,3]), !.
test(reverseT4) :- reverse([a,b,c], W), W==[c,b,a], !.
% no additional tests needed for reverse
:- end_tests(reverse).

%
% range( L, H, List ) should be true if
%  List is a list of integers from L, an int
%  to H, an int, inclusive of both endpoints
% both L and H should be bound to ints.
% List will then be generated.
%
range(L,H,[]) :- L >= H.
range(L,H,[L|R]) :-
	L < H, M is L+1, range(M,H,R).


%% Here are commented-out placeholders for this week's predicates...
%% Be sure to comment each predicate you write!



%% removeOne( E, L, NewL )

% The following tests can be run by typing:
% run_tests(removeOne)
:- begin_tests(removeOne).
test(removeOneT1) :- removeOne(a, [a], []), !.
test(removeOneT2) :- \+removeOne(a, [], []), !.
test(removeOneT3) :- removeOne(b, [a,b,a,b],[a,b,a]), !.
test(removeOneT4) :- \+removeOne(d, [a,b,c,a],_), !.
test(removeOneT5) :-
	setof([E,X], removeOne(E, [1,2,3], X), Answer),
	sort(Answer, Sorted),
	Sorted == [[1,[2,3]],[2,[1,3]],[3,[1,2]]].
% add additional tests below:

:- end_tests(removeOne).



%% count( E, L, N )



% The following tests can be run by typing:
% run_tests(count)
:- begin_tests(count).
test(countT1) :- count(spam, [oh,spam,spam,we,love,spam], 3), !.
test(countT2) :-
	setof(N, count(oh, [oh,spam,spam,we,love,spam], N), Answer),
	Answer = [1].
test(countT3) :-
	setof(N, count(spam, [oh,spam,spam,we,love,spam], N), Answer),
	Answer = [3].
test(countT4) :-
	setof(N, count(alien, [oh,spam,spam,we,love,spam], N), Answer),
	Answer = [0].
test(countT5) :-
	setof(N, count(we, [oh,spam,spam,we,love,spam], N), Answer),
	Answer = [1].

% add additional tests below:

:- end_tests(count).






%% find( Pattern, Target, Index )

% The following tests can be run by typing:
% run_tests(find)
:- begin_tests(find).
test(findT1) :- find([1, 2], [1, 2, 1, 2, 1], 0), !.
test(findT2) :-	\+find([], [1, 2, 1, 2, 1], _).
test(findT3) :- setof(N, find([1,2],[1,2,1,2,1],N), Answer),
    Answer==[0, 2].
test(findT4) :- setof([N,P], find(P,[a,c,a,c],N),Answer),
    Answer == [[0, [a]], [0, [a, c]],
	       [0, [a, c, a]], [0, [a, c, a, c]],
	       [1, [c]], [1, [c, a]], [1, [c, a, c]],
	       [2, [a]], [2, [a, c]], [3, [c]]].
% add additional tests below:

:- end_tests(find).



%% depth( E, Tree, N )

% a helper predicate to define a tree
tree1( [ 42, [ 20, [10, [5, [], []], [18, [], []]], [] ],
             [ 100, [67, [50, [], []], []], [150, [], [2009, [], []]] ] ] ).

% NOTE - YOU SHOULD MAKE A NEW SMALL TREE!!!!
% & should write these tests BEFORE writing your code

% The following tests can be run by typing:
% run_tests(depth)
:- begin_tests(depth).
test(depthT1) :- tree1( T1 ), depth( 42, T1, N ),
	T1==[42,[20,[10,[5,[],[]],[18,[],[]]],[]],[100,[67,[50,[],[]],[]],[150,[],[2009,[],[]]]]],
	N==0, !.
test(depthT2) :-  tree1(T1 ),
	          setof(E, depth(E,T1,3),Answer),
		  T1 = [42,[20,[10,[5,[],[]],[18,[],[]]],[]],[100,[67,[50,[],[]],[]],[150,[],[2009,[],[]]]]],
		  Answer = [5,18,50,2009], !.
% add additional tests below:

:- end_tests(depth).



%% insert( E, Tree, NewTree )

% The following tests can be run by typing:
% run_tests(insert)
:- begin_tests(insert).
test(insertT1) :-  tree1( T1 ),
	           insert( 43, T1, NewTree ),
		   T1 = [42,[20,[10,[5,[],[]],
				 [18,[],[]]],[]],
			 [100,[67,[50,[],[]],[]],
			  [150,[],[2009,[],[]]]]],
		   NewTree = [42,[20,[10,[5,[],[]],
				      [18,[],[]]],[]],
			      [100,[67,[50,[43,[],[]],[]],[]],
			       [150,[],[2009,[],[]]]]], !.

test(insertT2) :-  tree1( T1 ),
		   insert( 41, T1, NewTree ),
		   T1 = [42,[20,[10,[5,[],[]],[18,[],[]]],
			     []],[100,[67,[50,[],[]],[]],
				  [150,[],[2009,[],[]]]]],
		   NewTree = [42,[20,[10,[5,[],[]],
				      [18,[],[]]],[41,[],[]]],
			      [100,[67,[50,[],[]],[]],
			       [150,[],[2009,[],[]]]]], !.
% add additional tests below:

:- end_tests(insert).





%% path( A, B, Graph, Path )


% NOTE - YOU SHOULD MAKE A NEW SMALL GRAPH!!!!
% & should write these tests BEFORE writing your code


% a helper predicate to define a graph
graph1(  [ [a,b], [b,c], [c,d], [b,w], [w,x], [x,z], [b,z] ] ).

% The following tests can be run by typing:
% run_tests(path)
:- begin_tests(path).
test(pathT1) :- graph1(G1),
	        path( a, z, G1, P ),
		G1 = [[a,b],[b,c],[c,d],[b,w],[w,x],[x,z],[b,z]],
		P = [a,b,w,x,z], !.

test(pathT2) :- graph1(G1),
	        setof( P, path( a, z, G1, P ), Answer),
		G1 = [[a,b],[b,c],[c,d],[b,w],[w,x],[x,z],[b,z]],
		Answer = [[a,b,w,x,z],[a,b,z]], !.

test(pathT3) :- graph1( G1 ),
	        G2 = [ [z,a] | G1 ],
		setof( Path, path( a, z, G2, Path ),Answer ),
		member( [a,b,z], Answer ),
		G1 = [[a,b],[b,c],[c,d],[b,w],[w,x],[x,z],[b,z]],
		G2 = [[z,a],[a,b],[b,c],[c,d],[b,w],[w,x],[x,z],[b,z]], !.
% add additional tests below:

:- end_tests(path).