util/style/region.py - public/gem5 - Git at Google

 # 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 xrange(0,30,2)))
     y = Regions(*((i, i + 4) for i in xrange(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

     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
	# 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 xrange(0,30,2)))
	y = Regions(*((i, i + 4) for i in xrange(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

	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