aboutsummaryrefslogtreecommitdiff
path: root/rpki/gui/app/range_list.py
diff options
context:
space:
mode:
Diffstat (limited to 'rpki/gui/app/range_list.py')
-rwxr-xr-xrpki/gui/app/range_list.py252
1 files changed, 252 insertions, 0 deletions
diff --git a/rpki/gui/app/range_list.py b/rpki/gui/app/range_list.py
new file mode 100755
index 00000000..21fd1f29
--- /dev/null
+++ b/rpki/gui/app/range_list.py
@@ -0,0 +1,252 @@
+# Copyright (C) 2012 SPARTA, Inc. a Parsons Company
+#
+# Permission to use, copy, modify, and distribute this software for any
+# purpose with or without fee is hereby granted, provided that the above
+# copyright notice and this permission notice appear in all copies.
+#
+# THE SOFTWARE IS PROVIDED "AS IS" AND SPARTA DISCLAIMS ALL WARRANTIES WITH
+# REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
+# AND FITNESS. IN NO EVENT SHALL SPARTA BE LIABLE FOR ANY SPECIAL, DIRECT,
+# INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
+# LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
+# OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+# PERFORMANCE OF THIS SOFTWARE.
+
+__version__ = '$Id$'
+
+import bisect
+import unittest
+
+
+class RangeList(list):
+ """A sorted list of ranges, which automatically merges adjacent ranges.
+
+ Items in the list are expected to have ".min" and ".max" attributes."""
+
+ def __init__(self, ini=None):
+ list.__init__(self)
+ if ini:
+ self.extend(ini)
+
+ def append(self, v):
+ keys = [x.min for x in self]
+
+ # lower bound
+ i = bisect.bisect_left(keys, v.min)
+
+ # upper bound
+ j = bisect.bisect_right(keys, v.max, lo=i)
+
+ # if the max value for the previous item is greater than v.min, include
+ # the previous item in the range to replace and use its min value.
+ # also include the previous item if the max value is 1 less than the
+ # min value for the inserted item
+ if i > 0 and self[i - 1].max >= v.min - 1:
+ i = i - 1
+ vmin = self[i].min
+ else:
+ vmin = v.min
+
+ # if the max value for the previous item is greater than the max value
+ # for the new item, use the previous item's max
+ if j > 0 and self[j - 1].max > v.max:
+ vmax = self[j - 1].max
+ else:
+ vmax = v.max
+
+ # if the max value for the new item is 1 less than the min value for
+ # the next item, combine into a single item
+ if j < len(self) and vmax + 1 == self[j].min:
+ vmax = self[j].max
+ j = j + 1
+
+ # replace the range with a new object covering the entire range
+ self[i:j] = [v.__class__(vmin, vmax)]
+
+ def extend(self, args):
+ for x in args:
+ self.append(x)
+
+ def difference(self, other):
+ """Return a RangeList object which contains ranges in this object which
+ are not in "other"."""
+ it = iter(other)
+
+ try:
+ cur = it.next()
+ except StopIteration:
+ return self
+
+ r = RangeList()
+
+ for x in self:
+ xmin = x.min
+
+ def V(v):
+ """convert the integer value to the appropriate type for this
+ range"""
+ return x.__class__.datum_type(v)
+
+ try:
+ while xmin <= x.max:
+ if xmin < cur.min:
+ r.append(x.__class__(V(xmin),
+ V(min(x.max, cur.min - 1))))
+ xmin = cur.max + 1
+ elif xmin == cur.min:
+ xmin = cur.max + 1
+ else: # xmin > cur.min
+ if xmin <= cur.max:
+ xmin = cur.max + 1
+ else: # xmin > cur.max
+ cur = it.next()
+
+ except StopIteration:
+ r.append(x.__class__(V(xmin), x.max))
+
+ return r
+
+
+class TestRangeList(unittest.TestCase):
+ class MinMax(object):
+ datum_type = int
+
+ def __init__(self, range_min, range_max):
+ self.min = range_min
+ self.max = range_max
+
+ def __str__(self):
+ return '(%d, %d)' % (self.min, self.max)
+
+ def __repr__(self):
+ return '<MinMax: (%d, %d)>' % (self.min, self.max)
+
+ def __eq__(self, other):
+ return self.min == other.min and self.max == other.max
+
+ def setUp(self):
+ self.v1 = TestRangeList.MinMax(1, 2)
+ self.v2 = TestRangeList.MinMax(4, 5)
+ self.v3 = TestRangeList.MinMax(7, 8)
+ self.v4 = TestRangeList.MinMax(3, 4)
+ self.v5 = TestRangeList.MinMax(2, 3)
+ self.v6 = TestRangeList.MinMax(1, 10)
+
+ def test_empty_append(self):
+ s = RangeList()
+ s.append(self.v1)
+ self.assertTrue(len(s) == 1)
+ self.assertEqual(s[0], self.v1)
+
+ def test_no_overlap(self):
+ s = RangeList()
+ s.append(self.v1)
+ s.append(self.v2)
+ self.assertTrue(len(s) == 2)
+ self.assertEqual(s[0], self.v1)
+ self.assertEqual(s[1], self.v2)
+
+ def test_no_overlap_prepend(self):
+ s = RangeList()
+ s.append(self.v2)
+ s.append(self.v1)
+ self.assertTrue(len(s) == 2)
+ self.assertEqual(s[0], self.v1)
+ self.assertEqual(s[1], self.v2)
+
+ def test_insert_middle(self):
+ s = RangeList()
+ s.append(self.v1)
+ s.append(self.v3)
+ s.append(self.v2)
+ self.assertTrue(len(s) == 3)
+ self.assertEqual(s[0], self.v1)
+ self.assertEqual(s[1], self.v2)
+ self.assertEqual(s[2], self.v3)
+
+ def test_append_overlap(self):
+ s = RangeList()
+ s.append(self.v1)
+ s.append(self.v5)
+ self.assertTrue(len(s) == 1)
+ self.assertEqual(s[0], TestRangeList.MinMax(1, 3))
+
+ def test_combine_range(self):
+ s = RangeList()
+ s.append(self.v1)
+ s.append(self.v4)
+ self.assertTrue(len(s) == 1)
+ self.assertEqual(s[0], TestRangeList.MinMax(1, 4))
+
+ def test_append_subset(self):
+ s = RangeList()
+ s.append(self.v6)
+ s.append(self.v3)
+ self.assertTrue(len(s) == 1)
+ self.assertEqual(s[0], self.v6)
+
+ def test_append_equal(self):
+ s = RangeList()
+ s.append(self.v6)
+ s.append(self.v6)
+ self.assertTrue(len(s) == 1)
+ self.assertEqual(s[0], self.v6)
+
+ def test_prepend_combine(self):
+ s = RangeList()
+ s.append(self.v4)
+ s.append(self.v1)
+ self.assertTrue(len(s) == 1)
+ self.assertEqual(s[0], TestRangeList.MinMax(1, 4))
+
+ def test_append_aggregate(self):
+ s = RangeList()
+ s.append(self.v1)
+ s.append(self.v2)
+ s.append(self.v3)
+ s.append(self.v6)
+ self.assertTrue(len(s) == 1)
+ self.assertEqual(s[0], self.v6)
+
+ def test_diff_empty(self):
+ s = RangeList()
+ s.append(self.v1)
+ self.assertEqual(s, s.difference([]))
+
+ def test_diff_self(self):
+ s = RangeList()
+ s.append(self.v1)
+ self.assertEqual(s.difference(s), [])
+
+ def test_diff_middle(self):
+ s1 = RangeList([self.v6])
+ s2 = RangeList([self.v3])
+ self.assertEqual(s1.difference(s2), RangeList([TestRangeList.MinMax(1, 6), TestRangeList.MinMax(9, 10)]))
+
+ def test_diff_overlap(self):
+ s1 = RangeList([self.v2])
+ s2 = RangeList([self.v4])
+ self.assertEqual(s1.difference(s2), RangeList([TestRangeList.MinMax(5, 5)]))
+
+ def test_diff_overlap2(self):
+ s1 = RangeList([self.v2])
+ s2 = RangeList([self.v4])
+ self.assertEqual(s2.difference(s1), RangeList([TestRangeList.MinMax(3, 3)]))
+
+ def test_diff_multi(self):
+ s1 = RangeList([TestRangeList.MinMax(1, 2), TestRangeList.MinMax(4, 5)])
+ s2 = RangeList([TestRangeList.MinMax(4, 4)])
+ self.assertEqual(s1.difference(s2), RangeList([TestRangeList.MinMax(1, 2), TestRangeList.MinMax(5, 5)]))
+
+ def test_diff_multi_overlap(self):
+ s1 = RangeList([TestRangeList.MinMax(1, 2), TestRangeList.MinMax(3, 4)])
+ s2 = RangeList([TestRangeList.MinMax(2, 3)])
+ self.assertEqual(s1.difference(s2), RangeList([TestRangeList.MinMax(1,1), TestRangeList.MinMax(4,4)]))
+
+ def test_diff_multi_overlap2(self):
+ s1 = RangeList([TestRangeList.MinMax(1,2), TestRangeList.MinMax(3,4), TestRangeList.MinMax(6,7)])
+ s2 = RangeList([TestRangeList.MinMax(2, 3), TestRangeList.MinMax(6, 6)])
+ self.assertEqual(s1.difference(s2), RangeList([TestRangeList.MinMax(1,1), TestRangeList.MinMax(4,4), TestRangeList.MinMax(7,7)]))
+
+if __name__ == '__main__':
+ unittest.main()
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-10 16:52:51 +0000