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
27class _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)
36neg_inf = _neg_inf()
37
38class _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)
47pos_inf = _pos_inf()
48
49class 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
141class 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
233all_regions = Regions(Region(neg_inf, pos_inf))
234
235if __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
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
282