Merge pull request #42 from snordhausen/master

Even more performance, extended __contains__

2 files changed, 84 insertions, 59 deletions

diff --git a/netaddr/ip/__init__.py b/netaddr/ip/__init__.py
index 8feaad4..de20126 100644
--- a/netaddr/ip/__init__.py
+++ b/netaddr/ip/__init__.py
@@ -743,11 +743,16 @@ class IPListMixin(object):
         :return: ``True`` if other falls within the boundary of this one,
             ``False`` otherwise.
         """
-        if self._module.version != other.version:
-            return False
-        if hasattr(other, '_value') and not hasattr(other, '_prefixlen'):
-            return other._value >= self.first and other._value <= self.last
-        return other.first >= self.first and other.last <= self.last
+        if isinstance(other, BaseIP):
+            if self._module.version != other._module.version:
+                return False
+            if isinstance(other, IPAddress):
+                return other._value >= self.first and other._value <= self.last
+            # Assume that we (and the other) provide .first and .last.
+            return other.first >= self.first and other.last <= self.last
+
+        # Whatever it is, try to interpret it as IPAddress.
+        return IPAddress(other) in self
 
     def __nonzero__(self):
         """
@@ -1101,19 +1106,28 @@ class IPNetwork(BaseIP, IPListMixin):
         :return: ``True`` if other falls within the boundary of this one,
             ``False`` otherwise.
         """
-        if self._module.version != other._module.version:
-            return False
-        if isinstance(other, IPRange):
-            # IPRange has no _value.
-            return (self.first <= other._start._value) and (self.last >= other._end._value)
-
-        shiftwidth = self._module.width - self._prefixlen
-        other_val = other._value >> shiftwidth
-        self_val = self._value >> shiftwidth
-        if isinstance(other, IPAddress):
-            return other_val == self_val
-        # Must be IPNetwork
-        return self_val == other_val and self._prefixlen <= other._prefixlen
+        if isinstance(other, BaseIP):
+            if self._module.version != other._module.version:
+                return False
+
+            # self_net will contain only the network bits.
+            shiftwidth = self._module.width - self._prefixlen
+            self_net = self._value >> shiftwidth
+            if isinstance(other, IPRange):
+                # IPRange has no _value.
+                # (self_net+1)<<shiftwidth is not our last address, but the one
+                # after the last one.
+                return ((self_net << shiftwidth) <= other._start._value and
+                        (((self_net + 1) << shiftwidth) > other._end._value))
+
+            other_net = other._value >> shiftwidth
+            if isinstance(other, IPAddress):
+                return other_net == self_net
+            if isinstance(other, IPNetwork):
+                return self_net == other_net and self._prefixlen <= other._prefixlen
+
+        # Whatever it is, try to interpret it as IPAddress.
+        return IPAddress(other) in self
 
     def key(self):
         """
@@ -1126,8 +1140,9 @@ class IPNetwork(BaseIP, IPListMixin):
         :return: A key tuple used to compare and sort this `IPNetwork` correctly.
         """
         net_size_bits = self._prefixlen - 1
-        host_bits = self._value - self.first
-        return self._module.version, self.first, net_size_bits, host_bits
+        first = self._value & (self._module.max_int ^ self._hostmask_int)
+        host_bits = self._value - first
+        return self._module.version, first, net_size_bits, host_bits
 
     def ipv4(self):
         """
@@ -1363,6 +1378,28 @@ class IPRange(BaseIP, IPListMixin):
         self._module = self._start._module
         self._end = IPAddress(end, version)
 
+    def __contains__(self, other):
+        if isinstance(other, BaseIP):
+            if self._module.version != other._module.version:
+                return False
+            if isinstance(other, IPAddress):
+                return (self._start._value <= other._value and
+                        self._end._value >= other._value)
+            if isinstance(other, IPRange):
+                return (self._start._value <= other._start._value and
+                        self._end._value >= other._end._value)
+            if isinstance(other, IPNetwork):
+                shiftwidth = other._module.width - other._prefixlen
+                other_start = (other._value >> shiftwidth) << shiftwidth
+                # Start of the next network after other
+                other_next_start = other_start + (1 << shiftwidth)
+
+                return (self._start._value <= other_start and
+                        self._end._value > other_next_start)
+
+        # Whatever it is, try to interpret it as IPAddress.
+        return IPAddress(other) in self
+
     @property
     def first(self):
         """The integer value of first IP address in this `IPRange` object."""
@@ -1384,7 +1421,7 @@ class IPRange(BaseIP, IPListMixin):
         :return: A key tuple used to compare and sort this `IPRange` correctly.
         """
         skey = self._module.width - num_bits(self.size)
-        return self._module.version, self.first, skey
+        return self._module.version, self._start._value, skey
 
     def cidrs(self):
         """
