text: # 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("\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)
  