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. -- http://mail.python.org/mailman/listinfo/python-list