diff --git a/netaddr/ip/sets.py b/netaddr/ip/sets.py
index bd3788f..0107f74 100644
--- a/netaddr/ip/sets.py
+++ b/netaddr/ip/sets.py
@@ -431,22 +431,10 @@ class IPSet(object):
         :return: ``True`` if every IP address and subnet in this IP set
             is found within ``other``.
         """
-        if not hasattr(other, '_cidrs'):
-            return NotImplemented
-
-        l_ipv4, l_ipv6 = partition_ips(self._cidrs)
-        r_ipv4, r_ipv6 = partition_ips(other._cidrs)
-
-        l_ipv4_iset = _IntSet(*[(c.first, c.last) for c in l_ipv4])
-        r_ipv4_iset = _IntSet(*[(c.first, c.last) for c in r_ipv4])
-
-        l_ipv6_iset = _IntSet(*[(c.first, c.last) for c in l_ipv6])
-        r_ipv6_iset = _IntSet(*[(c.first, c.last) for c in r_ipv6])
-
-        ipv4 = l_ipv4_iset.issubset(r_ipv4_iset)
-        ipv6 = l_ipv6_iset.issubset(r_ipv6_iset)
-
-        return ipv4 and ipv6
+        for cidr in self._cidrs:
+            if cidr not in other:
+                return False
+        return True
 
     __le__ = issubset
 
@@ -472,19 +460,10 @@ class IPSet(object):
         if not hasattr(other, '_cidrs'):
             return NotImplemented
 
-        l_ipv4, l_ipv6 = partition_ips(self._cidrs)
-        r_ipv4, r_ipv6 = partition_ips(other._cidrs)
-
-        l_ipv4_iset = _IntSet(*[(c.first, c.last) for c in l_ipv4])
-        r_ipv4_iset = _IntSet(*[(c.first, c.last) for c in r_ipv4])
-
-        l_ipv6_iset = _IntSet(*[(c.first, c.last) for c in l_ipv6])
-        r_ipv6_iset = _IntSet(*[(c.first, c.last) for c in r_ipv6])
-
-        ipv4 = l_ipv4_iset.issuperset(r_ipv4_iset)
-        ipv6 = l_ipv6_iset.issuperset(r_ipv6_iset)
-
-        return ipv4 and ipv6
+        for cidr in other._cidrs:
+            if cidr not in self:
+                return False
+        return True
 
     __ge__ = issuperset
 
@@ -520,7 +499,7 @@ class IPSet(object):
 
         ipv4_result = l_ipv4_iset & r_ipv4_iset
 
-        for start, end in list(ipv4_result._ranges):
+        for start, end in ipv4_result._ranges:
             cidrs = iprange_to_cidrs(IPAddress(start, 4), IPAddress(end-1, 4))
             cidr_list.extend(cidrs)
 
@@ -530,11 +509,14 @@ class IPSet(object):
 
         ipv6_result = l_ipv6_iset & r_ipv6_iset
 
-        for start, end in list(ipv6_result._ranges):
+        for start, end in ipv6_result._ranges:
             cidrs = iprange_to_cidrs(IPAddress(start, 6), IPAddress(end-1, 6))
             cidr_list.extend(cidrs)
 
-        return IPSet(cidr_list)
+        result = IPSet()
+        # None of these CIDRs can be compacted, so skip that operation.
+        result._cidrs = dict.fromkeys(cidr_list, True)
+        return result
 
     __and__ = intersection
 
@@ -558,7 +540,7 @@ class IPSet(object):
 
         ipv4_result = l_ipv4_iset ^ r_ipv4_iset
 
-        for start, end in list(ipv4_result._ranges):
+        for start, end in ipv4_result._ranges:
             cidrs = iprange_to_cidrs(IPAddress(start, 4), IPAddress(end-1, 4))
             cidr_list.extend(cidrs)
 
@@ -568,11 +550,14 @@ class IPSet(object):
 
         ipv6_result = l_ipv6_iset ^ r_ipv6_iset
 
-        for start, end in list(ipv6_result._ranges):
+        for start, end in ipv6_result._ranges:
             cidrs = iprange_to_cidrs(IPAddress(start, 6), IPAddress(end-1, 6))
             cidr_list.extend(cidrs)
 
-        return IPSet(cidr_list)
+        result = IPSet()
+        # None of these CIDRs can be compacted, so skip that operation.
+        result._cidrs = dict.fromkeys(cidr_list, True)
+        return result
 
     __xor__ = symmetric_difference
 
@@ -596,7 +581,7 @@ class IPSet(object):
 
         ipv4_result = l_ipv4_iset - r_ipv4_iset
 
-        for start, end in list(ipv4_result._ranges):
+        for start, end in ipv4_result._ranges:
             cidrs = iprange_to_cidrs(IPAddress(start, 4), IPAddress(end-1, 4))
             cidr_list.extend(cidrs)
 
@@ -606,11 +591,14 @@ class IPSet(object):
 
         ipv6_result = l_ipv6_iset - r_ipv6_iset
 
-        for start, end in list(ipv6_result._ranges):
+        for start, end in ipv6_result._ranges:
             cidrs = iprange_to_cidrs(IPAddress(start, 6), IPAddress(end-1, 6))
             cidr_list.extend(cidrs)
 
-        return IPSet(cidr_list)
+        result = IPSet()
+        # None of these CIDRs can be compacted, so skip that operation.
+        result._cidrs = dict.fromkeys(cidr_list, True)
+        return result
 
     __sub__ = difference