Skip to content

Instantly share code, notes, and snippets.

@jwintersinger
Created July 6, 2013 00:16
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jwintersinger/5937985 to your computer and use it in GitHub Desktop.
Save jwintersinger/5937985 to your computer and use it in GitHub Desktop.
#!/usr/bin/env python2
# Efficient means of determining which ranges from set overlap a given query
# range. See http://www.cise.ufl.edu/~sahni/cop5536/powerpoint/lec34.ppt for
# details.
class Node(object):
def __init__(self, intervals):
self._olap = []
self.l = None
self.r = None
self.pt = None
self._set_centre(intervals)
self._add_intervals(intervals)
def _set_centre(self, intervals):
endpoints = set()
for interval in intervals:
endpoints.add(interval.l)
endpoints.add(interval.r)
self.pt = self._find_median(endpoints)
def _add_intervals(self, intervals):
to_left = []
to_right = []
for interval in intervals:
if self.pt in interval:
self._olap.append(interval)
elif self.pt < interval.l:
to_right.append(interval)
elif self.pt > interval.r:
to_left.append(interval)
if to_left:
self.l = Node(to_left)
if to_right:
self.r = Node(to_right)
def _find_median(self, points):
midpoint = int((len(points) - 1) / 2)
return sorted(points)[midpoint]
def find_overlapping(self, interval):
olap = []
if self.pt in interval:
olap += self._olap
if self.l:
olap += self.l.find_overlapping(interval)
if self.r:
olap += self.r.find_overlapping(interval)
elif self.pt < interval.l:
for candidate in self._olap:
if candidate.r >= interval.l:
olap.append(candidate)
if self.r:
olap += self.r.find_overlapping(interval)
elif self.pt > interval.r:
for candidate in self._olap:
if candidate.l <= interval.r:
olap.append(candidate)
if self.l:
olap += self.l.find_overlapping(interval)
return olap
class Interval(object):
def __init__(self, l, r):
self.l = l
self.r = r
def __contains__(self, p):
return self.l <= p <= self.r
def __repr__(self):
return '[%s, %s]' % (self.l, self.r)
class IntervalTree(object):
def __init__(self, intervals):
self._root = Node([Interval(i[0], i[1]) for i in intervals])
def find_overlapping(self, interval):
return self._root.find_overlapping(interval)
def main():
r1 = IntervalTree([ (1, 1000), (1100, 1200) ])
r2 = IntervalTree([ (30, 50), (60, 200), (1150, 1300) ])
print(r2.find_overlapping(Interval(30, 60)))
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment