X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=src%2FCidr.hs;h=77f1ae41fe42569d5801c50158aef48f1a595ce7;hb=a767881c16a119a90ff80d9c14106348d8bc310d;hp=266b7c57f8a8e8318124a2518900de75a4d166ca;hpb=b22b30048819a3a53517e44370a97a2e37ba3f10;p=hath.git

diff --git a/src/Cidr.hs b/src/Cidr.hs
index 266b7c5..77f1ae4 100644
--- a/src/Cidr.hs
+++ b/src/Cidr.hs
@@ -1,9 +1,13 @@
 module Cidr
 ( Cidr(..),
   cidr_from_string,
+  cidr_tests,
   combine_all
 ) where
 
+import Data.List (nubBy)
+import Test.HUnit
+
 import IPv4Address
 import ListUtils
 import Maskable
@@ -13,9 +17,23 @@ import Octet
 
 data Cidr = None | Cidr { ipv4address :: IPv4Address,
                           maskbits :: Maskbits }
-            deriving (Eq, Show)
+            deriving (Eq)
+
+
+instance Show Cidr where
+    show Cidr.None = "None"
+    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
@@ -104,8 +122,70 @@ 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,
+-- and can be combined in to 10.1.0.0/23.
+adjacent :: Cidr -> Cidr -> Bool
+adjacent Cidr.None _ = False
+adjacent _ Cidr.None = False
+adjacent cidr1 cidr2
+  | mbits1 /= mbits2 = False
+  | mbits1 == Maskbits.Zero = False -- They're equal.
+  | otherwise = (mbits1 == (most_sig_bit_different addr1 addr2))
+  where
+    addr1 = ipv4address cidr1
+    addr2 = ipv4address cidr2
+    mbits1 = maskbits cidr1
+    mbits2 = maskbits cidr2
+
+
+
+
+
+-- HUnit Tests
+
+test_contains :: Test
+test_contains =
+    TestCase $ assertEqual "10.1.1.0/23 contains 10.1.1.0/24" (cidr1 `contains` cidr2) True
+    where
+      cidr1 = cidr_from_string "10.1.1.0/23"
+      cidr2 = cidr_from_string "10.1.1.0/24"
+
+
+cidr_tests :: [Test]
+cidr_tests = [ test_contains ]