circular 0.3.1.1 → 0.4.0.0

raw patch · 4 files changed

+103/−83 lines, 4 filesdep ~QuickCheckdep ~aesondep ~basePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: QuickCheck, aeson, base, criterion, hspec, primitive, quickcheck-instances, vector

API changes (from Hackage documentation)

Files

• ChangeLog.md +7/−1
• circular.cabal +57/−57
• src/Data/Stack/Circular.hs +35/−21
• test/Data/Stack/CircularSpec.hs +4/−4

@@ -1,8 +1,14 @@ -# Changelog for circular+# Revision history for circular   ## Unreleased changes+++## 0.4.0.0++-   Do not export data constructors nor record fields.+-   `fromVectorWith`.   ## 0.3.1.1

@@ -1,68 +1,68 @@-cabal-version:      1.12-name:               circular-version:            0.3.1.1-license:            BSD3-license-file:       LICENSE-copyright:          Dominik Schrempf (2020)-maintainer:         dominik.schrempf@gmail.com-author:             Dominik Schrempf-homepage:           https://github.com/dschrempf/circular#readme-bug-reports:        https://github.com/dschrempf/circular/issues-synopsis:           Circular fixed-sized mutable vectors-description:-    Please see the README at <https://github.com/dschrempf/circular#readme>--category:           Math, Data Structures-build-type:         Simple+cabal-version:  1.12+name:           circular+version:        0.4.0.0+synopsis:       Circular fixed-sized mutable vectors+description:    Please see the README at <https://github.com/dschrempf/circular#readme>+category:       Math, Data Structures+homepage:       https://github.com/dschrempf/circular#readme+bug-reports:    https://github.com/dschrempf/circular/issues+author:         Dominik Schrempf+maintainer:     dominik.schrempf@gmail.com+copyright:      Dominik Schrempf (2020)+license:        BSD3+license-file:   LICENSE+build-type:     Simple extra-source-files:     README.md     ChangeLog.md  source-repository head-    type:     git-    location: https://github.com/dschrempf/circular+  type: git+  location: https://github.com/dschrempf/circular  library-    exposed-modules:  Data.Stack.Circular-    hs-source-dirs:   src-    other-modules:    Paths_circular-    default-language: Haskell2010-    ghc-options:      -Wall -Wunused-packages-    build-depends:-        aeson >=1.5.4.1 && <1.6,-        base >=4.14.1.0 && <4.15,-        primitive >=0.7.1.0 && <0.8,-        vector >=0.12.1.2 && <0.13+  exposed-modules:+      Data.Stack.Circular+  other-modules:+      Paths_circular+  hs-source-dirs: src+  ghc-options: -Wall -Wunused-packages+  build-depends:+      aeson+    , base >=4.7 && <5+    , primitive+    , vector+  default-language: Haskell2010  test-suite circular-test-    type:             exitcode-stdio-1.0-    main-is:          Spec.hs-    hs-source-dirs:   test-    other-modules:-        Data.Stack.CircularSpec-        Paths_circular--    default-language: Haskell2010-    ghc-options:      -Wall -Wunused-packages-    build-depends:-        QuickCheck >=2.13.2 && <2.14,-        aeson >=1.5.4.1 && <1.6,-        base >=4.14.1.0 && <4.15,-        circular -any,-        hspec >=2.7.4 && <2.8,-        primitive >=0.7.1.0 && <0.8,-        quickcheck-instances >=0.3.23 && <0.4,-        vector >=0.12.1.2 && <0.13+  type: exitcode-stdio-1.0+  main-is: Spec.hs+  other-modules:+      Data.Stack.CircularSpec+      Paths_circular+  hs-source-dirs: test+  ghc-options: -Wall -Wunused-packages+  build-depends:+      QuickCheck+    , aeson+    , base >=4.7 && <5+    , circular+    , hspec+    , primitive+    , quickcheck-instances+    , vector+  default-language: Haskell2010  benchmark circular-bench-    type:             exitcode-stdio-1.0-    main-is:          Bench.hs-    hs-source-dirs:   bench-    other-modules:    Paths_circular-    default-language: Haskell2010-    ghc-options:      -Wall -Wunused-packages-    build-depends:-        base >=4.14.1.0 && <4.15,-        circular -any,-        criterion >=1.5.7.0 && <1.6,-        vector >=0.12.1.2 && <0.13+  type: exitcode-stdio-1.0+  main-is: Bench.hs+  other-modules:+      Paths_circular+  hs-source-dirs: bench+  ghc-options: -Wall -Wunused-packages+  build-depends:+      base >=4.7 && <5+    , circular+    , criterion+    , vector+  default-language: Haskell2010

