aboutsummaryrefslogtreecommitdiff
path: root/rpkid/rpki/gui/app/range_list.py
diff options
context:
space:
mode:
Diffstat (limited to 'rpkid/rpki/gui/app/range_list.py')
-rwxr-xr-xrpkid/rpki/gui/app/range_list.py252
1 files changed, 0 insertions, 252 deletions
diff --git a/rpkid/rpki/gui/app/range_list.py b/rpkid/rpki/gui/app/range_list.py
deleted file mode 100755
index 21fd1f29..00000000
--- a/rpkid/rpki/gui/app/range_list.py
+++ /dev/null
@@ -1,252 +0,0 @@
-# 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-12 00:54:23 +0000