rangeset.py

   1 # Supports operations only on non-overlapping, adjacent or fully contained ranges
   2 # i.e. unioning (10, 30) and (20, 40) may not work
   3 class RangeSet:
   4
   5     def __init__(self):
   6         self.r = []
   7
   8     @staticmethod
   9     def _contained(r1, r2):
  10         return r1[1] <= r2[1]
  11
  12     def add(self, r):
  13         last = len(self.r) - 1
  14         for i, t in enumerate(self.r):
  15             if r[0] == t[1]:
  16                 new = (t[0], r[1])
  17                 if i != last and new[1] == self.r[i + 1][0]:
  18                     self.r[i] = (new[0], self.r[i + 1][1])
  19                     del self.r[i + 1]
  20                 else:
  21                     self.r[i] = new
  22                 return
  23             elif r[1] == t[0]:
  24                 new = (r[0], t[1])
  25                 if i != 0 and new[0] == self.r[i - 1][1]:
  26                     self.r[i] = (self.r[i - 1][0], new[1])
  27                     del self.r[i - 1]
  28                 else:
  29                     self.r[i] = new
  30                 return
  31             elif r[0] < t[0]:
  32                 if i > 0:
  33                     if self._contained(r, self.r[i - 1]):
  34                         return
  35                 self.r.insert(i, r)
  36                 return
  37         if last >= 0 and self._contained(r, self.r[-1]):
  38             return
  39         self.r.append(r)
  40
  41     def bounds(self):
  42         if self.r:
  43             return (self.r[0][0], self.r[-1][1])
  44
  45     def __str__(self):
  46         return str(self.r)
  47
  48     def str(self, render=lambda x: str(x)):
  49         rlist = [(render(x[0]), render(x[1])) for x in self.r]
  50         return str(rlist)
  51
  52     # This allows to apply list(), but this creates a copy, using
  53     # to_list() is more efficient.
  54     def __iter__(self):
  55         return iter(self.r)
  56
  57     def to_list(self):
  58         return self.r
  59
  60
  61 if __name__ == "__main__":
  62     r = RangeSet()
  63     r.add((10, 20))
  64     assert r.to_list() == [(10, 20)]
  65     r.add((1, 5))
  66     assert r.to_list() == [(1, 5), (10, 20)]
  67     r.add((100, 110))
  68     assert r.to_list() == [(1, 5), (10, 20), (100, 110)]
  69     r.add((5, 8))
  70     assert r.to_list() == [(1, 8), (10, 20), (100, 110)]
  71     r.add((8, 10))
  72     assert r.to_list() == [(1, 20), (100, 110)]
  73     r.add((110, 120))
  74     assert r.to_list() == [(1, 20), (100, 120)]
  75     r.add((5, 10))
  76     assert r.to_list() == [(1, 20), (100, 120)]
  77
  78     r = RangeSet()
  79     r.add((10, 20))
  80     r.add((12, 15))
  81     assert r.to_list() == [(10, 20)]
  82
  83     r = RangeSet()
  84     r.add((10, 30))
  85     r.add((20, 40))
  86     #assert r.to_list() == [(10, 40)]
  87     print(list(r))
  88
  89     r = RangeSet()
  90     r.add((30, 40))
  91     r.add((10, 20))
  92     r.add((20, 30))
  93     assert r.to_list() == [(10, 40)]
  94
  95     r = RangeSet()
  96     r.add((10, 20))
  97     r.add((1, 10))
  98     assert r.to_list() == [(1, 20)]