Reinstate the ordering guarantees for Int{Set.Map}.splitRoot.
authorMilan Straka <fox@ucw.cz>
Wed, 4 Dec 2013 18:31:23 +0000 (19:31 +0100)
committerMilan Straka <fox@ucw.cz>
Wed, 4 Dec 2013 19:11:03 +0000 (20:11 +0100)
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 ebdbc12..34a263a 100644 (file)
@@ -2080,10 +2080,11 @@ 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.  Further, there are no guarantees about the ordering
--- relationships of the output subsets.
+--
+-- 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).
 --
 -- Examples:
 --
@@ -2098,9 +2099,10 @@ foldlStrict f = go
 splitRoot :: IntMap a -> [IntMap a]
 splitRoot orig =
   case orig of
-    Nil           -> []
-    x@(Tip _ _)   -> [x]
-    Bin _ _ l r   -> [l, r]
+    Nil -> []
+    x@(Tip _ _) -> [x]
+    Bin _ m l r | m < 0 -> [r, l]
+                | otherwise -> [l, r]
 {-# INLINE splitRoot #-}
 
 
index dcff687..be41db5 100644 (file)
@@ -1487,10 +1487,11 @@ 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.  Further, there are no guarantees about the ordering
--- relationships of the output subsets.
+--
+-- 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).
 --
 -- Examples:
 --
@@ -1505,8 +1506,9 @@ foldlStrict f = go
 splitRoot :: IntSet -> [IntSet]
 splitRoot orig =
   case orig of
-    Nil           -> []
+    Nil -> []
     -- NOTE: we don't currently split below Tip, but we could.
-    x@(Tip _ _)   -> [x]
-    Bin _ _ l r   -> [l, r]
+    x@(Tip _ _) -> [x]
+    Bin _ m l r | m < 0 -> [r, l]
+                | otherwise -> [l, r]
 {-# INLINE splitRoot #-}
index f598021..b37f5bc 100644 (file)
@@ -160,7 +160,7 @@ main = defaultMain
              , testProperty "fmap"                 prop_fmap
              , testProperty "mapkeys"              prop_mapkeys
              , testProperty "split"                prop_splitModel
-             , testProperty "prop_splitRoot"       prop_splitRoot
+             , testProperty "splitRoot"            prop_splitRoot
              , testProperty "foldr"                prop_foldr
              , testProperty "foldr'"               prop_foldr'
              , testProperty "foldl"                prop_foldl
@@ -996,7 +996,14 @@ prop_splitModel n ys = length ys > 0 ==>
       toAscList r == sort [(k, v) | (k,v) <- xs, k > n]
 
 prop_splitRoot :: IMap -> Bool
-prop_splitRoot s = (s == unions (splitRoot s))
+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_foldr :: Int -> [(Int, Int)] -> Property
 prop_foldr n ys = length ys > 0 ==>
index abfb96d..1671967 100644 (file)
@@ -310,7 +310,14 @@ 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_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 :: IntSet -> Int -> Bool
 prop_partition s i = case partition odd s of
index 27f08dc..f0dd066 100644 (file)
@@ -863,7 +863,7 @@ prop_split k t = let (r,l) = split k t
 prop_splitRoot :: UMap -> Bool
 prop_splitRoot s = loop ls && (s == unions ls)
  where
-  ls = splitRoot s 
+  ls = splitRoot s
   loop [] = True
   loop (s1:rst) = List.null
                   [ (x,y) | x <- toList s1
index 3ff6f73..694437c 100644 (file)
@@ -363,7 +363,7 @@ prop_splitMember s i = case splitMember i s of
 prop_splitRoot :: Set Int -> Bool
 prop_splitRoot s = loop ls && (s == unions ls)
  where
-  ls = splitRoot s 
+  ls = splitRoot s
   loop [] = True
   loop (s1:rst) = List.null
                   [ (x,y) | x <- toList s1