***
from statistics import median
from typing import List, Tuple
def isInRange(q1:float, v:float, q2:float):
if q1 is not None and q2 is not None and q1<=v<=q2: return True
elif q1 is None and q2 is not None and v<=v: return True
elif q1 is not None and q2 is None and q1<=v: return True
return False
def isInWindow(p:Tuple, qx1:float, qx2:float, qy1:float, qy2:float):
return isInRange(qx1, p[0], qx2) and isInRange(qy1, p[1], qy2)
class IntervalNode:
def __init__(self, xmed:float):
self.xmed=xmed
self.leftChild, self.rightChild=None, None
self.intervals=[]
self.taul, self.taur=[],[]
class IntervalTree:
def __init__(self, I:List):
self.rootNode=self._create(I)
def _create(self, I:list):
if len(I) == 0: return None
else:
epoints=set(map(lambda si:si[0][0], I)).union(set((map(lambda si: si[0][1], I))))
xmed=median(epoints)
n=IntervalNode(xmed)
Ileft=list(filter(lambda si:si[0][0]<xmed and si[0][1]<xmed, I))
Iright=list(filter(lambda si:si[0][0]>xmed and si[0][1]>xmed, I))
Imed=list(filter(lambda si:si not in Ileft+Iright, I))
n.intervals=Imed
nl,nr=self._create(Ileft), self._create(Iright)
n.leftChild, n.rightChild=nl,nr
if len(Imed) > 0:
n.taul+=list(map(lambda si:{'point':(min(si[0][0], si[0][1]), si[1]), 'interval':si}, Imed))
n.taur+=list(map(lambda si:{'point':(max(si[0][0], si[0][1]), si[1]), 'interval':si}, Imed))
return n
