%
% This file contains example code for manipulating the data structures
% in the assignment.  You do not need to use any of this code except the
% 'op' declarations, but you may include as much or as little as you 
% like in your submission. 
%
% IF YOU ARE HAVING TROUBLE, YOU SHOULD TRY TO READ AND UNDERSTAND THE CODE
% HERE BEFORE ATTEMPTING YOUR SOLUTION. ALSO READ THE HINTS IN THE ASSIGNMENT!
%

%
% YOU WILL NEED THE FOLLOWING 'op' DECLARATIONS IN YOUR SUBMISSION:
%

:- op(400,xfy,'*').
:- op(500,xfy,'+').

%
% Write numeral - writes a Peano arithmetic numeral in conventional form.
%

write_numeral(X) :-
	numeral_to_number(X,N),
	write(N).

numeral_to_number(0,0).
numeral_to_number(s(X),NN) :-
	numeral_to_number(X,N),
	NN is N + 1.

%
% Write polynomial - writes a well formed polynomial in easier to read form.
% 


write_polynomial(X + Y) :-
	write_monic(X),
	write(' + '),
	write_polynomial(Y).

write_polynomial(X) :-
	X \= _ + _,
	write_monic(X).

write_monic(Num) :-
	Num \= _ * _,
	write_numeral(Num).
write_monic(Num * EL) :-
	write_numeral(Num),
	write_explist(EL).

write_explist(Exp) :-
	Exp \= _ * _,
	write(' * '),
	write_exponent(Exp).

write_explist(Exp * Rest) :-
	write(' * '),
	write_exponent(Exp),
	write_explist(Rest).

write_exponent(A^Y) :-
	write(A),
	write('^'),
	write_numeral(Y).


%
% Write matrix - writes a matrix in easier to read form.
%

write_matrix([]).
write_matrix([Row|Rest]) :-
	write_row(Row),
	write_matrix(Rest).

write_row(Row) :-
	write(' [ '),
	write_row_1(Row),
	write(' ] \n').

write_row_1([]).
write_row_1([Head|Rest]) :-
	write_polynomial(Head),
	write('\t\t'),
	write_row_1(Rest).

%
% Standard Peano arithmetic defintions for "add" and "multiply"
%

add(X,0,X).
add(X,s(Y),Z) :- add(s(X),Y,Z).

multiply(0,_,0).
multiply(s(X),Y,Z) :- multiply(X,Y,ZZ), add(Y,ZZ,Z).
	
gt(s(_),0).
gt(s(X),s(Y)) :- gt(X,Y).


%
%  SAMPLE CODE FOR COMPARING TWO MONIC POLYNOMIALS
%
%  YOU MAY FIND THIS USEFUL FOR REFERENCE, OR CALL THIS FROM YOUR PROGRAM
%
% Compare monics  - determines if the degree of two monics is greater
%  than, equal to or less than the other.
%

degree_greater_than(_ * M1,_ * M2) :-
	total_degree(M1,0,D1),
	total_degree(M2,0,D2),
	gt(D1,D2).

degree_greater_than(_ * M1,_ * M2) :-
	total_degree(M1,0,D),
	total_degree(M2,0,D),
	M1 @< M2.

%
% total_degree - tail recursively find the total degree of a list
%  of exponents
%

total_degree(_^Y,N,F) :-
	add(Y,N,F).

total_degree(_ ^ Y * R,N,F) :-
	add(Y,N,NN),
	total_degree(R,NN,F).