heaps 0.3.3 → 0.3.4.1

raw patch · 6 files changed

+319/−60 lines, 6 filesdep ~directorydep ~doctestbuild-type:Customsetup-changednew-uploaderPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: directory, doctest

API changes (from Hackage documentation)

Files

• .travis.yml +85/−23
• CHANGELOG.markdown +11/−0
• Setup.lhs +180/−5
• heaps.cabal +11/−5
• src/Data/Heap.hs +13/−5
• tests/doctests.hs +19/−22

@@ -1,47 +1,107 @@-# NB: don't set `language: haskell` here+# This file has been generated -- see https://github.com/hvr/multi-ghc-travis+language: c+sudo: false -# See also https://github.com/hvr/multi-ghc-travis for more information-env:- # we have to use CABALVER=1.16 for GHC<7.6 as well, as there's- # no package for earlier cabal versions in the PPA- - GHCVER=7.4.2 CABALVER=1.16- - GHCVER=7.6.3 CABALVER=1.16- - GHCVER=7.8.4 CABALVER=1.18- - GHCVER=7.10.1 CABALVER=1.22- - GHCVER=head CABALVER=1.22+cache:+  directories:+    - $HOME/.cabsnap+    - $HOME/.cabal/packages +before_cache:+  - rm -fv $HOME/.cabal/packages/hackage.haskell.org/build-reports.log+  - rm -fv $HOME/.cabal/packages/hackage.haskell.org/00-index.tar+ matrix:+  include:+    - env: CABALVER=1.24 GHCVER=7.0.4+      compiler: ": #GHC 7.0.4"+      addons: {apt: {packages: [cabal-install-1.24,ghc-7.0.4,hlint], sources: [hvr-ghc]}}+    - env: CABALVER=1.24 GHCVER=7.2.2+      compiler: ": #GHC 7.2.2"+      addons: {apt: {packages: [cabal-install-1.24,ghc-7.2.2,hlint], sources: [hvr-ghc]}}+    - env: CABALVER=1.24 GHCVER=7.4.2+      compiler: ": #GHC 7.4.2"+      addons: {apt: {packages: [cabal-install-1.24,ghc-7.4.2,hlint], sources: [hvr-ghc]}}+    - env: CABALVER=1.24 GHCVER=7.6.3+      compiler: ": #GHC 7.6.3"+      addons: {apt: {packages: [cabal-install-1.24,ghc-7.6.3,hlint], sources: [hvr-ghc]}}+    - env: CABALVER=1.24 GHCVER=7.8.4+      compiler: ": #GHC 7.8.4"+      addons: {apt: {packages: [cabal-install-1.24,ghc-7.8.4,hlint], sources: [hvr-ghc]}}+    - env: CABALVER=1.24 GHCVER=7.10.3+      compiler: ": #GHC 7.10.3"+      addons: {apt: {packages: [cabal-install-1.24,ghc-7.10.3,hlint], sources: [hvr-ghc]}}+    - env: CABALVER=1.24 GHCVER=8.0.2+      compiler: ": #GHC 8.0.2"+      addons: {apt: {packages: [cabal-install-1.24,ghc-8.0.2,hlint], sources: [hvr-ghc]}}+    - env: CABALVER=1.24 GHCVER=8.2.1+      compiler: ": #GHC 8.2.1"+      addons: {apt: {packages: [cabal-install-1.24,ghc-8.2.1,hlint], sources: [hvr-ghc]}}+    - env: CABALVER=1.24 GHCVER=head+      compiler: ": #GHC head"+      addons: {apt: {packages: [cabal-install-1.24,ghc-head,hlint], sources: [hvr-ghc]}}+   allow_failures:-   - env: GHCVER=head CABALVER=1.22+    - env: CABALVER=1.24 GHCVER=7.0.4+    - env: CABALVER=1.24 GHCVER=7.2.2+    - env: CABALVER=1.24 GHCVER=head -# Note: the distinction between `before_install` and `install` is not-#       important. before_install:- - travis_retry sudo add-apt-repository -y ppa:hvr/ghc- - travis_retry sudo apt-get update- - travis_retry sudo apt-get install cabal-install-$CABALVER ghc-$GHCVER- - export PATH=/opt/ghc/$GHCVER/bin:/opt/cabal/$CABALVER/bin:$PATH- - cabal --version+ - unset CC+ - export PATH=$HOME/.cabal/bin:/opt/ghc/$GHCVER/bin:/opt/cabal/$CABALVER/bin:$PATH  install:- - travis_retry cabal update- - cabal install --only-dependencies- - travis_retry sudo apt-get -q -y install hlint || cabal install hlint+ - cabal --version+ - echo "$(ghc --version) [$(ghc --print-project-git-commit-id 2> /dev/null || echo '?')]"+ - if [ -f $HOME/.cabal/packages/hackage.haskell.org/00-index.tar.gz ];+   then+     zcat $HOME/.cabal/packages/hackage.haskell.org/00-index.tar.gz >+          $HOME/.cabal/packages/hackage.haskell.org/00-index.tar;+   fi+ - travis_retry cabal update -v+ - sed -i 's/^jobs:/-- jobs:/' ${HOME}/.cabal/config+ - cabal install --only-dependencies --enable-tests --enable-benchmarks --dry -v > installplan.txt+ - sed -i -e '1,/^Resolving /d' installplan.txt; cat installplan.txt +# check whether current requested install-plan matches cached package-db snapshot+ - if diff -u installplan.txt $HOME/.cabsnap/installplan.txt;+   then+     echo "cabal build-cache HIT";+     rm -rfv .ghc;+     cp -a $HOME/.cabsnap/ghc $HOME/.ghc;+     cp -a $HOME/.cabsnap/lib $HOME/.cabsnap/share $HOME/.cabsnap/bin $HOME/.cabal/;+   else+     echo "cabal build-cache MISS";+     rm -rf $HOME/.cabsnap;+     mkdir -p $HOME/.ghc $HOME/.cabal/lib $HOME/.cabal/share $HOME/.cabal/bin;+     cabal install -j --only-dependencies --enable-tests --enable-benchmarks;+   fi++# snapshot package-db on cache miss+ - if [ ! -d $HOME/.cabsnap ];+   then+      echo "snapshotting package-db to build-cache";+      mkdir $HOME/.cabsnap;+      cp -a $HOME/.ghc $HOME/.cabsnap/ghc;+      cp -a $HOME/.cabal/lib $HOME/.cabal/share $HOME/.cabal/bin installplan.txt $HOME/.cabsnap/;+   fi+ # 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. script:  # -v2 provides useful information for debugging- - cabal configure -v2+ - cabal configure --enable-tests --enable-benchmarks -v2   # this builds all libraries and executables  # (including tests/benchmarks)  - cabal build + - cabal test+ - hlint src --cpp-define HLINT+  # tests that a source-distribution can be generated  - cabal sdist- - hlint src --cpp-define HLINT   # check that the generated source-distribution can be built & installed  - export SRC_TGZ=$(cabal info . | awk '{print $2 ".tar.gz";exit}') ;@@ -60,3 +120,5 @@     skip_join: true     template:       - "\x0313heaps\x03/\x0306%{branch}\x03 \x0314%{commit}\x03 %{build_url} %{message}"++# EOF

