From f74d9ccfb98a2ac25b4eebbfadf9a16b7a5202e1 Mon Sep 17 00:00:00 2001
From: Michael Orlitzky <michael@orlitzky.com>
Date: Sun, 9 May 2010 13:49:56 -0400
Subject: [PATCH] Added the functions to combine and remove adjacent Cidrs.
 Updated combine_all to perform both types (contained, adjacent) of
 combination.

---
 src/Cidr.hs | 42 ++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 40 insertions(+), 2 deletions(-)

diff --git a/src/Cidr.hs b/src/Cidr.hs
index 1b7d1dd..08eebcb 100644
--- a/src/Cidr.hs
+++ b/src/Cidr.hs
@@ -4,6 +4,8 @@ module Cidr
   combine_all
 ) where
 
+import Data.List (nubBy)
+
 import IPv4Address
 import ListUtils
 import Maskable
@@ -21,6 +23,15 @@ instance Show Cidr where
     show cidr = (show (ipv4address cidr)) ++ "/" ++ (show (maskbits cidr))
 
 
+-- Two CIDR ranges are equivalent if they have the same network bits
+-- and the masks are the same.
+equivalent :: Cidr -> Cidr -> Bool
+equivalent Cidr.None Cidr.None = True
+equivalent Cidr.None _ = False
+equivalent _ Cidr.None = False
+equivalent (Cidr addr1 mbits1) (Cidr addr2 mbits2) =
+    (mbits1 == mbits2) && ((apply_mask addr1 mbits1) == (apply_mask addr2 mbits2))
+
 -- Returns the mask portion of a CIDR address. That is, everything
 -- after the trailing slash.
 maskbits_from_cidr_string :: String -> Maskbits
@@ -109,13 +120,40 @@ redundant :: [Cidr] -> Cidr -> Bool
 redundant cidrlist cidr = any ((flip contains_proper) cidr) cidrlist
 
 
--- We want to get rid of all the Cidrs that are properly contained
--- in some other Cidr.
+-- First, we look at all possible pairs of cidrs, and combine the
+-- adjacent ones in to a new list. Then, we concatenate that list with
+-- the original one, and filter out all of the redundancies. If two
+-- adjacent Cidrs are combined into a larger one, they will be removed
+-- in the second step since the larger Cidr must contain the smaller
+-- two.
 combine_all :: [Cidr] -> [Cidr]
 combine_all cidrs =
+    combine_contained unique_cidrs
+    where
+      unique_cidrs = nubBy equivalent valid_cidr_combinations
+      valid_cidr_combinations = filter (/= Cidr.None) cidr_combinations
+      cidr_combinations =
+          cidrs ++ [ (combine_adjacent x y) | x <- cidrs, y <- cidrs ]
+
+
+-- Take a list of CIDR ranges and filter out all of the ones that are
+-- contained entirelt within some other range in the list.
+combine_contained :: [Cidr] -> [Cidr]
+combine_contained cidrs =
     filter (not . (redundant cidrs)) cidrs
 
 
+-- If the two Cidrs are not adjacent, return Cidr.None. Otherwise,
+-- decrement the maskbits of cidr1 and return that; it will contain
+-- both cidr1 and cidr2.
+combine_adjacent :: Cidr -> Cidr -> Cidr
+combine_adjacent cidr1 cidr2
+  | not (adjacent cidr1 cidr2) = Cidr.None
+  | (maskbits cidr1 == Zero) = Cidr.None
+  | otherwise = cidr1 { maskbits = decrement (maskbits cidr1) }
+
+
+
 -- Determine whether or not two CIDR ranges are adjacent. If two
 -- ranges lie consecutively within the IP space, they can be
 -- combined. For example, 10.1.0.0/24 and 10.0.1.0/24 are adjacent,
-- 
2.44.2