author Milan Straka Wed, 4 Dec 2013 18:31:23 +0000 (19:31 +0100) committer Milan Straka Wed, 4 Dec 2013 19:11:03 +0000 (20:11 +0100)
 Data/IntMap/Base.hs patch | blob | history Data/IntSet/Base.hs patch | blob | history tests/intmap-properties.hs patch | blob | history tests/intset-properties.hs patch | blob | history tests/map-properties.hs patch | blob | history tests/set-properties.hs patch | blob | history

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