summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorryanglscott <>2018-01-18 19:45:00 (GMT)
committerhdiff <hdiff@hdiff.luite.com>2018-01-18 19:45:00 (GMT)
commit3d36ba12531f21f3496e872c11d416da3d186930 (patch)
tree462f6350f8786ea0d567b2382f344411d505c5d4
parentb532f868941ab6026a995b828ad2138a22457cec (diff)
version 0.3.6HEAD0.3.6master
-rw-r--r--.travis.yml228
-rw-r--r--CHANGELOG.markdown4
-rw-r--r--heaps.cabal14
-rw-r--r--src/Data/Heap.hs11
4 files changed, 156 insertions, 101 deletions
diff --git a/.travis.yml b/.travis.yml
index 721bd4b..ab558ab 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -1,124 +1,156 @@
-# This file has been generated -- see https://github.com/hvr/multi-ghc-travis
+# This Travis job script has been generated by a script via
+#
+# runghc make_travis_yml_2.hs '-o' '.travis.yml' '--irc-channel=irc.freenode.org#haskell-lens' '--no-no-tests-no-bench' '--no-installed' 'cabal.project'
+#
+# For more information, see https://github.com/hvr/multi-ghc-travis
+#
language: c
sudo: false
+git:
+ submodules: false # whether to recursively clone submodules
+
+notifications:
+ irc:
+ channels:
+ - "irc.freenode.org#haskell-lens"
+ skip_join: true
+ template:
+ - "\x0313heaps\x03/\x0306%{branch}\x03 \x0314%{commit}\x03 %{build_url} %{message}"
+
cache:
directories:
- - $HOME/.cabsnap
- $HOME/.cabal/packages
+ - $HOME/.cabal/store
before_cache:
- rm -fv $HOME/.cabal/packages/hackage.haskell.org/build-reports.log
- - rm -fv $HOME/.cabal/packages/hackage.haskell.org/00-index.tar
+ # remove files that are regenerated by 'cabal update'
+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/00-index.*
+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/*.json
+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.cache
+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.tar
+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.tar.idx
+
+ - rm -rfv $HOME/.cabal/packages/head.hackage
+
+addons:
+ apt:
+ packages: &apt_packages
+ - ghc-ppa-tools
+ - hlint
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=2.0 GHCVER=8.2.1
- compiler: ": #GHC 8.2.1"
- addons: {apt: {packages: [cabal-install-2.0,ghc-8.2.1,hlint], sources: [hvr-ghc]}}
- - env: CABALVER=head GHCVER=head
- compiler: ": #GHC head"
- addons: {apt: {packages: [cabal-install-head,ghc-head,hlint], sources: [hvr-ghc]}}
+ - compiler: "ghc-7.0.4"
+ # env: TEST=--disable-tests BENCH=--disable-benchmarks
+ addons: {apt: {packages: [*apt_packages,cabal-install-2.0,ghc-7.0.4], sources: [hvr-ghc]}}
+ - compiler: "ghc-7.2.2"
+ # env: TEST=--disable-tests BENCH=--disable-benchmarks
+ addons: {apt: {packages: [*apt_packages,cabal-install-2.0,ghc-7.2.2], sources: [hvr-ghc]}}
+ - compiler: "ghc-7.4.2"
+ # env: TEST=--disable-tests BENCH=--disable-benchmarks
+ addons: {apt: {packages: [*apt_packages,cabal-install-2.0,ghc-7.4.2], sources: [hvr-ghc]}}
+ - compiler: "ghc-7.6.3"
+ # env: TEST=--disable-tests BENCH=--disable-benchmarks
+ addons: {apt: {packages: [*apt_packages,cabal-install-2.0,ghc-7.6.3], sources: [hvr-ghc]}}
+ - compiler: "ghc-7.8.4"
+ # env: TEST=--disable-tests BENCH=--disable-benchmarks
+ addons: {apt: {packages: [*apt_packages,cabal-install-2.0,ghc-7.8.4], sources: [hvr-ghc]}}
+ - compiler: "ghc-7.10.3"
+ # env: TEST=--disable-tests BENCH=--disable-benchmarks
+ addons: {apt: {packages: [*apt_packages,cabal-install-2.0,ghc-7.10.3], sources: [hvr-ghc]}}
+ - compiler: "ghc-8.0.2"
+ # env: TEST=--disable-tests BENCH=--disable-benchmarks
+ addons: {apt: {packages: [*apt_packages,cabal-install-2.0,ghc-8.0.2], sources: [hvr-ghc]}}
+ - compiler: "ghc-8.2.2"
+ # env: TEST=--disable-tests BENCH=--disable-benchmarks
+ addons: {apt: {packages: [*apt_packages,cabal-install-2.0,ghc-8.2.2], sources: [hvr-ghc]}}
+ - compiler: "ghc-8.4.1"
+ env: GHCHEAD=true
+ addons: {apt: {packages: [*apt_packages,cabal-install-head,ghc-8.4.1], sources: [hvr-ghc]}}
+ - compiler: "ghc-head"
+ env: GHCHEAD=true
+ addons: {apt: {packages: [*apt_packages,cabal-install-head,ghc-head], sources: [hvr-ghc]}}
allow_failures:
- - env: CABALVER=1.24 GHCVER=7.0.4
- - env: CABALVER=1.24 GHCVER=7.2.2
- - env: CABALVER=head GHCVER=head
+ - compiler: "ghc-7.0.4"
+ - compiler: "ghc-7.2.2"
+ - compiler: "ghc-8.4.1"
+ - compiler: "ghc-head"
before_install:
- - unset CC
- - export PATH=$HOME/.cabal/bin:/opt/ghc/$GHCVER/bin:/opt/cabal/$CABALVER/bin:$PATH
+ - HC=${CC}
+ - HCPKG=${HC/ghc/ghc-pkg}
+ - unset CC
+ - ROOTDIR=$(pwd)
+ - mkdir -p $HOME/.local/bin
+ - "PATH=/opt/ghc/bin:/opt/ghc-ppa-tools/bin:$HOME/local/bin:$PATH"
+ - HCNUMVER=$(( $(${HC} --numeric-version|sed -E 's/([0-9]+)\.([0-9]+)\.([0-9]+).*/\1 * 10000 + \2 * 100 + \3/') ))
+ - echo $HCNUMVER
install:
- - 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.
+ - cabal --version
+ - echo "$(${HC} --version) [$(${HC} --print-project-git-commit-id 2> /dev/null || echo '?')]"
+ - BENCH=${BENCH---enable-benchmarks}
+ - TEST=${TEST---enable-tests}
+ - HADDOCK=${HADDOCK-true}
+ - INSTALLED=${INSTALLED-true}
+ - GHCHEAD=${GHCHEAD-false}
+ - travis_retry cabal update -v
+ - "sed -i.bak 's/^jobs:/-- jobs:/' ${HOME}/.cabal/config"
+ - rm -fv cabal.project cabal.project.local
+ # Overlay Hackage Package Index for GHC HEAD: https://github.com/hvr/head.hackage
+ - |
+ if $GHCHEAD; then
+ sed -i.bak 's/-- allow-newer:.*/allow-newer: *:base, *:template-haskell, *:ghc, *:Cabal/' ${HOME}/.cabal/config
+
+ echo 'repository head.hackage' >> ${HOME}/.cabal/config
+ echo ' url: http://head.hackage.haskell.org/' >> ${HOME}/.cabal/config
+ echo ' secure: True' >> ${HOME}/.cabal/config
+ echo ' root-keys: 07c59cb65787dedfaef5bd5f987ceb5f7e5ebf88b904bbd4c5cbdeb2ff71b740' >> ${HOME}/.cabal/config
+ echo ' 2e8555dde16ebd8df076f1a8ef13b8f14c66bad8eafefd7d9e37d0ed711821fb' >> ${HOME}/.cabal/config
+ echo ' 8f79fd2389ab2967354407ec852cbe73f2e8635793ac446d09461ffb99527f6e' >> ${HOME}/.cabal/config
+ echo ' key-threshold: 3' >> ${HOME}/.cabal.config
+
+ cabal new-update head.hackage -v
+ fi
+ - grep -Ev -- '^\s*--' ${HOME}/.cabal/config | grep -Ev '^\s*$'
+ - "printf 'packages: \".\"\\n' > cabal.project"
+ - cat cabal.project
+ - if [ -f "./configure.ac" ]; then
+ (cd "." && autoreconf -i);
+ fi
+ - rm -f cabal.project.freeze
+ - cabal new-build -w ${HC} ${TEST} ${BENCH} --project-file="cabal.project" --dep -j2 all
+ - rm -rf "."/.ghc.environment.* "."/dist
+ - DISTDIR=$(mktemp -d /tmp/dist-test.XXXX)
+
+# 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 --enable-tests --enable-benchmarks -v2
+ # test that source-distributions can be generated
+ - (cd "." && cabal sdist)
+ - mv "."/dist/heaps-*.tar.gz ${DISTDIR}/
+ - cd ${DISTDIR} || false
+ - find . -maxdepth 1 -name '*.tar.gz' -exec tar -xvf '{}' \;
+ - "printf 'packages: heaps-*/*.cabal\\n' > cabal.project"
+ - cat cabal.project
- # this builds all libraries and executables
- # (including tests/benchmarks)
- - cabal build
- - cabal test
- - hlint src --cpp-define HLINT
+ # build & run tests, build benchmarks
+ - cabal new-build -w ${HC} ${TEST} ${BENCH} all
+ - if [ "x$TEST" = "x--enable-tests" ]; then cabal new-test -w ${HC} ${TEST} ${BENCH} all; fi
- # tests that a source-distribution can be generated
- - cabal sdist
+ # cabal check
+ - (cd heaps-* && cabal check)
- # check that the generated source-distribution can be built & installed
- - export SRC_TGZ=$(cabal info . | awk '{print $2 ".tar.gz";exit}') ;
- cd dist/;
- if [ -f "$SRC_TGZ" ]; then
- cabal install --force-reinstalls "$SRC_TGZ";
- else
- echo "expected '$SRC_TGZ' not found";
- exit 1;
- fi
+ # haddock
+ - rm -rf ./dist-newstyle
+ - if $HADDOCK; then cabal new-haddock -w ${HC} ${TEST} ${BENCH} all; else echo "Skipping haddock generation";fi
-notifications:
- irc:
- channels:
- - "irc.freenode.org#haskell-lens"
- skip_join: true
- template:
- - "\x0313heaps\x03/\x0306%{branch}\x03 \x0314%{commit}\x03 %{build_url} %{message}"
+ # hlint
+ - (cd heaps-* && hlint src --cpp-define=HLINT)
+# REGENDATA ["-o",".travis.yml","--irc-channel=irc.freenode.org#haskell-lens","--no-no-tests-no-bench","--no-installed","cabal.project"]
# EOF
diff --git a/CHANGELOG.markdown b/CHANGELOG.markdown
index ec6148a..37bc116 100644
--- a/CHANGELOG.markdown
+++ b/CHANGELOG.markdown
@@ -1,3 +1,7 @@
+0.3.6 [2018.01.18]
+------------------
+* Add `Semigroup` instance for `Heap`.
+
0.3.5
-----
* Support `doctest-0.12`
diff --git a/heaps.cabal b/heaps.cabal
index 536967a..afd2f33 100644
--- a/heaps.cabal
+++ b/heaps.cabal
@@ -1,5 +1,5 @@
name: heaps
-version: 0.3.5
+version: 0.3.6
license: BSD3
license-file: LICENSE
author: Edward A. Kmett
@@ -11,7 +11,15 @@ category: Data Structures
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.3, GHC == 8.0.2, GHC == 8.2.1
+tested-with: GHC == 7.0.4
+ , GHC == 7.2.2
+ , GHC == 7.4.2
+ , GHC == 7.6.3
+ , GHC == 7.8.4
+ , GHC == 7.10.3
+ , GHC == 8.0.2
+ , GHC == 8.2.2
+ , GHC == 8.4.1
build-type: Custom
cabal-version: >=1.8
extra-source-files:
@@ -46,7 +54,7 @@ test-suite doctests
build-depends:
base,
directory >= 1.0 && < 1.4,
- doctest >= 0.9 && < 0.13,
+ doctest >= 0.9 && < 0.14,
filepath,
heaps
ghc-options: -Wall
diff --git a/src/Data/Heap.hs b/src/Data/Heap.hs
index 39f3534..c786284 100644
--- a/src/Data/Heap.hs
+++ b/src/Data/Heap.hs
@@ -94,6 +94,9 @@ import Data.Bifunctor
import qualified Data.List as L
import Control.Applicative (Applicative(pure))
import Control.Monad (liftM)
+#if MIN_VERSION_base(4,9,0)
+import Data.Semigroup (Semigroup(..))
+#endif
import Data.Monoid (Monoid(mappend, mempty))
import Data.Foldable hiding (minimum, concatMap)
import Data.Function (on)
@@ -377,11 +380,19 @@ sort :: Ord a => [a] -> [a]
sort = toList . fromList
{-# INLINE sort #-}
+#if MIN_VERSION_base(4,9,0)
+instance Semigroup (Heap a) where
+ (<>) = union
+ {-# INLINE (<>) #-}
+#endif
+
instance Monoid (Heap a) where
mempty = empty
{-# INLINE mempty #-}
+#if !(MIN_VERSION_base(4,11,0))
mappend = union
{-# INLINE mappend #-}
+#endif
-- | /O(n)/. Returns the elements in the heap in some arbitrary, very likely unsorted, order.
--