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.