General package stuff, mostly
authorDavid Feuer <David.Feuer@gmail.com>
Fri, 2 Sep 2016 03:59:12 +0000 (23:59 -0400)
committerDavid Feuer <David.Feuer@gmail.com>
Fri, 2 Sep 2016 15:34:04 +0000 (11:34 -0400)
* Rename the internals again. I think they're getting close to
reasonable now. Get the cabal benchmarks running again. Deprecate
the "deprecated" `IntMap` stuff. Make a `Debug` module for the
`Data.Map` debugging functions.

* Rewrite `Data.Map.Internal.Debug.validSize` to use the
  `Monad Maybe` instance for clarity.

25 files changed:
.travis.yml
Data/IntMap.hs
Data/IntMap/Internal.hs
Data/IntMap/Strict.hs
Data/IntSet/Internal.hs
Data/Map/Internal.hs
Data/Map/Internal/Debug.hs [new file with mode: 0644]
Data/Map/Internal/DeprecatedShowTree.hs [new file with mode: 0644]
Data/Map/Lazy.hs
Data/Map/Strict/Internal.hs
Data/Sequence/Internal.hs
Data/Set/Internal.hs
Data/Utils/StrictPair.hs [deleted file]
Utils/Containers/Internal/BitQueue.hs [moved from Data/Utils/BitQueue.hs with 96% similarity]
Utils/Containers/Internal/BitUtil.hs [moved from Data/Utils/BitUtil.hs with 96% similarity]
Utils/Containers/Internal/PtrEquality.hs [moved from Data/Utils/PtrEquality.hs with 75% similarity]
Utils/Containers/Internal/StrictFold.hs [moved from Data/Utils/StrictFold.hs with 57% similarity]
Utils/Containers/Internal/StrictMaybe.hs [moved from Data/Utils/StrictMaybe.hs with 58% similarity]
Utils/Containers/Internal/StrictPair.hs [new file with mode: 0644]
benchmarks/IntMap.hs
benchmarks/Map.hs
containers.cabal
tests/bitqueue-properties.hs
tests/deprecated-properties.hs
tests/map-properties.hs

index c8cd29f..f7c0082 100644 (file)
@@ -28,10 +28,12 @@ before_install:
 install:
  - travis_retry cabal update
  - cabal install --only-dependencies
- # we need to install the test-suite deps manually as the cabal solver would
- # otherwise complaing about cyclic deps
+ # we need to install the test-suite and benchmark deps manually as the cabal
+ # solver would otherwise complain about cyclic deps
  - cabal install 'test-framework >= 0.3.3' 'test-framework-quickcheck2 >= 0.2.9' 'QuickCheck >= 2.4.0.1' 'ChasingBottoms' 'HUnit' 'test-framework-hunit'
 
+ # If we enable benchmarks, we'll need 'criterion >= 0.4.0 && < 1.2'
+
 # Here starts the actual work to be performed for the package under
 # test; any command which exits with a non-zero exit code causes the
 # build to fail.
@@ -39,6 +41,10 @@ script:
  # -v2 provides useful information for debugging
  - cabal configure -v2 --enable-tests
 
+ # We'd like to
+ # --enable-benchmarks
+ # but CI time goes through the roof. Maybe there's a way to limit it to just one GHC version?
+
  # this builds all libraries and executables
  # (including tests/benchmarks)
  - cabal build
index 7867e67..cceff63 100644 (file)
@@ -65,38 +65,33 @@ import Prelude ()  -- hide foldr
 import qualified Data.IntMap.Strict as Strict
 import Data.IntMap.Lazy
 
--- | /Deprecated./ As of version 0.5, replaced by
--- 'Data.IntMap.Strict.insertWith'.
---
--- /O(log n)/. Same as 'insertWith', but the result of the combining function
+-- | /O(log n)/. Same as 'insertWith', but the result of the combining function
 -- is evaluated to WHNF before inserted to the map.
 
