from utils.memory_array import MemoryArray
from utils.memory_cell import MemoryCell
from utils.constants import MIN_VALUE
from utils.memory_manager import MemoryManager
from utils.memory_range import mrange
from utils.literal import Literal

def max_sequence_1(z: MemoryArray):
    n = z.length()
    m = MemoryCell(MIN_VALUE)
    s = MemoryCell()
    l = MemoryCell()
    r = MemoryCell()
    for i in mrange(n):
        for j in mrange(i, n):
            s.set(0)
            for k in mrange(i, j.succ()):
                s += z[k]
            if s > m:
                m.set(s)
                l.set(i)
                r.set(j)
    return m, l, r

def max_sequence_2(z: MemoryArray):
    n = z.length()
    m = MemoryCell(MIN_VALUE)
    s = MemoryCell()
    l = MemoryCell()
    r = MemoryCell()
    for i in mrange(n):
        s.set(0)
        for j in mrange(i, n):
            s += z[j]
            if s > m:
                m.set(s)
                l.set(i)
                r.set(j)
    return m, l, r

def max_sequence_3(z: MemoryArray, l = None, r = None):
    if l is None:
        l = Literal(0)
    if r is None:
        r = z.length().pred()
    if l == r:
        return z[l], l, r
    m = Literal((int(l) + int(r)) // 2)
    lm, ll, lr = max_sequence_3(z, l, m)
    rm, rl, rr = max_sequence_3(z, m.succ(), r)
    zm, zl, zr = find_between(z, l, m, r)
    if lm >= rm and lm >= zm:
        return lm, ll, lr
    if rm >= lm and rm >= zm:
        return rm, rl, rr
    return zm, zl, zr

def find_between(z: MemoryArray, l, m, r):
    max_sum = MemoryCell(MIN_VALUE)
    s = MemoryCell(0)
    border = MemoryCell()
    for i in mrange(m, l.pred(), -1):
        s += z[i]
        if s > max_sum:
            max_sum.set(s)
            border.set(i)
    left_max = Literal(max_sum)
    left_border = Literal(border)
    max_sum = MemoryCell(MIN_VALUE)
    s.set(0)
    for i in mrange(m.succ(), r.succ()):
        s += z[i]
        if s > max_sum:
            max_sum.set(s)
            border.set(i)
    max_sum += left_max
    return max_sum, left_border, border

def max_sequence_4(z: MemoryArray):
    n = z.length()
    max_sum = MemoryCell(MIN_VALUE)
    curr_sum = MemoryCell(0)
    curr_left = MemoryCell(0)
    r = MemoryCell()
    l = MemoryCell()
    for i in mrange(n):
        curr_sum += z[i]
        if curr_sum > max_sum:
            max_sum.set(curr_sum)
            l.set(curr_left)
            r.set(i)
        if curr_sum < Literal(0):
            curr_sum.set(0)
            curr_left.set(i.succ())
    return max_sum, l, r

def example(max_sequence_func):
    l = [-59, 52, 46, 14, -50, 58, -87, -77, 34, 15]
    print(l)
    z = MemoryArray(l)
    m, l, r = max_sequence_func(z)
    print(m, l, r)

def seq(filename, max_sequence_func):
    z = MemoryArray.create_array_from_file(filename)
    m, l, r = max_sequence_func(z)
    print(m, l, r)


def analyze_complexity(max_sequence_func, sizes):
    """
    Analysiert die Komplexität einer maximalen Teilfolgenfunktion.

    :param max_sequence_func: Die Funktion, die analysiert wird.
    :param sizes: Eine Liste von Eingabegrößen für die Analyse.
    """
    for size in sizes:
        MemoryManager.purge()  # Speicher zurücksetzen
        random_array = MemoryArray.create_random_array(size, -100, 100)
        max_sequence_func(random_array)
        MemoryManager.save_stats(size)

    MemoryManager.plot_stats(["cells", "adds"])



if __name__ == '__main__':
    for func in [max_sequence_1, max_sequence_2, max_sequence_3, max_sequence_4]:
        example(func)
        for filename in ["data/seq0.txt", "data/seq1.txt"]:
            print(filename)
            seq(filename, func)
        analyze_complexity(func, [10, 20, 30, 40, 50, 60, 70, 80, 90, 100])