Range Module


for question 1
The loop in the function
_bounds()
is an improvement for finding the upper bound and lower bound faster (instead of increase/decrease only by 1).The original code may something like this:
while i < len(self.ranges) and self.ranges[i][1] < left: i += 1 while j >= 0 and self.ranges[j][0] > right: j = 1
If we didn't use
i + d  1
, the improved code will have different semantic from the original.Think of the following two cases. (d == 1)
self.ranges[i][1] < left
butself.ranges[i + 1][1] >= left
self.ranges[i][1] < left
buti + 1 >= len(self.ranges)
As we want the final
i
to satisfy the conditionself.ranges[i][1] >= left
. If we usei + d
instead ofi + d  1
, in either case, the returnedi
would be offbyone.for question 2
The bisect in the function
queryRange
is for finding the first segment (leftoriented) which overlapped to(left, right)
. Thefloat('inf')
is for normalize the returned value ofbisect_left
. As the subsequent code isif i: i = 1
.Assume we have
[(1, 10), (60, 80)]
in theself.ranges
. Think of the two cases.queryRange
for the range(1, 6)
queryRange
for the range(2, 6)
In either case, we want the final
i
to be0
. If we use
(left, )
to bisect the range, case 1bisect_left
will return 0 and case 2 will return 1.  if we use
(left, float('inf'))
to bisect, case 1bisect_left
will return 1 and case 2 will return 1.
Note that the following line is
if i: i = 1
. Obviously, use(left, float('inf'))
to bisect will get the code correct.

@awice, it seems the java solution gives wrong result for the following test cases:
addRange(1,9);
addRange(10,20);
queryRange(9,10);
results intrue
which is not correct.the fix is in the
addRange()
method change
Iterator<Interval> itr = ranges.tailSet(new Interval(0, left  1)).iterator();
to
Iterator<Interval> itr = ranges.tailSet(new Interval(0, left)).iterator();

@awice
Thanks for your excellent explanation!
But as for the Java code,I think in the addRange method,this line:
Iterator<Interval> itr = ranges.tailSet(new Interval(0, left  1)).iterator();
left  1 is quite confusing.It should be modified as left.
If I am wrong,please correct me please.Thanks!!!