ip.py

class Node(object):
    def __init__(self, value, is_start):
        self.value = value
        self.is_start = is_start

    def __lt__(self, other):
        if self.value != other.value:
            return self.value < other.value
        if self.is_start != other.is_start:
            return self.is_start
        return False

    def __repr__(self):
        return '.'.join(str(v) for v in [((self.value >> 24) & 0xff),
                                         ((self.value >> 16) & 0xff),
                                         ((self.value >> 8) & 0xff),
                                         (self.value & 0xff)]) + ('S' if self.is_start else 'E')

def ip_to_num(ip):
    split = ip.split('.')
    assert len(split) == 4
    v = [int(i) for i in split]
    return (v[0] << 24) + (v[1] << 16) + (v[2] << 8) + v[3]


def ip_range_to_nodes(ip_range):
    split = ip_range.split('/')
    if len(split) == 1 or split[1] == '32':
        value = ip_to_num(split[0])
        return Node(value, True), Node(value, False)
    elif len(split) == 2:
        value = ip_to_num(split[0])
        mask = (2 << (31 - int(split[1]))) - 1
        start_value = value - (value & mask)
        end_value = start_value + mask
        return Node(start_value, True), Node(end_value, False)
    else:
        assert False


def merge_nodes(nodes):
    nodes.sort()
    start_node = None
    level = 0
    result = []
    for node in nodes:
        if start_node is None:
            assert node.is_start
            start_node = node
            level = 1
            continue

        if node.is_start:
            level += 1
            continue

        level -= 1
        if level == 0:
            result.append((start_node, node))
            start_node = None

    assert start_node is None
    return result


def index_of(nodes, value):
    left, right = 0, len(nodes) - 1
    while left <= right:
        mid = (left + right) / 2
        start_value, end_value = nodes[mid][0].value, nodes[mid][1].value
        if end_value < value:
            left = mid + 1
        elif start_value > value:
            right = mid - 1
        else:
            return mid
    return -1


def main():
    from itertools import chain
    IP_list1=['192.168.1.0/24', '192.168.2.1/24', '222.42.112.234/24']
    IP_list2=['192.168.1.0/26', '192.168.3.1/24', '221.234.47.12', '222.42.112.2']
    nodes = list(chain.from_iterable(ip_range_to_nodes(ip) for ip in IP_list1))
    segments = merge_nodes(nodes)

    for ip in IP_list2:
        start, end = ip_range_to_nodes(ip)
        start_index, end_index = index_of(segments, start.value), index_of(segments, end.value)
        if start_index != -1 and start_index == end_index:
            print ip


if __name__ == '__main__':
    main()