Number set type

[Heiko Wundram]

Justin  Azoff wrote:
> You could use IPy...
> http://svn.23.nu/svn/repos/IPy/trunk/IPy.py is one location for it...

I know about IPy... But: it simply doesn't implement all I need it for.

> I wonder where you get O(n) and O(n^2) from... CIDR blocks are all
> sequential.. All you need to store is the starting and ending address
> or length.  Then any set operation only has to deal with 4 numbers, and
> should be literally a few lines of code with no loops.

You make assumptions that my usage simply doesn't fill. An IP4Range must
consist of more than a single block of IP addresses (like 192.168.0.0/24
_and_ 192.168.10.0/24), that's why it's an IP4Range and not a IP4Network
(which I implement as an addr/mask pair in my IP4 abstraction).

An IP4Range can consist of several different ranges (which are of course
normalized and disjunct). I can specify what I meant by O(n) and O(n^2):

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.

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.

Just as intersection and union can be done more efficiently, I guess that
several set operations can be done the simple way (like
self.difference(other) <=> self.union(other.inverse()), whereby inverse is
O(n) too), but still maybe there are better algorithms to do it directly.

Anyway, that's why I wanted to have a look at a ready implementation of a
number set type so that I might get a glimpse at somebody elses
implementation.

--- Heiko.