range 0.1.1.1 → 0.1.2.0

raw patch · 14 files changed

+168/−86 lines, 14 filesdep +freedep ~basePVP ok

version bump matches the API change (PVP)

Dependencies added: free

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• Data/Range/Algebra.hs +43/−0
• Data/Range/Algebra/Internal.hs +30/−0
• Data/Range/Algebra/Predicate.hs +9/−0
• Data/Range/Algebra/Range.hs +10/−0
• Data/Range/Data.hs +4/−2
• Data/Range/NestedRange.hs +2/−0
• Data/Range/Range.hs +13/−12
• Data/Range/RangeInternal.hs +2/−0
• Data/Range/RangeTree.hs +12/−4
• Data/Range/RangeTreeInternal.hs +0/−15
• Data/Range/Spans.hs +2/−0
• Data/Range/Util.hs +2/−0
• Test/Range.hs +25/−44
• range.cabal +14/−9

@@ -0,0 +1,43 @@+{-# LANGUAGE Safe #-}+{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}++module Data.Range.Algebra+  ( RangeExpr+    -- ** Operations+  , const, invert, union, intersection, difference+    -- ** Evaluation+  , Algebra, RangeAlgebra(..)+  ) where++import Prelude hiding (const)++import Data.Range.Data+import Data.Range.Algebra.Internal+import Data.Range.Algebra.Range+import Data.Range.Algebra.Predicate++import Control.Monad.Free++const :: a -> RangeExpr a+const = RangeExpr . Pure++invert :: RangeExpr a -> RangeExpr a+invert = RangeExpr . Free . Invert . getFree++union :: RangeExpr a -> RangeExpr a -> RangeExpr a+union a b = RangeExpr . Free $ Union (getFree a) (getFree b)++intersection :: RangeExpr a -> RangeExpr a -> RangeExpr a+intersection a b = RangeExpr . Free $ Intersection (getFree a) (getFree b)++difference :: RangeExpr a -> RangeExpr a -> RangeExpr a+difference a b = RangeExpr . Free $ Difference (getFree a) (getFree b)++class RangeAlgebra a where+  eval :: Algebra RangeExpr a++instance (Ord a, Enum a) => RangeAlgebra [Range a] where+  eval = iter rangeAlgebra . getFree++instance RangeAlgebra (a -> Bool) where+  eval = iter predicateAlgebra . getFree

@@ -0,0 +1,30 @@+{-# LANGUAGE Safe #-}+{-# LANGUAGE DeriveFunctor #-}+{-# LANGUAGE FlexibleContexts #-}++module Data.Range.Algebra.Internal where++import Prelude hiding (const)++import Data.Range.Data+import Data.Range.RangeInternal++import Control.Monad.Free++data RangeExprF r+  = Invert r+  | Union r r+  | Intersection r r+  | Difference r r+  deriving (Show, Eq, Ord, Functor)++newtype RangeExpr a = RangeExpr { getFree :: Free RangeExprF a }+  deriving (Show, Eq, Ord, Functor)++type Algebra f a = f a -> a++rangeMergeAlgebra :: (Ord a, Enum a) => Algebra RangeExprF (RangeMerge a)+rangeMergeAlgebra (Invert a) = invertRM a+rangeMergeAlgebra (Union a b) = a `unionRangeMerges` b+rangeMergeAlgebra (Intersection a b) = a `intersectionRangeMerges` b+rangeMergeAlgebra (Difference a b) = a `intersectionRangeMerges` invertRM b

@@ -0,0 +1,9 @@+module Data.Range.Algebra.Predicate where++import Data.Range.Algebra.Internal++predicateAlgebra :: Algebra RangeExprF (a -> Bool)+predicateAlgebra (Invert f) a = not (f a)+predicateAlgebra (Union f g) a = f a || g a+predicateAlgebra (Intersection f g) a = f a && g a+predicateAlgebra (Difference f g) a = f a && not (g a)

@@ -0,0 +1,10 @@+module Data.Range.Algebra.Range where++import Data.Range.Data+import Data.Range.RangeInternal (exportRangeMerge, loadRanges)+import Data.Range.Algebra.Internal++import Control.Monad.Free++rangeAlgebra :: (Ord a, Enum a) => Algebra RangeExprF [Range a]+rangeAlgebra = exportRangeMerge . iter rangeMergeAlgebra . Free . fmap (Pure . loadRanges)

@@ -1,3 +1,5 @@+{-# LANGUAGE Safe #-}+ -- | The Data module for common data types within the code. module Data.Range.Data where @@ -13,7 +15,7 @@    deriving(Eq, Show)  -- | These are the operations that can join two disjunct lists of ranges together.-data RangeOperation +data RangeOperation    = RangeUnion         -- ^ Represents the set union operation.    | RangeIntersection  -- ^ Represents the set intersection operation.    | RangeDifference    -- ^ Represents the set difference operation.@@ -22,7 +24,7 @@ -- you can compress an entire tree of operations on ranges into a single range quickly. -- The only purpose of this tree is to allow efficient construction of range operations -- that can be evaluated as is required.-data RangeTree a +data RangeTree a    = RangeNode RangeOperation (RangeTree a) (RangeTree a) -- ^ Combine two range trees together with a single operation    | RangeNodeInvert (RangeTree a) -- ^ Invert a range tree, this is a 'not' operation.    | RangeLeaf [Range a] -- ^ A leaf with a set of ranges that are collected together.

@@ -1,3 +1,5 @@+{-# LANGUAGE Safe #-}+ -- | Nested Ranges are common in practical usage. They appear in such forms as library -- version numbers ("Version 1.4.5.6" for example). And it is very useful to be able to -- compare these ranges to one another. This module exists for the purpose of allowing

@@ -1,3 +1,5 @@+{-# LANGUAGE Safe #-}+ -- | This entire library is concerned with ranges and this module implements the absolute -- basic range functions. module Data.Range.Range (@@ -14,31 +16,30 @@    ) where  import Data.Range.Data-import Data.Range.RangeInternal import Data.Range.Util+import qualified Data.Range.Algebra as Alg  -- | Performs a set union between the two input ranges and returns the resultant set of -- ranges. union :: (Ord a, Enum a) => [Range a] -> [Range a] -> [Range a]-union a b = exportRangeMerge $ unionRangeMerges (loadRanges a) (loadRanges b)+union a b = Alg.eval $ Alg.union (Alg.const a) (Alg.const b) {-# INLINE union #-}  -- | Performs a set intersection between the two input ranges and returns the resultant set of -- ranges. intersection :: (Ord a, Enum a) => [Range a] -> [Range a] -> [Range a]-intersection a b = exportRangeMerge $ intersectionRangeMerges (loadRanges a) (loadRanges b)+intersection a b = Alg.eval $ Alg.intersection (Alg.const a) (Alg.const b) {-# INLINE intersection #-}  -- | Performs a set difference between the two input ranges and returns the resultant set of -- ranges. difference :: (Ord a, Enum a) => [Range a] -> [Range a] -> [Range a]-difference a b = exportRangeMerge $ intersectionRangeMerges a' (invertRM b')-  where a' = loadRanges a-        b' = loadRanges b+difference a b = Alg.eval $ Alg.difference (Alg.const a) (Alg.const b)+{-# INLINE difference #-}  -- | An inversion function, given a set of ranges it returns the inverse set of ranges. invert :: (Ord a, Enum a) => [Range a] -> [Range a]-invert = exportRangeMerge . invertRM . loadRanges+invert = Alg.eval . Alg.invert . Alg.const {-# INLINE invert #-}  -- | A check to see if two ranges overlap. If they do then true is returned; false@@ -69,7 +70,7 @@ -- | Given a list of ranges this function tells you if a value is in any of those ranges. -- This is especially useful for more complex ranges. inRanges :: (Ord a) => [Range a] -> a -> Bool-inRanges ranges value = any (flip inRange value) ranges+inRanges rs a = any (`inRange` a) rs  -- | When you create a range there may be overlaps in your ranges. However, for the sake -- of efficiency you probably want the list of ranges with no overlaps. The mergeRanges@@ -79,7 +80,7 @@ -- intersection then this is automatically done for you. Which means that a function like -- this is redundant: mergeRanges . intersection mergeRanges :: (Ord a, Enum a) => [Range a] -> [Range a]-mergeRanges = exportRangeMerge . loadRanges+mergeRanges = Alg.eval . Alg.const {-# INLINE mergeRanges #-}  -- | A set of ranges represents a collection of real values without actually instantiating@@ -89,9 +90,9 @@ -- like. fromRanges :: (Ord a, Enum a) => [Range a] -> [a] fromRanges = concatMap fromRange-   where -      fromRange range = case range of -         SingletonRange x -> [x] +   where+      fromRange range = case range of+         SingletonRange x -> [x]          SpanRange a b -> [a..b]          LowerBoundRange x -> iterate succ x          UpperBoundRange x -> iterate pred x

@@ -1,3 +1,5 @@+{-# LANGUAGE Safe #-}+ module Data.Range.RangeInternal where  import Data.Maybe (catMaybes)

@@ -1,3 +1,5 @@+{-# LANGUAGE Safe #-}+ -- | Internally the range library converts your ranges into an internal representation of -- multiple ranges that I call a RangeMerge. When you do multiple unions and intersections -- in a row converting to and from that data structure becomes extra work that is not@@ -5,17 +7,23 @@ -- a tree of operations in advance and then evaluate them all at once. This is not only -- useful for efficiency but for parsing too. Use RangeTree's whenever you wish to perform -- multiple operations in a row and wish for it to be as efficient as possible.-module Data.Range.RangeTree +module Data.Range.RangeTree    ( evaluate    , RangeTree(..)    , RangeOperation(..)    ) where  import Data.Range.Data-import Data.Range.RangeInternal-import Data.Range.RangeTreeInternal+import qualified Data.Range.Algebra as Alg +toExpr :: RangeTree a -> Alg.RangeExpr [Range a]+toExpr (RangeLeaf a) = Alg.const a+toExpr (RangeNodeInvert a) = Alg.invert (toExpr a)+toExpr (RangeNode RangeUnion a b) = Alg.union (toExpr a) (toExpr b)+toExpr (RangeNode RangeIntersection a b) = Alg.intersection (toExpr a) (toExpr b)+toExpr (RangeNode RangeDifference a b) = Alg.difference (toExpr a) (toExpr b)+ -- | Evaluates a Range Tree into the final set of ranges that it compresses down to. Use -- this whenever you want to finally evaluate your constructed Range Tree. evaluate :: (Ord a, Enum a) => RangeTree a -> [Range a]-evaluate = exportRangeMerge . evaluateRangeTree +evaluate = Alg.eval . toExpr

@@ -1,15 +0,0 @@-module Data.Range.RangeTreeInternal where--import Data.Range.Data-import Data.Range.RangeInternal--evaluateRangeTree :: (Ord a, Enum a) => RangeTree a -> RangeMerge a-evaluateRangeTree (RangeNode operation left right) = case operation of-   RangeUnion -> leftEval `unionRangeMerges` rightEval-   RangeIntersection -> leftEval `intersectionRangeMerges` rightEval-   RangeDifference -> leftEval `intersectionRangeMerges` (invertRM rightEval)-   where-      leftEval = evaluateRangeTree left -      rightEval = evaluateRangeTree right-evaluateRangeTree (RangeNodeInvert node) = invertRM . evaluateRangeTree $ node-evaluateRangeTree (RangeLeaf ranges) = loadRanges ranges

@@ -1,3 +1,5 @@+{-# LANGUAGE Safe #-}+ -- This module contains every function that purely performs operations on spans. module Data.Range.Spans where 

@@ -1,3 +1,5 @@+{-# LANGUAGE Safe #-}+ module Data.Range.Util where  -- This module is supposed to contain all of the functions that are required by the rest

@@ -1,3 +1,4 @@+{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-} {-# OPTIONS_GHC -fno-warn-orphans #-} -- This is only okay in test classes @@ -7,10 +8,12 @@ import Test.QuickCheck import Test.Framework.Providers.QuickCheck2 +import Control.Applicative ((<$>), (<*>)) import Control.Monad (liftM) import System.Random  import Data.Range.Range+import qualified Data.Range.Algebra as Alg  import Test.RangeMerge @@ -34,7 +37,7 @@  instance (Num a, Integral a, Ord a, Random a) => Arbitrary (SpanContains a) where    arbitrary = do-      begin <- arbitrarySizedIntegral +      begin <- arbitrarySizedIntegral       end <- arbitrarySizedIntegral `suchThat` (>= begin)       middle <- choose (begin, end)       return $ SpanContains (begin, end) middle@@ -53,7 +56,7 @@    ]  instance (Num a, Integral a, Ord a, Enum a) => Arbitrary (Range a) where-   arbitrary = oneof +   arbitrary = oneof       [ generateSingleton       , generateSpan       , generateLowerBound@@ -63,7 +66,7 @@       where          generateSingleton = liftM SingletonRange arbitrarySizedIntegral          generateSpan = do-            first <- arbitrarySizedIntegral +            first <- arbitrarySizedIntegral             second <- arbitrarySizedIntegral `suchThat` (> first)             return $ SpanRange first second          generateLowerBound = liftM LowerBoundRange arbitrarySizedIntegral@@ -79,59 +82,37 @@ -- ((1, 3) intersection (3, 4)) union (3, 4) => (3, 4)  prop_in_range_out_of_range_after_invert :: (Integer, [Range Integer]) -> Bool-prop_in_range_out_of_range_after_invert (point, ranges) = +prop_in_range_out_of_range_after_invert (point, ranges) =    (inRanges ranges point) /= (inRanges (invert ranges) point)  test_ranges_invert = testGroup "invert function for ranges"    [ testProperty "element in range is now out of range after invert" prop_in_range_out_of_range_after_invert    ] -prop_elements_before_union_or_true :: ([Integer], [Range Integer], [Range Integer]) -> Bool-prop_elements_before_union_or_true (points, a, b) = actual == expected-   where-      before_a = map (inRanges a) points-      before_b = map (inRanges b) points-      unionRanges = a `union` b-      actual = map (inRanges unionRanges) points-      expected = zipWith (||) before_a before_b--prop_elements_before_intersection_and_true :: ([Integer], [Range Integer], [Range Integer]) -> Bool-prop_elements_before_intersection_and_true (points, a, b) = actual == expected-   where-      before_a = map (inRanges a) points-      before_b = map (inRanges b) points-      intersectedRanges = a `intersection` b-      actual = map (inRanges intersectedRanges) points-      expected = zipWith (&&) before_a before_b--prop_elements_before_difference_and_not_true :: ([Integer], [Range Integer], [Range Integer]) -> Bool-prop_elements_before_difference_and_not_true (points, a, b) = actual == expected-   where-      before_a = map (inRanges a) points-      before_b = map (inRanges b) points-      diffedRanges = a `difference` b-      actual = map (inRanges diffedRanges) points-      expected = zipWith (&&) before_a $ map not before_b--test_union = testGroup "union function properties"-   [ testProperty "Unions from before OR together and continue to work" prop_elements_before_union_or_true-   ]+instance (Num a, Integral a, Ord a, Enum a) => Arbitrary (Alg.RangeExpr [Range a]) where+  arbitrary = frequency+    [ (3, Alg.const <$> arbitrary)+    , (1, Alg.invert <$> arbitrary)+    , (1, Alg.union <$> arbitrary <*> arbitrary)+    , (1, Alg.intersection <$> arbitrary <*> arbitrary)+    , (1, Alg.difference <$> arbitrary <*> arbitrary)+    ] -test_intersection = testGroup "intersection function properties"-   [ testProperty "Intersection before AND's to after" prop_elements_before_intersection_and_true-   ]+prop_equivalence_eval_and_evalPredicate :: ([Integer], Alg.RangeExpr [Range Integer]) -> Bool+prop_equivalence_eval_and_evalPredicate (points, expr) = actual == expected+  where+      actual = map (inRanges $ Alg.eval expr) points+      expected = map (Alg.eval $ fmap inRanges expr) points -test_difference = testGroup "difference function properties"-   [ testProperty "Difference before AND/NOT's to after" prop_elements_before_difference_and_not_true+test_algebra_equivalence = testGroup "algebra equivalence"+   [ testProperty "eval and evalPredicate" prop_equivalence_eval_and_evalPredicate    ]  --tests :: [Test]-tests = -   [ tests_inRange +tests =+   [ tests_inRange    , test_ranges_invert-   , test_union-   , test_intersection-   , test_difference+   , test_algebra_equivalence    ]    ++ rangeMergeTestCases 

@@ -4,13 +4,13 @@ -- The name of the package. name:                range --- The package version.  See the Haskell package versioning policy (PVP) +-- The package version.  See the Haskell package versioning policy (PVP) -- for standards guiding when and how versions should be incremented. -- http://www.haskell.org/haskellwiki/Package_versioning_policy -- PVP summary:      +-+------- breaking API changes --                   | | +----- non-breaking API additions --                   | | | +--- code changes with no API change-version:             0.1.1.1+version:             0.1.2.0  -- A short (one-line) description of the package. synopsis:            This has a bunch of code for specifying and managing ranges in your code.@@ -33,12 +33,12 @@ -- The package author(s). author:              Robert Massaioli --- An email address to which users can send suggestions, bug reports, and +-- An email address to which users can send suggestions, bug reports, and -- patches. maintainer:          robertmassaioli@gmail.com  -- A copyright notice.--- copyright:           +-- copyright:  category:            Data @@ -54,22 +54,26 @@                       , Data.Range.NestedRange                       , Data.Range.RangeTree                       , Data.Range.Parser-  +                      , Data.Range.Algebra+   -- Modules included in this library but not exported.   other-modules:  Data.Range.Data                   , Data.Range.RangeInternal-                  , Data.Range.RangeTreeInternal                   , Data.Range.Spans                   , Data.Range.Util+                  , Data.Range.Algebra.Internal+                  , Data.Range.Algebra.Range+                  , Data.Range.Algebra.Predicate -  +   -- Other library packages from which modules are imported.   build-depends:  base >= 4.5 && < 5                   , parsec >= 3+                  , free >=4.12    ghc-options: -Wall-   -  ++ Test-Suite test-range    type:       exitcode-stdio-1.0    main-is: Test/Range.hs@@ -80,5 +84,6 @@                   , test-framework-quickcheck2  >= 0.2 && < 0.4                   , test-framework              >= 0.4 && < 0.9                   , random                      >= 1.0+                  , free                        >= 4.12                   , range    ghc-options: -rtsopts -Wall -fno-enable-rewrite-rules