blob: 39eaba50becb54578aff8dcfbfe45d0326e9102a [file] [log] [blame]
# Copyright (c) 2006 Nathan Binkert <nate@binkert.org>
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are
# met: redistributions of source code must retain the above copyright
# notice, this list of conditions and the following disclaimer;
# redistributions in binary form must reproduce the above copyright
# notice, this list of conditions and the following disclaimer in the
# documentation and/or other materials provided with the distribution;
# neither the name of the copyright holders nor the names of its
# contributors may be used to endorse or promote products derived from
# this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
class _neg_inf(object):
"""This object always compares less than any other object"""
def __repr__(self):
return "<neg_inf>"
def __lt__(self, other):
return type(self) != type(other)
def __le__(self, other):
return True
def __gt__(self, other):
return False
def __ge__(self, other):
return type(self) == type(other)
def __eq__(self, other):
return type(self) == type(other)
def __ne__(self, other):
return type(self) != type(other)
neg_inf = _neg_inf()
class _pos_inf(object):
"""This object always compares greater than any other object"""
def __repr__(self):
return "<pos_inf>"
def __lt__(self, other):
return False
def __le__(self, other):
return type(self) == type(other)
def __gt__(self, other):
return type(self) != type(other)
def __ge__(self, other):
return True
def __eq__(self, other):
return type(self) == type(other)
def __ne__(self, other):
return type(self) != type(other)
pos_inf = _pos_inf()
class Region(tuple):
"""A region (range) of [start, end).
This includes utility functions to compare overlap of regions."""
def __new__(cls, *args):
if len(args) == 1:
arg = args[0]
if isinstance(arg, Region):
return arg
args = tuple(arg)
if len(args) != 2:
raise AttributeError(
"Only one or two arguments allowed, %d provided" % (alen,)
)
return tuple.__new__(cls, args)
def __repr__(self):
return "Region(%s, %s)" % (self[0], self[1])
@property
def start(self):
return self[0]
@property
def end(self):
return self[1]
def __contains__(self, other):
"""other is
region: True if self and other is fully contained within self.
pos: True if other is within the region"""
if isinstance(other, tuple):
return self[0] <= other[0] and self[1] >= other[1]
return self[0] <= other and other < self[1]
def __eq__(self, other):
"""other is
region: True if self and other are identical.
pos: True if other is within the region"""
if isinstance(other, tuple):
return self[0] == other[0] and self[1] == other[1]
return self[0] <= other and other < self[1]
# @param self is a region.
# @param other is a region.
# @return if self and other are not identical.
def __ne__(self, other):
"""other is
region: true if they are not identical
pos: True if other is not in the region"""
if isinstance(other, tuple):
return self[0] != other[0] or self[1] != other[1]
return other < self[0] or self[1] <= other
# @param self is a region.
# @param other is a region.
# @return if self is less than other and does not overlap self.
def __lt__(self, other):
"self completely left of other (cannot overlap)"
if isinstance(other, tuple):
return self[1] <= other[0]
return self[1] <= other
# @param self is a region.
# @param other is a region.
# @return if self is less than other. self may overlap other,
# but not extend beyond the _end of other.
def __le__(self, other):
"self extends to the left of other (can overlap)"
if isinstance(other, tuple):
return self[0] <= other[0]
return self[0] <= other
# @param self is a region.
# @param other is a region.
# @return if self is greater than other and does not overlap other.
def __gt__(self, other):
"self is completely right of other (cannot overlap)"
if isinstance(other, tuple):
return self[0] >= other[1]
return self[0] > other
# @param self is a region.
# @param other is a region.
# @return if self is greater than other. self may overlap other,
# but not extend beyond the beginning of other.
def __ge__(self, other):
"self ex_ends beyond other to the right (can overlap)"
if isinstance(other, tuple):
return self[1] >= other[1]
return self[1] > other
class Regions(object):
"""A set of regions (ranges). Basically a region with holes.
Includes utility functions to merge regions and figure out if
something is in one of the regions."""
def __init__(self, *args):
self.regions = []
self.extend(*args)
def copy(self):
copy = Regions()
copy.regions.extend(self.regions)
return copy
def append(self, *args):
self.regions.append(Region(*args))
def extend(self, *args):
self.regions.extend(Region(a) for a in args)
def __contains__(self, position):
for region in self.regions:
if position in region:
return True
return False
def __len__(self):
return len(self.regions)
def __iand__(self, other):
A = self.regions
B = other.regions
R = []
i = 0
j = 0
while i < len(self) and j < len(other):
a = A[i]
b = B[j]
if a[1] <= b[0]:
# A is completely before B. Skip A
i += 1
elif a[0] <= b[0]:
if a[1] <= b[1]:
# A and B overlap with B not left of A and A not right of B
R.append(Region(b[0], a[1]))
# Advance A because nothing is left
i += 1
if a[1] == b[1]:
# Advance B too
j += 1
else:
# A and B overlap with B completely within the bounds of A
R.append(Region(b[0], b[1]))
# Advance only B because some of A may still be useful
j += 1
elif b[1] <= a[0]:
# B is completely before A. Skip B.
j += 1
else:
assert b[0] < a[0]
if b[1] <= a[1]:
# A and B overlap with A not left of B and B not right of A
R.append(Region(a[0], b[1]))
# Advance B because nothing is left
j += 1
if a[1] == b[1]:
# Advance A too
i += 1
else:
# A and B overlap with A completely within the bounds of B
R.append(Region(a[0], a[1]))
# Advance only A because some of B may still be useful
i += 1
self.regions = R
return self
def __and__(self, other):
result = self.copy()
result &= other
return result
def __repr__(self):
return "Regions(%s)" % ([(r[0], r[1]) for r in self.regions],)
all_regions = Regions(Region(neg_inf, pos_inf))
if __name__ == "__main__":
x = Regions(*((i, i + 1) for i in range(0, 30, 2)))
y = Regions(*((i, i + 4) for i in range(0, 30, 5)))
z = Region(6, 7)
n = Region(9, 10)
def test(left, right):
print("%s == %s: %s" % (left, right, left == right))
print("%s != %s: %s" % (left, right, left != right))
print("%s < %s: %s" % (left, right, left < right))
print("%s <= %s: %s" % (left, right, left <= right))
print("%s > %s: %s" % (left, right, left > right))
print("%s >= %s: %s" % (left, right, left >= right))
print("\n")
test(neg_inf, neg_inf)
test(neg_inf, pos_inf)
test(pos_inf, neg_inf)
test(pos_inf, pos_inf)
test(neg_inf, 0)
test(neg_inf, -11111)
test(neg_inf, 11111)
test(0, neg_inf)
test(-11111, neg_inf)
test(11111, neg_inf)
test(pos_inf, 0)
test(pos_inf, -11111)
test(pos_inf, 11111)
test(0, pos_inf)
test(-11111, pos_inf)
test(11111, pos_inf)
print(x)
print(y)
print(x & y)
print(z)
print(4 in x)
print(4 in z)
print(5 not in x)
print(6 not in z)
print(z in y)
print(n in y, n not in y)