class Rational(object):
	def __init__(self, f_list, g_list):
		self.f = Polynomial(f_list)
		self.g = Polynomial(g_list)

	def __str__(self):
		f_str = str(self.f)
		g_str = str(self.g)
		# length of line between numerator and denominator
		# depends on length of strings
		line_length = max(len(f_str), len(g_str))
		# I join a list comprehension to make the line
		line = "".join(["-" for i in range(line_length)])
		# and join everything with newlines
		result = "\n".join([f_str, line, g_str])
		return result

	def add(self, other_rat):
		#	f1	 f2
		#	-- + --
		#	g1   g2
		f1 = self.f
		f2 = other_rat.f
		g1 = self.g
		g2 = other_rat.g
		# f1 * g2 + f2 * g1
		# ------------------
		# 		g1 * g2
		first_term = f1.multiply(g2)
		second_term = f2.multiply(g1)
		numerator = first_term.add(second_term)
		denominator = g1.multiply(g2)
		return Rational(numerator.coefficients, denominator.coefficients)

	def multiply(self, other_rat):
		#	f1	 f2
		#	-- * --
		#	g1   g2
		f1 = self.f
		f2 = other_rat.f
		g1 = self.g
		g2 = other_rat.g
		# 	f1 * f2
		# 	-------
		# 	g1 * g2
		numerator = f1.multiply(f2)
		denominator = g1.multiply(g2)
		return Rational(numerator.coefficients, denominator.coefficients)

	def derivative(self):
		f = self.f
		g = self.g
		# Formula:
		#	g*f' - f*g'
		#	----------
		#		g^2
		# first term is g*f'
		first_term = g.multiply(f.derivative())
		# second term is f*g'
		second_term = f.multiply(g.derivative())
		# we need to negate the second term
		neg_second_term_list = [-c for c in second_term.coefficients]
		neg_second_term = Polynomial(neg_second_term_list)
		# numerator is g*f' - f*g'
		numerator = first_term.add(neg_second_term)
		# denominator is g^2
		denominator = g.multiply(g)
		return Rational(numerator.coefficients, denominator.coefficients)


class Polynomial(object):
	# Constructor just takes a list of coefficients
	# Note that the coefficient lists go from
	# zero-th power to highest power
	# Opposite order from printing!
	def __init__(self, coefficients):
		assert type(coefficients) is list
		self.coefficients = coefficients
		self.degree = len(coefficients) - 1

	# Prints polynomial from greatest power first to lowest power last
	# (opposite from stored list)
	def __str__(self):
		if self.coefficients == []:
			return "0"
		poly_string = []
		coeffs = reversed(self.coefficients)
		degree = self.degree
		for i, coeff in enumerate(coeffs):
			power = degree - i
			if coeff == 0:
				continue
			if power == 0:
				poly_string.append(str(coeff))
			else:
				poly_string.append(str(coeff) + "x^" + str(power))
		poly_string = " + ".join(poly_string)
		return poly_string

	# This function sums two polynomials
	# by adding the coefficient lists element-wise
	def add(self, other_poly):
		p3 = []
		degree_diff = other_poly.degree - self.degree
		p1 = []
		p2 = []
		# One of the lists (p1 or p2) will need to be
		# padded with zeros
		# to get them to the same length
		# (I feel like there must be a better way though)
		if degree_diff >= 0:
			p1 = self.coefficients + [0 for i in range(degree_diff)]
			p2 = other_poly.coefficients
		else:
			p1 = other_poly.coefficients + [0 for i in range(-degree_diff)]
			p2 = self.coefficients
		# After padding, sum together the coefficients
		# element-wise
		for i in range(len(p1)):
			p3.append(p1[i] + p2[i])
		return Polynomial(p3)

	# This function multiplies two polynomials
	def multiply(self, other_poly):
		p1 = self.coefficients
		p2 = other_poly.coefficients
		n = len(p1)
		m = len(p2)
		matrix = [[0 for j in range(m)] for i in range(n)]
		for j in range(m):  # column index
			for i in range(n):  # row index
				# populate matrix
				matrix[i][j] = p1[i] * p2[j]
		p3 = [0 for k in range(m + n - 1)]
		for k in range(m + n - 1):
			j = min(k, m - 1)
			i = max(0, k - (m - 1))
			while i < n and j >= 0:
				# sum over diagonals
				p3[k] += matrix[i][j]
				i += 1
				j -= 1
		return Polynomial(p3)

	# This function returns the derivative of the Polynomial
	# Recall that each component a*x^n is mapped to (a*n)*x^(n-1)
	def derivative(self):
		coeffs = self.coefficients
		result = [i * coeffs[i] for i in range(self.degree + 1)]
		result = result[1:]
		return Polynomial(result)


def main():
	# Here I make two polynomials, and test the
	# results of addition, multiplication, and
	# symbolic differentiation
	poly1 = Polynomial([1, 2, 3, 4, 5])
	poly2 = Polynomial([2, 4, 6])
	# Old testing for polynomials
	'''
	print("Poly 1: ")
	print(poly1)
	print()
	print("Poly 2: ")
	print(poly2)
	print()
	poly3 = poly1.add(poly2)
	print("Poly 1 + Poly 2: ")
	print(poly3)
	print()
	poly4 = poly2.multiply(poly1)
	print("Poly 1 * Poly 2: ")
	print(poly4)
	print()
	poly5 = poly1.derivative()
	poly6 = poly2.derivative()
	print("Derivative of Poly 1: ")
	print(poly5)
	print()
	print("Derivative of Poly 2: ")
	print(poly6)
	print()
	'''
	# new testing for rational functions
	rat1 = Rational(poly1.coefficients, poly2.coefficients)
	print("Rational function 1: ")
	print(rat1)
	print()
	rat2 = Rational(poly2.coefficients, poly1.coefficients)
	print("Rational function 1: ")
	print(rat1)
	print()
	rat3 = rat1.add(rat2)
	print("Rational 1 + Rational 2: ")
	print(rat3)
	print()
	rat4 = rat1.multiply(rat2)
	print("Rational 1 * Rational 2: ")
	print(rat4)
	print()
	rat1_diff = rat1.derivative()
	print("Derivative of rational function: ")
	print(rat1_diff)
	print()

	'''
Output:

Rational function 1:
5x^4 + 4x^3 + 3x^2 + 2x^1 + 1
-----------------------------
6x^2 + 4x^1 + 2

Rational function 1:
5x^4 + 4x^3 + 3x^2 + 2x^1 + 1
-----------------------------
6x^2 + 4x^1 + 2

Rational 1 + Rational 2:
25x^8 + 40x^7 + 46x^6 + 44x^5 + 71x^4 + 68x^3 + 50x^2 + 20x^1 + 5
-----------------------------------------------------------------
30x^6 + 44x^5 + 44x^4 + 32x^3 + 20x^2 + 8x^1 + 2

Rational 1 * Rational 2:
30x^6 + 44x^5 + 44x^4 + 32x^3 + 20x^2 + 8x^1 + 2
------------------------------------------------
30x^6 + 44x^5 + 44x^4 + 32x^3 + 20x^2 + 8x^1 + 2

Derivative of rational function:
60x^5 + 84x^4 + 72x^3 + 24x^2
---------------------------------
36x^4 + 48x^3 + 40x^2 + 16x^1 + 4
'''


if __name__ == "__main__":
	main()