@@ -1,3 +1,14 @@+0.3.4.1+-------+* Fix a typo in the `doctests` for `mapMonotonic`++0.3.4+-----+* Add `Bifunctor Entry` instance+* Revamp `Setup.hs` to use `cabal-doctest`. This makes it build+  with `Cabal-2.0`, and makes the `doctest`s work with `cabal new-build` and+  sandboxes.+ 0.3.3 ----- * Remove redundant constraints

@@ -1,7 +1,182 @@-#!/usr/bin/runhaskell-> module Main (main) where+\begin{code}+{-# LANGUAGE CPP #-}+{-# LANGUAGE OverloadedStrings #-}+module Main (main) where -> import Distribution.Simple+#ifndef MIN_VERSION_cabal_doctest+#define MIN_VERSION_cabal_doctest(x,y,z) 0+#endif -> main :: IO ()-> main = defaultMain++#if MIN_VERSION_cabal_doctest(1,0,0)+import Distribution.Extra.Doctest ( defaultMainWithDoctests )+#else++-- Otherwise we provide a shim++#ifndef MIN_VERSION_Cabal+#define MIN_VERSION_Cabal(x,y,z) 0+#endif+#ifndef MIN_VERSION_directory+#define MIN_VERSION_directory(x,y,z) 0+#endif+#if MIN_VERSION_Cabal(1,24,0)+#define InstalledPackageId UnitId+#endif++import Control.Monad ( when )+import Data.List ( nub )+import Data.String ( fromString )+import Distribution.Package ( InstalledPackageId )+import Distribution.Package ( PackageId, Package (..), packageVersion )+import Distribution.PackageDescription ( PackageDescription(), TestSuite(..) , Library (..), BuildInfo (..))+import Distribution.Simple ( defaultMainWithHooks, UserHooks(..), simpleUserHooks )+import Distribution.Simple.Utils ( rewriteFile, createDirectoryIfMissingVerbose )+import Distribution.Simple.BuildPaths ( autogenModulesDir )+import Distribution.Simple.Setup ( BuildFlags(buildDistPref, buildVerbosity), fromFlag)+import Distribution.Simple.LocalBuildInfo ( withPackageDB, withLibLBI, withTestLBI, LocalBuildInfo(), ComponentLocalBuildInfo(componentPackageDeps), compiler )+import Distribution.Simple.Compiler ( showCompilerId , PackageDB (..))+import Distribution.Text ( display , simpleParse )+import System.FilePath ( (</>) )++#if MIN_VERSION_Cabal(1,25,0)+import Distribution.Simple.BuildPaths ( autogenComponentModulesDir )+#endif++#if MIN_VERSION_directory(1,2,2)+import System.Directory (makeAbsolute)+#else+import System.Directory (getCurrentDirectory)+import System.FilePath (isAbsolute)++makeAbsolute :: FilePath -> IO FilePath+makeAbsolute p | isAbsolute p = return p+               | otherwise    = do+    cwd <- getCurrentDirectory+    return $ cwd </> p+#endif++generateBuildModule :: String -> BuildFlags -> PackageDescription -> LocalBuildInfo -> IO ()+generateBuildModule testsuiteName flags pkg lbi = do+  let verbosity = fromFlag (buildVerbosity flags)+  let distPref = fromFlag (buildDistPref flags)++  -- Package DBs+  let dbStack = withPackageDB lbi ++ [ SpecificPackageDB $ distPref </> "package.conf.inplace" ]+  let dbFlags = "-hide-all-packages" : packageDbArgs dbStack++  withLibLBI pkg lbi $ \lib libcfg -> do+    let libBI = libBuildInfo lib++    -- modules+    let modules = exposedModules lib ++ otherModules libBI+    -- it seems that doctest is happy to take in module names, not actual files!+    let module_sources = modules++    -- We need the directory with library's cabal_macros.h!+#if MIN_VERSION_Cabal(1,25,0)+    let libAutogenDir = autogenComponentModulesDir lbi libcfg+#else+    let libAutogenDir = autogenModulesDir lbi+#endif++    -- Lib sources and includes+    iArgs <- mapM (fmap ("-i"++) . makeAbsolute) $ libAutogenDir : hsSourceDirs libBI+    includeArgs <- mapM (fmap ("-I"++) . makeAbsolute) $ includeDirs libBI++    -- CPP includes, i.e. include cabal_macros.h+    let cppFlags = map ("-optP"++) $+            [ "-include", libAutogenDir ++ "/cabal_macros.h" ]+            ++ cppOptions libBI++    withTestLBI pkg lbi $ \suite suitecfg -> when (testName suite == fromString testsuiteName) $ do++      -- get and create autogen dir+#if MIN_VERSION_Cabal(1,25,0)+      let testAutogenDir = autogenComponentModulesDir lbi suitecfg+#else+      let testAutogenDir = autogenModulesDir lbi+#endif+      createDirectoryIfMissingVerbose verbosity True testAutogenDir++      -- write autogen'd file+      rewriteFile (testAutogenDir </> "Build_doctests.hs") $ unlines+        [ "module Build_doctests where"+        , ""+        -- -package-id etc. flags+        , "pkgs :: [String]"+        , "pkgs = " ++ (show $ formatDeps $ testDeps libcfg suitecfg)+        , ""+        , "flags :: [String]"+        , "flags = " ++ show (iArgs ++ includeArgs ++ dbFlags ++ cppFlags)+        , ""+        , "module_sources :: [String]"+        , "module_sources = " ++ show (map display module_sources)+        ]+  where+    -- we do this check in Setup, as then doctests don't need to depend on Cabal+    isOldCompiler = maybe False id $ do+      a <- simpleParse $ showCompilerId $ compiler lbi+      b <- simpleParse "7.5"+      return $ packageVersion (a :: PackageId) < b++    formatDeps = map formatOne+    formatOne (installedPkgId, pkgId)+      -- The problem is how different cabal executables handle package databases+      -- when doctests depend on the library+      | packageId pkg == pkgId = "-package=" ++ display pkgId+      | otherwise              = "-package-id=" ++ display installedPkgId++    -- From Distribution.Simple.Program.GHC+    packageDbArgs :: [PackageDB] -> [String]+    packageDbArgs | isOldCompiler = packageDbArgsConf+                  | otherwise     = packageDbArgsDb++    -- GHC <7.6 uses '-package-conf' instead of '-package-db'.+    packageDbArgsConf :: [PackageDB] -> [String]+    packageDbArgsConf dbstack = case dbstack of+      (GlobalPackageDB:UserPackageDB:dbs) -> concatMap specific dbs+      (GlobalPackageDB:dbs)               -> ("-no-user-package-conf")+                                           : concatMap specific dbs+      _ -> ierror+      where+        specific (SpecificPackageDB db) = [ "-package-conf=" ++ db ]+        specific _                      = ierror+        ierror = error $ "internal error: unexpected package db stack: "+                      ++ show dbstack++    -- GHC >= 7.6 uses the '-package-db' flag. See+    -- https://ghc.haskell.org/trac/ghc/ticket/5977.+    packageDbArgsDb :: [PackageDB] -> [String]+    -- special cases to make arguments prettier in common scenarios+    packageDbArgsDb dbstack = case dbstack of+      (GlobalPackageDB:UserPackageDB:dbs)+        | all isSpecific dbs              -> concatMap single dbs+      (GlobalPackageDB:dbs)+        | all isSpecific dbs              -> "-no-user-package-db"+                                           : concatMap single dbs+      dbs                                 -> "-clear-package-db"+                                           : concatMap single dbs+     where+       single (SpecificPackageDB db) = [ "-package-db=" ++ db ]+       single GlobalPackageDB        = [ "-global-package-db" ]+       single UserPackageDB          = [ "-user-package-db" ]+       isSpecific (SpecificPackageDB _) = True+       isSpecific _                     = False++testDeps :: ComponentLocalBuildInfo -> ComponentLocalBuildInfo -> [(InstalledPackageId, PackageId)]+testDeps xs ys = nub $ componentPackageDeps xs ++ componentPackageDeps ys++defaultMainWithDoctests :: String -> IO ()+defaultMainWithDoctests testSuiteName = defaultMainWithHooks simpleUserHooks+  { buildHook = \pkg lbi hooks flags -> do+     generateBuildModule testSuiteName flags pkg lbi+     buildHook simpleUserHooks pkg lbi hooks flags+  }++#endif++main :: IO ()+main = defaultMainWithDoctests "doctests"++\end{code}

