import matplotlib.pyplot as plt
import random


class LagrangePolynom:
	def __init__(self, x_list, y_list):
		self.x_list = list(x_list)
		self.y_list = list(y_list)
		self.denominators  = []
		self.n = len(x_list)
		for i in range(self.n):
			denom = 1
			for j in range(self.n):
				if i != j:
					denom *= x_list[i] - x_list[j]
			self.denominators.append(denom)
	def __call__(self, x):
		if x in self.x_list:
			return self.y_list[self.x_list.index(x)]
		full_numerator = 1
		for j in range(self.n):
			full_numerator *= x - self.x_list[j]
		result = 0
		for i in range(self.n):
			P = full_numerator / (self.denominators[i] * (x - self.x_list[i]))
			result += self.y_list[i] * P
		return result

a, b = -2,2
N = 25
x_list = [a +i*(b-a)/(N - 1) for i in range(N)]
y_list = [random.random() for i in range(N)]


N = 500
plt.axis('equal')
plt.plot([a, b], [0,0], "--")
plt.plot(x_list, y_list, "*")

#P = LagrangePolynom(x_list, y_list)

if len(x_list) % 3 == 1:
	i = 0
	j = 0
	while i < len(x_list) - 3 :
		new_x = []
		new_y = []
		for a in x_list[j:j+4]:
			new_x.append(a)
		for a in y_list[j:j+4]:
			new_y.append(a)
		P = LagrangePolynom(new_x, new_y)
		a,b = x_list[j], x_list[j+3]
		x = [a + i*(b-a)/(N - 1) for i in range(N)]
		y = list(map(P,x))
		plt.plot(x,y,color="red")
		j += 3
		i += 3
elif len(x_list) % 3 == 2:
	i = 0
	j = 0
	while i < len(x_list) - 4 :
		new_x = []
		new_y = []
		for a in x_list[j:j+4]:
			new_x.append(a)
		for a in y_list[j:j+4]:
			new_y.append(a)
		P = LagrangePolynom(new_x, new_y)
		a,b = x_list[j], x_list[j+3]
		x = [a + i*(b-a)/(N - 1) for i in range(N)]
		y = list(map(P,x))
		plt.plot(x,y,color="red")
		j += 3
		i += 3
	new_x = (x_list[j],x_list[j+1])
	new_y = (y_list[j],y_list[j+1])
	P = LagrangePolynom(new_x, new_y)
	a,b = x_list[j], x_list[j + 1]
	x = [a + i*(b-a)/(N - 1) for i in range(N)]
	y = list(map(P,x))
	plt.plot(x,y,color="red")
else:
	i = 0
	j = 0
	while i < len(x_list) - 5 :
		new_x = []
		new_y = []
		for a in x_list[j:j+4]:
			new_x.append(a)
		for a in y_list[j:j+4]:
			new_y.append(a)
		P = LagrangePolynom(new_x, new_y)
		a,b = x_list[j], x_list[j+3]
		x = [a + i*(b-a)/(N - 1) for i in range(N)]
		y = list(map(P,x))
		plt.plot(x,y,color="red")
		j += 3
		i += 3
	new_x = (x_list[j],x_list[j+1], x_list[j + 2])
	new_y = (y_list[j],y_list[j+1], y_list[j + 2])
	P = LagrangePolynom(new_x, new_y)
	a,b = x_list[j], x_list[j + 2]
	x = [a + i*(b-a)/(N - 1) for i in range(N)]
	y = list(map(P,x))
	plt.plot(x,y,color="red")
plt.show()