+{-# DEPRECATED insertWith' "As of version 0.5, replaced by 'Data.IntMap.Strict.insertWith'." #-}
 insertWith' :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
 insertWith' = Strict.insertWith
 
--- | /Deprecated./ As of version 0.5, replaced by
--- 'Data.IntMap.Strict.insertWithKey'.
---
--- /O(log n)/. Same as 'insertWithKey', but the result of the combining
+-- | /O(log n)/. Same as 'insertWithKey', but the result of the combining
 -- function is evaluated to WHNF before inserted to the map.
 
+{-# DEPRECATED insertWithKey' "As of version 0.5, replaced by 'Data.IntMap.Strict.insertWithKey'." #-}
 insertWithKey' :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
 insertWithKey' = Strict.insertWithKey
 
--- | /Deprecated./ As of version 0.5, replaced by 'foldr'.
---
--- /O(n)/. Fold the values in the map using the given
+-- | /O(n)/. Fold the values in the map using the given
 -- right-associative binary operator. This function is an equivalent
 -- of 'foldr' and is present for compatibility only.
+{-# DEPRECATED fold "As of version 0.5, replaced by 'foldr'." #-}
 fold :: (a -> b -> b) -> b -> IntMap a -> b
 fold = foldr
 {-# INLINE fold #-}
 
--- | /Deprecated./ As of version 0.5, replaced by 'foldrWithKey'.
---
--- /O(n)/. Fold the keys and values in the map using the given
+-- | /O(n)/. Fold the keys and values in the map using the given
 -- right-associative binary operator. This function is an equivalent
 -- of 'foldrWithKey' and is present for compatibility only.
+
+{-# DEPRECATED foldWithKey "As of version 0.5, replaced by 'foldrWithKey'." #-}
 foldWithKey :: (Key -> a -> b -> b) -> b -> IntMap a -> b
 foldWithKey = foldrWithKey
 {-# INLINE foldWithKey #-}
index dfbd76b..dbecfa0 100644 (file)
@@ -256,9 +256,9 @@ import Prelude hiding (lookup, map, filter, foldr, foldl, null)
 
 import Data.IntSet.Internal (Key)
 import qualified Data.IntSet.Internal as IntSet
-import Data.Utils.BitUtil
-import Data.Utils.StrictFold
-import Data.Utils.StrictPair
+import Utils.Containers.Internal.BitUtil
+import Utils.Containers.Internal.StrictFold
+import Utils.Containers.Internal.StrictPair
 
 #if __GLASGOW_HASKELL__
 import Data.Data (Data(..), Constr, mkConstr, constrIndex, Fixity(Prefix),
index ec657d7..dfb083c 100644 (file)
@@ -265,9 +265,9 @@ import Data.IntMap.Internal hiding
     )
 
 import qualified Data.IntSet.Internal as IntSet
-import Data.Utils.BitUtil
-import Data.Utils.StrictFold
-import Data.Utils.StrictPair
+import Utils.Containers.Internal.BitUtil
+import Utils.Containers.Internal.StrictFold
+import Utils.Containers.Internal.StrictPair
 #if __GLASGOW_HASKELL__ >= 709
 import Data.Coerce
 #endif
index e16f78a..8b7f796 100644 (file)
@@ -194,9 +194,9 @@ import Data.Semigroup (Semigroup((<>), stimes), stimesIdempotentMonoid)
 import Data.Typeable
 import Prelude hiding (filter, foldr, foldl, null, map)
 
-import Data.Utils.BitUtil
-import Data.Utils.StrictFold
-import Data.Utils.StrictPair
+import Utils.Containers.Internal.BitUtil
+import Utils.Containers.Internal.StrictFold
+import Utils.Containers.Internal.StrictPair
 
 #if __GLASGOW_HASKELL__
 import Data.Data (Data(..), Constr, mkConstr, constrIndex, Fixity(Prefix), DataType, mkDataType)
index 88b12f4..a3bc550 100644 (file)
@@ -327,11 +327,6 @@ module Data.Map.Internal (
     , minViewWithKey
     , maxViewWithKey
 
-    -- * Debugging
-    , showTree
-    , showTreeWith
-    , valid
-
     -- Used by the strict version
     , AreWeStrict (..)
     , atKeyImpl
@@ -340,7 +335,6 @@ module Data.Map.Internal (
 #endif
     , bin
     , balance
-    , balanced
     , balanceL
     , balanceR
     , delta
@@ -380,13 +374,13 @@ import Prelude hiding (lookup, map, filter, foldr, foldl, null, splitAt, take, d
 
 import qualified Data.Set.Internal as Set
 import Data.Set.Internal (Set)
-import Data.Utils.PtrEquality (ptrEq)
-import Data.Utils.StrictFold
-import Data.Utils.StrictPair
-import Data.Utils.StrictMaybe
-import Data.Utils.BitQueue
+import Utils.Containers.Internal.PtrEquality (ptrEq)
+import Utils.Containers.Internal.StrictFold
+import Utils.Containers.Internal.StrictPair
+import Utils.Containers.Internal.StrictMaybe
+import Utils.Containers.Internal.BitQueue
 #if DEFINE_ALTERF_FALLBACK
-import Data.Utils.BitUtil (wordSize)
+import Utils.Containers.Internal.BitUtil (wordSize)
 #endif
 
 #if __GLASGOW_HASKELL__
@@ -3961,102 +3955,6 @@ instance (Show k, Show a) => Show (Map k a) where
   showsPrec d m  = showParen (d > 10) $
     showString "fromList " . shows (toList m)
 
--- | /O(n)/. Show the tree that implements the map. The tree is shown
--- in a compressed, hanging format. See 'showTreeWith'.
-{-# DEPRECATED showTree "This function is being removed from the public API." #-}
-showTree :: (Show k,Show a) => Map k a -> String
-showTree m
-  = showTreeWith showElem True False m
-  where
-    showElem k x  = show k ++ ":=" ++ show x
-
-
-{- | /O(n)/. The expression (@'showTreeWith' showelem hang wide map@) shows
- the tree that implements the map. Elements are shown using the @showElem@ function. If @hang@ is
- 'True', a /hanging/ tree is shown otherwise a rotated tree is shown. If
- @wide@ is 'True', an extra wide version is shown.
-
->  Map> let t = fromDistinctAscList [(x,()) | x <- [1..5]]
->  Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True False t
->  (4,())
->  +--(2,())
->  |  +--(1,())
->  |  +--(3,())
->  +--(5,())
->
->  Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True True t
->  (4,())
->  |
->  +--(2,())
->  |  |
->  |  +--(1,())
->  |  |
->  |  +--(3,())
->  |
->  +--(5,())
->
->  Map> putStrLn $ showTreeWith (\k x -> show (k,x)) False True t
->  +--(5,())
->  |
->  (4,())
->  |
->  |  +--(3,())
->  |  |
->  +--(2,())
->     |
->     +--(1,())
-
--}
-{-# DEPRECATED showTreeWith "This function is being removed from the public API." #-}
-showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> String
-showTreeWith showelem hang wide t
-  | hang      = (showsTreeHang showelem wide [] t) ""
-  | otherwise = (showsTree showelem wide [] [] t) ""
-
-showsTree :: (k -> a -> String) -> Bool -> [String] -> [String] -> Map k a -> ShowS
-showsTree showelem wide lbars rbars t
-  = case t of
-      Tip -> showsBars lbars . showString "|\n"
-      Bin _ kx x Tip Tip
-          -> showsBars lbars . showString (showelem kx x) . showString "\n"
-      Bin _ kx x l r
-          -> showsTree showelem wide (withBar rbars) (withEmpty rbars) r .
-             showWide wide rbars .
-             showsBars lbars . showString (showelem kx x) . showString "\n" .
-             showWide wide lbars .
-             showsTree showelem wide (withEmpty lbars) (withBar lbars) l
-
-showsTreeHang :: (k -> a -> String) -> Bool -> [String] -> Map k a -> ShowS
-showsTreeHang showelem wide bars t
-  = case t of
-      Tip -> showsBars bars . showString "|\n"
-      Bin _ kx x Tip Tip
-          -> showsBars bars . showString (showelem kx x) . showString "\n"
-      Bin _ kx x l r
-          -> showsBars bars . showString (showelem kx x) . showString "\n" .
-             showWide wide bars .
-             showsTreeHang showelem wide (withBar bars) l .
-             showWide wide bars .
-             showsTreeHang showelem wide (withEmpty bars) r
-
-showWide :: Bool -> [String] -> String -> String
-showWide wide bars
-  | wide      = showString (concat (reverse bars)) . showString "|\n"
-  | otherwise = id
-
-showsBars :: [String] -> ShowS
-showsBars bars
-  = case bars of
-      [] -> id
-      _  -> showString (concat (reverse (tail bars))) . showString node
-
-node :: String
-node           = "+--"
-
-withBar, withEmpty :: [String] -> [String]
-withBar bars   = "|  ":bars
-withEmpty bars = "   ":bars
-
 {--------------------------------------------------------------------
   Typeable
 --------------------------------------------------------------------}
@@ -4064,46 +3962,6 @@ withEmpty bars = "   ":bars
 INSTANCE_TYPEABLE2(Map)
 
 {--------------------------------------------------------------------
-  Assertions
---------------------------------------------------------------------}
--- | /O(n)/. Test if the internal map structure is valid.
---
--- > valid (fromAscList [(3,"b"), (5,"a")]) == True
--- > valid (fromAscList [(5,"a"), (3,"b")]) == False
-
-valid :: Ord k => Map k a -> Bool
-valid t
-  = balanced t && ordered t && validsize t
-
-ordered :: Ord a => Map a b -> Bool
-ordered t
-  = bounded (const True) (const True) t
-  where
-    bounded lo hi t'
-      = case t' of
-          Tip              -> True
-          Bin _ kx _ l r  -> (lo kx) && (hi kx) && bounded lo (<kx) l && bounded (>kx) hi r
-
--- | Exported only for "Debug.QuickCheck"
-balanced :: Map k a -> Bool
-balanced t
-  = case t of
-      Tip            -> True
-      Bin _ _ _ l r  -> (size l + size r <= 1 || (size l <= delta*size r && size r <= delta*size l)) &&
-                        balanced l && balanced r
-
-validsize :: Map a b -> Bool
-validsize t
-  = (realsize t == Just (size t))
-  where
-    realsize t'
-      = case t' of
-          Tip            -> Just 0
-          Bin sz _ _ l r -> case (realsize l,realsize r) of
-                            (Just n,Just m)  | n+m+1 == sz  -> Just sz
-                            _                               -> Nothing
-
-{--------------------------------------------------------------------
   Utilities
 --------------------------------------------------------------------}
 
diff --git a/Data/Map/Internal/Debug.hs b/Data/Map/Internal/Debug.hs
new file mode 100644 (file)
index 0000000..e17aa8a
--- /dev/null
@@ -0,0 +1,144 @@
+{-# LANGUAGE CPP #-}
+#include "containers.h"
+
+module Data.Map.Internal.Debug where
+
+import Data.Map.Internal (Map (..), size, delta)
+import Control.Monad (guard)
+
+-- | /O(n)/. Show the tree that implements the map. The tree is shown
+-- in a compressed, hanging format. See 'showTreeWith'.
+showTree :: (Show k,Show a) => Map k a -> String
+showTree m
+  = showTreeWith showElem True False m
+  where
+    showElem k x  = show k ++ ":=" ++ show x
+
+
+{- | /O(n)/. The expression (@'showTreeWith' showelem hang wide map@) shows
+ the tree that implements the map. Elements are shown using the @showElem@ function. If @hang@ is
+ 'True', a /hanging/ tree is shown otherwise a rotated tree is shown. If
+ @wide@ is 'True', an extra wide version is shown.
+
+>  Map> let t = fromDistinctAscList [(x,()) | x <- [1..5]]
+>  Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True False t
+>  (4,())
+>  +--(2,())
+>  |  +--(1,())
+>  |  +--(3,())
+>  +--(5,())
+>
+>  Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True True t
+>  (4,())
+>  |
+>  +--(2,())
+>  |  |
+>  |  +--(1,())
+>  |  |
+>  |  +--(3,())
+>  |
+>  +--(5,())
+>
+>  Map> putStrLn $ showTreeWith (\k x -> show (k,x)) False True t
+>  +--(5,())
+>  |
+>  (4,())
+>  |
+>  |  +--(3,())
+>  |  |
+>  +--(2,())
+>     |
+>     +--(1,())
+
+-}
+showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> String
+showTreeWith showelem hang wide t
+  | hang      = (showsTreeHang showelem wide [] t) ""
+  | otherwise = (showsTree showelem wide [] [] t) ""
+
+showsTree :: (k -> a -> String) -> Bool -> [String] -> [String] -> Map k a -> ShowS
+showsTree showelem wide lbars rbars t
+  = case t of
+      Tip -> showsBars lbars . showString "|\n"
+      Bin _ kx x Tip Tip
+          -> showsBars lbars . showString (showelem kx x) . showString "\n"
+      Bin _ kx x l r
+          -> showsTree showelem wide (withBar rbars) (withEmpty rbars) r .
+             showWide wide rbars .
+             showsBars lbars . showString (showelem kx x) . showString "\n" .
+             showWide wide lbars .
+             showsTree showelem wide (withEmpty lbars) (withBar lbars) l
+
+showsTreeHang :: (k -> a -> String) -> Bool -> [String] -> Map k a -> ShowS
+showsTreeHang showelem wide bars t
+  = case t of
+      Tip -> showsBars bars . showString "|\n"
+      Bin _ kx x Tip Tip
+          -> showsBars bars . showString (showelem kx x) . showString "\n"
+      Bin _ kx x l r
+          -> showsBars bars . showString (showelem kx x) . showString "\n" .
+             showWide wide bars .
+             showsTreeHang showelem wide (withBar bars) l .
+             showWide wide bars .
+             showsTreeHang showelem wide (withEmpty bars) r
+
+showWide :: Bool -> [String] -> String -> String
+showWide wide bars
+  | wide      = showString (concat (reverse bars)) . showString "|\n"
+  | otherwise = id
+
+showsBars :: [String] -> ShowS
+showsBars bars
+  = case bars of
+      [] -> id
+      _  -> showString (concat (reverse (tail bars))) . showString node
+
+node :: String
+node           = "+--"
+
+withBar, withEmpty :: [String] -> [String]
+withBar bars   = "|  ":bars
+withEmpty bars = "   ":bars
+
+{--------------------------------------------------------------------
+  Assertions
+--------------------------------------------------------------------}
+-- | /O(n)/. Test if the internal map structure is valid.
+--
+-- > valid (fromAscList [(3,"b"), (5,"a")]) == True
+-- > valid (fromAscList [(5,"a"), (3,"b")]) == False
+
+valid :: Ord k => Map k a -> Bool
+valid t
+  = balanced t && ordered t && validsize t
+
+-- | Test if the keys are ordered correctly.
+ordered :: Ord a => Map a b -> Bool
+ordered t
+  = bounded (const True) (const True) t
+  where
+    bounded lo hi t'
+      = case t' of
+          Tip              -> True
+          Bin _ kx _ l r  -> (lo kx) && (hi kx) && bounded lo (<kx) l && bounded (>kx) hi r
+
+-- | Test if a map obeys the balance invariants.
+balanced :: Map k a -> Bool
+balanced t
+  = case t of
+      Tip            -> True
+      Bin _ _ _ l r  -> (size l + size r <= 1 || (size l <= delta*size r && size r <= delta*size l)) &&
+                        balanced l && balanced r
+
+-- | Test if each node of a map reports its size correctly.
+validsize :: Map a b -> Bool
+validsize t = case slowSize t of
+      Nothing -> False
+      Just _ -> True
+  where
+    slowSize Tip = Just 0
+    slowSize (Bin sz _ _ l r) = do
+            ls <- slowSize l
+            rs <- slowSize r
+            guard (sz == ls + rs + 1)
+            return sz
diff --git a/Data/Map/Internal/DeprecatedShowTree.hs b/Data/Map/Internal/DeprecatedShowTree.hs
new file mode 100644 (file)
index 0000000..9f7f503
--- /dev/null
@@ -0,0 +1,56 @@
+{-# LANGUAGE CPP #-}
+
+#include "containers.h"
+
+-- | This module simply holds deprecated copies of functions from
+-- Data.Map.Internal.Debug.
+module Data.Map.Internal.DeprecatedShowTree where
+
+import qualified Data.Map.Internal.Debug as Debug
+import Data.Map.Internal (Map)
+
+-- | /O(n)/. Show the tree that implements the map. The tree is shown
+-- in a compressed, hanging format. See 'showTreeWith'.
+{-# DEPRECATED showTree "'showTree' is now in \"Data.Map.Internal.Debug\"" #-}
+showTree :: (Show k,Show a) => Map k a -> String
+showTree = Debug.showTree
+
+{- | /O(n)/. The expression (@'showTreeWith' showelem hang wide map@) shows
+ the tree that implements the map. Elements are shown using the @showElem@ function. If @hang@ is
+ 'True', a /hanging/ tree is shown otherwise a rotated tree is shown. If
+ @wide@ is 'True', an extra wide version is shown.
+
+>  Map> let t = fromDistinctAscList [(x,()) | x <- [1..5]]
+>  Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True False t
+>  (4,())
+>  +--(2,())
+>  |  +--(1,())
+>  |  +--(3,())
+>  +--(5,())
+>
+>  Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True True t
+>  (4,())
+>  |
+>  +--(2,())
+>  |  |
+>  |  +--(1,())
+>  |  |
+>  |  +--(3,())
+>  |
+>  +--(5,())
+>
+>  Map> putStrLn $ showTreeWith (\k x -> show (k,x)) False True t
+>  +--(5,())
+>  |
+>  (4,())
+>  |
+>  |  +--(3,())
+>  |  |
+>  +--(2,())
+>     |
+>     +--(1,())
+
+-}
+{-# DEPRECATED showTreeWith "'showTreeWith' is now in \"Data.Map.Internal.Debug\"" #-}
+showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> String
+showTreeWith = Debug.showTreeWith
index 917d187..966b442 100644 (file)
@@ -69,11 +69,11 @@ module Data.Map.Lazy (
     , (!), (\\)
 
     -- * Query
-    , M.null
+    , null
     , size
     , member
     , notMember
-    , M.lookup
+    , lookup
     , findWithDefault
     , lookupLT
     , lookupGT
@@ -128,7 +128,7 @@ module Data.Map.Lazy (
 
     -- * Traversal
     -- ** Map
-    , M.map
+    , map
     , mapWithKey
     , traverseWithKey
     , traverseMaybeWithKey
@@ -140,8 +140,8 @@ module Data.Map.Lazy (
     , mapKeysMonotonic
 
     -- * Folds
-    , M.foldr
-    , M.foldl
+    , foldr
+    , foldl
     , foldrWithKey
     , foldlWithKey
     , foldMapWithKey
@@ -178,7 +178,7 @@ module Data.Map.Lazy (
     , fromDistinctDescList
 
     -- * Filter
-    , M.filter
+    , filter
     , filterWithKey
     , restrictKeys
     , withoutKeys
@@ -233,7 +233,9 @@ module Data.Map.Lazy (
     , valid
     ) where
 
-import Data.Map.Internal as M
+import Data.Map.Internal
+import Data.Map.Internal.DeprecatedShowTree (showTree, showTreeWith)
+import Data.Map.Internal.Debug (valid)
 import Prelude ()
 
 -- $strictness
index 4581a91..5ed14b3 100644 (file)
@@ -292,11 +292,6 @@ module Data.Map.Strict.Internal
     , showTree
     , showTreeWith
     , valid
-
-    , bin
-    , balanced
-    , link
-    , link2
     ) where
 
 import Prelude hiding (lookup,map,filter,foldr,foldl,null,take,drop,splitAt)
@@ -381,8 +376,6 @@ import Data.Map.Internal
   , partition
   , partitionWithKey
   , restrictKeys
-  , showTree
-  , showTreeWith
   , size
   , spanAntitone
   , split
@@ -396,18 +389,18 @@ import Data.Map.Internal
   , toDescList
   , union
   , unions
-  , valid
   , withoutKeys )
 
-import Data.Map.Internal (bin, balanced)
+import Data.Map.Internal.DeprecatedShowTree (showTree, showTreeWith)
+import Data.Map.Internal.Debug (valid)
 
 import Control.Applicative (Const (..))
 #if !MIN_VERSION_base(4,8,0)
 import Control.Applicative (Applicative (..), (<$>))
 #endif
 import qualified Data.Set.Internal as Set
-import Data.Utils.StrictFold
-import Data.Utils.StrictPair
+import Utils.Containers.Internal.StrictFold
+import Utils.Containers.Internal.StrictPair
 
 import Data.Bits (shiftL, shiftR)
 #if __GLASGOW_HASKELL__ >= 709
index 31b5678..40a7fc9 100644 (file)
@@ -258,7 +258,7 @@ import Data.Functor.Identity (Identity(..))
 import Data.Word (Word)
 #endif
 
-import Data.Utils.StrictPair (StrictPair (..), toPair)
+import Utils.Containers.Internal.StrictPair (StrictPair (..), toPair)
 
 default ()
 
index bda84be..2fefcb6 100644 (file)
@@ -231,9 +231,9 @@ import qualified Data.Foldable as Foldable
 import Data.Typeable
 import Control.DeepSeq (NFData(rnf))
 
-import Data.Utils.StrictFold
-import Data.Utils.StrictPair
-import Data.Utils.PtrEquality
+import Utils.Containers.Internal.StrictFold
+import Utils.Containers.Internal.StrictPair
+import Utils.Containers.Internal.PtrEquality
 
 #if __GLASGOW_HASKELL__
 import GHC.Exts ( build )
diff --git a/Data/Utils/StrictPair.hs b/Data/Utils/StrictPair.hs
deleted file mode 100644 (file)
index 13424f8..0000000
+++ /dev/null
@@ -1,32 +0,0 @@
-{-# LANGUAGE CPP #-}
-#if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703
-{-# LANGUAGE Safe #-}
-#endif
-
-#include "containers.h"
-
-{-# OPTIONS_HADDOCK hide #-}
-
--- | A strict pair
---
--- = WARNING
---
--- This module is considered __internal__.
---
--- The Package Versioning Policy __does not apply__.
---
--- This contents of this module may change __in any way whatsoever__
--- and __without any warning__ between minor versions of this package.
---
--- Authors importing this module are expected to track development
--- closely.
-
-module Data.Utils.StrictPair (StrictPair(..), toPair) where
-
--- | Same as regular Haskell pairs, but (x :*: _|_) = (_|_ :*: y) =
--- _|_
-data StrictPair a b = !a :*: !b
-
-toPair :: StrictPair a b -> (a, b)
-toPair (x :*: y) = (x, y)
-{-# INLINE toPair #-}
similarity index 96%
rename from Data/Utils/BitQueue.hs
rename to Utils/Containers/Internal/BitQueue.hs
index ad7d84f..455b4b9 100644 (file)
@@ -3,11 +3,9 @@
 
 #include "containers.h"
 
-{-# OPTIONS_HADDOCK hide #-}
-
 -----------------------------------------------------------------------------
 -- |
--- Module      :  Data.Utils.BitQueue
+-- Module      :  Utils.Containers.Internal.BitQueue
 -- Copyright   :  (c) David Feuer 2016
 -- License     :  BSD-style
 -- Maintainer  :  libraries@haskell.org
@@ -37,7 +35,7 @@
 -- exceeded, further operations will silently produce nonsense.
 -----------------------------------------------------------------------------
 
-module Data.Utils.BitQueue
+module Utils.Containers.Internal.BitQueue
     ( BitQueue
     , BitQueueB
     , emptyQB
@@ -50,7 +48,7 @@ module Data.Utils.BitQueue
 #if !MIN_VERSION_base(4,8,0)
 import Data.Word (Word)
 #endif
-import Data.Utils.BitUtil (shiftLL, shiftRL, wordSize)
+import Utils.Containers.Internal.BitUtil (shiftLL, shiftRL, wordSize)
 import Data.Bits ((.|.), (.&.), testBit)
 #if MIN_VERSION_base(4,8,0)
 import Data.Bits (countTrailingZeros)
similarity index 96%
rename from Data/Utils/BitUtil.hs
rename to Utils/Containers/Internal/BitUtil.hs
index 106e387..8a127f6 100644 (file)
@@ -8,10 +8,9 @@
 
 #include "containers.h"
 
-{-# OPTIONS_HADDOCK hide #-}
 -----------------------------------------------------------------------------
 -- |
--- Module      :  Data.Utils.BitUtil
+-- Module      :  Utils.Containers.Internal.BitUtil
 -- Copyright   :  (c) Clark Gaebel 2012
 --                (c) Johan Tibel 2012
 -- License     :  BSD-style
@@ -32,7 +31,7 @@
 -- Authors importing this module are expected to track development
 -- closely.
 
-module Data.Utils.BitUtil
+module Utils.Containers.Internal.BitUtil
     ( highestBitMask
     , shiftLL
     , shiftRL
similarity index 75%
rename from Data/Utils/PtrEquality.hs
rename to Utils/Containers/Internal/PtrEquality.hs
index 48ea4b6..d6ac879 100644 (file)
@@ -6,20 +6,7 @@
 {-# OPTIONS_HADDOCK hide #-}
 
 -- | Really unsafe pointer equality
---
--- = WARNING
---
--- This module is considered __internal__.
---
--- The Package Versioning Policy __does not apply__.
---
--- This contents of this module may change __in any way whatsoever__
--- and __without any warning__ between minor versions of this package.
---
--- Authors importing this module are expected to track development
--- closely.
-
-module Data.Utils.PtrEquality (ptrEq, hetPtrEq) where
+module Utils.Containers.Internal.PtrEquality (ptrEq, hetPtrEq) where
 
 #ifdef __GLASGOW_HASKELL__
 import GHC.Exts ( reallyUnsafePtrEquality# )
similarity index 57%
rename from Data/Utils/StrictFold.hs
rename to Utils/Containers/Internal/StrictFold.hs
index 799c0f5..cba4ffd 100644 (file)
@@ -6,19 +6,7 @@
 #include "containers.h"
 {-# OPTIONS_HADDOCK hide #-}
 
--- = WARNING
---
--- This module is considered __internal__.
---
--- The Package Versioning Policy __does not apply__.
---
--- This contents of this module may change __in any way whatsoever__
--- and __without any warning__ between minor versions of this package.
---
--- Authors importing this module are expected to track development
--- closely.
-
-module Data.Utils.StrictFold (foldlStrict) where
+module Utils.Containers.Internal.StrictFold (foldlStrict) where
 
 -- | Same as regular 'Data.List.foldl'', but marked INLINE so that it is always
 -- inlined. This allows further optimization of the call to f, which can be
similarity index 58%
rename from Data/Utils/StrictMaybe.hs
rename to Utils/Containers/Internal/StrictMaybe.hs
index 99933d1..ed0e3c9 100644 (file)
@@ -4,20 +4,8 @@
 
 {-# OPTIONS_HADDOCK hide #-}
 -- | Strict 'Maybe'
---
--- = WARNING
---
--- This module is considered __internal__.
---
--- The Package Versioning Policy __does not apply__.
---
--- This contents of this module may change __in any way whatsoever__
--- and __without any warning__ between minor versions of this package.
---
--- Authors importing this module are expected to track development
--- closely.
-
-module Data.Utils.StrictMaybe (MaybeS (..), maybeS, toMaybe, toMaybeS) where
+
+module Utils.Containers.Internal.StrictMaybe (MaybeS (..), maybeS, toMaybe, toMaybeS) where
 
 #if !MIN_VERSION_base(4,8,0)
 import Data.Foldable (Foldable (..))
diff --git a/Utils/Containers/Internal/StrictPair.hs b/Utils/Containers/Internal/StrictPair.hs
new file mode 100644 (file)
index 0000000..2ffd740
--- /dev/null
@@ -0,0 +1,22 @@
+{-# LANGUAGE CPP #-}
+#if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703
+{-# LANGUAGE Safe #-}
+#endif
+
+#include "containers.h"
+
+-- | A strict pair
+
+module Utils.Containers.Internal.StrictPair (StrictPair(..), toPair) where
+
+-- | The same as a regular Haskell pair, but
+--
+-- @
+-- (x :*: _|_) = (_|_ :*: y) = _|_
+-- @
+data StrictPair a b = !a :*: !b
+
+-- | Convert a strict pair to a standard pair.
+toPair :: StrictPair a b -> (a, b)
+toPair (x :*: y) = (x, y)
+{-# INLINE toPair #-}
index 56758a3..8fabda4 100644 (file)
@@ -6,6 +6,7 @@ import Control.Exception (evaluate)
 import Criterion.Main (bench, defaultMain, whnf)
 import Data.List (foldl')
 import qualified Data.IntMap as M
+import qualified Data.IntMap.Strict as MS
 import Data.Maybe (fromMaybe)
 import Prelude hiding (lookup)
 
@@ -64,10 +65,10 @@ insWithKey :: [(Int, Int)] -> M.IntMap Int -> M.IntMap Int
 insWithKey xs m = foldl' (\m (k, v) -> M.insertWithKey add3 k v m) m xs
 
 insWith' :: [(Int, Int)] -> M.IntMap Int -> M.IntMap Int
-insWith' xs m = foldl' (\m (k, v) -> M.insertWith' (+) k v m) m xs
+insWith' xs m = foldl' (\m (k, v) -> MS.insertWith (+) k v m) m xs
 
 insWithKey' :: [(Int, Int)] -> M.IntMap Int -> M.IntMap Int
-insWithKey' xs m = foldl' (\m (k, v) -> M.insertWithKey' add3 k v m) m xs
+insWithKey' xs m = foldl' (\m (k, v) -> MS.insertWithKey add3 k v m) m xs
 
 data PairS a b = PS !a !b
 
index 1376e62..60de4b4 100644 (file)
@@ -9,6 +9,7 @@ import Criterion.Main (bench, defaultMain, whnf, nf)
 import Data.Functor.Identity (Identity(..))
 import Data.List (foldl')
 import qualified Data.Map as M
+import qualified Data.Map.Strict as MS
 import Data.Map (alterF)
 import Data.Maybe (fromMaybe)
 import Data.Functor ((<$))
@@ -147,10 +148,10 @@ insWithKey :: [(Int, Int)] -> M.Map Int Int -> M.Map Int Int
 insWithKey xs m = foldl' (\m (k, v) -> M.insertWithKey add3 k v m) m xs
 
 insWith' :: [(Int, Int)] -> M.Map Int Int -> M.Map Int Int
-insWith' xs m = foldl' (\m (k, v) -> M.insertWith' (+) k v m) m xs
+insWith' xs m = foldl' (\m (k, v) -> MS.insertWith (+) k v m) m xs
 
 insWithKey' :: [(Int, Int)] -> M.Map Int Int -> M.Map Int Int
-insWithKey' xs m = foldl' (\m (k, v) -> M.insertWithKey' add3 k v m) m xs
+insWithKey' xs m = foldl' (\m (k, v) -> MS.insertWithKey add3 k v m) m xs
 
 data PairS a b = PS !a !b
 
@@ -163,7 +164,7 @@ insLookupWithKey xs m = let !(PS a b) = foldl' f (PS 0 m) xs in (a, b)
 insLookupWithKey' :: [(Int, Int)] -> M.Map Int Int -> (Int, M.Map Int Int)
 insLookupWithKey' xs m = let !(PS a b) = foldl' f (PS 0 m) xs in (a, b)
   where
-    f (PS n m) (k, v) = let !(n', m') = M.insertLookupWithKey' add3 k v m
+    f (PS n m) (k, v) = let !(n', m') = MS.insertLookupWithKey add3 k v m
                         in PS (fromMaybe 0 n' + n) m'
 
 del :: [Int] -> M.Map Int Int -> M.Map Int Int
index dbd554d..b8ab295 100644 (file)
@@ -54,20 +54,22 @@ Library
         Data.Map.Strict
         Data.Map.Strict.Merge
         Data.Map.Internal
+        Data.Map.Internal.Debug
         Data.Set.Internal
         Data.Set
         Data.Graph
         Data.Sequence
         Data.Sequence.Internal
         Data.Tree
-        Data.Utils.BitUtil
-        Data.Utils.BitQueue
+        Utils.Containers.Internal.BitUtil
+        Utils.Containers.Internal.BitQueue
+        Utils.Containers.Internal.StrictPair
 
     other-modules:
-        Data.Utils.StrictFold
-        Data.Utils.StrictPair
-        Data.Utils.StrictMaybe
-        Data.Utils.PtrEquality
+        Utils.Containers.Internal.StrictFold
+        Utils.Containers.Internal.StrictMaybe
+        Utils.Containers.Internal.PtrEquality
+        Data.Map.Internal.DeprecatedShowTree
 
     include-dirs: include
 
@@ -106,7 +108,8 @@ benchmark map-benchmarks
     base >= 4.2 && < 5,
     containers,
     criterion >= 0.4.0 && < 1.2,
-    deepseq >= 1.1.0.0 && < 1.5
+    deepseq >= 1.1.0.0 && < 1.5,
+    transformers
 
 benchmark sequence-benchmarks
   type: exitcode-stdio-1.0
index 06ab54a..7ee2693 100644 (file)
@@ -8,8 +8,8 @@ import qualified Data.List as List
 import Test.Framework
 import Test.Framework.Providers.QuickCheck2
 import Test.QuickCheck
-import Data.Utils.BitUtil (wordSize)
-import Data.Utils.BitQueue
+import Utils.Containers.Internal.BitUtil (wordSize)
+import Utils.Containers.Internal.BitQueue
     ( BitQueue
     , emptyQB
     , snocQB
index ec49c32..5478520 100644 (file)
@@ -1,4 +1,5 @@
 {-# LANGUAGE CPP #-}
+{-# OPTIONS_GHC -fno-warn-warnings-deprecations #-}
 
 -- This module tests the deprecated properties of Data.Map and Data.IntMap,
 -- because these cannot be tested in either map-properties or
index be56f00..5647292 100644 (file)
@@ -1,13 +1,14 @@
 {-# LANGUAGE CPP #-}
 
 #ifdef STRICT
-import Data.Map.Strict as Data.Map
+import Data.Map.Strict as Data.Map hiding (showTree, showTreeWith)
 import Data.Map.Strict.Merge
 #else
-import Data.Map.Lazy as Data.Map
+import Data.Map.Lazy as Data.Map hiding (showTree, showTreeWith)
 import Data.Map.Lazy.Merge
 #endif
-import Data.Map.Internal (Map (..), balanced, link2, link, bin)
+import Data.Map.Internal (Map (..), link2, link, bin)
+import Data.Map.Internal.Debug (showTree, showTreeWith, balanced)
 
 import Control.Applicative (Const(Const, getConst), pure, (<$>), (<*>))
 import Data.Functor.Identity (Identity(runIdentity))