"""Compute the Newton's Interpolation Polynomial"""

def newtonPolValue(n, nodesX, coeffs, t):
    '''
    Value of Newton interpolation polynomial in point t
        n       Number of nodes (degree of polynomial = n-1)
        nodesX  Nodes of interpolation: x0, x1, ..., xn
        coeffs  Coefficients of Newton polynomial
        t       Point of interpolation
    '''
    s = coeffs[0]
    p = 1.
    for i in range(1, n+1):
        p *= (t - nodesX[i-1]);
        s += coeffs[i] * p;
    return s

def computeNewtonPol(nodes):
    '''
    Compute the coefficients of Newton
    interpolation polynomial
        n       Number of nodes - 1 == degree of polynomial
        nodes   Nodes of interpolation:
                [(x0, y0), ..., (xn, yn)]
        Return:
        coeffs  Coefficients of Newton polynomial
    '''
    n = len(nodes) - 1  # Degree of polynomial
    coeffs = [0.0]*(n + 1)

    nodesX = [t[0] for t in nodes]
    coeffs[0] = nodes[0][1]
    for i in range(1, n + 1):
        p = 1.
        for j in range(0, i):
            p *= (nodes[i][0] - nodes[j][0])
        coeffs[i] = (
            (nodes[i][1] -
            newtonPolValue(i-1, nodesX, coeffs, nodes[i][0])) / p
        )
    return coeffs