Add test properties for splitRoot.
authorRyan Newton <rrnewton@gmail.com>
Wed, 4 Dec 2013 00:57:16 +0000 (19:57 -0500)
committerRyan Newton <rrnewton@gmail.com>
Wed, 4 Dec 2013 00:57:16 +0000 (19:57 -0500)
Remove the ordering guarantee for IntSet and IntMap.
(Negative numbers screw it up.)

Data/IntMap/Base.hs
Data/IntSet/Base.hs
tests/intmap-properties.hs
tests/intset-properties.hs
tests/map-properties.hs
tests/set-properties.hs

index 5f238ac..08448dd 100644 (file)
@@ -2081,10 +2081,9 @@ foldlStrict f = go
 -- | /O(1)/.  Decompose a map into pieces based on the structure of the underlying
 -- tree.  This function is useful for consuming a map in parallel.
 --     
--- No guarantee is made as to the sizes of the pieces; an internal, but
--- deterministic process determines this.  However, it is guaranteed that the pieces
--- returned will be in ascending order (all elements in the first submap less than all
--- elements in the second, and so on).
+-- No guarantee is made as to the sizes of the pieces; an internal, but deterministic
+-- process determines this.  Further, there are no guarantees about the ordering
+-- relationships of the output subsets.
 --
 -- Examples:
 --     
index 0d88363..d58583a 100644 (file)
@@ -1488,10 +1488,9 @@ foldlStrict f = go
 -- | /O(1)/.  Decompose a set into pieces based on the structure of the underlying
 -- tree.  This function is useful for consuming a set in parallel.
 --     
--- No guarantee is made as to the sizes of the pieces; an internal, but
--- deterministic process determines this.  However, it is guaranteed that the pieces
--- returned will be in ascending order (all elements in the first subset less than all
--- elements in the second, and so on).
+-- No guarantee is made as to the sizes of the pieces; an internal, but deterministic
+-- process determines this.  Further, there are no guarantees about the ordering
+-- relationships of the output subsets.
 --
 -- Examples:
 --     
index 6bf7ac5..f598021 100644 (file)
@@ -160,6 +160,7 @@ main = defaultMain
              , testProperty "fmap"                 prop_fmap
              , testProperty "mapkeys"              prop_mapkeys
              , testProperty "split"                prop_splitModel
+             , testProperty "prop_splitRoot"       prop_splitRoot
              , testProperty "foldr"                prop_foldr
              , testProperty "foldr'"               prop_foldr'
              , testProperty "foldl"                prop_foldl
@@ -994,6 +995,9 @@ prop_splitModel n ys = length ys > 0 ==>
   in  toAscList l == sort [(k, v) | (k,v) <- xs, k < n] &&
       toAscList r == sort [(k, v) | (k,v) <- xs, k > n]
 
+prop_splitRoot :: IMap -> Bool
+prop_splitRoot s = (s == unions (splitRoot s))
+
 prop_foldr :: Int -> [(Int, Int)] -> Property
 prop_foldr n ys = length ys > 0 ==>
   let xs = List.nubBy ((==) `on` fst) ys
index e424ee9..abfb96d 100644 (file)
@@ -63,6 +63,7 @@ main = defaultMain [ testCase "lookupLT" test_lookupLT
                    , testProperty "prop_minView" prop_minView
                    , testProperty "prop_split" prop_split
                    , testProperty "prop_splitMember" prop_splitMember
+                   , testProperty "prop_splitRoot" prop_splitRoot
                    , testProperty "prop_partition" prop_partition
                    , testProperty "prop_filter" prop_filter
 #if MIN_VERSION_base(4,5,0)
@@ -308,6 +309,9 @@ prop_splitMember :: IntSet -> Int -> Bool
 prop_splitMember s i = case splitMember i s of
     (s1,t,s2) -> all (<i) (toList s1) && all (>i) (toList s2) && t == i `member` s && i `delete` s == union s1 s2
 
+prop_splitRoot :: IntSet -> Bool
+prop_splitRoot s = (s == unions (splitRoot s))
+
 prop_partition :: IntSet -> Int -> Bool
 prop_partition s i = case partition odd s of
     (s1,s2) -> all odd (toList s1) && all even (toList s2) && s == s1 `union` s2
index 151bcf2..3361e9f 100644 (file)
@@ -136,6 +136,7 @@ main = defaultMain
          , testProperty "deleteMin"            prop_deleteMin
          , testProperty "deleteMax"            prop_deleteMax
          , testProperty "split"                prop_split
+         , testProperty "splitRoot"            prop_splitRoot
 --         , testProperty "split then join"      prop_join
          , testProperty "split then merge"     prop_merge
          , testProperty "union"                prop_union
@@ -859,6 +860,16 @@ prop_split :: Int -> UMap -> Bool
 prop_split k t = let (r,l) = split k t
                  in (valid r, valid l) == (True, True)
 
+prop_splitRoot :: UMap -> Bool
+prop_splitRoot s = loop ls && (s == unions ls)
+ where
+  ls = splitRoot s 
+  loop [] = True
+  loop (s1:rst) = List.null
+                  [ (x,y) | x <- toList s1
+                          , y <- toList (unions rst)
+                          , x > y ]
+
 -- prop_join :: Int -> UMap -> Bool
 -- prop_join k t = let (l,r) = split k t
 --                 in valid (join k () l r)
index e32a141..880f9c0 100644 (file)
@@ -64,6 +64,7 @@ main = defaultMain [ testCase "lookupLT" test_lookupLT
                    , testProperty "prop_minView" prop_minView
                    , testProperty "prop_split" prop_split
                    , testProperty "prop_splitMember" prop_splitMember
+                   , testProperty "prop_splitRoot" prop_splitRoot
                    , testProperty "prop_partition" prop_partition
                    , testProperty "prop_filter" prop_filter
                    ]
@@ -359,6 +360,16 @@ prop_splitMember :: Set Int -> Int -> Bool
 prop_splitMember s i = case splitMember i s of
     (s1,t,s2) -> all (<i) (toList s1) && all (>i) (toList s2) && t == i `member` s && i `delete` s == union s1 s2
 
+prop_splitRoot :: Set Int -> Bool
+prop_splitRoot s = loop ls && (s == unions ls)
+ where
+  ls = splitRoot s 
+  loop [] = True
+  loop (s1:rst) = List.null
+                  [ (x,y) | x <- toList s1
+                          , y <- toList (unions rst)
+                          , x > y ]
+
 prop_partition :: Set Int -> Int -> Bool
 prop_partition s i = case partition odd s of
     (s1,s2) -> all odd (toList s1) && all even (toList s2) && s == s1 `union` s2