Ranged-sets (empty) → 0.1.0
raw patch · 17 files changed
+4904/−0 lines, 17 filesdep +basebuild-type:Customsetup-changed
Dependencies added: base
Files
- CHANGES.txt +37/−0
- Data/Ranged.hs +10/−0
- Data/Ranged/Boundaries.hs +170/−0
- Data/Ranged/RangedSet.hs +539/−0
- Data/Ranged/Ranges.hs +294/−0
- Doc/Data-Ranged-Boundaries.html +681/−0
- Doc/Data-Ranged-RangedSet.html +1456/−0
- Doc/Data-Ranged-Ranges.html +838/−0
- Doc/Data-Ranged.html +106/−0
- Doc/doc-index.html +454/−0
- Doc/index.html +120/−0
- INSTALL.txt +14/−0
- LICENSE.txt +30/−0
- README.txt +119/−0
- Ranged-sets.cabal +17/−0
- Setup.hs +6/−0
- TODO.txt +13/−0
+ CHANGES.txt view
@@ -0,0 +1,37 @@+Version 0.0.4+-------------++Added Monoid instances and singleton ranges, courtesy of Jean-Philippe+Bernardy.++Version 0.0.3+-------------++Removed support for infinite sets. They sometimes still work, but generally +are more trouble than they are worth. There is no simple set of rules for+client applications to guarantee termination.++Replaced the "deriving" clause for the Range type with instance declarations.+Empty ranges created with different bounds will now test as equal. All+empty ranges now compare as less than all non-empty ranges. "show" returns+a string such as "3.5 < x <= 4.6", or "x < 23".++Removed "maybeRange".++Changed "rangeIntersection" to return a "Range" instead of a "Maybe Range".+If the intersection is empty then it returns an empty range instead of+Nothing.++Renamed "rangeEmpty" to "rangeIsEmpty" for consistency with "rSetIsEmpty"++Added "emptyRange" and "fullRange"++++Version 0.0.2+-------------++Fixed the infinite loop with infinite sets, at least as far as possible.+Added lots more QuickCheck properties.+Added subset predicates.+Added infix operators.
+ Data/Ranged.hs view
@@ -0,0 +1,10 @@++module Data.Ranged (+ module Data.Ranged.Boundaries,+ module Data.Ranged.Ranges,+ module Data.Ranged.RangedSet+) where++import Data.Ranged.Boundaries+import Data.Ranged.Ranges+import Data.Ranged.RangedSet
+ Data/Ranged/Boundaries.hs view
@@ -0,0 +1,170 @@+-----------------------------------------------------------------------------+-- |+-- Module : Data.Ranged.Boundaries+-- Copyright : (c) Paul Johnson 2006+-- License : BSD-style+-- Maintainer : paul@cogito.org.uk+-- Stability : experimental+-- Portability : portable+--+-----------------------------------------------------------------------------++++module Data.Ranged.Boundaries (+ DiscreteOrdered,+ adjacent,+ enumAdjacent,+ boundedAdjacent,+ Boundary (..),+ above,+ (/>/)+) where++import Data.Ratio+import Test.QuickCheck++infix 4 />/++{- | +Distinguish between dense and sparse ordered types. A dense type is +one in which any two values @v1 < v2@ have a third value @v3@ such that +@v1 < v3 < v2@.++In theory the floating types are dense, although in practice they can only have+finitely many values. This class treats them as dense.++Tuples up to 4 members are declared as instances. Larger tuples may be added+if necessary.++This approach was suggested by Ben Rudiak-Gould on comp.lang.functional.+-}+class Ord a => DiscreteOrdered a where+ -- | Two values @x@ and @y@ are adjacent if @x < y@ and there does not + -- exist a third value between them. Always @False@ for dense types.+ adjacent :: a -> a -> Bool++instance DiscreteOrdered Bool where adjacent = boundedAdjacent+instance DiscreteOrdered Ordering where adjacent = boundedAdjacent+instance DiscreteOrdered Char where adjacent = boundedAdjacent+instance DiscreteOrdered Int where adjacent = boundedAdjacent+instance DiscreteOrdered Integer where adjacent = enumAdjacent+instance Integral a => DiscreteOrdered (Ratio a)+ where adjacent _ _ = False+instance DiscreteOrdered Float where adjacent _ _ = False+instance DiscreteOrdered Double where adjacent _ _ = False+instance Ord a => DiscreteOrdered [a] where adjacent _ _ = False+instance (Ord a, DiscreteOrdered b) => DiscreteOrdered (a, b)+ where adjacent (x1, x2) (y1, y2) = (x1 == y1) && adjacent x2 y2+instance (Ord a, Ord b, DiscreteOrdered c) => DiscreteOrdered (a, b, c)+ where + adjacent (x1, x2, x3) (y1, y2, y3) =+ (x1 == y1) && (x2 == y2) && adjacent x3 y3+instance (Ord a, Ord b, Ord c, DiscreteOrdered d) => + DiscreteOrdered (a, b, c, d)+ where + adjacent (x1, x2, x3, x4) (y1, y2, y3, y4) =+ (x1 == y1) && (x2 == y2) && (x3 == y3) && adjacent x4 y4+ +-- | Check adjacency for sparse enumerated types (i.e. where there+-- is no value between @x@ and @succ x@). Use as the definition of+-- "adjacent" for most enumerated types.+enumAdjacent :: (Ord a, Enum a) => a -> a -> Bool+enumAdjacent x y = (succ x == y) + +-- | Check adjacency, allowing for case where x = maxBound. Use as the+-- definition of "adjacent" for bounded enumerated types such as Int and Char.+boundedAdjacent :: (Ord a, Enum a) => a -> a -> Bool+boundedAdjacent x y = if x < y then succ x == y else False+ + +{- |+A Boundary is a division of an ordered type into values above +and below the boundary. No value can sit on a boundary.++Known bug: for Bounded types ++* @BoundaryAbove maxBound < BoundaryAboveAll@++* @BoundaryBelow minBound > BoundaryBelowAll@+ +This is incorrect because there are no possible values in +between the left and right sides of these inequalities. +-}++data Boundary a =+ -- | The argument is the highest value below the boundary.+ BoundaryAbove a | + -- | The argument is the lowest value above the boundary.+ BoundaryBelow a |+ -- | The boundary above all values.+ BoundaryAboveAll | + -- | The boundary below all values.+ BoundaryBelowAll+ deriving (Show)++-- | True if the value is above the boundary, false otherwise.+above :: Ord v => Boundary v -> v -> Bool+above (BoundaryAbove b) v = v > b+above (BoundaryBelow b) v = v >= b+above BoundaryAboveAll _ = False+above BoundaryBelowAll _ = True+ +-- | Same as 'above', but with the arguments reversed for more intuitive infix+-- usage. +(/>/) :: Ord v => v -> Boundary v -> Bool+(/>/) = flip above+ +instance (DiscreteOrdered a) => Eq (Boundary a) where+ b1 == b2 = compare b1 b2 == EQ++instance (DiscreteOrdered a) => Ord (Boundary a) where+ -- Comparison alogrithm based on brute force and ignorance: + -- enumerate all combinations.+ + compare boundary1 boundary2 =+ case boundary1 of+ BoundaryAbove b1 ->+ case boundary2 of+ BoundaryAbove b2 -> compare b1 b2+ BoundaryBelow b2 -> + if b1 < b2 + then + if adjacent b1 b2 then EQ else LT + else GT+ BoundaryAboveAll -> LT+ BoundaryBelowAll -> GT+ BoundaryBelow b1 ->+ case boundary2 of+ BoundaryAbove b2 -> + if b1 > b2 + then + if adjacent b2 b1 then EQ else GT + else LT+ BoundaryBelow b2 -> compare b1 b2+ BoundaryAboveAll -> LT+ BoundaryBelowAll -> GT+ BoundaryAboveAll ->+ case boundary2 of+ BoundaryAboveAll -> EQ+ otherwise -> GT+ BoundaryBelowAll ->+ case boundary2 of+ BoundaryBelowAll -> EQ+ otherwise -> LT++-- QuickCheck Generator++instance Arbitrary a => Arbitrary (Boundary a) where+ arbitrary = frequency [+ (1, return BoundaryAboveAll),+ (1, return BoundaryBelowAll),+ (18, do+ v <- arbitrary+ oneof [return $ BoundaryAbove v, return $ BoundaryBelow v]+ )]+ coarbitrary BoundaryBelowAll = variant 0 + coarbitrary BoundaryAboveAll = variant 1+ coarbitrary (BoundaryBelow v) = variant 2 . coarbitrary v+ coarbitrary (BoundaryAbove v) = variant 3 . coarbitrary v+
+ Data/Ranged/RangedSet.hs view
@@ -0,0 +1,539 @@+module Data.Ranged.RangedSet ( + -- ** Ranged Set Type+ RSet,+ rSetRanges,+ -- ** Ranged Set construction functions and their Preconditions+ makeRangedSet,+ unsafeRangedSet,+ validRangeList,+ normaliseRangeList,+ rSingleton,+ -- ** Predicates+ rSetIsEmpty,+ (-?-), rSetHas, + (-<=-), rSetIsSubset,+ (-<-), rSetIsSubsetStrict,+ -- ** Set Operations+ (-\/-), rSetUnion, + (-/\-), rSetIntersection, + (-!-), rSetDifference,+ rSetNegation,+ -- ** Useful Sets+ rSetEmpty,+ rSetFull,+ rSetUnfold+ + -- ** QuickCheck Properties+ + -- *** Construction+ -- $ConstructionProperties+ + -- *** Basic Operations+ -- $BasicOperationProperties+ + -- *** Some Identities and Inequalities+ -- $SomeIdentitiesAndInequalities+) where++import Data.Ranged.Boundaries+import Data.Ranged.Ranges+import Data.Monoid++import Data.List+import Test.QuickCheck++infixl 7 -/\-+infixl 6 -\/-, -!-+infixl 5 -<=-, -<-, -?-++-- | An RSet (for Ranged Set) is a list of ranges. The ranges must be sorted+-- and not overlap.++newtype DiscreteOrdered v => RSet v = RSet {rSetRanges :: [Range v]}+ deriving (Eq, Show)++instance DiscreteOrdered a => Monoid (RSet a) where+ mappend = rSetUnion+ mempty = rSetEmpty++-- | Determine if the ranges in the list are both in order and non-overlapping.+-- If so then they are suitable input for the unsafeRangedSet function.+validRangeList :: DiscreteOrdered v => [Range v] -> Bool++validRangeList [] = True+validRangeList [Range lower upper] = lower <= upper+validRangeList ranges = and $ zipWith okAdjacent ranges (tail ranges)+ where+ okAdjacent (Range lower1 upper1) (Range lower2 upper2) =+ lower1 <= upper1 && upper1 <= lower2 && lower2 <= upper2+++-- | Rearrange and merge the ranges in the list so that they are in order and+-- non-overlapping.+normaliseRangeList :: DiscreteOrdered v => [Range v] -> [Range v]+ +normaliseRangeList ranges = + normalise $ sort $ filter (not . rangeIsEmpty) ranges+ ++-- Private routine: normalise a range list that is known to be already sorted.+-- This precondition is not checked.+normalise :: DiscreteOrdered v => [Range v] -> [Range v]+normalise (r1:r2:rs) =+ if overlap r1 r2 + then normalise $+ Range (rangeLower r1) + (max (rangeUpper r1) (rangeUpper r2))+ : rs+ else r1 : (normalise $ r2 : rs)+ where+ overlap (Range _ upper1) (Range lower2 _) = upper1 >= lower2+ +normalise rs = rs+++-- | Create a new Ranged Set from a list of ranges. The list may contain+-- ranges that overlap or are not in ascending order.+makeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v+makeRangedSet = RSet . normaliseRangeList+++-- | Create a new Ranged Set from a list of ranges. @validRangeList ranges@ +-- must return @True@. This precondition is not checked.+unsafeRangedSet :: DiscreteOrdered v => [Range v] -> RSet v+unsafeRangedSet = RSet++-- | Create a Ranged Set from a single element.+rSingleton :: DiscreteOrdered v => v -> RSet v+rSingleton v = unsafeRangedSet [singletonRange v]++-- | True if the set has no members.+rSetIsEmpty :: DiscreteOrdered v => RSet v -> Bool+rSetIsEmpty = null . rSetRanges+++-- | True if the negation of the set has no members.+rSetIsFull :: DiscreteOrdered v => RSet v -> Bool+rSetIsFull = rSetIsEmpty . rSetNegation+++-- | True if the value is within the ranged set. Infix precedence is left 5.+rSetHas, (-?-) :: DiscreteOrdered v => RSet v -> v -> Bool+rSetHas (RSet ls) value = rSetHas1 ls+ where+ rSetHas1 [] = False+ rSetHas1 (r:rs)+ | value />/ rangeLower r = rangeHas r value || rSetHas1 rs+ | otherwise = False++(-?-) = rSetHas++-- | True if the first argument is a subset of the second argument, or is +-- equal. +-- +-- Infix precedence is left 5.+rSetIsSubset, (-<=-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool+rSetIsSubset rs1 rs2 = rSetIsEmpty (rs1 -!- rs2)+(-<=-) = rSetIsSubset+++-- | True if the first argument is a strict subset of the second argument.+-- +-- Infix precedence is left 5.+rSetIsSubsetStrict, (-<-) :: DiscreteOrdered v => RSet v -> RSet v -> Bool+rSetIsSubsetStrict rs1 rs2 = + rSetIsEmpty (rs1 -!- rs2) + && not (rSetIsEmpty (rs2 -!- rs1))+ +(-<-) = rSetIsSubsetStrict++-- | Set union for ranged sets. Infix precedence is left 6.+rSetUnion, (-\/-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v+-- Implementation note: rSetUnion merges the two lists into a single+-- sorted list and then calls normalise to combine overlapping ranges.+rSetUnion (RSet ls1) (RSet ls2) = RSet $ normalise $ merge ls1 ls2+ where+ merge ls1 [] = ls1+ merge [] ls2 = ls2+ merge ls1@(h1:t1) ls2@(h2:t2) =+ if h1 < h2+ then h1 : merge t1 ls2+ else h2 : merge ls1 t2++(-\/-) = rSetUnion++-- | Set intersection for ranged sets. Infix precedence is left 7.+rSetIntersection, (-/\-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v+rSetIntersection (RSet ls1) (RSet ls2) = + RSet $ filter (not . rangeIsEmpty) $ merge ls1 ls2+ where+ merge ls1@(h1:t1) ls2@(h2:t2) =+ rangeIntersection h1 h2 + : if rangeUpper h1 < rangeUpper h2+ then merge t1 ls2+ else merge ls1 t2+ merge _ _ = []++(-/\-) = rSetIntersection+++-- | Set difference. Infix precedence is left 6.+rSetDifference, (-!-) :: DiscreteOrdered v => RSet v -> RSet v -> RSet v+rSetDifference rs1 rs2 = rs1 -/\- (rSetNegation rs2)+(-!-) = rSetDifference+++-- | Set negation.+rSetNegation :: DiscreteOrdered a => RSet a -> RSet a+rSetNegation set = RSet $ ranges $ setBounds1+ where+ ranges (b1:b2:bs) = Range b1 b2 : ranges bs+ ranges [BoundaryAboveAll] = []+ ranges [b] = [Range b BoundaryAboveAll]+ ranges _ = []+ setBounds1 = case setBounds of+ (BoundaryBelowAll : bs) -> bs+ _ -> BoundaryBelowAll : setBounds+ setBounds = bounds $ rSetRanges set + bounds (r:rs) = rangeLower r : rangeUpper r : bounds rs+ bounds _ = []+++-- | The empty set.+rSetEmpty :: DiscreteOrdered a => RSet a+rSetEmpty = RSet []++-- | The set that contains everything.+rSetFull :: DiscreteOrdered a => RSet a+rSetFull = RSet [Range BoundaryBelowAll BoundaryAboveAll]+++-- | Construct a range set.+rSetUnfold :: DiscreteOrdered a => + Boundary a+ -- ^ A first lower boundary.+ -> (Boundary a -> Boundary a) + -- ^ A function from a lower boundary to an upper boundary, which must+ -- return a result greater than the argument (not checked).+ -> (Boundary a -> Maybe (Boundary a))+ -- ^ A function from a lower boundary to @Maybe@ the successor lower + -- boundary, which must return a result greater than the argument + -- (not checked).+ -> RSet a+rSetUnfold bound upperFunc succFunc = RSet $ normalise $ ranges bound+ where+ ranges b = + Range b (upperFunc bound)+ : case succFunc b of+ Just b2 -> ranges b2+ Nothing -> []+ + +-- QuickCheck Generators++instance (Arbitrary v, DiscreteOrdered v, Show v) => + Arbitrary (RSet v) + where+ arbitrary = frequency [+ (1, return rSetEmpty),+ (1, return rSetFull),+ (18, do+ ls <- arbitrary+ return $ makeRangedSet $ rangeList $ sort ls+ )]+ where+ -- Arbitrary lists of ranges don't give many interesting sets after+ -- normalisation. So instead generate a sorted list of boundaries+ -- and pair them off. Odd boundaries are dropped.+ rangeList (b1:b2:bs) = Range b1 b2 : rangeList bs+ rangeList _ = []+ + coarbitrary (RSet ls) = variant 0 . coarbitrary ls++-- ================================================================== +-- QuickCheck Properties+-- ==================================================================++-- Note for maintenance: Haddock does not include QuickCheck properties,+-- so they have to be copied into documentation blocks manually. This+-- process must be repeated for new or modified properties.+++---------------------------------------------------------------------+-- Construction properties+---------------------------------------------------------------------++{- $ConstructionProperties++A normalised range list is valid for unsafeRangedSet++> prop_validNormalised ls = validRangeList $ normaliseRangeList ls+> where types = ls :: [Range Double]++Iff a value is in a range list then it is in a ranged set+constructed from that list.++> prop_has ls v = (ls `rangeListHas` v) == rangedSet ls -?- v++-}++-- A normalised range list is valid for unsafeRangedSet+prop_validNormalised ls = validRangeList $ normaliseRangeList ls+ where types = ls :: [Range Integer]++-- Iff a value is in a range list then it is in a ranged set+-- constructed from that list.+prop_has ls v = (ls `rangeListHas` v) == makeRangedSet ls -?- v+ where types = v :: Integer++---------------------------------------------------------------------+-- Basic operation properties+---------------------------------------------------------------------++{- $BasicOperationProperties+Iff a value is in either of two ranged sets then it is in the union of+those two sets.++> prop_union rs1 rs2 v =+> (rs1 -?- v || rs2 -?- v) == ((rs1 -\/- rs2) -?- v)++Iff a value is in both of two ranged sets then it is in the intersection+of those two sets.++> prop_intersection rs1 rs2 v =+> (rs1 -?- v && rs2 -?- v) == ((rs1 -/\- rs2) -?- v)++ +Iff a value is in ranged set 1 and not in ranged set 2 then it is in the+difference of the two.++> prop_difference rs1 rs2 v = +> (rs1 -?- v && not (rs2 -?- v)) == ((rs1 -!- rs2) -?- v)+++Iff a value is not in a ranged set then it is in its negation. ++> prop_negation rs v = rs -?- v == not (rSetNegation rs -?- v)+++A set that contains a value is not empty++> prop_not_empty rs v = (rs -?- v) ==> not (rSetIsEmpty rs)++-} + +-- Iff a value is in either of two ranged sets then it is in the union of+-- those two sets.+prop_union rs1 rs2 v = (rs1 -?- v || rs2 -?- v) == ((rs1 -\/- rs2) -?- v)+ where types = v :: Integer++-- Iff a value is in both of two ranged sets then it is in the intersection+-- of those two sets.+prop_intersection rs1 rs2 v = + (rs1 -?- v && rs2 -?- v) == ((rs1 `rSetIntersection` rs2) -?- v)+ where types = v :: Integer++ +-- Iff a value is in ranged set 1 and not in ranged set 2 then it is in the+-- difference of the two.+prop_difference rs1 rs2 v = + (rs1 -?- v && not (rs2 -?- v)) == ((rs1 -!- rs2) -?- v)+ where types = v :: Integer+++-- Iff a value is not in a ranged set then it is in its negation. +prop_negation rs v = rs -?- v == not (rSetNegation rs -?- v)+ where types = v :: Integer+++-- A set that contains a value is not empty+prop_not_empty rs v = (rs -?- v) ==> not (rSetIsEmpty rs)+ where types = v :: Integer+ ++---------------------------------------------------------------------+-- Some identities and inequalities of sets+---------------------------------------------------------------------++{- $SomeIdentitiesAndInequalities++The empty set has no members.++> prop_empty v = not (rSetEmpty -?- v)+++The full set has every member.++> prop_full v = rSetFull -?- v+++The intersection of a set with its negation is empty.++> prop_empty_intersection rs =+> rSetIsEmpty (rs -/\- rSetNegation rs) + + +The union of a set with its negation is full.++> prop_full_union rs v =+> rSetIsFull (rs -\/- rSetNegation rs)+++The union of two sets is the non-strict superset of both.++> prop_union_superset rs1 rs2 =+> rs1 -<=- u && rs2 -<=- u +> where+> u = rs1 -\/- rs2+ +The intersection of two sets is the non-strict subset of both.++> prop_intersection_subset rs1 rs2 =+> i -<=- rs1 && i -<=- rs2+> where+> i = rs1 -/\- rs2++The difference of two sets intersected with the subtractand is empty.++> prop_diff_intersect rs1 rs2 =+> rSetIsEmpty ((rs1 -!- rs2) -/\- rs2)++A set is the non-strict subset of itself.++> prop_subset rs = rs -<=- rs++ +A set is not the strict subset of itself.++> prop_strict_subset rs = not (rs -<- rs)+ ++If rs1 - rs2 is not empty then the union of rs1 and rs2 will be a strict +superset of rs2.++> prop_union_strict_superset rs1 rs2 =+> (not $ rSetIsEmpty (rs1 -!- rs2))+> ==> (rs2 -<- (rs1 -\/- rs2))++Intersection commutes++> prop_intersection_commutes rs1 rs2 =+> (rs1 -/\- rs2) == (rs2 -/\- rs1)+ +Union commutes++> prop_union_commutes rs1 rs2 =+> (rs1 -\/- rs2) == (rs2 -\/- rs1)+ +Intersection associates++> prop_intersection_associates rs1 rs2 rs3 =+> ((rs1 -/\- rs2) -/\- rs3) == (rs1 -/\- (rs2 -/\- rs3))+ +Union associates++> prop_union_associates rs1 rs2 rs3 =+> ((rs1 -\/- rs2) -\/- rs3) == (rs1 -\/- (rs2 -\/- rs3))++De Morgan's Law for Intersection++> prop_de_morgan_intersection rs1 rs2 =+> rSetNegation (rs1 -/\- rs2) == (rSetNegation rs1 -\/- rSetNegation rs2)++De Morgan's Law for Union++> prop_de_morgan_union rs1 rs2 =+> rSetNegation (rs1 -\/- rs2) == (rSetNegation rs1 -/\- rSetNegation rs2)++-}++-- The empty set has no members.+prop_empty v = not (rSetEmpty -?- v)+ where types = v :: Integer+++-- The full set has every member.+prop_full v = rSetFull -?- v+ where types = v :: Integer+++-- The intersection of a set with its negation is empty.+prop_empty_intersection rs =+ rSetIsEmpty (rs -/\- rSetNegation rs) + where types = rs :: RSet Integer+ + +-- The union of a set with its negation is full.+prop_full_union rs =+ rSetIsFull (rs -\/- rSetNegation rs)+ where types = rs :: RSet Integer+++-- The union of two sets is the non-strict superset of both.+prop_union_superset rs1 rs2 =+ rs1 -<=- u && rs2 -<=- u + where+ u :: RSet Integer+ u = rs1 -\/- rs2+ +-- The intersection of two sets is the non-strict subset of both.+prop_intersection_subset rs1 rs2 =+ i -<=- rs1 && i -<=- rs2+ where+ i :: RSet Integer+ i = rs1 -/\- rs2++-- The difference of two sets intersected with the subtractand is empty.+prop_diff_intersect rs1 rs2 =+ rSetIsEmpty ((rs1 -!- rs2) -/\- rs2)+ where types = rs1 :: RSet Integer+ + +-- A set is the non-strict subset of itself.+prop_subset rs =+ rs -<=- rs+ where types = rs :: RSet Integer+ +-- A set is not the strict subset of itself.+prop_strict_subset rs =+ not (rs -<- rs)+ where types = rs :: RSet Integer+ ++-- If rs1 - rs2 is not empty then the union of rs1 and rs2 will be a strict +-- superset of rs2.+prop_union_strict_superset rs1 rs2 =+ (not $ rSetIsEmpty (rs1 -!- rs2))+ ==> (rs2 -<- (rs1 -\/- rs2))+ where types = rs1 :: RSet Integer++-- Intersection commutes+prop_intersection_commutes :: RSet Integer -> RSet Integer -> Bool+prop_intersection_commutes rs1 rs2 =+ (rs1 -/\- rs2) == (rs2 -/\- rs1)+ where types = rs1 :: RSet Integer+ +-- Union commutes+prop_union_commutes rs1 rs2 =+ (rs1 -\/- rs2) == (rs2 -\/- rs1)+ where types = rs1 :: RSet Integer+ +-- Intersection associates+prop_intersection_associates rs1 rs2 rs3 =+ ((rs1 -/\- rs2) -/\- rs3) == (rs1 -/\- (rs2 -/\- rs3))+ where types = rs1 :: RSet Integer+ +-- Union associates+prop_union_associates rs1 rs2 rs3 =+ ((rs1 -\/- rs2) -\/- rs3) == (rs1 -\/- (rs2 -\/- rs3))+ where types = rs1 :: RSet Integer+ +-- De Morgan's Law for Intersection+prop_de_morgan_intersection rs1 rs2 =+ rSetNegation (rs1 -/\- rs2) == (rSetNegation rs1 -\/- rSetNegation rs2)+ where types = rs1 :: RSet Integer++-- De Morgan's Law for Union+prop_de_morgan_union rs1 rs2 =+ rSetNegation (rs1 -\/- rs2) == (rSetNegation rs1 -/\- rSetNegation rs2)+ where types = rs1 :: RSet Integer
+ Data/Ranged/Ranges.hs view
@@ -0,0 +1,294 @@+-----------------------------------------------------------------------------+-- +-- Module : Data.Ranged.Ranges+-- Copyright : (c) Paul Johnson 2006+-- License : BSD-style+-- Maintainer : paul@cogito.org.uk+-- Stability : experimental+-- Portability : portable+--+-----------------------------------------------------------------------------+++-- | A range has an upper and lower boundary.++module Data.Ranged.Ranges (+ -- ** Construction+ Range (..),+ emptyRange,+ fullRange,+ -- ** Predicates+ rangeIsEmpty,+ rangeOverlap,+ rangeEncloses,+ rangeSingletonValue,+ -- ** Membership+ rangeHas,+ rangeListHas,+ -- ** Set Operations+ singletonRange,+ rangeIntersection,+ rangeUnion,+ rangeDifference+ -- ** QuickCheck properties+ -- $properties+) where++import Data.Ranged.Boundaries+import Data.Maybe+import Test.QuickCheck++-- | A Range has upper and lower boundaries.+data Ord v => Range v = Range {rangeLower, rangeUpper :: Boundary v}++instance (DiscreteOrdered a) => Eq (Range a) where+ r1 == r2 = (rangeIsEmpty r1 && rangeIsEmpty r2) || + (rangeLower r1 == rangeLower r2 && + rangeUpper r1 == rangeUpper r2)+++instance (DiscreteOrdered a) => Ord (Range a) where+ compare r1 r2+ | r1 == r2 = EQ+ | rangeIsEmpty r1 = LT+ | rangeIsEmpty r2 = GT+ | otherwise = compare (rangeLower r1, rangeUpper r1)+ (rangeLower r2, rangeUpper r2)+ +instance (Show a, DiscreteOrdered a) => Show (Range a) where+ show r+ | rangeIsEmpty r = "Empty"+ | otherwise = + case rangeSingletonValue r of+ Just v -> "x == " ++ show v+ Nothing -> lowerBound ++ "x" ++ upperBound+ where+ lowerBound = case rangeLower r of+ BoundaryBelowAll -> ""+ BoundaryBelow v -> show v ++ " <= "+ BoundaryAbove v -> show v ++ " < "+ BoundaryAboveAll -> error "show Range: lower bound is BoundaryAboveAll"+ upperBound = case rangeUpper r of+ BoundaryBelowAll -> error "show Range: upper bound is BoundaryBelowAll"+ BoundaryBelow v -> " < " ++ show v+ BoundaryAbove v -> " <= " ++ show v+ BoundaryAboveAll -> ""+++-- | True if the value is within the range.+rangeHas :: Ord v => Range v -> v -> Bool++rangeHas (Range b1 b2) v =+ (v />/ b1) && not (v />/ b2)+++-- | True if the value is within one of the ranges.+rangeListHas :: Ord v =>+ [Range v] -> v -> Bool+rangeListHas ls v = or $ map (\r -> rangeHas r v) ls++-- | The empty range+emptyRange :: DiscreteOrdered v => Range v+emptyRange = Range BoundaryAboveAll BoundaryBelowAll++-- | The full range. All values are within it.+fullRange :: DiscreteOrdered v => Range v+fullRange = Range BoundaryBelowAll BoundaryAboveAll++-- | A range containing a single value+singletonRange :: DiscreteOrdered v => v -> Range v+singletonRange v = Range (BoundaryBelow v) (BoundaryAbove v)++-- | If the range is a singleton, returns @Just@ the value. Otherwise returns+-- @Nothing@.+rangeSingletonValue :: DiscreteOrdered v => Range v -> Maybe v+rangeSingletonValue (Range (BoundaryBelow v1) (BoundaryAbove v2))+ | v1 == v2 = Just v1+ | otherwise = Nothing+rangeSingletonValue _ = Nothing++-- | A range is empty unless its upper boundary is greater than its lower+-- boundary.+rangeIsEmpty :: DiscreteOrdered v => Range v -> Bool+rangeIsEmpty (Range lower upper) = upper <= lower+++-- | Two ranges overlap if their intersection is non-empty.+rangeOverlap :: DiscreteOrdered v => Range v -> Range v -> Bool+rangeOverlap r1 r2 = + not (rangeIsEmpty r1)+ && not (rangeIsEmpty r2)+ && not (rangeUpper r1 <= rangeLower r2 || rangeUpper r2 <= rangeLower r1)+ + +-- | The first range encloses the second if every value in the second range is +-- also within the first range. If the second range is empty then this is+-- always true.+rangeEncloses :: DiscreteOrdered v => Range v -> Range v -> Bool+rangeEncloses r1 r2 =+ (rangeLower r1 <= rangeLower r2 && rangeUpper r2 <= rangeUpper r1) + || rangeIsEmpty r2+++-- | Intersection of two ranges, if any.+rangeIntersection :: DiscreteOrdered v => Range v -> Range v -> Range v+ +rangeIntersection (Range lower1 upper1) (Range lower2 upper2) =+ Range (max lower1 lower2) (min upper1 upper2)+ + +-- | Union of two ranges. Returns one or two results.+--+-- If there are two results then they are guaranteed to have a non-empty+-- gap in between, but may not be in ascending order.+rangeUnion :: DiscreteOrdered v => Range v -> Range v -> [Range v]+ +rangeUnion r1@(Range lower1 upper1) r2@(Range lower2 upper2) =+ if touching+ then [Range lower upper]+ else [r1, r2]+ where+ touching = (max lower1 lower2) <= (min upper1 upper2)+ lower = min lower1 lower2+ upper = max upper1 upper2+++-- | @range1@ minus @range2@. Returns zero, one or two results. Multiple +-- results are guaranteed to have non-empty gaps in between, but may not be in +-- ascending order.+rangeDifference :: DiscreteOrdered v => Range v -> Range v -> [Range v]+ +rangeDifference r1@(Range lower1 upper1) r2@(Range lower2 upper2) =+ -- There are six possibilities+ -- 1: r2 completely less than r1+ -- 2: r2 overlaps bottom of r1+ -- 3: r2 encloses r1+ -- 4: r1 encloses r2+ -- 5: r2 overlaps top of r1+ -- 6: r2 completely greater than r1+ if intersects+ then -- Cases 2,3,4,5+ filter (not . rangeIsEmpty) [Range lower1 lower2, Range upper2 upper1]+ else -- Cases 1, 6+ [r1]+ where+ intersects = (max lower1 lower2) < (min upper1 upper2)+++-- QuickCheck generators++instance (Arbitrary v, DiscreteOrdered v, Show v) => + Arbitrary (Range v) where+ + arbitrary = frequency [+ (17, do -- Ordinary range+ b1 <- arbitrary+ b2 <- arbitrary+ if b1 < b2 + then return $ Range b1 b2+ else return $ Range b2 b1+ ),+ (1, do -- Singleton range+ v <- arbitrary+ return $ singletonRange v+ ),+ (1, return emptyRange),+ (1, return fullRange)+ ]+ + coarbitrary (Range lower upper) =+ variant 0 . coarbitrary lower . coarbitrary upper+ ++ +-- QuickCheck Properties++{- $properties+Range union++> prop_union r1 r2 n =+> (r1 `rangeHas` n || r2 `rangeHas` n) +> == (r1 `rangeUnion` r2) `rangeListHas` n++Range intersection++> prop_intersection r1 r2 n =+> (r1 `rangeHas` n && r2 `rangeHas` n)+> == (r1 `rangeIntersection` r2) `rangeHas` n++Range difference++> prop_difference r1 r2 n =+> (r1 `rangeHas` n && not (r2 `rangeHas` n))+> == (r1 `rangeDifference` r2) `rangeListHas` n++Singleton range++> prop_singletonHas v =+> singletonRange v `rangeHas` v++> prop_singletonConverse v =+> rangeSingletonValue (singletonRange v) == Just v++-}++-- For Integers (sparse type)++-- Range union+prop_union_int r1 r2 n = + (r1 `rangeHas` n || r2 `rangeHas` n) + == (r1 `rangeUnion` r2) `rangeListHas` n+ where t :: Integer ; t = n+++-- Range intersection+prop_intersection_int r1 r2 n =+ (r1 `rangeHas` n && r2 `rangeHas` n)+ == (r1 `rangeIntersection` r2) `rangeHas` n+ where t :: Integer ; t = n++-- Range difference+prop_difference_int r1 r2 n =+ (r1 `rangeHas` n && not (r2 `rangeHas` n))+ == (r1 `rangeDifference` r2) `rangeListHas` n+ where t :: Integer ; t = n++-- Range Singleton Has+prop_singletonHas_int v =+ singletonRange v `rangeHas` v+ where t :: Integer ; t = v++-- Range Singleton inverse+prop_singletonConverse_int v =+ rangeSingletonValue (singletonRange v) == Just v+ where t :: Integer ; t = v++-- For Reals (dense type)++-- Range Union+prop_union_real r1 r2 n = + (r1 `rangeHas` n || r2 `rangeHas` n) + == (r1 `rangeUnion` r2) `rangeListHas` n+ where t :: Double ; t = n++-- Range intersection+prop_intersection_real r1 r2 n =+ (r1 `rangeHas` n && r2 `rangeHas` n)+ == (r1 `rangeIntersection` r2) `rangeHas` n+ where t :: Double ; t = n++-- Range difference+prop_difference_real r1 r2 n =+ (r1 `rangeHas` n && not (r2 `rangeHas` n))+ == (r1 `rangeDifference` r2) `rangeListHas` n+ where t :: Double ; t = n++-- Range Singleton Has+prop_singletonHas_real v =+ singletonRange v `rangeHas` v+ where t :: Double ; t = v++-- Range Singleton inverse+prop_singletonConverse_real v =+ rangeSingletonValue (singletonRange v) == Just v+ where t :: Double ; t = v
+ Doc/Data-Ranged-Boundaries.html view
@@ -0,0 +1,681 @@+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">+<!--Rendered using the Haskell Html Library v0.2-->+<HTML+><HEAD+><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"+><TITLE+>Data.Ranged.Boundaries</TITLE+><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"+><SCRIPT SRC="haddock.js" TYPE="text/javascript"+></SCRIPT+></HEAD+><BODY+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="topbar"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD+><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "+></TD+><TD CLASS="title"+></TD+><TD CLASS="topbut"+><A HREF="index.html"+>Contents</A+></TD+><TD CLASS="topbut"+><A HREF="doc-index.html"+>Index</A+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="modulebar"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD+><FONT SIZE="6"+>Data.Ranged.Boundaries</FONT+></TD+><TD ALIGN="right"+><TABLE CLASS="narrow" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="infohead"+>Portability</TD+><TD CLASS="infoval"+>portable</TD+></TR+><TR+><TD CLASS="infohead"+>Stability</TD+><TD CLASS="infoval"+>experimental</TD+></TR+><TR+><TD CLASS="infohead"+>Maintainer</TD+><TD CLASS="infoval"+>paul@cogito.org.uk</TD+></TR+></TABLE+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section1"+>Description</TD+></TR+><TR+><TD CLASS="doc"+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section1"+>Synopsis</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="body"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="decl"+><SPAN CLASS="keyword"+>class</SPAN+> Ord a => <A HREF="#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a <SPAN CLASS="keyword"+>where</SPAN+></TD+></TR+><TR+><TD CLASS="body"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="decl"+><A HREF="#v%3Aadjacent"+>adjacent</A+> :: a -> a -> Bool</TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3Aadjacent"+>adjacent</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => a -> a -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3AenumAdjacent"+>enumAdjacent</A+> :: (Ord a, Enum a) => a -> a -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3AboundedAdjacent"+>boundedAdjacent</A+> :: (Ord a, Enum a) => a -> a -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="decl"+><SPAN CLASS="keyword"+>data</SPAN+> <A HREF="#t%3ABoundary"+>Boundary</A+> a</TD+></TR+><TR+><TD CLASS="body"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="decl"+>= <A HREF="#v%3ABoundaryAbove"+>BoundaryAbove</A+> a</TD+></TR+><TR+><TD CLASS="decl"+>| <A HREF="#v%3ABoundaryBelow"+>BoundaryBelow</A+> a</TD+></TR+><TR+><TD CLASS="decl"+>| <A HREF="#v%3ABoundaryAboveAll"+>BoundaryAboveAll</A+></TD+></TR+><TR+><TD CLASS="decl"+>| <A HREF="#v%3ABoundaryBelowAll"+>BoundaryBelowAll</A+></TD+></TR+></TABLE+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3Aabove"+>above</A+> :: Ord v => <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> v -> v -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3A%2F%3E%2F"+>(/>/)</A+> :: Ord v => v -> <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> v -> Bool</TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section1"+>Documentation</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><SPAN CLASS="keyword"+>class</SPAN+> Ord a => <A NAME="t%3ADiscreteOrdered"+></A+><B+>DiscreteOrdered</B+> a <SPAN CLASS="keyword"+>where</SPAN+></TD+></TR+><TR+><TD CLASS="body"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="ndoc"+><P+>Distinguish between dense and sparse ordered types. A dense type is +one in which any two values <TT+>v1 < v2</TT+> have a third value <TT+>v3</TT+> such that +<TT+>v1 < v3 < v2</TT+>.+</P+><P+>In theory the floating types are dense, although in practice they can only have+finitely many values. This class treats them as dense.+</P+><P+>Tuples up to 4 members are declared as instances. Larger tuples may be added+if necessary.+</P+><P+>This approach was suggested by Ben Rudiak-Gould on comp.lang.functional.+</P+></TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="section4"+>Methods</TD+></TR+><TR+><TD CLASS="body"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="decl"+><A NAME="v%3Aadjacent"+></A+><B+>adjacent</B+> :: a -> a -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>Two values <TT+>x</TT+> and <TT+>y</TT+> are adjacent if <TT+>x < y</TT+> and there does not + exist a third value between them. Always <TT+>False</TT+> for dense types.+</TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="section4"+><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:DiscreteOrdered')" ALT="show/hide"+> Instances</TD+></TR+><TR+><TD CLASS="body"+><DIV ID="i:DiscreteOrdered" STYLE="display:block;"+><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"+><TR+><TD CLASS="decl"+><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> Bool</TD+></TR+><TR+><TD CLASS="decl"+><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> Char</TD+></TR+><TR+><TD CLASS="decl"+><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> Double</TD+></TR+><TR+><TD CLASS="decl"+><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> Float</TD+></TR+><TR+><TD CLASS="decl"+><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> Int</TD+></TR+><TR+><TD CLASS="decl"+><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> Integer</TD+></TR+><TR+><TD CLASS="decl"+><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> Ordering</TD+></TR+><TR+><TD CLASS="decl"+>(Ord a, <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> b) => <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> (a, b)</TD+></TR+><TR+><TD CLASS="decl"+>(Ord a, Ord b, <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> c) => <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> (a, b, c)</TD+></TR+><TR+><TD CLASS="decl"+>(Ord a, Ord b, Ord c, <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> d) => <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> (a, b, c, d)</TD+></TR+><TR+><TD CLASS="decl"+>Integral a => <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> (Ratio a)</TD+></TR+><TR+><TD CLASS="decl"+>Ord a => <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> [a]</TD+></TR+></TABLE+></DIV+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3Aadjacent"+></A+><B+>adjacent</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => a -> a -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>Two values <TT+>x</TT+> and <TT+>y</TT+> are adjacent if <TT+>x < y</TT+> and there does not + exist a third value between them. Always <TT+>False</TT+> for dense types.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3AenumAdjacent"+></A+><B+>enumAdjacent</B+> :: (Ord a, Enum a) => a -> a -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>Check adjacency for sparse enumerated types (i.e. where there+ is no value between <TT+>x</TT+> and <TT+>succ x</TT+>). Use as the definition of+ <A HREF="adjacent.html"+>adjacent</A+> for most enumerated types.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3AboundedAdjacent"+></A+><B+>boundedAdjacent</B+> :: (Ord a, Enum a) => a -> a -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>Check adjacency, allowing for case where x = maxBound. Use as the+ definition of <A HREF="adjacent.html"+>adjacent</A+> for bounded enumerated types such as Int and Char.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><SPAN CLASS="keyword"+>data</SPAN+> <A NAME="t%3ABoundary"+></A+><B+>Boundary</B+> a</TD+></TR+><TR+><TD CLASS="body"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="ndoc"+><P+>A Boundary is a division of an ordered type into values above +and below the boundary. No value can sit on a boundary.+</P+><P+>Known bug: for Bounded types +</P+><UL+><LI+><PRE+>BoundaryAbove maxBound < BoundaryAboveAll</PRE+></LI+><LI+><PRE+>BoundaryBelow minBound > BoundaryBelowAll</PRE+></LI+></UL+><P+>This is incorrect because there are no possible values in +between the left and right sides of these inequalities. +</P+></TD+></TR+><TR+><TD CLASS="section4"+>Constructors</TD+></TR+><TR+><TD CLASS="body"+><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"+><TR+><TD CLASS="arg"+><A NAME="v%3ABoundaryAbove"+></A+><B+>BoundaryAbove</B+> a</TD+><TD CLASS="rdoc"+>The argument is the highest value below the boundary.+</TD+></TR+><TR+><TD CLASS="arg"+><A NAME="v%3ABoundaryBelow"+></A+><B+>BoundaryBelow</B+> a</TD+><TD CLASS="rdoc"+>The argument is the lowest value above the boundary.+</TD+></TR+><TR+><TD CLASS="arg"+><A NAME="v%3ABoundaryAboveAll"+></A+><B+>BoundaryAboveAll</B+></TD+><TD CLASS="rdoc"+>The boundary above all values.+</TD+></TR+><TR+><TD CLASS="arg"+><A NAME="v%3ABoundaryBelowAll"+></A+><B+>BoundaryBelowAll</B+></TD+><TD CLASS="rdoc"+>The boundary below all values.+</TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="section4"+><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:Boundary')" ALT="show/hide"+> Instances</TD+></TR+><TR+><TD CLASS="body"+><DIV ID="i:Boundary" STYLE="display:block;"+><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"+><TR+><TD CLASS="decl"+>Arbitrary a => Arbitrary (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a)</TD+></TR+><TR+><TD CLASS="decl"+><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => Eq (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a)</TD+></TR+><TR+><TD CLASS="decl"+><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => Ord (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a)</TD+></TR+><TR+><TD CLASS="decl"+>Show a => Show (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a)</TD+></TR+></TABLE+></DIV+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3Aabove"+></A+><B+>above</B+> :: Ord v => <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> v -> v -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>True if the value is above the boundary, false otherwise.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3A%2F%3E%2F"+></A+><B+>(/>/)</B+> :: Ord v => v -> <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>Same as <TT+><A HREF="Data-Ranged-Boundaries.html#v%3Aabove"+>above</A+></TT+>, but with the arguments reversed for more intuitive infix+ usage. +</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="botbar"+>Produced by <A HREF="http://www.haskell.org/haddock/"+>Haddock</A+> version 0.8</TD+></TR+></TABLE+></BODY+></HTML+>
+ Doc/Data-Ranged-RangedSet.html view
@@ -0,0 +1,1456 @@+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">+<!--Rendered using the Haskell Html Library v0.2-->+<HTML+><HEAD+><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"+><TITLE+>Data.Ranged.RangedSet</TITLE+><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"+><SCRIPT SRC="haddock.js" TYPE="text/javascript"+></SCRIPT+></HEAD+><BODY+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="topbar"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD+><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "+></TD+><TD CLASS="title"+></TD+><TD CLASS="topbut"+><A HREF="index.html"+>Contents</A+></TD+><TD CLASS="topbut"+><A HREF="doc-index.html"+>Index</A+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="modulebar"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD+><FONT SIZE="6"+>Data.Ranged.RangedSet</FONT+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="section4"+><B+>Contents</B+></TD+></TR+><TR+><TD+><DL+><DT+><A HREF="#1"+>Ranged Set Type+</A+></DT+><DT+><A HREF="#2"+>Ranged Set construction functions and their Preconditions+</A+></DT+><DT+><A HREF="#3"+>Predicates+</A+></DT+><DT+><A HREF="#4"+>Set Operations+</A+></DT+><DT+><A HREF="#5"+>Useful Sets+</A+></DT+><DT+><A HREF="#6"+>QuickCheck Properties+</A+></DT+><DD+><DL+><DT+><A HREF="#7"+>Construction+</A+></DT+><DT+><A HREF="#8"+>Basic Operations+</A+></DT+><DT+><A HREF="#9"+>Some Identities and Inequalities+</A+></DT+></DL+></DD+></DL+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section1"+>Synopsis</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="body"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="decl"+><SPAN CLASS="keyword"+>data</SPAN+> <A HREF="#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArSetRanges"+>rSetRanges</A+> :: <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v]</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3AmakeRangedSet"+>makeRangedSet</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v] -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3AunsafeRangedSet"+>unsafeRangedSet</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v] -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3AvalidRangeList"+>validRangeList</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v] -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3AnormaliseRangeList"+>normaliseRangeList</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v] -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v]</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArSingleton"+>rSingleton</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArSetIsEmpty"+>rSetIsEmpty</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3A-%3F-"+>(-?-)</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> v -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArSetHas"+>rSetHas</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> v -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3A-%3C%3D-"+>(-<=-)</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArSetIsSubset"+>rSetIsSubset</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3A-%3C-"+>(-<-)</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArSetIsSubsetStrict"+>rSetIsSubsetStrict</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3A-%5C%2F-"+>(-\/-)</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArSetUnion"+>rSetUnion</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3A-%2F%5C-"+>(-/\-)</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArSetIntersection"+>rSetIntersection</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3A-%21-"+>(-!-)</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArSetDifference"+>rSetDifference</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArSetNegation"+>rSetNegation</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> a -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> a</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArSetEmpty"+>rSetEmpty</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> a</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArSetFull"+>rSetFull</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> a</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArSetUnfold"+>rSetUnfold</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a -> (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a -> <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a) -> (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a -> Maybe (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a)) -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> a</TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section2"+><A NAME="1"+>Ranged Set Type+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><SPAN CLASS="keyword"+>data</SPAN+> <A NAME="t%3ARSet"+></A+><B+>RSet</B+> v</TD+></TR+><TR+><TD CLASS="body"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="ndoc"+>An RSet (for Ranged Set) is a list of ranges. The ranges must be sorted+ and not overlap.+</TD+></TR+><TR+><TD CLASS="section4"+><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:RSet')" ALT="show/hide"+> Instances</TD+></TR+><TR+><TD CLASS="body"+><DIV ID="i:RSet" STYLE="display:block;"+><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"+><TR+><TD CLASS="decl"+>(Arbitrary v, <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v, Show v) => Arbitrary (<A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v)</TD+></TR+><TR+><TD CLASS="decl"+>(<A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v, ??? v) => Eq (<A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v)</TD+></TR+><TR+><TD CLASS="decl"+><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => Monoid (<A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> a)</TD+></TR+><TR+><TD CLASS="decl"+>(<A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v, ??? v) => Show (<A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v)</TD+></TR+></TABLE+></DIV+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArSetRanges"+></A+><B+>rSetRanges</B+> :: <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v]</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section2"+><A NAME="2"+>Ranged Set construction functions and their Preconditions+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3AmakeRangedSet"+></A+><B+>makeRangedSet</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v] -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="doc"+>Create a new Ranged Set from a list of ranges. The list may contain+ ranges that overlap or are not in ascending order.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3AunsafeRangedSet"+></A+><B+>unsafeRangedSet</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v] -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="doc"+>Create a new Ranged Set from a list of ranges. <TT+>validRangeList ranges</TT+> + must return <TT+>True</TT+>. This precondition is not checked.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3AvalidRangeList"+></A+><B+>validRangeList</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v] -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>Determine if the ranges in the list are both in order and non-overlapping.+ If so then they are suitable input for the unsafeRangedSet function.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3AnormaliseRangeList"+></A+><B+>normaliseRangeList</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v] -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v]</TD+></TR+><TR+><TD CLASS="doc"+>Rearrange and merge the ranges in the list so that they are in order and+ non-overlapping.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArSingleton"+></A+><B+>rSingleton</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="doc"+>Create a Ranged Set from a single element.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section2"+><A NAME="3"+>Predicates+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArSetIsEmpty"+></A+><B+>rSetIsEmpty</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>True if the set has no members.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3A-%3F-"+></A+><B+>(-?-)</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> v -> Bool</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArSetHas"+></A+><B+>rSetHas</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> v -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>True if the value is within the ranged set. Infix precedence is left 5.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3A-%3C%3D-"+></A+><B+>(-<=-)</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArSetIsSubset"+></A+><B+>rSetIsSubset</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="doc"+><P+>True if the first argument is a subset of the second argument, or is + equal. +</P+><P+>Infix precedence is left 5.+</P+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3A-%3C-"+></A+><B+>(-<-)</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArSetIsSubsetStrict"+></A+><B+>rSetIsSubsetStrict</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="doc"+><P+>True if the first argument is a strict subset of the second argument.+</P+><P+>Infix precedence is left 5.+</P+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section2"+><A NAME="4"+>Set Operations+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3A-%5C%2F-"+></A+><B+>(-\/-)</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArSetUnion"+></A+><B+>rSetUnion</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="doc"+>Set union for ranged sets. Infix precedence is left 6.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3A-%2F%5C-"+></A+><B+>(-/\-)</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArSetIntersection"+></A+><B+>rSetIntersection</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="doc"+>Set intersection for ranged sets. Infix precedence is left 7.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3A-%21-"+></A+><B+>(-!-)</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArSetDifference"+></A+><B+>rSetDifference</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> v</TD+></TR+><TR+><TD CLASS="doc"+>Set difference. Infix precedence is left 6.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArSetNegation"+></A+><B+>rSetNegation</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> a -> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> a</TD+></TR+><TR+><TD CLASS="doc"+>Set negation.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section2"+><A NAME="5"+>Useful Sets+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArSetEmpty"+></A+><B+>rSetEmpty</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> a</TD+></TR+><TR+><TD CLASS="doc"+>The empty set.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArSetFull"+></A+><B+>rSetFull</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> a</TD+></TR+><TR+><TD CLASS="doc"+>The set that contains everything.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArSetUnfold"+></A+><B+>rSetUnfold</B+></TD+></TR+><TR+><TD CLASS="body"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="arg"+>:: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a</TD+><TD CLASS="rdoc"+></TD+></TR+><TR+><TD CLASS="arg"+>=> <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a</TD+><TD CLASS="rdoc"+>A first lower boundary.+</TD+></TR+><TR+><TD CLASS="arg"+>-> (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a -> <A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a)</TD+><TD CLASS="rdoc"+>A function from a lower boundary to an upper boundary, which must+ return a result greater than the argument (not checked).+</TD+></TR+><TR+><TD CLASS="arg"+>-> (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a -> Maybe (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> a))</TD+><TD CLASS="rdoc"+>A function from a lower boundary to <TT+>Maybe</TT+> the successor lower + boundary, which must return a result greater than the argument + (not checked).+</TD+></TR+><TR+><TD CLASS="arg"+>-> <A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>RSet</A+> a</TD+><TD CLASS="rdoc"+></TD+></TR+><TR+><TD CLASS="ndoc" COLSPAN="2"+>Construct a range set.+</TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section2"+><A NAME="6"+>QuickCheck Properties+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section3"+><A NAME="7"+>Construction+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="doc"+><P+>A normalised range list is valid for unsafeRangedSet+</P+><PRE+> prop_validNormalised ls = validRangeList $ normaliseRangeList ls+ where types = ls :: [Range Double]+</PRE+><P+>Iff a value is in a range list then it is in a ranged set+constructed from that list.+</P+><PRE+> prop_has ls v = (ls `rangeListHas` v) == rangedSet ls -?- v+</PRE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section3"+><A NAME="8"+>Basic Operations+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="doc"+><P+>Iff a value is in either of two ranged sets then it is in the union of+those two sets.+</P+><PRE+> prop_union rs1 rs2 v =+ (rs1 -?- v || rs2 -?- v) == ((rs1 -\/- rs2) -?- v)+</PRE+><P+>Iff a value is in both of two ranged sets then it is in the intersection+of those two sets.+</P+><PRE+> prop_intersection rs1 rs2 v =+ (rs1 -?- v && rs2 -?- v) == ((rs1 -/\- rs2) -?- v)+</PRE+><P+>Iff a value is in ranged set 1 and not in ranged set 2 then it is in the+difference of the two.+</P+><PRE+> prop_difference rs1 rs2 v = + (rs1 -?- v && not (rs2 -?- v)) == ((rs1 -!- rs2) -?- v)+</PRE+><P+>Iff a value is not in a ranged set then it is in its negation. +</P+><PRE+> prop_negation rs v = rs -?- v == not (rSetNegation rs -?- v)+</PRE+><P+>A set that contains a value is not empty+</P+><PRE+> prop_not_empty rs v = (rs -?- v) ==> not (rSetIsEmpty rs)+</PRE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section3"+><A NAME="9"+>Some Identities and Inequalities+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="doc"+><P+>The empty set has no members.+</P+><PRE+> prop_empty v = not (rSetEmpty -?- v)+</PRE+><P+>The full set has every member.+</P+><PRE+> prop_full v = rSetFull -?- v+</PRE+><P+>The intersection of a set with its negation is empty.+</P+><PRE+> prop_empty_intersection rs =+ rSetIsEmpty (rs -/\- rSetNegation rs) +</PRE+><P+>The union of a set with its negation is full.+</P+><PRE+> prop_full_union rs v =+ rSetIsFull (rs -\/- rSetNegation rs)+</PRE+><P+>The union of two sets is the non-strict superset of both.+</P+><PRE+> prop_union_superset rs1 rs2 =+ rs1 -<=- u && rs2 -<=- u + where+ u = rs1 -\/- rs2+</PRE+><P+>The intersection of two sets is the non-strict subset of both.+</P+><PRE+> prop_intersection_subset rs1 rs2 =+ i -<=- rs1 && i -<=- rs2+ where+ i = rs1 -/\- rs2+</PRE+><P+>The difference of two sets intersected with the subtractand is empty.+</P+><PRE+> prop_diff_intersect rs1 rs2 =+ rSetIsEmpty ((rs1 -!- rs2) -/\- rs2)+</PRE+><P+>A set is the non-strict subset of itself.+</P+><PRE+> prop_subset rs = rs -<=- rs+</PRE+><P+>A set is not the strict subset of itself.+</P+><PRE+> prop_strict_subset rs = not (rs -<- rs)+</PRE+><P+>If rs1 - rs2 is not empty then the union of rs1 and rs2 will be a strict +superset of rs2.+</P+><PRE+> prop_union_strict_superset rs1 rs2 =+ (not $ rSetIsEmpty (rs1 -!- rs2))+ ==> (rs2 -<- (rs1 -\/- rs2))+</PRE+><P+>Intersection commutes+</P+><PRE+> prop_intersection_commutes rs1 rs2 =+ (rs1 -/\- rs2) == (rs2 -/\- rs1)+</PRE+><P+>Union commutes+</P+><PRE+> prop_union_commutes rs1 rs2 =+ (rs1 -\/- rs2) == (rs2 -\/- rs1)+</PRE+><P+>Intersection associates+</P+><PRE+> prop_intersection_associates rs1 rs2 rs3 =+ ((rs1 -/\- rs2) -/\- rs3) == (rs1 -/\- (rs2 -/\- rs3))+</PRE+><P+>Union associates+</P+><PRE+> prop_union_associates rs1 rs2 rs3 =+ ((rs1 -\/- rs2) -\/- rs3) == (rs1 -\/- (rs2 -\/- rs3))+</PRE+><P+>De Morgan's Law for Intersection+</P+><PRE+> prop_de_morgan_intersection rs1 rs2 =+ rSetNegation (rs1 -/\- rs2) == (rSetNegation rs1 -\/- rSetNegation rs2)+</PRE+><P+>De Morgan's Law for Union+</P+><PRE+> prop_de_morgan_union rs1 rs2 =+ rSetNegation (rs1 -\/- rs2) == (rSetNegation rs1 -/\- rSetNegation rs2)+</PRE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="botbar"+>Produced by <A HREF="http://www.haskell.org/haddock/"+>Haddock</A+> version 0.8</TD+></TR+></TABLE+></BODY+></HTML+>
+ Doc/Data-Ranged-Ranges.html view
@@ -0,0 +1,838 @@+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">+<!--Rendered using the Haskell Html Library v0.2-->+<HTML+><HEAD+><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"+><TITLE+>Data.Ranged.Ranges</TITLE+><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"+><SCRIPT SRC="haddock.js" TYPE="text/javascript"+></SCRIPT+></HEAD+><BODY+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="topbar"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD+><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "+></TD+><TD CLASS="title"+></TD+><TD CLASS="topbut"+><A HREF="index.html"+>Contents</A+></TD+><TD CLASS="topbut"+><A HREF="doc-index.html"+>Index</A+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="modulebar"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD+><FONT SIZE="6"+>Data.Ranged.Ranges</FONT+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="section4"+><B+>Contents</B+></TD+></TR+><TR+><TD+><DL+><DT+><A HREF="#1"+>Construction+</A+></DT+><DT+><A HREF="#2"+>Predicates+</A+></DT+><DT+><A HREF="#3"+>Membership+</A+></DT+><DT+><A HREF="#4"+>Set Operations+</A+></DT+><DT+><A HREF="#5"+>QuickCheck properties+</A+></DT+></DL+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section1"+>Description</TD+></TR+><TR+><TD CLASS="doc"+>A range has an upper and lower boundary.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section1"+>Synopsis</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="body"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="decl"+><SPAN CLASS="keyword"+>data</SPAN+> <A HREF="#t%3ARange"+>Range</A+> v = <A HREF="#v%3ARange"+>Range</A+> {<TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="recfield"+><A HREF="#v%3ArangeLower"+>rangeLower</A+>, <A HREF="#v%3ArangeUpper"+>rangeUpper</A+> :: (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> v)</TD+></TR+></TABLE+>}</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3AemptyRange"+>emptyRange</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3AfullRange"+>fullRange</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArangeIsEmpty"+>rangeIsEmpty</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArangeOverlap"+>rangeOverlap</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArangeEncloses"+>rangeEncloses</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArangeSingletonValue"+>rangeSingletonValue</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> Maybe v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArangeHas"+>rangeHas</A+> :: Ord v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> v -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArangeListHas"+>rangeListHas</A+> :: Ord v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v] -> v -> Bool</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3AsingletonRange"+>singletonRange</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArangeIntersection"+>rangeIntersection</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArangeUnion"+>rangeUnion</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v]</TD+></TR+><TR+><TD CLASS="s8"+></TD+></TR+><TR+><TD CLASS="decl"+><A HREF="#v%3ArangeDifference"+>rangeDifference</A+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v]</TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section2"+><A NAME="1"+>Construction+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><SPAN CLASS="keyword"+>data</SPAN+> <A NAME="t%3ARange"+></A+><B+>Range</B+> v</TD+></TR+><TR+><TD CLASS="body"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="ndoc"+>A Range has upper and lower boundaries.+</TD+></TR+><TR+><TD CLASS="section4"+>Constructors</TD+></TR+><TR+><TD CLASS="body"+><TABLE CLASS="vanilla" CELLSPACING="5" CELLPADDING="0"+><TR+><TD CLASS="arg"+><A NAME="v%3ARange"+></A+><B+>Range</B+></TD+><TD CLASS="rdoc"+></TD+></TR+><TR+><TD CLASS="body" COLSPAN="2"+><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"+><TR+><TD CLASS="arg"+><A NAME="v%3ArangeLower"+></A+><B+>rangeLower</B+>, <A NAME="v%3ArangeUpper"+></A+><B+>rangeUpper</B+> :: (<A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Boundary</A+> v)</TD+><TD CLASS="rdoc"+></TD+></TR+></TABLE+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="section4"+><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:Range')" ALT="show/hide"+> Instances</TD+></TR+><TR+><TD CLASS="body"+><DIV ID="i:Range" STYLE="display:block;"+><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"+><TR+><TD CLASS="decl"+>(Arbitrary v, <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v, Show v) => Arbitrary (<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v)</TD+></TR+><TR+><TD CLASS="decl"+><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => Eq (<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> a)</TD+></TR+><TR+><TD CLASS="decl"+><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a => Ord (<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> a)</TD+></TR+><TR+><TD CLASS="decl"+>(Show a, <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> a) => Show (<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> a)</TD+></TR+></TABLE+></DIV+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3AemptyRange"+></A+><B+>emptyRange</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v</TD+></TR+><TR+><TD CLASS="doc"+>The empty range+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3AfullRange"+></A+><B+>fullRange</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v</TD+></TR+><TR+><TD CLASS="doc"+>The full range. All values are within it.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section2"+><A NAME="2"+>Predicates+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArangeIsEmpty"+></A+><B+>rangeIsEmpty</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>A range is empty unless its upper boundary is greater than its lower+ boundary.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArangeOverlap"+></A+><B+>rangeOverlap</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>Two ranges overlap if their intersection is non-empty.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArangeEncloses"+></A+><B+>rangeEncloses</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>The first range encloses the second if every value in the second range is + also within the first range. If the second range is empty then this is+ always true.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArangeSingletonValue"+></A+><B+>rangeSingletonValue</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> Maybe v</TD+></TR+><TR+><TD CLASS="doc"+>If the range is a singleton, returns <TT+>Just</TT+> the value. Otherwise returns+ <TT+>Nothing</TT+>.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section2"+><A NAME="3"+>Membership+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArangeHas"+></A+><B+>rangeHas</B+> :: Ord v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> v -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>True if the value is within the range.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArangeListHas"+></A+><B+>rangeListHas</B+> :: Ord v => [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v] -> v -> Bool</TD+></TR+><TR+><TD CLASS="doc"+>True if the value is within one of the ranges.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section2"+><A NAME="4"+>Set Operations+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3AsingletonRange"+></A+><B+>singletonRange</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v</TD+></TR+><TR+><TD CLASS="doc"+>A range containing a single value+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArangeIntersection"+></A+><B+>rangeIntersection</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v</TD+></TR+><TR+><TD CLASS="doc"+>Intersection of two ranges, if any.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArangeUnion"+></A+><B+>rangeUnion</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v]</TD+></TR+><TR+><TD CLASS="doc"+><P+>Union of two ranges. Returns one or two results.+</P+><P+>If there are two results then they are guaranteed to have a non-empty+ gap in between, but may not be in ascending order.+</P+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+><A NAME="v%3ArangeDifference"+></A+><B+>rangeDifference</B+> :: <A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>DiscreteOrdered</A+> v => <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> <A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v -> [<A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Range</A+> v]</TD+></TR+><TR+><TD CLASS="doc"+><TT+>range1</TT+> minus <TT+>range2</TT+>. Returns zero, one or two results. Multiple + results are guaranteed to have non-empty gaps in between, but may not be in + ascending order.+</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section2"+><A NAME="5"+>QuickCheck properties+</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="doc"+><P+>Range union+</P+><PRE+> prop_union r1 r2 n =+ (r1 `rangeHas` n || r2 `rangeHas` n) + == (r1 `rangeUnion` r2) `rangeListHas` n+</PRE+><P+>Range intersection+</P+><PRE+> prop_intersection r1 r2 n =+ (r1 `rangeHas` n && r2 `rangeHas` n)+ == (r1 `rangeIntersection` r2) `rangeHas` n+</PRE+><P+>Range difference+</P+><PRE+> prop_difference r1 r2 n =+ (r1 `rangeHas` n && not (r2 `rangeHas` n))+ == (r1 `rangeDifference` r2) `rangeListHas` n+</PRE+><P+>Singleton range+</P+><PRE+> prop_singletonHas v =+ singletonRange v `rangeHas` v+</PRE+><PRE+> prop_singletonConverse v =+ rangeSingletonValue (singletonRange v) == Just v+</PRE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="botbar"+>Produced by <A HREF="http://www.haskell.org/haddock/"+>Haddock</A+> version 0.8</TD+></TR+></TABLE+></BODY+></HTML+>
+ Doc/Data-Ranged.html view
@@ -0,0 +1,106 @@+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">+<!--Rendered using the Haskell Html Library v0.2-->+<HTML+><HEAD+><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"+><TITLE+>Data.Ranged</TITLE+><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"+><SCRIPT SRC="haddock.js" TYPE="text/javascript"+></SCRIPT+></HEAD+><BODY+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="topbar"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD+><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "+></TD+><TD CLASS="title"+></TD+><TD CLASS="topbut"+><A HREF="index.html"+>Contents</A+></TD+><TD CLASS="topbut"+><A HREF="doc-index.html"+>Index</A+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="modulebar"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD+><FONT SIZE="6"+>Data.Ranged</FONT+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="section1"+>Documentation</TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+>module <A HREF="Data-Ranged-Boundaries.html"+>Data.Ranged.Boundaries</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+>module <A HREF="Data-Ranged-Ranges.html"+>Data.Ranged.Ranges</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="decl"+>module <A HREF="Data-Ranged-RangedSet.html"+>Data.Ranged.RangedSet</A+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="botbar"+>Produced by <A HREF="http://www.haskell.org/haddock/"+>Haddock</A+> version 0.8</TD+></TR+></TABLE+></BODY+></HTML+>
+ Doc/doc-index.html view
@@ -0,0 +1,454 @@+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">+<!--Rendered using the Haskell Html Library v0.2-->+<HTML+><HEAD+><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"+><TITLE+> (Index)</TITLE+><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"+></HEAD+><BODY+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="topbar"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD+><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "+></TD+><TD CLASS="title"+></TD+><TD CLASS="topbut"+><A HREF="index.html"+>Contents</A+></TD+><TD CLASS="topbut"+><A HREF="doc-index.html"+>Index</A+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD+><TABLE CELLPADDING="0" CELLSPACING="5"+><TR+><TD CLASS="indexentry"+>-!-</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3A-%21-"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>-/\-</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3A-%2F%5C-"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>-<-</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3A-%3C-"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>-<=-</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3A-%3C%3D-"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>-?-</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3A-%3F-"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>-\/-</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3A-%5C%2F-"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>/>/</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Boundaries.html#v%3A%2F%3E%2F"+>Data.Ranged.Boundaries</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>Boundary</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Boundaries.html#t%3ABoundary"+>Data.Ranged.Boundaries</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>BoundaryAbove</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Boundaries.html#v%3ABoundaryAbove"+>Data.Ranged.Boundaries</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>BoundaryAboveAll</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Boundaries.html#v%3ABoundaryAboveAll"+>Data.Ranged.Boundaries</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>BoundaryBelow</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Boundaries.html#v%3ABoundaryBelow"+>Data.Ranged.Boundaries</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>BoundaryBelowAll</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Boundaries.html#v%3ABoundaryBelowAll"+>Data.Ranged.Boundaries</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>DiscreteOrdered</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Boundaries.html#t%3ADiscreteOrdered"+>Data.Ranged.Boundaries</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>RSet</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#t%3ARSet"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry" COLSPAN="2"+>Range</TD+></TR+><TR+><TD CLASS="indexannot"+>1 (Type/Class)</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#t%3ARange"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexannot"+>2 (Data Constructor)</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3ARange"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>above</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Boundaries.html#v%3Aabove"+>Data.Ranged.Boundaries</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>adjacent</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Boundaries.html#v%3Aadjacent"+>Data.Ranged.Boundaries</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>boundedAdjacent</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Boundaries.html#v%3AboundedAdjacent"+>Data.Ranged.Boundaries</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>emptyRange</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3AemptyRange"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>enumAdjacent</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Boundaries.html#v%3AenumAdjacent"+>Data.Ranged.Boundaries</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>fullRange</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3AfullRange"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>makeRangedSet</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3AmakeRangedSet"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>normaliseRangeList</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3AnormaliseRangeList"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rSetDifference</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3ArSetDifference"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rSetEmpty</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3ArSetEmpty"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rSetFull</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3ArSetFull"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rSetHas</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3ArSetHas"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rSetIntersection</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3ArSetIntersection"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rSetIsEmpty</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3ArSetIsEmpty"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rSetIsSubset</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3ArSetIsSubset"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rSetIsSubsetStrict</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3ArSetIsSubsetStrict"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rSetNegation</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3ArSetNegation"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rSetRanges</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3ArSetRanges"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rSetUnfold</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3ArSetUnfold"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rSetUnion</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3ArSetUnion"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rSingleton</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3ArSingleton"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rangeDifference</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3ArangeDifference"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rangeEncloses</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3ArangeEncloses"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rangeHas</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3ArangeHas"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rangeIntersection</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3ArangeIntersection"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rangeIsEmpty</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3ArangeIsEmpty"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rangeListHas</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3ArangeListHas"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rangeLower</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3ArangeLower"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rangeOverlap</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3ArangeOverlap"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rangeSingletonValue</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3ArangeSingletonValue"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rangeUnion</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3ArangeUnion"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>rangeUpper</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3ArangeUpper"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>singletonRange</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-Ranges.html#v%3AsingletonRange"+>Data.Ranged.Ranges</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>unsafeRangedSet</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3AunsafeRangedSet"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+><TR+><TD CLASS="indexentry"+>validRangeList</TD+><TD CLASS="indexlinks"+><A HREF="Data-Ranged-RangedSet.html#v%3AvalidRangeList"+>Data.Ranged.RangedSet</A+>, Data.Ranged</TD+></TR+></TABLE+></TD+></TR+></TABLE+></BODY+></HTML+>
+ Doc/index.html view
@@ -0,0 +1,120 @@+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">+<!--Rendered using the Haskell Html Library v0.2-->+<HTML+><HEAD+><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"+><TITLE+></TITLE+><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"+><SCRIPT SRC="haddock.js" TYPE="text/javascript"+></SCRIPT+></HEAD+><BODY+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="topbar"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD+><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "+></TD+><TD CLASS="title"+></TD+><TD CLASS="topbut"+><A HREF="index.html"+>Contents</A+></TD+><TD CLASS="topbut"+><A HREF="doc-index.html"+>Index</A+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="section1"+>Modules</TD+></TR+><TR+><TD+><TABLE CLASS="vanilla2" CELLSPACING="0" CELLPADDING="0"+><TR+><TD STYLE="width: 50em"+><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'n:0')" ALT="show/hide"+>Data</TD+><TD+></TD+><TD+></TD+></TR+><TR+><TD STYLE="padding: 0; padding-left: 2em" COLSPAN="3"+><TABLE CLASS="vanilla2" CELLSPACING="0" CELLPADDING="0" ID="n:0" STYLE="display:block;"+><TR+><TD STYLE="width: 48em"+><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'n:1')" ALT="show/hide"+><A HREF="Data-Ranged.html"+>Data.Ranged</A+></TD+><TD+></TD+><TD+></TD+></TR+><TR+><TD STYLE="padding: 0; padding-left: 2em" COLSPAN="3"+><TABLE CLASS="vanilla2" CELLSPACING="0" CELLPADDING="0" ID="n:1" STYLE="display:block;"+><TR+><TD STYLE="padding-left: 1.25em;width: 46em"+><A HREF="Data-Ranged-Boundaries.html"+>Data.Ranged.Boundaries</A+></TD+><TD+></TD+><TD+></TD+></TR+><TR+><TD STYLE="padding-left: 1.25em;width: 46em"+><A HREF="Data-Ranged-RangedSet.html"+>Data.Ranged.RangedSet</A+></TD+><TD+></TD+><TD+></TD+></TR+><TR+><TD STYLE="padding-left: 1.25em;width: 46em"+><A HREF="Data-Ranged-Ranges.html"+>Data.Ranged.Ranges</A+></TD+><TD+></TD+><TD+></TD+></TR+></TABLE+></TD+></TR+></TABLE+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="botbar"+>Produced by <A HREF="http://www.haskell.org/haddock/"+>Haddock</A+> version 0.8</TD+></TR+></TABLE+></BODY+></HTML+>
+ INSTALL.txt view
@@ -0,0 +1,14 @@+As user, from within the project directory:++ runghc Setup.hs configure+ runghc Setup.hs build++As root or administrator:++ runghc Setup.hs install+ +If you have Haddock then generate the documentation with:++ runghc Setup.hs haddock+ +If you use Hugs then type "runhugs" instead of "runghc".
+ LICENSE.txt view
@@ -0,0 +1,30 @@+Copyright (c) 2005, Paul Johnson+All rights reserved.++Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions +are met:++ * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer.+ + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in + the documentation and/or other materials provided with the + distribution.+ + * Neither the name of the Ranged Sets project nor the names of its + contributors may be used to endorse or promote products derived + from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR +CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY +OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.txt view
@@ -0,0 +1,119 @@+Ranged Sets for Haskell+=======================++Ranged sets allow programming with sets of values that are described+by a list of ranges. A value is a member of the set if it lies within+one of the ranges. The ranges in a set are ordered and+non-overlapping, so the standard set operations can be implemented by+merge algorithms in O(n) time.++License+-------++Currently the Ranged Set library is under the BSD 3 license. This is+a very permissive license. I am hoping that Ranged Sets will+eventually become part of the Base library, and at that point the+implementation will have to be issued under the same license as the+rest of the library (which in practice probably means different+licenses for different compiler versions). As I understand it the BSD+3 license will allow this without me having to get either assignment+of copyright or explicit permission from everyone who submits+contributions.+++Boundaries+----------++Module Data.Ranged.Boundaries defines the Boundary type. A boundary+divides an ordered type into values above and below the boundary. No+value can ever sit on a boundary.++Two boundaries are equal if they divide the values at the same point.+This definition of equality causes an implementation problem because+some types are "discrete". For instance there is no value between the+characters 'a' and 'b', or between the integers 3 and 4. However+there are values between 3.0 and 4.0. Similarly for strings, there+are values between "a" and "b" such as "aa", "ab", and so on. This is+important because "BoundaryAbove 3" is equal to "BoundaryBelow 4". 3+is below both boundaries, and 4 is above both. Hence they divide the+integers at the same place. But on the other hand "BoundaryAbove 3.0"+and "BoundaryBelow 4.0" are not equal because 3.5 is above the first+and below the second.++To solve this the DiscreteOrdered class is defined, which provides a+function "adjacent". Two values x1 and x3 are adjacent if x1 < x3 and+there does not exist an x2 such that x1 < x2 < x3. This provides the+distinction necessary for boundary equality to be defined for all+ordered types. The ordered types from the prelude are instances of+DiscreteOrdered, and others can be added by defining "adjacent". The+functions "enumAdjacent" and "boundedAdjacent" are provided for+instances of Enum and Bounded. Lists and tuples of DiscreteOrdered+types are also instances of DiscreteOrdered.++This approach was suggested by Ben Rudiak-Gould on+comp.lang.functional.++In theory the Float and Double types should be treated as enumerated+because they are held in fixed-length data fields, and hence must have+pairs of values that are adjacent. However they are treated as+continuous here for two reasons:++ * The Float and Double types are practical approximations to Real+ numbers, which are continuous. Hence it makes sense for Float+ and Double to pretend to share this property.++ * There is no standard way to determine the adjacency of Float and+ Double values in Haskell. "succ 3.0" returns 4.0, which is not+ appropriate here.+++Ranges+------++Module Data.Ranged.Ranges defines the Range type. A range has a lower and an+upper Boundary.++Set-like operations are defined on ranges, but they return variable+numbers of results, and hence return either Maybe Range or [Range].+++RangedSet+---------++Module Data.Ranged.RangedSet defines the RSet type. This is the+actual ranged set type. It is constructed from a list of ranges.+There are two functions to do this:++ * makeRangedSet takes a finite list of ranges that may overlap or be+ out of order. It sorts them and merges overlapping ranges using+ the normaliseRangeList function.+ + * unsafeRangedSet takes a list of ranges that must be in order and not+ overlapping. The behaviour of the resulting set is not defined if this+ precondition is not met.+ +In theory the standard QuickCheck generator for RSet could generate an+arbitrary list of ranges and then normalise them, but in practice this+tends to produce a very small number of ranges because of the high+probability of overlaps. So instead an arbitrary list of boundaries+is generated and these are then sorted and paired off into+non-overlapping ranges.+++Infinite Sets+-------------++In theory, thanks to lazy evaluation ranged sets can handle infinite+lists of ranges. These are known as "infinite sets". Note that this+is not the same as a set with a final upper bound of "AboveAll".++Unfortunately there is no simple way to guarantee that computations on+infinite sets will terminate. So infinite sets are not supported.++QuickCheck+----------++All the types in the Ranged Set library are instances of Arbitrary from+the QuickCheck library, and the source code includes a number of+important properties for Ranges and RSets defined using QuickCheck. These +can be treated as a formal specification of the properties of these types.
+ Ranged-sets.cabal view
@@ -0,0 +1,17 @@+Name: Ranged-sets+Version: 0.1.0+License: BSD3+License-file: LICENSE.txt+Copyright: Paul Johnson, 2005, 2006, 2007+Author: Paul Johnson+Homepage: http://ranged-sets.sourceforge.net/+Maintainer: paul@cogito.org.uk+Stability: beta+Category: Data +Build-Depends: base+Synopsis: Ranged sets for Haskell+Description: A ranged set is an ordered list of ranges. This allows sets + such as all reals x such that + (0.25 < x <= 0.75 or 1.4 <= x < 2.3 or 4.5 < x).+Exposed-modules: Data.Ranged, Data.Ranged.Boundaries, Data.Ranged.Ranges, Data.Ranged.RangedSet+Extra-source-files: README.txt CHANGES.txt INSTALL.txt TODO.txt Doc/Data-Ranged-Boundaries.html Doc/Data-Ranged.html Doc/Data-Ranged-RangedSet.html Doc/Data-Ranged-Ranges.html Doc/doc-index.html Doc/index.html
+ Setup.hs view
@@ -0,0 +1,6 @@++module Main where++import Distribution.Simple++main = defaultMain
+ TODO.txt view
@@ -0,0 +1,13 @@+Things to do:+ +* Test with yhc.++* Define ranges of times and dates. The set of all Mondays, for instance,+ or the set of all second weeks in the month. Any such functions would+ have to take a start date because the only alternative is to start+ with the epoch, and that would not be efficient. The existing date-time+ functions look a bit clunky for this job, but the proposals of+ Ashley Yakeley at http://semantic.org/TimeLib/ look more suitable.+++