Advertisement
Guest User

Untitled

a guest
Oct 31st, 2015
395
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/bin/sh
  2. exec /Users/baldur/scala-2.11.7/bin/scala "$0" "$@"
  3. !#
  4.  
  5. val inputRE = """\s*(add|remove)\s+(\d+)\.(\d+)\.(\d+)\.(\d+)/(\d+)\s*""".r
  6. def toIP(i1: Int, i2: Int, i3: Int, i4: Int) = (i1 << 24) | (i2 << 16) | (i3 << 8) | i4
  7. def ipToString(ip: Int): String = f"${(ip>>24)&255}.${(ip>>16)&255}.${(ip>>8)&255}.${ip&255}"
  8. case class Subnet(ip: Int, prefixLength: Int) {
  9.   override def toString: String = f"${ipToString(ip)}/${prefixLength}"
  10. }
  11. def netmask(prefixLength: Int) = if (prefixLength==0) 0 else -1 << (32 - prefixLength)
  12.  
  13. // a valid subnet is a subnet where (ip & netmask) == ip
  14. def makeValid(subnet: Subnet): Subnet =
  15.   subnet.copy(ip = subnet.ip & netmask(subnet.prefixLength))
  16.  
  17. // split a subnet into two each with prefixLength+1
  18. def split(subnet: Subnet): (Subnet,Subnet) = (
  19.   Subnet(subnet.ip, subnet.prefixLength + 1),
  20.   Subnet(subnet.ip + (1 << (31 - subnet.prefixLength)), subnet.prefixLength + 1))
  21.  
  22. /*
  23.   subnetList: current set of subnets that shall be expanded
  24.   subnetToAdd: subnet that will be added to subnetList
  25.   returns: set of subnets that includes everything from subnetList plus subnetToAdd
  26.  
  27.   requirements:
  28.  
  29.   subnetToAdd is valid
  30.  
  31.   subnetList is optimal
  32.   subnetList does not contain overlapping subnets
  33.   subnetList does not contain subnets that could be merged
  34.   subnetList does not contain invalid subnets
  35.  
  36.   return value provides same guaranties
  37. */
  38. def add(subnetList: Set[Subnet], subnetToAdd: Subnet): Set[Subnet] = {
  39.   // 1) remove all subnets covered by subnetToAdd
  40.   val subnetList2 = subnetList.filterNot { subnet =>
  41.     subnet.prefixLength >= subnetToAdd.prefixLength &&
  42.       ((subnet.ip & netmask(subnetToAdd.prefixLength)) == subnetToAdd.ip)
  43.   }
  44.      
  45.   // 2) add subnetToAdd
  46.   val subnetList3 = subnetList2 + subnetToAdd
  47.  
  48.   // 3) possibly merge subnetToAdd with adjicent subnet
  49.   // 4) recursively perform step 4 until no merge or 0.0.0.0/0
  50.   def merge(subnetList: Set[Subnet], toBeMerged: Subnet): Set[Subnet] = {
  51.     if (toBeMerged.prefixLength == 0) return subnetList
  52.     val supernet = makeValid(Subnet(toBeMerged.ip,toBeMerged.prefixLength-1))
  53.     val (subnet1,subnet2) = split(supernet)
  54.     // either subnet1 or subnet2 will be equal to toBeMerged
  55.     if (subnetList(subnet1) && subnetList(subnet2)) {
  56.       // two subnets found, remove both and add supernet instead
  57.       // then run merge recursively
  58.       merge(subnetList - subnet1 - subnet2 + supernet, supernet)
  59.     } else {
  60.       // done, could not find two subnets to merge
  61.       subnetList
  62.     }
  63.    
  64.   }
  65.  
  66.   merge(subnetList3, subnetToAdd)
  67. }
  68.  
  69. /*
  70.   subnetList: current set of subnets that shall be reduced
  71.   subnetToRemove: subnet that will be removed from subnetList
  72.   returns: set of subnets that includes all address space covered by subnetList excluding subnetToRemove
  73.  
  74.   requirements:
  75.  
  76.   subnetList is optimal
  77.   subnetList does not contain overlapping subnets
  78.   subnetList does not contain subnets that could be merged
  79.   subnetList does not contain invalid subnets
  80.  
  81.   return value provides same guaranties
  82. */
  83. def remove(subnetList: Set[Subnet], subnetToRemove: Subnet): Set[Subnet] = {
  84.   // 1) remove all subnets covered by subnetToRemove
  85.   val subnetList2 = subnetList.filterNot { subnet =>
  86.     subnet.prefixLength >= subnetToRemove.prefixLength &&
  87.       ((subnet.ip & netmask(subnetToRemove.prefixLength)) == subnetToRemove.ip)
  88.   }
  89.  
  90.   // 2) find all subnets that covers subnetToRemove
  91.   val subnetCoversList = subnetList2.filter { subnet =>
  92.     (subnetToRemove.ip & netmask(subnet.prefixLength)) == subnet.ip
  93.   }
  94.  
  95.   // 3) select bestMatch, that is the one of largest prefixLength
  96.   val bestMatch = subnetCoversList.toVector.sortBy(-_.prefixLength).headOption.getOrElse {
  97.     // subnetCoversList is empty so we are done
  98.     return subnetList2
  99.   }
  100.  
  101.   // 4) remove bestMatch
  102.   val subnetList3 = subnetList2 - bestMatch
  103.  
  104.   // 5) possibly split bestMatch and add the half that does not cover subnetToRemove
  105.   // 6) recursively perform step 4 until subnet to split is equal to subnetToRemove
  106.   def splitStep(subnetList: Set[Subnet], toBeSplit: Subnet): Set[Subnet] = {
  107.     if (toBeSplit == subnetToRemove) return subnetList
  108.     val (subnet1,subnet2) = split(toBeSplit)
  109.     if ((subnetToRemove.ip & netmask(subnet1.prefixLength)) == subnet1.ip) {
  110.       // add subnet2 and split subnet1
  111.       splitStep(subnetList + subnet2, subnet1)
  112.     } else {
  113.       // add subnet1 and split subnet2
  114.       splitStep(subnetList + subnet1, subnet2)
  115.     }
  116.   }
  117.  
  118.   splitStep(subnetList3, bestMatch)
  119. }
  120.  
  121. val input = io.Source.stdin.getLines.collect {
  122.   case inputRE(command,i1,i2,i3,i4,l) =>
  123.     (command,makeValid(Subnet(toIP(i1.toInt,i2.toInt,i3.toInt,i4.toInt),l.toInt)))
  124. }
  125.  
  126. val result = input.foldLeft[Set[Subnet]](Set.empty){ case (acc,op) => op match {
  127.   case ("add",subnet: Subnet) => add(acc,subnet)
  128.   case ("remove",subnet: Subnet) => remove(acc,subnet)
  129. }}
  130.  
  131. for(subnet <- result.toVector.sortBy(_.prefixLength).sortBy(_.ip.toLong & 0xffffffffL))
  132.   println(subnet)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement