class Interval:
    def __init__(self, minimum, maximum):
        self.min = minimum
        self.max = maximum

    def length(self):
        self.length = self.max - self.min
        return (self.length)

    def mid(self):
        self.mid = (self.min + self.max) / 2
        return (self.mid)

    def contains(self, x):
        if x >= self.min and x <= self.max:
            return True
        else:
            return False

    def __add__(self, other):
        newmax = self.max + other.max
        newmin = self.min + other.min
        return (Interval(newmin, newmax))

    def __sub__(self, other):
        newmin = self.min - other.max
        newmax = self.max - other.min
        return (Interval(newmin, newmax))

    def __repr__(self):
        return ("[" + str(self.min) + "," + str(self.max) + "]")

    def __mul__(self, other):
        newmin = min(self.max * other.min, self.max * other.max, self.min * other.min, self.min * other.max)
        newmax = max(self.max * other.min, self.max * other.max, self.min * other.min, self.min * other.max)
        return (Interval(newmin, newmax))

    def evalPolynomial(self, a):
        if len(a) == 1:
            #print(Interval(self.min, self.max))
            return (Interval(self.min, self.max) * (Interval(a[0], a[0])))
        else:
            # print(Interval(self.min,self.max))
            # print(a[0])
            return (Interval(a[0], a[0]) + (Interval(self.min, self.max) * (self.evalPolynomial(a[1:]))))


def findZeros(a, I, zeros=[]):
    if I.evalPolynomial(a).contains(0) == False:
        return None
    if I.length() < 0.000001 and I.evalPolynomial(a).contains(0):
        zeros.append(I.mid())
        return None
    findZeros(a, Interval(I.min, I.mid()), zeros)
    findZeros(a, Interval(I.mid, I.max), zeros)
    return (zeros)


a = Interval(-0.0000001, 0.0000000001)
b = Interval(12, 26)
d = [1, 0, 5, 2, 13, 9]
dd = Interval(1, 1)

print(findZeros([-6, 11, -6, 1], Interval(0, 4), []))

print(Interval(0,4).evalPolynomial([-6, 11, -6, 1]).contains(0))
print(Interval(2,4).evalPolynomial([-6, 11, -6, 1]).contains(0))
print(Interval(3,4).evalPolynomial([-6, 11, -6, 1]).contains(0))

print(findZeros([1,2,1],Interval(-1,1),[]))