@@ -1,5 +1,5 @@ name:           heaps-version:        0.3.3+version:        0.3.4.1 license:        BSD3 license-file:   LICENSE author:         Edward A. Kmett@@ -11,11 +11,17 @@ synopsis:       Asymptotically optimal Brodal/Okasaki heaps. description:    Asymptotically optimal Brodal\/Okasaki bootstrapped skew-binomial heaps from the paper <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 "Optimal Purely Functional Priority Queues">, extended with a 'Foldable' interface. copyright:      (c) 2010-2015 Edward A. Kmett-tested-with:    GHC == 7.4.2, GHC == 7.6.3, GHC == 7.8.4, GHC == 7.10.0.20150307-build-type:     Simple+tested-with:    GHC == 7.4.2, GHC == 7.6.3, GHC == 7.8.4, GHC == 7.10.3, GHC == 8.0.2, GHC == 8.2.1+build-type:     Custom cabal-version:  >=1.8 extra-source-files: HLint.hs .gitignore .travis.yml CHANGELOG.markdown README.markdown +custom-setup+  setup-depends:+    base          >= 4.3 && <5,+    Cabal         >= 1.10,+    cabal-doctest >= 1 && <1.1+ source-repository head   type: git   location: git://github.com/ekmett/heaps.git@@ -33,8 +39,8 @@   main-is: doctests.hs   build-depends:     base,-    directory >= 1.0 && < 1.3,-    doctest >= 0.9 && <= 0.10,+    directory >= 1.0 && < 1.4,+    doctest >= 0.9 && <= 0.12,     filepath   ghc-options: -Wall   hs-source-dirs: tests

