rbst 0.0.0.0 → 0.0.0.1
raw patch · 18 files changed
+299/−253 lines, 18 filesdep ~basePVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base
API changes (from Hackage documentation)
Files
- CHANGELOG.md +9/−0
- README.md +1/−0
- rbst.cabal +11/−10
- src/RBST.hs +1/−1
- src/RBST/Internal.hs +2/−2
- src/RBST/Pretty.hs +3/−1
- test/Spec.hs +15/−1
- test/Test/RBST.hs +19/−0
- test/Test/RBST/Cuts.hs +53/−0
- test/Test/RBST/CutsSpec.hs +0/−53
- test/Test/RBST/Laws.hs +46/−0
- test/Test/RBST/LawsSpec.hs +0/−46
- test/Test/RBST/Query.hs +56/−0
- test/Test/RBST/QuerySpec.hs +0/−56
- test/Test/RBST/SetOps.hs +46/−0
- test/Test/RBST/SetOpsSpec.hs +0/−46
- test/Test/RBST/Update.hs +37/−0
- test/Test/RBST/UpdateSpec.hs +0/−37
CHANGELOG.md view
@@ -7,5 +7,14 @@ * Work in progress. +## 0.0.0.1 — May 9, 2020++* Update copyright to include credit to Dmitrii Kovanikov work.++## 0.0.0.0 — May 9, 2020++* First release including modules `RBST` and `RBST.Pretty`.++ [1]: https://pvp.haskell.org [2]: https://github.com/monadplus/RBST/releases
README.md view
@@ -2,6 +2,7 @@  [](https://hackage.haskell.org/package/rbst)+[](https://github.com/monadplus/rbst/actions) [](https://travis-ci.org/monadplus/RBST) [](LICENSE)
rbst.cabal view
@@ -1,7 +1,7 @@ cabal-version: >= 1.10 name: rbst-version: 0.0.0.0+version: 0.0.0.1 build-type: Simple license: MIT license-file: LICENSE@@ -36,7 +36,7 @@ other-modules: RBST.Internal - build-depends: base >=4.12 && <4.14,+ build-depends: base >=4.12 && <4.15, bytestring >=0.10.8.2 && <0.11.0.0, containers >=0.5.0.1 && <0.7, deepseq >=1.4 && <1.5,@@ -104,14 +104,15 @@ hs-source-dirs: test main-is: Spec.hs other-modules: Test.Common- Test.RBST.CutsSpec- Test.RBST.LawsSpec- Test.RBST.QuerySpec- Test.RBST.SetOpsSpec- Test.RBST.UpdateSpec+ Test.RBST+ Test.RBST.Cuts+ Test.RBST.Laws+ Test.RBST.Query+ Test.RBST.SetOps+ Test.RBST.Update build-depends: rbst,- base >=4.12 && <4.14,+ base, hspec >=2.6.0 && <2.8, hspec-expectations >=0.8.0 && <0.9, hspec-core >=2.6.0 && <2.8,@@ -178,7 +179,7 @@ hs-source-dirs: test main-is: Doctest.hs - build-depends: base >=4.12 && <4.14,+ build-depends: base, doctest >=0.16 && <0.17, Glob >=0.9 && <0.11 @@ -206,7 +207,7 @@ main-is: Benchmark.hs build-depends: rbst,- base >=4.12 && <4.14,+ base, gauge >=0.2.4 && <0.3, mwc-random >= 0.14.0 && <0.15
src/RBST.hs view
@@ -1,7 +1,7 @@ -------------------------------------------------------------------- -- | -- Module : RBST--- Copyright : (c) Arnau Abella 2020+-- Copyright : (c) 2020 Arnau Abella, Dmitrii Kovanikov -- License : MIT (see the file LICENSE) -- Maintainer : Arnau Abella arnauabell@gmail.com -- Stability : experimental
src/RBST/Internal.hs view
@@ -1,8 +1,8 @@ -------------------------------------------------------------------- -- | -- Module : RBST.Internal--- Copyright : (c) Arnau Abella 2020--- License : MIT+-- Copyright : (c) 2020 Arnau Abella, Dmitrii Kovanikov+-- License : MIT (see the file LECENSE) -- Maintainer : arnauabell@gmail.com -- Stability : experimental -- Portability : non-portable
src/RBST/Pretty.hs view
@@ -1,13 +1,15 @@ -------------------------------------------------------------------- -- | -- Module : RBST.Pretty--- Copyright : (C) Arnau Abella 2020+-- Copyright : (c) 2020 Arnau Abella, Dmitrii Kovanikov -- License : MIT (see the file LECENSE) -- Maintainer : Arnau Abella arnauabell@gmail.com -- Stability : experimental -- Portability : non-portable -- -- 'RBST' visualization.+--+-- 'prettyPrint' was copied from @treap@ package wrote by Dmitrii Kovanikov. -- -------------------------------------------------------------------- module RBST.Pretty (
test/Spec.hs view
@@ -1,1 +1,15 @@-{-# OPTIONS_GHC -F -pgmF hspec-discover #-}+module Main (main) where++import System.IO (hSetEncoding, stderr, stdout, utf8)+import Test.Hspec (Spec, hspec)+import Test.RBST (rbstSpec)++main :: IO ()+main = do+ hSetEncoding stdout utf8+ hSetEncoding stderr utf8++ hspec allUnitTests++allUnitTests :: Spec+allUnitTests = rbstSpec
+ test/Test/RBST.hs view
@@ -0,0 +1,19 @@+module Test.RBST (+ rbstSpec+ ) where++import Test.Hspec (Spec, describe)++import Test.RBST.Cuts (cutsSpec)+import Test.RBST.Laws (lawsSpec)+import Test.RBST.Query (querySpec)+import Test.RBST.SetOps (setOpsSpec)+import Test.RBST.Update (updateSpec)++rbstSpec :: Spec+rbstSpec = describe "RBST" $ do+ cutsSpec+ lawsSpec+ querySpec+ setOpsSpec+ updateSpec
+ test/Test/RBST/Cuts.hs view
@@ -0,0 +1,53 @@+module Test.RBST.Cuts (+ cutsSpec+ ) where++import Test.Common (describedAs, smallRBST)+import Test.Hspec (Spec, describe, it, shouldBe)++import qualified RBST++cutsSpec :: Spec+cutsSpec = describe "Cuts tests" $ do+ takeSpec+ dropSpec+ removeSpec++takeSpec :: Spec+takeSpec = describe "take" $ do+ it "take negative returns an empty tree" $+ RBST.take (-1) smallRBST `shouldBe` RBST.empty+ it "take 0 returns an empty tree" $+ RBST.take 0 smallRBST `shouldBe` RBST.empty+ it "take size returns tree itself" $+ RBST.take 5 smallRBST `shouldBe` smallRBST+ it "take 2 returns first two elements" $+ RBST.take 2 smallRBST `describedAs` [('A', 1), ('B', 2)]+ it "take 4 returns first four elements" $+ RBST.take 4 smallRBST `describedAs` [('A', 1), ('B', 2), ('C', 3), ('D', 4)]++dropSpec :: Spec+dropSpec = describe "drop" $ do+ it "drop negative returns tree itself" $+ RBST.drop (-1) smallRBST `shouldBe` smallRBST+ it "drop 0 returns tree itself" $+ RBST.drop 0 smallRBST `shouldBe` smallRBST+ it "drop size returns empty tree" $+ RBST.drop 5 smallRBST `shouldBe` RBST.empty+ it "drop 2 returns first two elements" $+ RBST.drop 2 smallRBST `describedAs` [('C', 3), ('D', 4), ('E', 5)]+ it "drop 4 returns first four elements" $+ RBST.drop 4 smallRBST `describedAs` [('E', 5)]++removeSpec :: Spec+removeSpec = describe "remove" $ do+ it "remove negative returns the tree itself" $+ RBST.remove (-1) smallRBST `shouldBe` smallRBST+ it "remove size returns the tree itself" $+ RBST.remove 5 smallRBST `shouldBe` smallRBST+ it "remove 0 removes the first element of the tree" $+ RBST.remove 0 smallRBST `describedAs` [('B', 2), ('C', 3), ('D', 4), ('E', 5)]+ it "remove 2 removes the 2th element of the tree" $+ RBST.remove 2 smallRBST `describedAs` [('A', 1), ('B', 2), ('D', 4), ('E', 5)]+ it "remove 4 removes the 4th element of the tree" $+ RBST.remove 4 smallRBST `describedAs` [('A', 1), ('B', 2), ('C', 3), ('D', 4)]
− test/Test/RBST/CutsSpec.hs
@@ -1,53 +0,0 @@-module Test.RBST.CutsSpec (- spec- ) where--import Test.Common (describedAs, smallRBST)-import Test.Hspec (Spec, describe, it, shouldBe)--import qualified RBST--spec :: Spec-spec = describe "Cuts tests" $ do- takeSpec- dropSpec- removeSpec--takeSpec :: Spec-takeSpec = describe "take" $ do- it "take negative returns an empty tree" $- RBST.take (-1) smallRBST `shouldBe` RBST.empty- it "take 0 returns an empty tree" $- RBST.take 0 smallRBST `shouldBe` RBST.empty- it "take size returns tree itself" $- RBST.take 5 smallRBST `shouldBe` smallRBST- it "take 2 returns first two elements" $- RBST.take 2 smallRBST `describedAs` [('A', 1), ('B', 2)]- it "take 4 returns first four elements" $- RBST.take 4 smallRBST `describedAs` [('A', 1), ('B', 2), ('C', 3), ('D', 4)]--dropSpec :: Spec-dropSpec = describe "drop" $ do- it "drop negative returns tree itself" $- RBST.drop (-1) smallRBST `shouldBe` smallRBST- it "drop 0 returns tree itself" $- RBST.drop 0 smallRBST `shouldBe` smallRBST- it "drop size returns empty tree" $- RBST.drop 5 smallRBST `shouldBe` RBST.empty- it "drop 2 returns first two elements" $- RBST.drop 2 smallRBST `describedAs` [('C', 3), ('D', 4), ('E', 5)]- it "drop 4 returns first four elements" $- RBST.drop 4 smallRBST `describedAs` [('E', 5)]--removeSpec :: Spec-removeSpec = describe "remove" $ do- it "remove negative returns the tree itself" $- RBST.remove (-1) smallRBST `shouldBe` smallRBST- it "remove size returns the tree itself" $- RBST.remove 5 smallRBST `shouldBe` smallRBST- it "remove 0 removes the first element of the tree" $- RBST.remove 0 smallRBST `describedAs` [('B', 2), ('C', 3), ('D', 4), ('E', 5)]- it "remove 2 removes the 2th element of the tree" $- RBST.remove 2 smallRBST `describedAs` [('A', 1), ('B', 2), ('D', 4), ('E', 5)]- it "remove 4 removes the 4th element of the tree" $- RBST.remove 4 smallRBST `describedAs` [('A', 1), ('B', 2), ('C', 3), ('D', 4)]
+ test/Test/RBST/Laws.hs view
@@ -0,0 +1,46 @@+module Test.RBST.Laws (+ lawsSpec+ ) where++import GHC.Exts (IsList (..))+import Test.Common (TestRBST)+import Test.Hspec (Spec, describe)+import Test.Hspec.QuickCheck (prop)+import Test.QuickCheck+import RBST.Pretty (compact)++lawsSpec :: Spec+lawsSpec = describe "Law abiding instances" $ do+ --semigroupSpec+ monoidSpec++-- | Semigroup is not lawful until unionWith is implemented.++-- semigroupSpec :: Spec+-- semigroupSpec = describe "Semigroup" $+-- prop "associativity" $+-- forAllShow arbitraryTree compact $ \a -> do+-- forAllShow arbitraryTree compact $ \b -> do+-- forAllShow arbitraryTree compact $ \c -> do+-- (a <> b) <> c `iso` a <> (b <> c)++monoidSpec :: Spec+monoidSpec = describe "Monoid" $+ prop "identity" $+ forAllShow arbitraryTree compact $ \a -> do+ (a <> mempty) `iso` a .&&. (mempty <> a) `iso` a+++----------------------------------------+----------------------------------------++arbitraryTree :: Gen TestRBST+arbitraryTree = do+ n <- choose (0, 100)+ xs <- vectorOf n arbitrary+ return $ fromList xs++-- | '(===)' for trees.+iso :: TestRBST -> TestRBST -> Property+t1 `iso` t2 = toList t1 === toList t2+infix 4 `iso`
− test/Test/RBST/LawsSpec.hs
@@ -1,46 +0,0 @@-module Test.RBST.LawsSpec (- spec- ) where--import GHC.Exts (IsList (..))-import Test.Common (TestRBST)-import Test.Hspec (Spec, describe)-import Test.Hspec.QuickCheck (prop)-import Test.QuickCheck-import RBST.Pretty (compact)--spec :: Spec-spec = describe "Law abiding instances" $ do- --semigroupSpec- monoidSpec---- | Semigroup is not lawful until unionWith is implemented.---- semigroupSpec :: Spec--- semigroupSpec = describe "Semigroup" $--- prop "associativity" $--- forAllShow arbitraryTree compact $ \a -> do--- forAllShow arbitraryTree compact $ \b -> do--- forAllShow arbitraryTree compact $ \c -> do--- (a <> b) <> c `iso` a <> (b <> c)--monoidSpec :: Spec-monoidSpec = describe "Monoid" $- prop "identity" $- forAllShow arbitraryTree compact $ \a -> do- (a <> mempty) `iso` a .&&. (mempty <> a) `iso` a--------------------------------------------------------------------------------------arbitraryTree :: Gen TestRBST-arbitraryTree = do- n <- choose (0, 100)- xs <- vectorOf n arbitrary- return $ fromList xs---- | '(===)' for trees.-iso :: TestRBST -> TestRBST -> Property-t1 `iso` t2 = toList t1 === toList t2-infix 4 `iso`
+ test/Test/RBST/Query.hs view
@@ -0,0 +1,56 @@+{-# LANGUAGE TupleSections #-}+module Test.RBST.Query (+ querySpec+ ) where++import GHC.Exts (IsList (..))+import Test.Common (TestRBST, smallRBST)+import Test.Hspec (Spec, describe, it, shouldBe)++import qualified RBST++querySpec :: Spec+querySpec = describe "Query tests" $ do+ sizeSpec+ heightSpec+ isListSpec+ lookupSpec+ atSpec++sizeSpec :: Spec+sizeSpec = describe "size" $ do+ it "size of empty RBST is 0" $+ RBST.size (RBST.empty :: TestRBST) `shouldBe` 0+ it "size of single node RBST is 1" $+ RBST.size (RBST.one 'A' 0 :: TestRBST) `shouldBe` 1+ it "size of smallRBST is 5" $+ RBST.size smallRBST `shouldBe` 5++heightSpec :: Spec+heightSpec = describe "height" $ do+ it "height of empty RBST is -1" $+ RBST.height (RBST.empty :: TestRBST) `shouldBe` -1+ it "height of single node RBST is 0" $+ RBST.height (RBST.one 'A' 0 :: TestRBST) `shouldBe` 0+ it "height of smallRBST is 2" $+ RBST.height smallRBST `shouldBe` 2++isListSpec :: Spec+isListSpec = describe "fromList/toList" $ do+ it "toList smallRBST is [1..5]" $+ toList smallRBST `shouldBe` zip ['A'..'E'] [1..5 :: Int]+ it "toList should sort by key" $+ let sort = fmap fst . toList @(RBST.RBST Int ()) . fromList . fmap (,())+ in sort [2,5,1,4,3] `shouldBe` [1..5 :: Int]++lookupSpec :: Spec+lookupSpec = describe "lookup" $ do+ it "lookup by keys are correct" $+ map (`RBST.lookup` smallRBST) ['A'..'F'] `shouldBe`+ [Just 1, Just 2, Just 3, Just 4, Just 5, Nothing]++atSpec :: Spec+atSpec = describe "at" $ do+ it "elements by indices are correct" $+ map (`RBST.at` smallRBST) [-1..5] `shouldBe`+ [Nothing, Just ('A',1), Just ('B',2), Just ('C',3), Just ('D',4), Just ('E',5), Nothing]
− test/Test/RBST/QuerySpec.hs
@@ -1,56 +0,0 @@-{-# LANGUAGE TupleSections #-}-module Test.RBST.QuerySpec (- spec- ) where--import GHC.Exts (IsList (..))-import Test.Common (TestRBST, smallRBST)-import Test.Hspec (Spec, describe, it, shouldBe)--import qualified RBST--spec :: Spec-spec = describe "Query tests" $ do- sizeSpec- heightSpec- isListSpec- lookupSpec- atSpec--sizeSpec :: Spec-sizeSpec = describe "size" $ do- it "size of empty RBST is 0" $- RBST.size (RBST.empty :: TestRBST) `shouldBe` 0- it "size of single node RBST is 1" $- RBST.size (RBST.one 'A' 0 :: TestRBST) `shouldBe` 1- it "size of smallRBST is 5" $- RBST.size smallRBST `shouldBe` 5--heightSpec :: Spec-heightSpec = describe "height" $ do- it "height of empty RBST is -1" $- RBST.height (RBST.empty :: TestRBST) `shouldBe` -1- it "height of single node RBST is 0" $- RBST.height (RBST.one 'A' 0 :: TestRBST) `shouldBe` 0- it "height of smallRBST is 2" $- RBST.height smallRBST `shouldBe` 2--isListSpec :: Spec-isListSpec = describe "fromList/toList" $ do- it "toList smallRBST is [1..5]" $- toList smallRBST `shouldBe` zip ['A'..'E'] [1..5 :: Int]- it "toList should sort by key" $- let sort = fmap fst . toList @(RBST.RBST Int ()) . fromList . fmap (,())- in sort [2,5,1,4,3] `shouldBe` [1..5 :: Int]--lookupSpec :: Spec-lookupSpec = describe "lookup" $ do- it "lookup by keys are correct" $- map (`RBST.lookup` smallRBST) ['A'..'F'] `shouldBe`- [Just 1, Just 2, Just 3, Just 4, Just 5, Nothing]--atSpec :: Spec-atSpec = describe "at" $ do- it "elements by indices are correct" $- map (`RBST.at` smallRBST) [-1..5] `shouldBe`- [Nothing, Just ('A',1), Just ('B',2), Just ('C',3), Just ('D',4), Just ('E',5), Nothing]
+ test/Test/RBST/SetOps.hs view
@@ -0,0 +1,46 @@+module Test.RBST.SetOps (+ setOpsSpec+ ) where++import Test.Hspec (Spec, describe, it)+import Test.Common (TestRBST, describedAs)+import GHC.Exts (IsList(..))++import RBST (union)+import qualified RBST++setOpsSpec :: Spec+setOpsSpec = describe "Set operations tests" $ do+ unionSpec+ intersectionSpec+ subtractionSpec+ differenceSpec++unionSpec :: Spec+unionSpec = describe "union" $ do+ it "union of two trees works" $+ tree1 `union` tree2 `describedAs` [('A', 1), ('B', 0), ('C', 3), ('D', 4)]++intersectionSpec :: Spec+intersectionSpec = describe "intersection" $ do+ it "intersection of two trees works" $+ RBST.intersection tree1 tree2 `describedAs` [('B', 2)]++subtractionSpec :: Spec+subtractionSpec = describe "subtraction" $ do+ it "subtraction of two trees works" $+ RBST.subtraction tree1 tree2 `describedAs` [('A', 1)]++differenceSpec :: Spec+differenceSpec = describe "difference" $ do+ it "difference of two trees works" $+ RBST.difference tree1 tree2 `describedAs` [('A', 1), ('C', 3), ('D', 4)]++--------------------------------------------------------+--------------------------------------------------------++tree1 :: TestRBST+tree1 = fromList [('A', 1), ('B', 2)]++tree2 :: TestRBST+tree2 = fromList [('B', 0), ('C', 3), ('D', 4)]
− test/Test/RBST/SetOpsSpec.hs
@@ -1,46 +0,0 @@-module Test.RBST.SetOpsSpec (- spec- ) where--import Test.Hspec (Spec, describe, it)-import Test.Common (TestRBST, describedAs)-import GHC.Exts (IsList(..))--import RBST (union)-import qualified RBST--spec :: Spec-spec = describe "Set operations tests" $ do- unionSpec- intersectionSpec- subtractionSpec- differenceSpec--unionSpec :: Spec-unionSpec = describe "union" $ do- it "union of two trees works" $- tree1 `union` tree2 `describedAs` [('A', 1), ('B', 0), ('C', 3), ('D', 4)]--intersectionSpec :: Spec-intersectionSpec = describe "intersection" $ do- it "intersection of two trees works" $- RBST.intersection tree1 tree2 `describedAs` [('B', 2)]--subtractionSpec :: Spec-subtractionSpec = describe "subtraction" $ do- it "subtraction of two trees works" $- RBST.subtraction tree1 tree2 `describedAs` [('A', 1)]--differenceSpec :: Spec-differenceSpec = describe "difference" $ do- it "difference of two trees works" $- RBST.difference tree1 tree2 `describedAs` [('A', 1), ('C', 3), ('D', 4)]---------------------------------------------------------------------------------------------------------------------tree1 :: TestRBST-tree1 = fromList [('A', 1), ('B', 2)]--tree2 :: TestRBST-tree2 = fromList [('B', 0), ('C', 3), ('D', 4)]
+ test/Test/RBST/Update.hs view
@@ -0,0 +1,37 @@+module Test.RBST.Update (+ updateSpec+ ) where++import Test.Hspec (Spec, describe, it, shouldBe)+import Test.Common (smallRBST, describedAs)++import qualified RBST++updateSpec :: Spec+updateSpec = describe "Modification operations tests" $ do+ insertSpec+ deleteSpec++insertSpec :: Spec+insertSpec = describe "insert" $ do+ it "insert on empty tree works" $+ RBST.insert 'A' 1 RBST.empty `describedAs` [('A', 1)]+ it "insert on test tree works" $+ RBST.insert 'F' 6 smallRBST `describedAs` [('A', 1), ('B', 2), ('C', 3), ('D', 4), ('E', 5), ('F', 6)]+ it "insert a repeated key should update the item" $+ RBST.insert 'E' 0 smallRBST `describedAs` [('A', 1), ('B', 2), ('C', 3), ('D', 4), ('E', 0)]++deleteSpec :: Spec+deleteSpec = describe "delete" $ do+ it "delete removes a key from the tree" $+ RBST.delete 'E' smallRBST `describedAs` [('A', 1), ('B', 2), ('C', 3), ('D', 4)]+ it "delete a missing key has no effect" $+ RBST.delete 'F' smallRBST `shouldBe` smallRBST+ it "delete should work on empty trees" $+ ( RBST.delete 'A'+ $ RBST.delete 'B'+ $ RBST.delete 'C'+ $ RBST.delete 'D'+ $ RBST.delete 'E'+ $ RBST.delete 'E'+ smallRBST ) `shouldBe` RBST.empty
− test/Test/RBST/UpdateSpec.hs
@@ -1,37 +0,0 @@-module Test.RBST.UpdateSpec (- spec- ) where--import Test.Hspec (Spec, describe, it, shouldBe)-import Test.Common (smallRBST, describedAs)--import qualified RBST--spec :: Spec-spec = describe "Modification operations tests" $ do- insertSpec- deleteSpec--insertSpec :: Spec-insertSpec = describe "insert" $ do- it "insert on empty tree works" $- RBST.insert 'A' 1 RBST.empty `describedAs` [('A', 1)]- it "insert on test tree works" $- RBST.insert 'F' 6 smallRBST `describedAs` [('A', 1), ('B', 2), ('C', 3), ('D', 4), ('E', 5), ('F', 6)]- it "insert a repeated key should update the item" $- RBST.insert 'E' 0 smallRBST `describedAs` [('A', 1), ('B', 2), ('C', 3), ('D', 4), ('E', 0)]--deleteSpec :: Spec-deleteSpec = describe "delete" $ do- it "delete removes a key from the tree" $- RBST.delete 'E' smallRBST `describedAs` [('A', 1), ('B', 2), ('C', 3), ('D', 4)]- it "delete a missing key has no effect" $- RBST.delete 'F' smallRBST `shouldBe` smallRBST- it "delete should work on empty trees" $- ( RBST.delete 'A'- $ RBST.delete 'B'- $ RBST.delete 'C'- $ RBST.delete 'D'- $ RBST.delete 'E'- $ RBST.delete 'E'- smallRBST ) `shouldBe` RBST.empty