util/style/region.py

   1 # Copyright (c) 2006 Nathan Binkert <nate@binkert.org>
   2 # All rights reserved.
   3 #
   4 # Redistribution and use in source and binary forms, with or without
   5 # modification, are permitted provided that the following conditions are
   6 # met: redistributions of source code must retain the above copyright
   7 # notice, this list of conditions and the following disclaimer;
   8 # redistributions in binary form must reproduce the above copyright
   9 # notice, this list of conditions and the following disclaimer in the
  10 # documentation and/or other materials provided with the distribution;
  11 # neither the name of the copyright holders nor the names of its
  12 # contributors may be used to endorse or promote products derived from
  13 # this software without specific prior written permission.
  14 #
  15 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  16 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  17 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  18 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  19 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  20 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  21 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  25 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26
  27 class _neg_inf(object):
  28     '''This object always compares less than any other object'''
  29     def __repr__(self): return '<neg_inf>'
  30     def __lt__(self, other): return type(self) != type(other)
  31     def __le__(self, other): return True
  32     def __gt__(self, other): return False
  33     def __ge__(self, other): return type(self) == type(other)
  34     def __eq__(self, other): return type(self) == type(other)
  35     def __ne__(self, other): return type(self) != type(other)
  36 neg_inf = _neg_inf()
  37
  38 class _pos_inf(object):
  39     '''This object always compares greater than any other object'''
  40     def __repr__(self): return '<pos_inf>'
  41     def __lt__(self, other): return False
  42     def __le__(self, other): return type(self) == type(other)
  43     def __gt__(self, other): return type(self) != type(other)
  44     def __ge__(self, other): return True
  45     def __eq__(self, other): return type(self) == type(other)
  46     def __ne__(self, other): return type(self) != type(other)
  47 pos_inf = _pos_inf()
  48
  49 class Region(tuple):
  50     '''A region (range) of [start, end).
  51     This includes utility functions to compare overlap of regions.'''
  52     def __new__(cls, *args):
  53         if len(args) == 1:
  54             arg = args[0]
  55             if isinstance(arg, Region):
  56                 return arg
  57             args = tuple(arg)
  58
  59         if len(args) != 2:
  60             raise(AttributeError, \
  61                 "Only one or two arguments allowed, %d provided" % (alen, ))
  62
  63         return tuple.__new__(cls, args)
  64
  65     def __repr__(self):
  66         return 'Region(%s, %s)' % (self[0], self[1])
  67
  68     @property
  69     def start(self):
  70         return self[0]
  71
  72     @property
  73     def end(self):
  74         return self[1]
  75
  76     def __contains__(self, other):
  77         '''other is
  78         region: True if self and other is fully contained within self.
  79         pos: True if other is within the region'''
  80         if isinstance(other, tuple):
  81             return self[0] <= other[0] and self[1] >= other[1]
  82         return self[0] <= other and other < self[1]
  83
  84     def __eq__(self, other):
  85         '''other is
  86         region: True if self and other are identical.
  87         pos: True if other is within the region'''
  88         if isinstance(other, tuple):
  89             return self[0] == other[0] and self[1] == other[1]
  90         return self[0] <= other and other < self[1]
  91
  92     # @param self is a region.
  93     # @param other is a region.
  94     # @return if self and other are not identical.
  95     def __ne__(self, other):
  96         '''other is
  97         region: true if they are not identical
  98         pos: True if other is not in the region'''
  99         if isinstance(other, tuple):
 100             return self[0] != other[0] or self[1] != other[1]
 101         return other < self[0] or self[1] <= other
 102
 103     # @param self is a region.
 104     # @param other is a region.
 105     # @return if self is less than other and does not overlap self.
 106     def __lt__(self, other):
 107         "self completely left of other (cannot overlap)"
 108         if isinstance(other, tuple):
 109             return self[1] <= other[0]
 110         return self[1] <= other
 111
 112     # @param self is a region.
 113     # @param other is a region.
 114     # @return if self is less than other.  self may overlap other,
 115     # but not extend beyond the _end of other.
 116     def __le__(self, other):
 117         "self extends to the left of other (can overlap)"
 118         if isinstance(other, tuple):
 119             return self[0] <= other[0]
 120         return self[0] <= other
 121
 122     # @param self is a region.
 123     # @param other is a region.
 124     # @return if self is greater than other and does not overlap other.
 125     def __gt__(self, other):
 126         "self is completely right of other (cannot overlap)"
 127         if isinstance(other, tuple):
 128             return self[0] >= other[1]
 129         return self[0] > other
 130
 131     # @param self is a region.
 132     # @param other is a region.
 133     # @return if self is greater than other.  self may overlap other,
 134     # but not extend beyond the beginning of other.
 135     def __ge__(self, other):
 136         "self ex_ends beyond other to the right (can overlap)"
 137         if isinstance(other, tuple):
 138             return self[1] >= other[1]
 139         return self[1] > other
 140
 141 class Regions(object):
 142     '''A set of regions (ranges).  Basically a region with holes.
 143     Includes utility functions to merge regions and figure out if
 144     something is in one of the regions.'''
 145     def __init__(self, *args):
 146         self.regions = []
 147         self.extend(*args)
 148
 149     def copy(self):
 150         copy = Regions()
 151         copy.regions.extend(self.regions)
 152         return copy
 153
 154     def append(self, *args):
 155         self.regions.append(Region(*args))
 156
 157     def extend(self, *args):
 158         self.regions.extend(Region(a) for a in args)
 159
 160     def __contains__(self, position):
 161         for region in self.regions:
 162             if position in region:
 163                 return True
 164
 165         return False
 166
 167     def __len__(self):
 168         return len(self.regions)
 169
 170     def __iand__(self, other):
 171         A = self.regions
 172         B = other.regions
 173         R = []
 174
 175         i = 0
 176         j = 0
 177         while i < len(self) and j < len(other):
 178             a = A[i]
 179             b = B[j]
 180             if a[1] <= b[0]:
 181                 # A is completely before B.  Skip A
 182                 i += 1
 183             elif a[0] <= b[0]:
 184                 if a[1] <= b[1]:
 185                     # A and B overlap with B not left of A and A not right of B
 186                     R.append(Region(b[0], a[1]))
 187
 188                     # Advance A because nothing is left
 189                     i += 1
 190
 191                     if a[1] == b[1]:
 192                         # Advance B too
 193                         j += 1
 194                 else:
 195                     # A and B overlap with B completely within the bounds of A
 196                     R.append(Region(b[0], b[1]))
 197
 198                     # Advance only B because some of A may still be useful
 199                     j += 1
 200             elif b[1] <= a[0]:
 201                 # B is completely before A. Skip B.
 202                 j += 1
 203             else:
 204                 assert b[0] < a[0]
 205                 if b[1] <= a[1]:
 206                     # A and B overlap with A not left of B and B not right of A
 207                     R.append(Region(a[0], b[1]))
 208
 209                     # Advance B because nothing is left
 210                     j += 1
 211
 212                     if a[1] == b[1]:
 213                         # Advance A too
 214                         i += 1
 215                 else:
 216                     # A and B overlap with A completely within the bounds of B
 217                     R.append(Region(a[0], a[1]))
 218
 219                     # Advance only A because some of B may still be useful
 220                     i += 1
 221
 222         self.regions = R
 223         return self
 224
 225     def __and__(self, other):
 226         result = self.copy()
 227         result &= other
 228         return result
 229
 230     def __repr__(self):
 231         return 'Regions(%s)' % ([(r[0], r[1]) for r in self.regions], )
 232
 233 all_regions = Regions(Region(neg_inf, pos_inf))
 234
 235 if __name__ == '__main__':
 236     x = Regions(*((i, i + 1) for i in xrange(0,30,2)))
 237     y = Regions(*((i, i + 4) for i in xrange(0,30,5)))
 238     z = Region(6,7)
 239     n = Region(9,10)
 240
 241     def test(left, right):
 242         print("%s == %s: %s" % (left, right, left == right))
 243         print("%s != %s: %s" % (left, right, left != right))
 244         print("%s <  %s: %s" % (left, right, left <  right))
 245         print("%s <= %s: %s" % (left, right, left <= right))
 246         print("%s >  %s: %s" % (left, right, left >  right))
 247         print("%s >= %s: %s" % (left, right, left >= right))
 248         print("\n")
 249
 250     test(neg_inf, neg_inf)
 251     test(neg_inf, pos_inf)
 252     test(pos_inf, neg_inf)
 253     test(pos_inf, pos_inf)
 254
 255     test(neg_inf, 0)
 256     test(neg_inf, -11111)
 257     test(neg_inf, 11111)
 258
 259     test(0, neg_inf)
 260     test(-11111, neg_inf)
 261     test(11111, neg_inf)
 262
 263     test(pos_inf, 0)
 264     test(pos_inf, -11111)
 265     test(pos_inf, 11111)
 266
 267     test(0, pos_inf)
 268     test(-11111, pos_inf)
 269     test(11111, pos_inf)
 270
 271     print(x)
 272     print(y)
 273     print(x & y)
 274     print(z)
 275
 276     print(4 in x)
 277     print(4 in z)
 278     print(5 not in x)
 279     print(6 not in z)
 280     print(z in y)
 281     print(n in y, n not in y)