Number set type

[Justin Azoff]

Heiko Wundram wrote:
> Union of two IP4Ranges is simply normalizing a concatenated list of both
> IP4Range ranges. Normalizing takes O(log n)+O(n) = O(n) steps, where n is
> the number of ranges in the combined IP4Range.

I see now :-)  If the ranges are sorted, I bet you could just iterate
through both at the same time, merging intersecting ranges where
possible.

> Intersection takes O(n^2) steps in my current implementation (which I know
> is mathematically correct), where n is max(n_1,n_2) where n_1 is the number
> of ranges in the first IP4Range and n_2 the number of ranges in the second
> IP4Range respectively.
>
> Intersecting two IP4Ranges can be done with fewer steps, and I think it
> could be done in O(n) in the case of normalized and sorted ranges, and I
> have a few ideas of myself, but I'm currently too lazy to try to prove them
> correct.

Yes.. if they are sorted, something like this should work:

    def intersection(self, other):
        ret = []
        ai=iter(self.ranges)
        bi=iter(other.ranges)
        try :
            a = ai.next()
            b = bi.next()
        except StopIteration:
            return IP4Range([])

        while 1:
            try :
                if a.intersects(b):
                    ret.append(a.intersection(b))
                    a = ai.next()
                    b = bi.next()
                elif a.start < b.start:
                    a = ai.next()
                else :
                    b = bi.next()
            except StopIteration:
                break
        return IP4Range(ret)


-- 
- Justin