packages feed

range-set-list 0.0.3 → 0.0.4

raw patch · 8 files changed

+325/−227 lines, 8 filesdep ~base

Dependency ranges changed: base

Files

+ .gitignore view
@@ -0,0 +1,1 @@+dist/
+ .travis.yml view
@@ -0,0 +1,12 @@+language: haskell+ghc:+  - 7.4+  - 7.6+  - 7.8++before_install:+  - cabal install packdeps++script:+  - cabal test --show-details=always+  - packdeps range-set-list.cabal
+ CHANGELOG.md view
@@ -0,0 +1,15 @@+### 0.0.4++- Complement sets (require `Bounded`), `full` and `complement`++### 0.0.3++- Dependencies update++### 0.0.2++- More quickcheck properties++### 0.0.1++- Initial release
− Data/RangeSet/List.hs 
@@ -1,209 +0,0 @@-{- |-Module      :  Data.RangeSet.List-Description :  A trivial implementation of range sets-Copyright   :  (c) Oleg Grenrus 2014-License     :  MIT--Maintainer  :  oleg.grenrus@iki.fi-Stability   :  experimental-Portability :  non-portable (tested with GHC only)--A trivial implementation of range sets.--This module is intended to be imported qualified, to avoid name-clashes with Prelude functions, e.g.-->  import Data.RangeSet.List (RSet)->  import qualified Data.RangeSet.List as RSet--The implementation of 'RSet' is based on /list/.--Compared to 'Data.Set', this module imposes also 'Enum' restriction for many functions.-We must be able to identify consecutive elements to be able to /glue/ and /split/ ranges properly.--The implementation assumes that--> x < succ x-> pred x < x--and there aren't elements in between (not true for 'Float' and 'Double').-Also 'succ' and 'pred' are never called for largest or smallest value respectively.--}--module Data.RangeSet.List (-  -- * Range set type-  RSet--  -- * Operators-  , (\\)--  -- * Query-  , null-  , member-  , notMember--  -- * Construction-  , empty-  , singleton-  , singletonRange-  , insert-  , insertRange-  , delete-  , deleteRange--  -- * Combine-  , union-  , difference-  , intersection--  -- * Conversion-  , elems-  , toList-  , fromList-  , toRangeList-  , fromRangeList--  ) where--import Prelude hiding (filter,foldl,foldr,null,map)-import qualified Prelude--import Data.Monoid (Monoid(..))---- | Internally set is represented as sorted list of distinct inclusive ranges.-newtype RSet a = RSet [(a, a)]-  deriving (Eq, Ord)--instance Show a => Show (RSet a) where-  show (RSet xs) = "fromRangeList " ++ show xs--instance (Ord a, Enum a) => Monoid (RSet a) where-    mempty  = empty-    mappend = union--{- Operators -}-infixl 9 \\ ------ | /O(n+m)/. See 'difference'.-(\\) :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a-m1 \\ m2 = difference m1 m2--{- Query -}---- | /O(1)/. Is this the empty set?-null :: RSet a -> Bool-null = Prelude.null . toRangeList---- | /O(n)/. Is the element in the set?-member :: (Ord a, Enum a) => a -> RSet a -> Bool-member x (RSet xs) = any f $ takeWhile g xs-  where f (a, b) = a <= x && x <= b-        g (a,_) = a <= x---- | /O(n)/. Is the element not in the set?-notMember :: (Ord a, Enum a) => a -> RSet a -> Bool-notMember a r = not $ member a r--{- Construction -}---- | /O(1)/. The empty set.-empty :: RSet a-empty = RSet []---- | /O(1)/. Create a singleton set.-singleton :: a -> RSet a-singleton x = RSet [(x, x)]---- | /O(1)/. Create a continuos range set.-singletonRange :: Ord a => (a, a) -> RSet a-singletonRange (x, y) | x > y     = empty-                      | otherwise = RSet [(x, y)]--{- Construction -}---- | /O(n)/. Insert an element in a set.-insert :: (Ord a, Enum a) => a -> RSet a -> RSet a-insert x set = insertRange (x, x) set---- | /O(n)/. Insert a continuos range in a set.-insertRange :: (Ord a, Enum a) => (a, a) -> RSet a -> RSet a-insertRange r@(x, y) set@(RSet xs)-  | x > y      = set-  | otherwise  = RSet $ insertRange' r xs---- There are three possibilities we consider, when inserting into non-empty set:--- * discretely less--- * discretely more--- * other-insertRange' :: (Ord a, Enum a) => (a, a) -> [(a, a)] -> [(a, a)]-insertRange' r        []  = [r]-insertRange' r@(x, y) set@(s@(u, v) : xs)-  | y < u && succ y /= u  = r : set-  | v < x && succ v /= x  = s : insertRange' r xs-  | otherwise             = insertRange' (min x u, max y v) xs---- | /O(n). Delete an element from a set.-delete :: (Ord a, Enum a) => a -> RSet a -> RSet a-delete x set = deleteRange (x, x) set---- | /O(n). Delete a continuos range from a set.-deleteRange :: (Ord a, Enum a) => (a, a) -> RSet a -> RSet a-deleteRange r@(x, y) set@(RSet xs)-  | x > y      = set-  | otherwise  = RSet $ deleteRange' r xs---- There are 6 possibilities we consider, when deleting from non-empty set:--- * less--- * more--- * strictly inside (splits)--- * overlapping less-edge--- * overlapping more-edge--- * stricly larger------ TODO: is there simpler rules, with less cases-deleteRange' :: (Ord a, Enum a) => (a, a) -> [(a, a)] -> [(a, a)]-deleteRange' _        []  = []-deleteRange' r@(x, y) set@(s@(u, v) : xs)-  | y < u                 = set-  | v < x                 = s : deleteRange' r xs-  | u < x && y < v        = (u, pred x) : (succ y, v) : xs-  | y < v                 = (succ y, v) : xs-  | u < x                 = (u, pred x) : deleteRange' r xs-  | otherwise             = deleteRange' r xs--{- Combination -}---- | /O(n*m)/. The union of two sets.-union :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a-union set (RSet xs) = Prelude.foldr insertRange set xs---- | /O(n*m)/. Difference of two sets.-difference :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a-difference set (RSet xs) = Prelude.foldr deleteRange set xs---- | /O(n*m)/. The intersection of two sets.-intersection :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a-intersection a b = a \\ (a \\ b)--{- Conversion -}---- | /O(n*r)/. Convert the set to a list of elements. /r/ is the size of longest range.-elems :: Enum a => RSet a -> [a]-elems = toList---- | /O(n*r)/. Convert the set to a list of elements. /r/ is the size of longest range.-toList :: Enum a => RSet a -> [a]-toList (RSet xs) = concatMap (uncurry enumFromTo) xs---- | /O(n^2)/. Create a set from a list of elements.-fromList :: (Ord a, Enum a) => [a] -> RSet a-fromList = fromRangeList . Prelude.map f-  where f a = (a, a)---- | /O(1)/. Convert the set to a list of range pairs.-toRangeList :: RSet a -> [(a, a)]-toRangeList (RSet xs) = xs---- | /O(n^2)/. Create a set from a list of range pairs.-fromRangeList :: (Ord a, Enum a) => [(a, a)] -> RSet a-fromRangeList = Prelude.foldr insertRange empty
+ README.md view
@@ -0,0 +1,38 @@+# range-set-list++[![Build Status](https://travis-ci.org/phadej/range-set-list.svg?branch=travis-expr)](https://travis-ci.org/phadej/range-set-list)++A trivial implementation of range sets.++You can find the package (and it's documentation) on [hackage](http://hackage.haskell.org/package/range-set-list).++This module is intended to be imported qualified, to avoid name+clashes with Prelude functions, e.g.++```haskell+import Data.RangeSet.List (RSet)+import qualified Data.RangeSet.List as RSet+```++The implementation of `RSet` is based on _list_.++Compared to [`Data.Set`](http://hackage.haskell.org/package/containers-0.5.4.0/docs/Data-Set.html),+this module imposes also [`Enum`](http://hackage.haskell.org/package/base-4.6.0.1/docs/Prelude.html#t:Enum)+restriction for many functions.+We must be able to identify consecutive elements to be able to _glue_ and _split_ ranges properly.++The implementation assumes that++```haskell+x < succ x+pred x < x+```++and there aren't elements in between (not true for `Float` and `Double`).+Also `succ` and `pred` are never called for largest or smallest value respectively.++## Changelog++- 0.0.3 Bump tasty and QuickCheck versions+- 0.0.2 More properties &amp; test coverage+- 0.0.1 Initial release
range-set-list.cabal view
@@ -1,5 +1,5 @@ name:                range-set-list-version:             0.0.3+version:             0.0.4 synopsis:            Memory efficient sets with continuous ranges of elements. description:         Memory efficient sets with continuous ranges of elements. List based implementation. Interface mimics "Data.Set" interface where possible. homepage:            https://github.com/phadej/range-set-list@@ -13,17 +13,27 @@ category:            Data Structures build-type:          Simple cabal-version:       >=1.10+extra-source-files:  .gitignore+                     .travis.yml+                     README.md+                     CHANGELOG.md  flag optimized   default: True  library   exposed-modules:     Data.RangeSet.List-  build-depends:       base >=4.6 && <5+  build-depends:       base >=4.5 && <5   default-language:    Haskell98+  hs-source-dirs:      src   ghc-options:         -Wall+                       -fwarn-tabs   if flag(optimized)-    ghc-options:       -funbox-strict-fields -O2+    ghc-options:       -funbox-strict-fields+                       -O2+                       -fspec-constr-count=6+                       -fmax-simplifier-iterations=10+                       -fdicts-cheap  test-suite test   default-language:    Haskell2010@@ -31,7 +41,7 @@   hs-source-dirs:      tests   main-is:             Tests.hs   ghc-options:         -Wall-  build-depends:       base >=4.6 && <5,+  build-depends:       base >=4.5 && <5,                        containers >= 0.5 && <0.6,                        tasty >= 0.8,                        tasty-quickcheck == 0.8.0.3,
+ src/Data/RangeSet/List.hs view
@@ -0,0 +1,222 @@+{- |+Module      :  Data.RangeSet.List+Description :  A trivial implementation of range sets+Copyright   :  (c) Oleg Grenrus 2014+License     :  MIT++Maintainer  :  oleg.grenrus@iki.fi+Stability   :  experimental+Portability :  non-portable (tested with GHC only)++A trivial implementation of range sets.++This module is intended to be imported qualified, to avoid name+clashes with Prelude functions, e.g.++>  import Data.RangeSet.List (RSet)+>  import qualified Data.RangeSet.List as RSet++The implementation of 'RSet' is based on /list/.++Compared to 'Data.Set', this module imposes also 'Enum' restriction for many functions.+We must be able to identify consecutive elements to be able to /glue/ and /split/ ranges properly.++The implementation assumes that++> x < succ x+> pred x < x++and there aren't elements in between (not true for 'Float' and 'Double').+Also 'succ' and 'pred' are never called for largest or smallest value respectively.+-}++module Data.RangeSet.List (+  -- * Range set type+  RSet++  -- * Operators+  , (\\)++  -- * Query+  , null+  , member+  , notMember++  -- * Construction+  , empty+  , singleton+  , singletonRange+  , insert+  , insertRange+  , delete+  , deleteRange++  -- * Combine+  , union+  , difference+  , intersection++  -- * Complement+  , complement++  -- * Conversion+  , elems+  , toList+  , fromList+  , toRangeList+  , fromRangeList++  ) where++import Prelude hiding (filter,foldl,foldr,null,map)+import qualified Prelude++import Data.Monoid (Monoid(..))++-- | Internally set is represented as sorted list of distinct inclusive ranges.+newtype RSet a = RSet [(a, a)]+  deriving (Eq, Ord)++instance Show a => Show (RSet a) where+  show (RSet xs) = "fromRangeList " ++ show xs++instance (Ord a, Enum a) => Monoid (RSet a) where+    mempty  = empty+    mappend = union++{- Operators -}+infixl 9 \\ --++-- | /O(n+m)/. See 'difference'.+(\\) :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a+m1 \\ m2 = difference m1 m2++{- Query -}++-- | /O(1)/. Is this the empty set?+null :: RSet a -> Bool+null = Prelude.null . toRangeList++-- | /O(n)/. Is the element in the set?+member :: (Ord a, Enum a) => a -> RSet a -> Bool+member x (RSet xs) = any f $ takeWhile g xs+  where f (a, b) = a <= x && x <= b+        g (a,_) = a <= x++-- | /O(n)/. Is the element not in the set?+notMember :: (Ord a, Enum a) => a -> RSet a -> Bool+notMember a r = not $ member a r++{- Construction -}++-- | /O(1)/. The empty set.+empty :: RSet a+empty = RSet []++-- | /O(1)/. The full set.+full :: Bounded a => RSet a+full = RSet [(minBound, maxBound)]++-- | /O(1)/. Create a singleton set.+singleton :: a -> RSet a+singleton x = RSet [(x, x)]++-- | /O(1)/. Create a continuos range set.+singletonRange :: Ord a => (a, a) -> RSet a+singletonRange (x, y) | x > y     = empty+                      | otherwise = RSet [(x, y)]++{- Construction -}++-- | /O(n)/. Insert an element in a set.+insert :: (Ord a, Enum a) => a -> RSet a -> RSet a+insert x = insertRange (x, x)++-- | /O(n)/. Insert a continuos range in a set.+insertRange :: (Ord a, Enum a) => (a, a) -> RSet a -> RSet a+insertRange r@(x, y) set@(RSet xs)+  | x > y      = set+  | otherwise  = RSet $ insertRange' r xs++-- There are three possibilities we consider, when inserting into non-empty set:+-- * discretely less+-- * discretely more+-- * other+insertRange' :: (Ord a, Enum a) => (a, a) -> [(a, a)] -> [(a, a)]+insertRange' r        []  = [r]+insertRange' r@(x, y) set@(s@(u, v) : xs)+  | y < u && succ y /= u  = r : set+  | v < x && succ v /= x  = s : insertRange' r xs+  | otherwise             = insertRange' (min x u, max y v) xs++-- | /O(n). Delete an element from a set.+delete :: (Ord a, Enum a) => a -> RSet a -> RSet a+delete x = deleteRange (x, x)++-- | /O(n). Delete a continuos range from a set.+deleteRange :: (Ord a, Enum a) => (a, a) -> RSet a -> RSet a+deleteRange r@(x, y) set@(RSet xs)+  | x > y      = set+  | otherwise  = RSet $ deleteRange' r xs++-- There are 6 possibilities we consider, when deleting from non-empty set:+-- * less+-- * more+-- * strictly inside (splits)+-- * overlapping less-edge+-- * overlapping more-edge+-- * stricly larger+--+-- TODO: is there simpler rules, with less cases+deleteRange' :: (Ord a, Enum a) => (a, a) -> [(a, a)] -> [(a, a)]+deleteRange' _        []  = []+deleteRange' r@(x, y) set@(s@(u, v) : xs)+  | y < u                 = set+  | v < x                 = s : deleteRange' r xs+  | u < x && y < v        = (u, pred x) : (succ y, v) : xs+  | y < v                 = (succ y, v) : xs+  | u < x                 = (u, pred x) : deleteRange' r xs+  | otherwise             = deleteRange' r xs++{- Combination -}++-- | /O(n*m)/. The union of two sets.+union :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a+union set (RSet xs) = Prelude.foldr insertRange set xs++-- | /O(n*m)/. Difference of two sets.+difference :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a+difference set (RSet xs) = Prelude.foldr deleteRange set xs++-- | /O(n*m)/. The intersection of two sets.+intersection :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a+intersection a b = a \\ (a \\ b)++{- Complement -}++-- | /O(n)/. Complement of the set.+complement :: (Ord a, Enum a, Bounded a) => RSet a -> RSet a+complement a = full `difference` a++{- Conversion -}++-- | /O(n*r)/. Convert the set to a list of elements. /r/ is the size of longest range.+elems :: Enum a => RSet a -> [a]+elems = toList++-- | /O(n*r)/. Convert the set to a list of elements. /r/ is the size of longest range.+toList :: Enum a => RSet a -> [a]+toList (RSet xs) = concatMap (uncurry enumFromTo) xs++-- | /O(n^2)/. Create a set from a list of elements.+fromList :: (Ord a, Enum a) => [a] -> RSet a+fromList = fromRangeList . Prelude.map f+  where f a = (a, a)++-- | /O(1)/. Convert the set to a list of range pairs.+toRangeList :: RSet a -> [(a, a)]+toRangeList (RSet xs) = xs++-- | /O(n^2)/. Create a set from a list of range pairs.+fromRangeList :: (Ord a, Enum a) => [(a, a)] -> RSet a+fromRangeList = Prelude.foldr insertRange empty
tests/Tests.hs view
@@ -64,17 +64,17 @@ toRSet (ADifference a b)    = RSet.difference (toRSet a) (toRSet b) toRSet (AIntersection a b)  = RSet.intersection (toRSet a) (toRSet b) -elementsProp :: SetAction Int -> Bool-elementsProp seta = Set.elems (toSet seta) == RSet.elems (toRSet seta)+elementsProp :: SetAction Int -> Property+elementsProp seta = Set.elems (toSet seta) === RSet.elems (toRSet seta) -nullProp :: SetAction Int -> Bool-nullProp seta = Set.null (toSet seta) == RSet.null (toRSet seta)+nullProp :: SetAction Int -> Property+nullProp seta = Set.null (toSet seta) === RSet.null (toRSet seta) -memberProp :: Int -> SetAction Int -> Bool-memberProp x seta = Set.member x (toSet seta) == RSet.member x (toRSet seta)+memberProp :: Int -> SetAction Int -> Property+memberProp x seta = Set.member x (toSet seta) === RSet.member x (toRSet seta) -notMemberProp :: Int -> SetAction Int -> Bool-notMemberProp x seta = Set.notMember x (toSet seta) == RSet.notMember x (toRSet seta)+notMemberProp :: Int -> SetAction Int -> Property+notMemberProp x seta = Set.notMember x (toSet seta) === RSet.notMember x (toRSet seta)  data RSetAction a = RAEmpty                   | RASingleton (a, a)@@ -100,7 +100,7 @@                                  , RAIntersection <$> arbitrary2 <*> arbitrary2                                  ]                               where arbitrary1 = arbitrary' $ n - 1-                                    arbitrary2 = arbitrary' $ n `div` 2  +                                    arbitrary2 = arbitrary' $ n `div` 2  rangeToSet :: (Enum a, Ord a) => RSetAction a -> Set a rangeToSet RAEmpty               = Set.empty@@ -122,8 +122,8 @@ rangeToRSet (RADifference a b)    = RSet.difference (rangeToRSet a) (rangeToRSet b) rangeToRSet (RAIntersection a b)  = RSet.intersection (rangeToRSet a) (rangeToRSet b) -rangeProp :: RSetAction Int8 -> Bool-rangeProp seta = Set.elems (rangeToSet seta) == RSet.elems (rangeToRSet seta)+rangeProp :: RSetAction Int8 -> Property+rangeProp seta = Set.elems (rangeToSet seta) === RSet.elems (rangeToRSet seta)  ordered :: Ord a => [(a,a)] -> Bool ordered rs = all lt $ zip rs (tail rs)@@ -138,12 +138,20 @@ orderedProp setAction = ordered rs && pairOrdered rs   where rs = RSet.toRangeList . rangeToRSet $ setAction +-- Complement laws+complementProps :: TestTree+complementProps = testGroup "complement"+  [ QC.testProperty "definition" (\a e -> RSet.member e (rs a) === RSet.notMember e (RSet.complement (rs a)))+  , QC.testProperty "involutive" (\a -> rs a === RSet.complement (RSet.complement (rs a)))+  ]+  where rs = rangeToRSet :: RSetAction Int -> RSet Int+ -- Monoid laws monoidLaws :: TestTree monoidLaws = testGroup "MonoidLaws"-  [ QC.testProperty "left identity"   (\a -> rs a == mempty <> rs a)-  , QC.testProperty "right identity"  (\a -> rs a == rs a <> mempty)-  , QC.testProperty "associativity"   (\a b c -> rs a <> (rs b <> rs c) == (rs a <> rs b) <> rs c)+  [ QC.testProperty "left identity"   (\a -> rs a === mempty <> rs a)+  , QC.testProperty "right identity"  (\a -> rs a === rs a <> mempty)+  , QC.testProperty "associativity"   (\a b c -> rs a <> (rs b <> rs c) === (rs a <> rs b) <> rs c)   ]   where rs = rangeToRSet :: RSetAction Int -> RSet Int @@ -156,5 +164,6 @@   , QC.testProperty "notMember operation similar" notMemberProp   , QC.testProperty "range operations similar" rangeProp   , QC.testProperty "ranges remain ordered" orderedProp+  , complementProps   , monoidLaws   ]