fork download
copy 
  1. import socket
  2. import struct
  3. import bisect
  4.  
  5.  
  6. def ip2long(ip):
  7.     '''IP to integer'''
  8.     packed = socket.inet_aton(ip)
  9.     return struct.unpack("!L", packed)[0]
  10.  
  11.  
  12. def long2ip(n):
  13.     '''integer to IP'''
  14.     unpacked = struct.pack('!L', n)
  15.     return socket.inet_ntoa(unpacked)
  16.  
  17.  
  18. def get_ips(s):
  19.     '''Convert string IP interval to tuple with integer representations of boundary IPs
  20. '1.1.1.1-7' -> (a,b)'''
  21.     s1,s2 = s.split('-')
  22.     if s2.isdigit():
  23.         s2 = s1[:-1] + s2
  24.     return (ip2long(s1),ip2long(s2))
  25.  
  26.  
  27. def add_range(iv,R):
  28.     '''add new Range to already merged ranges inplace'''
  29.     left,right = get_ips(R)
  30.     #left,right are left and right boundaries of the Range respectively
  31.  
  32.     #If this is the very first Range just add it to the list
  33.     if not iv:
  34.         iv.append([left,right])
  35.         return
  36.  
  37.     #Searching the first interval with left_boundary < left range side
  38.     p = bisect.bisect_right(iv, [left,right]) #place after the needed interval
  39.     p -= 1 #calculating the number of interval basing on the position where the insertion is needed
  40.  
  41.     to_extend = None
  42.  
  43.     #Interval: |----X----| (delete)    
  44.     #Range:   <--<--|----------| (extend)
  45.     #Detect if the left Range side is inside the found interval
  46.     if p >=0: #if p==-1 then there was no interval found
  47.         if iv[p][1]>= right:
  48.             #Detect if the Range is completely inside the interval
  49.             return #drop the Range; I think it will be a very common case
  50.  
  51.         if iv[p][1] >= left-1:
  52.             left = iv[p][0] #extending the left Range interval
  53.             to_extend = iv[p]
  54.             #del iv[p] #deleting the interval from the interval list
  55.             #p -= 1 #correcting index to keep the invariant
  56.  
  57.  
  58.     #Intervals:   |----X----| |---X---| (delete)    
  59.     #Range:  |-----------------------------|        
  60.     #Deleting all the intervals which are inside the Range interval
  61.     while True:
  62.         p += 1
  63.         if p >= len(iv) or iv[p][0] >= right or iv[p][1] > right:
  64.             'Stopping searching for the intervals which is inside the Range interval'
  65.             #there are no more intervals or
  66.             #the interval is to the right of the right Range side
  67.             # it's the next case (right Range side is inside the interval)
  68.             break
  69.         if to_extend is None:
  70.             to_extend = iv[p]
  71.             continue
  72.         del iv[p] #delete the now redundant interval from the interval list
  73.         p -= 1 #correcting index to keep the invariant
  74.  
  75.  
  76.     #Interval: |--------X--------| (delete)    
  77.     #Range: |-----------|-->--> (extend)    
  78.     #Working the case when the right Range side is inside the interval
  79.     if p < len(iv) and iv[p][0] <= right-1:
  80.         #there is no condition for right interval side since
  81.         #this case would have already been worked in the previous block
  82.         right = iv[p][1] #extending the right Range side
  83.         if to_extend is None:
  84.             to_extend = iv[p]
  85.         else:
  86.             del iv[p] #delete the now redundant interval from the interval list
  87.             #No p -= 1, so that p is no pointing to the beginning of the next interval
  88.             #which is the position of insertion
  89.  
  90.  
  91.     #Inserting the new interval to the list
  92.     if to_extend is None:
  93.         iv.insert(p, [left,right])
  94.     else:   
  95.         #Extending the interval
  96.         to_extend[:] = [left,right]
  97.  
  98.  
  99. def merge_ranges(ranges):
  100.     '''Merge the ranges'''
  101.     iv = []
  102.     for R in ranges:
  103.         add_range(iv,R)
  104.     return ['-'.join((long2ip(left),long2ip(right))) for left,right in iv]
  105.  
  106. ranges = ('10.10.255.1-255','10.11.0.0-50')
  107. print(merge_ranges(ranges))
  108.  
Success #stdin #stdout 0.03s 4876KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
['10.10.255.1-10.11.0.50']
https://ideone.com/ME8aU
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!