from operator import itemgetter
from intervals import punt_central

#
# crea_arbre_intervals
#

def crea_arbre_intervals(intervals):
    if len(intervals) == 0:
        r = None
    else:
        p = punt_central(intervals)
        e, m, d = classifica(intervals, p)
        ae = crea_arbre_intervals(e)
        ad = crea_arbre_intervals(d)
        mx = sorted(m, key=itemgetter(0))
        # equival a mx = sorted(m, key=lambda iv: iv[0])
        my = sorted(m, key=itemgetter(1))
        # equival a my = sorted(m, key=lambda iv: iv[1])
        r = (p, ae, ad, mx, my)
    return r


#
# classifica
#

def classifica_1(intervals, punt):
    if len(intervals) == 0:
        r = [], [], []
    else:
        e, m, d = classifica(intervals[1:], punt)
        c = classifica_interval(intervals[0], punt)
        if c == -1:
            e.insert(0, intervals[0])
        elif c == 0:
            m.insert(0, intervals[0])
        else:
            d.insert(0, intervals[0])
        r = e, m, d
    return r


def classifica_2(lint, punt):
    lesq, ldre, lcon = [], [], []
    classifica_r(lint, punt, 0, lesq, ldre, lcon)
    return lesq, lcon, ldre

def classifica_r(lint, punt, i, lesq, ldre, lcon):
    if i < len(lint):
        interval = lint[i]
        valor = classifica_interval(interval, punt)
        if valor == -1:
            lesq.append(interval)
        elif valor == 1:
            ldre.append(interval)
        else:
            lcon.append(interval)
        classifica_r(lint, punt, i+1, lesq, ldre, lcon)


# Trieu la solució que vulgueu provar
classifica = classifica_1
# classifica = classifica_2


#
# classifica_interval
#

def classifica_interval(interval, punt):
    n, x = interval
    if punt < n:
        r = 1
    elif punt > x:
        r = -1
    else:
        r = 0
    return r