# 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