@@ -7,7 +7,7 @@ -- | -- Module      :  Data.Stack.Circular -- Description :  Circular stacks of fixed size--- Copyright   :  (c) Dominik Schrempf, 2020+-- Copyright   :  (c) 2020 Dominik Schrempf -- License     :  GPL-3.0-or-later -- -- Maintainer  :  dominik.schrempf@gmail.com@@ -17,18 +17,18 @@ -- Creation date: Thu Jun 18 10:00:28 2020. -- -- Construction of mutable circular stacks is done with 'replicate' and subsequent--- 'push'es, or with 'fromVector'. Use the data constructors for 'MStack' and--- 'Stack' only if you know what you are doing.+-- 'push'es, or with 'fromVector'. -- -- When denoting the asymptotic runtime of functions, @n@ refers to the circular -- stack size. module Data.Stack.Circular   ( -- * Mutable circular stacks-    MStack (..),+    MStack,      -- ** Construction and conversion     replicate,     fromVector,+    fromVectorWithIndex,     toVector,     take, @@ -43,7 +43,7 @@     foldKM,      -- * Immutable circular stacks-    Stack (..),+    Stack,     thaw,     freeze,   )@@ -59,8 +59,8 @@ -- | Mutable circular stacks with fixed size are just mutable vectors with a -- pointer to the last element. data MStack v s a = MStack-  { mVector :: VG.Mutable v s a,-    mIndex :: !Int+  { _mVector :: VG.Mutable v s a,+    _mIndex :: !Int   }  -- | A circular stack of given size with the same element replicated.@@ -91,6 +91,19 @@   where     n = VG.length v +-- | Convert a vector to a circular stack with size being equal to the length of+-- the vector. The element of the vector at the given index is the youngest+-- element of the stack, the next element of the vector is the oldest element of+-- the stack.+--+-- The vector must be non-empty.+--+-- O(n).+fromVectorWithIndex :: (VG.Vector v a, PrimMonad m) => Int -> v a -> m (MStack v (PrimState m) a)+fromVectorWithIndex i v = do+  ms <- fromVector v+  return $ ms {_mIndex = i}+ -- | Convert a circular stack to a vector. The first element of the returned -- vector is the oldest element of the stack, the last element of the returned -- vector is the youngest element of the stack.@@ -134,7 +147,7 @@  -- | Size of the stack. size :: VG.Vector v a => MStack v s a -> Int-size = VM.length . mVector+size = VM.length . _mVector  -- | Get the last element without changing the stack. --@@ -155,12 +168,12 @@ -- -- Be careful: ----- - The stack is always full! Popping returns the last element and moves the---   index to the second-last element, but the element is not truly removed from---   the stack. It is only put to the end of the queue.+-- The stack is always full! Popping returns the last element and moves the+-- index to the second-last element, but the element is not truly removed from+-- the stack. It is only put to the end of the queue. ----- - Hence, `pop` always succeeds, even if there are actually no more elements---   on the stack (similar to walking backwards in a circle).+-- Hence, `pop` always succeeds, even if there are actually no more elements on+-- the stack (similar to walking backwards in a circle). -- -- O(1). pop :: (VG.Vector v a, PrimMonad m) => MStack v (PrimState m) a -> m (a, MStack v (PrimState m) a)@@ -191,7 +204,8 @@ -- O(n). foldM :: (VG.Vector v b, PrimMonad m) => (a -> b -> a) -> a -> MStack v (PrimState m) b -> m a foldM f x s = foldKM n f x s-  where n = VM.length $ mVector s+  where+    n = VM.length $ _mVector s  -- Monadic fold over k elements in a vector. foldKV ::@@ -208,7 +222,7 @@ foldKV k i f x v = do   x' <- f x <$> VM.unsafeRead v i   -- Assume that i-1 is non-negative.-  foldKV (k-1) (i-1) f x' v+  foldKV (k -1) (i -1) f x' v  -- | See 'foldM' but only over the @k@ youngest elements on the stack. --@@ -221,18 +235,18 @@   | k <= i' = foldKV k i f x v   -- Or not.   | otherwise = do-      x' <- foldKV i' i f x v-      -- Continue from the end of the vector.-      foldKV (k-i') (n-1) f x' v+    x' <- foldKV i' i f x v+    -- Continue from the end of the vector.+    foldKV (k - i') (n -1) f x' v   where     n = VM.length v-    i' = i+1+    i' = i + 1  -- | Immutable circular stack; useful, for example, to save, or restore a -- mutable circular stack. data Stack v a = Stack-  { iStack :: v a,-    iIndex :: !Int+  { _iStack :: v a,+    _iIndex :: !Int   }   deriving (Eq, Read, Show) 

@@ -39,7 +39,7 @@     n <- choose (1, s + 1)     v <- VB.fromList <$> vector n     i <- choose (0, n -1)-    return $ C.Stack v i+    return $ runST $ C.fromVectorWithIndex i v >>= C.freeze  se :: PrimMonad m => m (C.MStack VB.Vector (PrimState m) Int) se = C.replicate 10 0@@ -147,9 +147,9 @@     n = VB.length v     solV = VB.sum v     solSs =-      runST $ do-        stack <- C.fromVector v-        sequence [C.foldM (+) 0 (stack {C.mIndex = i}) | i <- [0 .. n - 1 :: Int]]+      runST $+        sequence+          [C.fromVectorWithIndex i v >>= C.foldM (+) 0 | i <- [0 .. n - 1 :: Int]]  spec :: Spec spec = do