@@ -88,6 +88,9 @@     , traverse #endif     )+#if MIN_VERSION_base(4,8,0)+import Data.Bifunctor+#endif import qualified Data.List as L import Control.Applicative (Applicative(pure)) import Control.Monad (liftM)@@ -254,13 +257,13 @@ -- -- >>> uncons (fromList [2,1,3]) -- Just (1,fromList [2,3])-uncons :: Heap a -> Maybe (a, Heap a)+uncons :: Ord a => Heap a -> Maybe (a, Heap a) uncons Empty = Nothing uncons l@(Heap _ _ t) = Just (root t, deleteMin l) {-# INLINE uncons #-}  -- | Same as 'uncons'-viewMin :: Heap a -> Maybe (a, Heap a)+viewMin :: Ord a => Heap a -> Maybe (a, Heap a) viewMin = uncons {-# INLINE viewMin #-} @@ -440,9 +443,9 @@ -- | /O(n)/. Map a monotone increasing function over the heap. -- Provides a better constant factor for performance than 'map', but no checking is performed that the function provided is monotone increasing. Misuse of this function can cause a Heap to violate the heap property. ----- >>> map (+1) (fromList [1,2,3])+-- >>> mapMonotonic (+1) (fromList [1,2,3]) -- fromList [2,3,4]--- >>> map (*2) (fromList [1,2,3])+-- >>> mapMonotonic (*2) (fromList [1,2,3]) -- fromList [2,4,6] mapMonotonic :: Ord b => (a -> b) -> Heap a -> Heap b mapMonotonic _ Empty = Empty@@ -571,7 +574,7 @@ -- -- >>> concatMap (\a -> fromList [a,a+1]) (fromList [1,4]) -- fromList [1,4,5,2]-concatMap :: (a -> Heap b) -> Heap a -> Heap b+concatMap :: Ord b => (a -> Heap b) -> Heap a -> Heap b concatMap _ Empty = Empty concatMap f h@(Heap _ _ t) = foldMap f t {-# INLINE concatMap #-}@@ -759,6 +762,11 @@ instance Functor (Entry p) where   fmap f (Entry p a) = Entry p (f a)   {-# INLINE fmap #-}++#if MIN_VERSION_base(4,8,0)+instance Bifunctor Entry where+  bimap f g (Entry p a) = Entry (f p) (g a)+#endif  instance Foldable (Entry p) where   foldMap f (Entry _ a) = f a

