#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
Polynom_mit_Horner.py für Aufgabe 35

Die Version der zugrunde liegenden Polynomklasse ist von Do, 01.12.
Der Infotext und nicht gebrauchte (außenliegende) Funktionen wurden hier der 
Übersicht halber weggelassen.
"""
class Polynom(object):
    import numpy as np
    import matplotlib.pyplot as plt

    def __init__(self, dp):
        if isinstance(dp, (int, float, complex)):
            dp = {0: dp}
        dp = {k: l for k, l in dp.items() if l != 0}
        if len(dp) == 0:
            dp = {0: 0}
        self.dp = dp
        self.degree = max(dp.keys())
        assert all(isinstance(x, int) and x >= 0 for x in dp.keys()),\
            "Die Exponenten (keys) müssen natürliche Zahlen (einschl. 0) sein."

    def __repr__(self):
        polystr = ''
        for k in sorted(self.dp):
            if isinstance(self.dp[k], complex):  # Klammern um komplexe Zahl
                polystr = polystr + f'+({self.dp[k]:.3f})*X^{ {k} }'
            elif round(self.dp[k]) == self.dp[k]:
                polystr = polystr + f'+{self.dp[k]:g}*X^{ {k} }'
            else:
                polystr = polystr + f'+{self.dp[k]:.3f}*X^{ {k} }'
        polystr = polystr.replace('*X^{0}', '')
        polystr = polystr.replace('X^{1}', 'X')
        polystr = polystr.replace('+-', '-')
        polystr = polystr.replace('/1', '')
        polystr = polystr.replace('+1*', '+')
        polystr = polystr.replace('-1*', '-')
        if polystr[0] == '+':
            polystr = polystr[1:]
        return 'Polynom: ' + polystr

    def __eq__(self, other):
        return self.dp == other.dp

    def __add__(self, other):
        """ Addition zweier Polynome oder eines Polynoms mit einem Skalar """
        if isinstance(other, (int, float, complex)):  # Skalare Addition
            other = Polynom(other)
        erg = dict((n, self.dp.get(n, 0) + other.dp.get(n, 0)) for n in
                   set(self.dp).union(set(other.dp)))
        return Polynom(erg)

# Umgekehrte Addition, so dass auch Skalar+Polynom funktioniert:
    __radd__ = __add__

    def __sub__(self, other):
        """ Substraktion zweier Polynomen oder eines Polynoms p mit einem Skalar a,
        d.h. p-a kann berechnet werden
        """
        if isinstance(other, (int, float, complex)):
            other = Polynom(other)
        erg = dict((n, self.dp.get(n, 0)-other.dp.get(n, 0)) for n in
                   set(self.dp).union(set(other.dp)))
        return Polynom(erg)

    def __rsub__(self, other):
        """ Subtraktion eines Skalars und eines Polynoms, d.h. a-p """
        if isinstance(other, (int, float, complex)):
            other = Polynom(other)
        return other - self

    def __call__(self, x):
        """ Auswertung des Polynoms """
        return sum([self.dp[k]*x**k for k in self.dp])

    def __mul__(self, other):
        """ Multiplikation eines Polynoms mit einem Skalar und
        Polynommultiplikation """
        erg = dict()
        if isinstance(other, (int, float, complex)):
            for k in self.dp:
                erg[k] = self.dp[k] * other
        else:
            for i in self.dp:
                for j in other.dp:
                    if i+j in erg:
                        erg[i+j] += self.dp[i]*other.dp[j]
                    else:
                        erg[i+j] = self.dp[i]*other.dp[j]
        return Polynom(erg)

# Umgekehrte Multiplikation, so dass auch Skalar*Polynom funktioniert:
    __rmul__ = __mul__

    def __pow__(self, n):
        """Potenzieren mit einer natürlichen Zahl"""
        if isinstance(n, int) and n>=0:
            erg = Polynom(1)
            for k in range(n):
                erg *= self
            return erg
        else:
            raise NotImplementedError()

    def diff(self):
        """ Ableitung des Polynoms """
        erg = dict()
        if self.degree == 0:
            erg[0] = 0
        else:
            for i in self.dp:
                if i != 0:
                    erg[i-1] = self.dp[i]*i
        return Polynom(erg)

    def integrate(self):
        """Stammfunktion des Polynoms"""
        erg = dict()
        for i in self.dp:
            erg[i+1] = self.dp[i]/(i+1)
        return Polynom(erg)

    def integral(self, a, b):
        """Wert des Integrals von a bis b"""
        intPol = self.integrate()
        return intPol(b) - intPol(a)

    def __neg__(self):
        """ Vorzeichen des Polynoms p ändern, d.h. -p funktioniert """
        return -1*self

    def __truediv__(self, other):
        """Division eines Polynoms p mit einem Skalar a, d.h. p/a ist definiert,
        und Polynomdivision von p durch q (ÜA)
        Hierbei gilt p = Q*q + r für Polynome Q und r (mit grad(r)<grad(Q)).
        Die Ausgabe von p/q soll ein Tupel mit den Werten (Q, q, r) sein """
        if isinstance(other, (int, float, complex)):
            erg = dict((n, self.dp[n]/other) for n in self.dp)
            return Polynom(erg)
        else:
            p = self
            q = other
            m = self.degree
            n = other.degree
            if n == 0:
                if q.dp[0] == 0:
                    raise ZeroDivisionError()
                else:
                    return Polynom(dict((n, p.dp[n]/q.dp[0]) for n in p.dp)), q, Polynom({0: 0})
            if m < n:
                return (Polynom({0: 0}), q, p)
            r = p
            Q = {}
            # Polynomdivision über while-Schliefe wie im Pseudocode
            while r.degree >= n:
                d = r.dp[r.degree] / q.dp[n]
                grad = r.degree - n
                Q[grad] = d
                r -= q*Polynom({grad: d})
                r.dp[grad + n] = 0
                r = Polynom(r.dp)
            return Polynom(Q), q, r

    def __mod__(self, other):
        """ Modulo-Rechnung mit Polynomen"""
        return (self/other)[-1]

    def plot(self, fig=None, ax=None, xmin=0, xmax=1, num=100, style='k--s',\
             method=None):
        """ Plotroutine für Klasse Polynom
         fig -- Figurehandle von pyplot.figure() \n
         ax -- Koordinatensysterm \n
        """
        if fig == None:
            fig = self.plt.figure()
        if ax == None:
            ax = fig.add_subplot(111)
        x = self.np.linspace(xmin, xmax, num)
        if method is None:
            ax.plot(x, self(x), style, label=f'${self}$')
        elif method == 'Horner':
            ax.plot(x, self.Horner(x), style, label=f'${self}$ (Horner)')
        else:
            raise NotImplementedError("Verfahren zur Auswertung nicht implementiert")
        ax.legend()
        return fig, ax
    
    # Achtung: Hier sind 4 Fehler versteckt!
    def Horner(self, x):
        erg = 1
        mk = self.degree
        for k in sorted(self.dp, reverse = true):
            erg = self.dp[k+1] + erg*x**(k - mk)
            mk = k
        # Die folgende If-Abfrage fehlte in der ersten Version von Polynom_mit_
        # Horner.py, ist aber notwendig, damit das Verfahren auch für Polynome
        # ohne konstantes Glied funktioniert.
        # Die 4 Fehler befinden sich oberhalb dieses Kommentares.
        if not 0 in self.dp:
            erg = erg*x**mk
        return erg

# BEISPIEL:
# Auwertung eines Polynoms mit beiden Methoden zum Testen
p = Polynom({7:1/2, 6:-7/2, 5:21/2, 4:-35/2, 3:35/2, 2:-21/2,1:7/2, 0:-1/2})
print(p(1))
print(p.Horner(1))
# Hinweis zum Plot: Damit zwei Polynome in ein Bild geplottet werden können,
# muss jetzt ein Figure-Objekt und ein Axes-Objekt übergeben werden.
#fig1 = plt.figure(1)
#ax1 = fig.add_subplot(111)
#p.plot(fig1, ax1, ...anderer Input...)