#!/usr/bin/python
# -*- coding: utf-8 -*-
"""
operations on [x..y[ intervals
"""
__author__ = "Philippe Guglielmetti"
__copyright__ = "Copyright 2012, Philippe Guglielmetti"
__credits__ = []
__license__ = "LGPL"
[docs]def in_interval(interval,x):
''' True if x is in interval [a,b] or [b,a] (tuple)'''
a,b = interval[0], interval[1]
return (a <= x <= b) or (b <= x <= a)
[docs]def intersect(t1, t2):
''' True if sorted tuples intervals [t1[ [t2[ intersect'''
'''http://stackoverflow.com/questions/3721249/python-date-interval-intersection'''
t1start, t1end = t1[0], t1[1]
t2start, t2end = t2[0], t2[1]
return (t1start <= t2start < t1end) or (t2start <= t1start < t2end)
[docs]def intersection(t1, t2):
'''returns intersection between 2 intervals (tuples),
or (None,None) if intervals don't intersect'''
t1start, t1end = t1[0], t1[1]
t2start, t2end = t2[0], t2[1]
start=max(t1start,t2start)
end=min(t1end,t2end)
if start>end: #no intersection
return None
return (start,end)
[docs]def intersectlen(t1, t2, none=0):
'''returns len of intersection between 2 intervals (tuples),
or none if intervals don't intersect'''
try:
(start,end)=intersection(t1,t2)
return end-start
except:
return None
[docs]class Interval(object):
"""
Represents an interval.
Defined as half-open interval [start,end), which includes the start position but not the end.
Start and end do not have to be numeric types.
http://code.activestate.com/recipes/576816-interval/
alternative could be http://pypi.python.org/pypi/
"""
[docs] def __init__(self, start, end):
"Construct, start must be <= end."
if start > end:
raise ValueError('Start (%s) must not be greater than end (%s)' % (start, end))
self._start = start
self._end = end
start = property(fget=lambda self: self._start, doc="The interval's start")
end = property(fget=lambda self: self._end, doc="The interval's end")
[docs] def __str__(self):
"As string."
return '[%s,%s)' % (self.start, self.end)
[docs] def __repr__(self):
"String representation."
return '[%s,%s)' % (self.start, self.end)
[docs] def __cmp__(self, other):
"Compare."
if None == other:
return 1
start_cmp = cmp(self.start, other.start)
if 0 != start_cmp:
return start_cmp
else:
return cmp(self.end, other.end)
[docs] def __hash__(self):
"Hash."
return hash(self.start) ^ hash(self.end)
[docs] def intersection(self, other):
"Intersection. @return: None if no intersection."
if self > other:
other, self = self, other
if self.end <= other.start:
return None
return Interval(other.start, self.end)
[docs] def hull(self, other):
"@return: Interval containing both self and other."
if self > other:
other, self = self, other
return Interval(self.start, other.end)
[docs] def overlap(self, other):
"@return: True iff self intersects other."
if self > other:
other, self = self, other
return self.end > other.start
[docs] def __contains__(self, item):
"@return: True iff item in self."
return self.start <= item and item < self.end
[docs] def contains(self,x):
"@return: True iff 0 in self."
return self.start <= x and x < self.end
[docs] def subset(self, other):
"@return: True iff self is subset of other."
return self.start >= other.start and self.end <= other.end
[docs] def proper_subset(self, other):
"@return: True iff self is proper subset of other."
return self.start > other.start and self.end < other.end
[docs] def empty(self):
"@return: True iff self is empty."
return self.start == self.end
[docs] def singleton(self):
"@return: True iff self.end - self.start == 1."
return self.end - self.start == 1
[docs] def separation(self, other):
"@return: The distance between self and other."
if self > other:
other, self = self, other
if self.end > other.start:
return 0
else:
return other.start - self.end
import bisect
[docs]class Intervals(list):
"""a list of intevals kept in ascending order"""
[docs] def __init__(self, init=[]):
super(Intervals,self).__init__()
self.extend(init)
[docs] def extend(self,iterable):
for i in iterable:
self.append(i)
[docs] def append(self, item):
i=bisect.bisect_left(self,item)
super(Intervals,self).insert(i,item)
[docs] def __call__(self,x):
""" returns list of intervals containing x"""
return [i for i in self if i.contains(x)]
import unittest
[docs]class TestCase(unittest.TestCase):
[docs] def setUp(self):
self.i12 = Interval(1,2)
self.i13 = Interval(1,3)
self.i24 = Interval(2,4)
self.intervals=Intervals([self.i24,self.i13,self.i12])
[docs] def runTest(self):
self.assertEqual(str(self.intervals),'[[1,2), [1,3), [2,4)]')
if __name__ == '__main__':
unittest.main()