region.py revision 11403
111403Sandreas.sandberg@arm.com# Copyright (c) 2006 Nathan Binkert <nate@binkert.org> 211403Sandreas.sandberg@arm.com# All rights reserved. 311403Sandreas.sandberg@arm.com# 411403Sandreas.sandberg@arm.com# Redistribution and use in source and binary forms, with or without 511403Sandreas.sandberg@arm.com# modification, are permitted provided that the following conditions are 611403Sandreas.sandberg@arm.com# met: redistributions of source code must retain the above copyright 711403Sandreas.sandberg@arm.com# notice, this list of conditions and the following disclaimer; 811403Sandreas.sandberg@arm.com# redistributions in binary form must reproduce the above copyright 911403Sandreas.sandberg@arm.com# notice, this list of conditions and the following disclaimer in the 1011403Sandreas.sandberg@arm.com# documentation and/or other materials provided with the distribution; 1111403Sandreas.sandberg@arm.com# neither the name of the copyright holders nor the names of its 1211403Sandreas.sandberg@arm.com# contributors may be used to endorse or promote products derived from 1311403Sandreas.sandberg@arm.com# this software without specific prior written permission. 1411403Sandreas.sandberg@arm.com# 1511403Sandreas.sandberg@arm.com# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1611403Sandreas.sandberg@arm.com# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1711403Sandreas.sandberg@arm.com# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1811403Sandreas.sandberg@arm.com# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1911403Sandreas.sandberg@arm.com# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2011403Sandreas.sandberg@arm.com# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2111403Sandreas.sandberg@arm.com# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2211403Sandreas.sandberg@arm.com# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2311403Sandreas.sandberg@arm.com# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2411403Sandreas.sandberg@arm.com# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2511403Sandreas.sandberg@arm.com# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2611403Sandreas.sandberg@arm.com 2711403Sandreas.sandberg@arm.comclass _neg_inf(object): 2811403Sandreas.sandberg@arm.com '''This object always compares less than any other object''' 2911403Sandreas.sandberg@arm.com def __repr__(self): return '<neg_inf>' 3011403Sandreas.sandberg@arm.com def __lt__(self, other): return type(self) != type(other) 3111403Sandreas.sandberg@arm.com def __le__(self, other): return True 3211403Sandreas.sandberg@arm.com def __gt__(self, other): return False 3311403Sandreas.sandberg@arm.com def __ge__(self, other): return type(self) == type(other) 3411403Sandreas.sandberg@arm.com def __eq__(self, other): return type(self) == type(other) 3511403Sandreas.sandberg@arm.com def __ne__(self, other): return type(self) != type(other) 3611403Sandreas.sandberg@arm.comneg_inf = _neg_inf() 3711403Sandreas.sandberg@arm.com 3811403Sandreas.sandberg@arm.comclass _pos_inf(object): 3911403Sandreas.sandberg@arm.com '''This object always compares greater than any other object''' 4011403Sandreas.sandberg@arm.com def __repr__(self): return '<pos_inf>' 4111403Sandreas.sandberg@arm.com def __lt__(self, other): return False 4211403Sandreas.sandberg@arm.com def __le__(self, other): return type(self) == type(other) 4311403Sandreas.sandberg@arm.com def __gt__(self, other): return type(self) != type(other) 4411403Sandreas.sandberg@arm.com def __ge__(self, other): return True 4511403Sandreas.sandberg@arm.com def __eq__(self, other): return type(self) == type(other) 4611403Sandreas.sandberg@arm.com def __ne__(self, other): return type(self) != type(other) 4711403Sandreas.sandberg@arm.compos_inf = _pos_inf() 4811403Sandreas.sandberg@arm.com 4911403Sandreas.sandberg@arm.comclass Region(tuple): 5011403Sandreas.sandberg@arm.com '''A region (range) of [start, end). 5111403Sandreas.sandberg@arm.com This includes utility functions to compare overlap of regions.''' 5211403Sandreas.sandberg@arm.com def __new__(cls, *args): 5311403Sandreas.sandberg@arm.com if len(args) == 1: 5411403Sandreas.sandberg@arm.com arg = args[0] 5511403Sandreas.sandberg@arm.com if isinstance(arg, Region): 5611403Sandreas.sandberg@arm.com return arg 5711403Sandreas.sandberg@arm.com args = tuple(arg) 5811403Sandreas.sandberg@arm.com 5911403Sandreas.sandberg@arm.com if len(args) != 2: 6011403Sandreas.sandberg@arm.com raise AttributeError, \ 6111403Sandreas.sandberg@arm.com "Only one or two arguments allowed, %d provided" % (alen, ) 6211403Sandreas.sandberg@arm.com 6311403Sandreas.sandberg@arm.com return tuple.__new__(cls, args) 6411403Sandreas.sandberg@arm.com 6511403Sandreas.sandberg@arm.com def __repr__(self): 6611403Sandreas.sandberg@arm.com return 'Region(%s, %s)' % (self[0], self[1]) 6711403Sandreas.sandberg@arm.com 6811403Sandreas.sandberg@arm.com @property 6911403Sandreas.sandberg@arm.com def start(self): 7011403Sandreas.sandberg@arm.com return self[0] 7111403Sandreas.sandberg@arm.com 7211403Sandreas.sandberg@arm.com @property 7311403Sandreas.sandberg@arm.com def end(self): 7411403Sandreas.sandberg@arm.com return self[1] 7511403Sandreas.sandberg@arm.com 7611403Sandreas.sandberg@arm.com def __contains__(self, other): 7711403Sandreas.sandberg@arm.com '''other is 7811403Sandreas.sandberg@arm.com region: True if self and other is fully contained within self. 7911403Sandreas.sandberg@arm.com pos: True if other is within the region''' 8011403Sandreas.sandberg@arm.com if isinstance(other, tuple): 8111403Sandreas.sandberg@arm.com return self[0] <= other[0] and self[1] >= other[1] 8211403Sandreas.sandberg@arm.com return self[0] <= other and other < self[1] 8311403Sandreas.sandberg@arm.com 8411403Sandreas.sandberg@arm.com def __eq__(self, other): 8511403Sandreas.sandberg@arm.com '''other is 8611403Sandreas.sandberg@arm.com region: True if self and other are identical. 8711403Sandreas.sandberg@arm.com pos: True if other is within the region''' 8811403Sandreas.sandberg@arm.com if isinstance(other, tuple): 8911403Sandreas.sandberg@arm.com return self[0] == other[0] and self[1] == other[1] 9011403Sandreas.sandberg@arm.com return self[0] <= other and other < self[1] 9111403Sandreas.sandberg@arm.com 9211403Sandreas.sandberg@arm.com # @param self is a region. 9311403Sandreas.sandberg@arm.com # @param other is a region. 9411403Sandreas.sandberg@arm.com # @return if self and other are not identical. 9511403Sandreas.sandberg@arm.com def __ne__(self, other): 9611403Sandreas.sandberg@arm.com '''other is 9711403Sandreas.sandberg@arm.com region: true if they are not identical 9811403Sandreas.sandberg@arm.com pos: True if other is not in the region''' 9911403Sandreas.sandberg@arm.com if isinstance(other, tuple): 10011403Sandreas.sandberg@arm.com return self[0] != other[0] or self[1] != other[1] 10111403Sandreas.sandberg@arm.com return other < self[0] or self[1] <= other 10211403Sandreas.sandberg@arm.com 10311403Sandreas.sandberg@arm.com # @param self is a region. 10411403Sandreas.sandberg@arm.com # @param other is a region. 10511403Sandreas.sandberg@arm.com # @return if self is less than other and does not overlap self. 10611403Sandreas.sandberg@arm.com def __lt__(self, other): 10711403Sandreas.sandberg@arm.com "self completely left of other (cannot overlap)" 10811403Sandreas.sandberg@arm.com if isinstance(other, tuple): 10911403Sandreas.sandberg@arm.com return self[1] <= other[0] 11011403Sandreas.sandberg@arm.com return self[1] <= other 11111403Sandreas.sandberg@arm.com 11211403Sandreas.sandberg@arm.com # @param self is a region. 11311403Sandreas.sandberg@arm.com # @param other is a region. 11411403Sandreas.sandberg@arm.com # @return if self is less than other. self may overlap other, 11511403Sandreas.sandberg@arm.com # but not extend beyond the _end of other. 11611403Sandreas.sandberg@arm.com def __le__(self, other): 11711403Sandreas.sandberg@arm.com "self extends to the left of other (can overlap)" 11811403Sandreas.sandberg@arm.com if isinstance(other, tuple): 11911403Sandreas.sandberg@arm.com return self[0] <= other[0] 12011403Sandreas.sandberg@arm.com return self[0] <= other 12111403Sandreas.sandberg@arm.com 12211403Sandreas.sandberg@arm.com # @param self is a region. 12311403Sandreas.sandberg@arm.com # @param other is a region. 12411403Sandreas.sandberg@arm.com # @return if self is greater than other and does not overlap other. 12511403Sandreas.sandberg@arm.com def __gt__(self, other): 12611403Sandreas.sandberg@arm.com "self is completely right of other (cannot overlap)" 12711403Sandreas.sandberg@arm.com if isinstance(other, tuple): 12811403Sandreas.sandberg@arm.com return self[0] >= other[1] 12911403Sandreas.sandberg@arm.com return self[0] > other 13011403Sandreas.sandberg@arm.com 13111403Sandreas.sandberg@arm.com # @param self is a region. 13211403Sandreas.sandberg@arm.com # @param other is a region. 13311403Sandreas.sandberg@arm.com # @return if self is greater than other. self may overlap other, 13411403Sandreas.sandberg@arm.com # but not extend beyond the beginning of other. 13511403Sandreas.sandberg@arm.com def __ge__(self, other): 13611403Sandreas.sandberg@arm.com "self ex_ends beyond other to the right (can overlap)" 13711403Sandreas.sandberg@arm.com if isinstance(other, tuple): 13811403Sandreas.sandberg@arm.com return self[1] >= other[1] 13911403Sandreas.sandberg@arm.com return self[1] > other 14011403Sandreas.sandberg@arm.com 14111403Sandreas.sandberg@arm.comclass Regions(object): 14211403Sandreas.sandberg@arm.com '''A set of regions (ranges). Basically a region with holes. 14311403Sandreas.sandberg@arm.com Includes utility functions to merge regions and figure out if 14411403Sandreas.sandberg@arm.com something is in one of the regions.''' 14511403Sandreas.sandberg@arm.com def __init__(self, *args): 14611403Sandreas.sandberg@arm.com self.regions = [] 14711403Sandreas.sandberg@arm.com self.extend(*args) 14811403Sandreas.sandberg@arm.com 14911403Sandreas.sandberg@arm.com def copy(self): 15011403Sandreas.sandberg@arm.com copy = Regions() 15111403Sandreas.sandberg@arm.com copy.regions.extend(self.regions) 15211403Sandreas.sandberg@arm.com return copy 15311403Sandreas.sandberg@arm.com 15411403Sandreas.sandberg@arm.com def append(self, *args): 15511403Sandreas.sandberg@arm.com self.regions.append(Region(*args)) 15611403Sandreas.sandberg@arm.com 15711403Sandreas.sandberg@arm.com def extend(self, *args): 15811403Sandreas.sandberg@arm.com self.regions.extend(Region(a) for a in args) 15911403Sandreas.sandberg@arm.com 16011403Sandreas.sandberg@arm.com def __contains__(self, position): 16111403Sandreas.sandberg@arm.com for region in self.regions: 16211403Sandreas.sandberg@arm.com if position in region: 16311403Sandreas.sandberg@arm.com return True 16411403Sandreas.sandberg@arm.com 16511403Sandreas.sandberg@arm.com return False 16611403Sandreas.sandberg@arm.com 16711403Sandreas.sandberg@arm.com def __len__(self): 16811403Sandreas.sandberg@arm.com return len(self.regions) 16911403Sandreas.sandberg@arm.com 17011403Sandreas.sandberg@arm.com def __iand__(self, other): 17111403Sandreas.sandberg@arm.com A = self.regions 17211403Sandreas.sandberg@arm.com B = other.regions 17311403Sandreas.sandberg@arm.com R = [] 17411403Sandreas.sandberg@arm.com 17511403Sandreas.sandberg@arm.com i = 0 17611403Sandreas.sandberg@arm.com j = 0 17711403Sandreas.sandberg@arm.com while i < len(self) and j < len(other): 17811403Sandreas.sandberg@arm.com a = A[i] 17911403Sandreas.sandberg@arm.com b = B[j] 18011403Sandreas.sandberg@arm.com if a[1] <= b[0]: 18111403Sandreas.sandberg@arm.com # A is completely before B. Skip A 18211403Sandreas.sandberg@arm.com i += 1 18311403Sandreas.sandberg@arm.com elif a[0] <= b[0]: 18411403Sandreas.sandberg@arm.com if a[1] <= b[1]: 18511403Sandreas.sandberg@arm.com # A and B overlap with B not left of A and A not right of B 18611403Sandreas.sandberg@arm.com R.append(Region(b[0], a[1])) 18711403Sandreas.sandberg@arm.com 18811403Sandreas.sandberg@arm.com # Advance A because nothing is left 18911403Sandreas.sandberg@arm.com i += 1 19011403Sandreas.sandberg@arm.com 19111403Sandreas.sandberg@arm.com if a[1] == b[1]: 19211403Sandreas.sandberg@arm.com # Advance B too 19311403Sandreas.sandberg@arm.com j += 1 19411403Sandreas.sandberg@arm.com else: 19511403Sandreas.sandberg@arm.com # A and B overlap with B completely within the bounds of A 19611403Sandreas.sandberg@arm.com R.append(Region(b[0], b[1])) 19711403Sandreas.sandberg@arm.com 19811403Sandreas.sandberg@arm.com # Advance only B because some of A may still be useful 19911403Sandreas.sandberg@arm.com j += 1 20011403Sandreas.sandberg@arm.com elif b[1] <= a[0]: 20111403Sandreas.sandberg@arm.com # B is completely before A. Skip B. 20211403Sandreas.sandberg@arm.com j += 1 20311403Sandreas.sandberg@arm.com else: 20411403Sandreas.sandberg@arm.com assert b[0] < a[0] 20511403Sandreas.sandberg@arm.com if b[1] <= a[1]: 20611403Sandreas.sandberg@arm.com # A and B overlap with A not left of B and B not right of A 20711403Sandreas.sandberg@arm.com R.append(Region(a[0], b[1])) 20811403Sandreas.sandberg@arm.com 20911403Sandreas.sandberg@arm.com # Advance B because nothing is left 21011403Sandreas.sandberg@arm.com j += 1 21111403Sandreas.sandberg@arm.com 21211403Sandreas.sandberg@arm.com if a[1] == b[1]: 21311403Sandreas.sandberg@arm.com # Advance A too 21411403Sandreas.sandberg@arm.com i += 1 21511403Sandreas.sandberg@arm.com else: 21611403Sandreas.sandberg@arm.com # A and B overlap with A completely within the bounds of B 21711403Sandreas.sandberg@arm.com R.append(Region(a[0], a[1])) 21811403Sandreas.sandberg@arm.com 21911403Sandreas.sandberg@arm.com # Advance only A because some of B may still be useful 22011403Sandreas.sandberg@arm.com i += 1 22111403Sandreas.sandberg@arm.com 22211403Sandreas.sandberg@arm.com self.regions = R 22311403Sandreas.sandberg@arm.com return self 22411403Sandreas.sandberg@arm.com 22511403Sandreas.sandberg@arm.com def __and__(self, other): 22611403Sandreas.sandberg@arm.com result = self.copy() 22711403Sandreas.sandberg@arm.com result &= other 22811403Sandreas.sandberg@arm.com return result 22911403Sandreas.sandberg@arm.com 23011403Sandreas.sandberg@arm.com def __repr__(self): 23111403Sandreas.sandberg@arm.com return 'Regions(%s)' % ([(r[0], r[1]) for r in self.regions], ) 23211403Sandreas.sandberg@arm.com 23311403Sandreas.sandberg@arm.comall_regions = Regions(Region(neg_inf, pos_inf)) 23411403Sandreas.sandberg@arm.com 23511403Sandreas.sandberg@arm.comif __name__ == '__main__': 23611403Sandreas.sandberg@arm.com x = Regions(*((i, i + 1) for i in xrange(0,30,2))) 23711403Sandreas.sandberg@arm.com y = Regions(*((i, i + 4) for i in xrange(0,30,5))) 23811403Sandreas.sandberg@arm.com z = Region(6,7) 23911403Sandreas.sandberg@arm.com n = Region(9,10) 24011403Sandreas.sandberg@arm.com 24111403Sandreas.sandberg@arm.com def test(left, right): 24211403Sandreas.sandberg@arm.com print "%s == %s: %s" % (left, right, left == right) 24311403Sandreas.sandberg@arm.com print "%s != %s: %s" % (left, right, left != right) 24411403Sandreas.sandberg@arm.com print "%s < %s: %s" % (left, right, left < right) 24511403Sandreas.sandberg@arm.com print "%s <= %s: %s" % (left, right, left <= right) 24611403Sandreas.sandberg@arm.com print "%s > %s: %s" % (left, right, left > right) 24711403Sandreas.sandberg@arm.com print "%s >= %s: %s" % (left, right, left >= right) 24811403Sandreas.sandberg@arm.com print 24911403Sandreas.sandberg@arm.com 25011403Sandreas.sandberg@arm.com test(neg_inf, neg_inf) 25111403Sandreas.sandberg@arm.com test(neg_inf, pos_inf) 25211403Sandreas.sandberg@arm.com test(pos_inf, neg_inf) 25311403Sandreas.sandberg@arm.com test(pos_inf, pos_inf) 25411403Sandreas.sandberg@arm.com 25511403Sandreas.sandberg@arm.com test(neg_inf, 0) 25611403Sandreas.sandberg@arm.com test(neg_inf, -11111) 25711403Sandreas.sandberg@arm.com test(neg_inf, 11111) 25811403Sandreas.sandberg@arm.com 25911403Sandreas.sandberg@arm.com test(0, neg_inf) 26011403Sandreas.sandberg@arm.com test(-11111, neg_inf) 26111403Sandreas.sandberg@arm.com test(11111, neg_inf) 26211403Sandreas.sandberg@arm.com 26311403Sandreas.sandberg@arm.com test(pos_inf, 0) 26411403Sandreas.sandberg@arm.com test(pos_inf, -11111) 26511403Sandreas.sandberg@arm.com test(pos_inf, 11111) 26611403Sandreas.sandberg@arm.com 26711403Sandreas.sandberg@arm.com test(0, pos_inf) 26811403Sandreas.sandberg@arm.com test(-11111, pos_inf) 26911403Sandreas.sandberg@arm.com test(11111, pos_inf) 27011403Sandreas.sandberg@arm.com 27111403Sandreas.sandberg@arm.com print x 27211403Sandreas.sandberg@arm.com print y 27311403Sandreas.sandberg@arm.com print x & y 27411403Sandreas.sandberg@arm.com print z 27511403Sandreas.sandberg@arm.com 27611403Sandreas.sandberg@arm.com print 4 in x 27711403Sandreas.sandberg@arm.com print 4 in z 27811403Sandreas.sandberg@arm.com print 5 not in x 27911403Sandreas.sandberg@arm.com print 6 not in z 28011403Sandreas.sandberg@arm.com print z in y 28111403Sandreas.sandberg@arm.com print n in y, n not in y 282