@@ -1,28 +1,25 @@+-----------------------------------------------------------------------------+-- |+-- Module      :  Main (doctests)+-- Copyright   :  (C) 2012-14 Edward Kmett+-- License     :  BSD-style (see the file LICENSE)+-- Maintainer  :  Edward Kmett <ekmett@gmail.com>+-- Stability   :  provisional+-- Portability :  portable+--+-- This module provides doctests for a project based on the actual versions+-- of the packages it was built with. It requires a corresponding Setup.lhs+-- to be added to the project+----------------------------------------------------------------------------- module Main where +import Build_doctests (flags, pkgs, module_sources)+import Data.Foldable (traverse_) import Test.DocTest-import System.Directory-import System.FilePath-import Control.Applicative-import Control.Monad-import Data.List  main :: IO ()-main = getSources >>= \sources -> doctest $-    "-isrc"-  : "-idist/build/autogen"-  : "-optP-include"-  : "-optPdist/build/autogen/cabal_macros.h"-  : sources--getSources :: IO [FilePath]-getSources = filter (isSuffixOf ".hs") <$> go "src"+main = do+    traverse_ putStrLn args+    doctest args   where-    go dir = do-      (dirs, files) <- getFilesAndDirectories dir-      (files ++) . concat <$> mapM go dirs--getFilesAndDirectories :: FilePath -> IO ([FilePath], [FilePath])-getFilesAndDirectories dir = do-  c <- map (dir </>) . filter (`notElem` ["..", "."]) <$> getDirectoryContents dir-  (,) <$> filterM doesDirectoryExist c <*> filterM doesFileExist c+    args = flags ++ pkgs ++ module_sources