-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Interval datatype, interval arithmetic and interval-based containers -- -- Interval datatype, interval arithmetic and interval-based containers -- for Haskell. Unlike the intervals package -- (http://hackage.haskell.org/package/intervals), this package -- provides both open and closed intervals and is intended to be used -- with exact number types such as Rational and Integer. @package data-interval @version 2.0.1 -- | Interval datatype and interval arithmetic. -- -- Unlike the intervals package -- (http://hackage.haskell.org/package/intervals), this module -- provides both open and closed intervals and is intended to be used -- with Rational. -- -- For the purpose of abstract interpretation, it might be convenient to -- use Lattice instance. See also lattices package -- (http://hackage.haskell.org/package/lattices). module Data.Interval -- | The intervals (i.e. connected and convex subsets) over real -- numbers R. data Interval r -- | Boundary of an interval may be open (excluding an endpoint) or closed -- (including an endpoint). data Boundary Open :: Boundary Closed :: Boundary -- | smart constructor for Interval interval :: Ord r => (Extended r, Boundary) -> (Extended r, Boundary) -> Interval r -- | closed interval [l,u] (<=..<=) :: Ord r => Extended r -> Extended r -> Interval r infix 5 <=..<= -- | left-open right-closed interval (l,u] (<..<=) :: Ord r => Extended r -> Extended r -> Interval r infix 5 <..<= -- | left-closed right-open interval [l, u) (<=..<) :: Ord r => Extended r -> Extended r -> Interval r infix 5 <=..< -- | open interval (l, u) (<..<) :: Ord r => Extended r -> Extended r -> Interval r infix 5 <..< -- | whole real number line (-∞, ∞) whole :: Ord r => Interval r -- | empty (contradicting) interval empty :: Ord r => Interval r -- | singleton set [x,x] singleton :: Ord r => r -> Interval r -- | Is the interval empty? null :: Ord r => Interval r -> Bool -- | Is the interval single point? isSingleton :: Ord r => Interval r -> Bool -- | Is the element in the interval? member :: Ord r => r -> Interval r -> Bool -- | Is the element not in the interval? notMember :: Ord r => r -> Interval r -> Bool -- | Is this a subset? (i1 `isSubsetOf` i2) tells whether -- i1 is a subset of i2. isSubsetOf :: Ord r => Interval r -> Interval r -> Bool -- | Is this a proper subset? (i.e. a subset but not equal). isProperSubsetOf :: Ord r => Interval r -> Interval r -> Bool -- | Does the union of two range form a connected set? -- -- Since 1.3.0 isConnected :: Ord r => Interval r -> Interval r -> Bool -- | Lower endpoint (i.e. greatest lower bound) of the interval. -- -- lowerBound :: Interval r -> Extended r -- | Upper endpoint (i.e. least upper bound) of the interval. -- -- upperBound :: Interval r -> Extended r -- | Lower endpoint (i.e. greatest lower bound) of the interval, -- together with Boundary information. The result is convenient to -- use as an argument for interval. lowerBound' :: Interval r -> (Extended r, Boundary) -- | Upper endpoint (i.e. least upper bound) of the interval, -- together with Boundary information. The result is convenient to -- use as an argument for interval. upperBound' :: Interval r -> (Extended r, Boundary) -- | Width of a interval. Width of an unbounded interval is -- undefined. width :: (Num r, Ord r) => Interval r -> r -- | For all x in X, y in Y. x -- < y? ( Interval r -> Interval r -> Bool infix 4 x in X, y in Y. x -- <= y? (<=!) :: Ord r => Interval r -> Interval r -> Bool infix 4 <=! -- | For all x in X, y in Y. x -- == y? (==!) :: Ord r => Interval r -> Interval r -> Bool infix 4 ==! -- | For all x in X, y in Y. x -- >= y? (>=!) :: Ord r => Interval r -> Interval r -> Bool infix 4 >=! -- | For all x in X, y in Y. x -- > y? (>!) :: Ord r => Interval r -> Interval r -> Bool infix 4 >! -- | For all x in X, y in Y. x -- /= y? -- -- Since 1.0.1 (/=!) :: Ord r => Interval r -> Interval r -> Bool infix 4 /=! -- | Does there exist an x in X, y in Y -- such that x < y? ( Interval r -> Interval r -> Bool infix 4 x in X, y in Y -- such that x <= y? (<=?) :: Ord r => Interval r -> Interval r -> Bool infix 4 <=? -- | Does there exist an x in X, y in Y -- such that x == y? -- -- Since 1.0.0 (==?) :: Ord r => Interval r -> Interval r -> Bool infix 4 ==? -- | Does there exist an x in X, y in Y -- such that x >= y? (>=?) :: Ord r => Interval r -> Interval r -> Bool infix 4 >=? -- | Does there exist an x in X, y in Y -- such that x > y? (>?) :: Ord r => Interval r -> Interval r -> Bool infix 4 >? -- | Does there exist an x in X, y in Y -- such that x /= y? -- -- Since 1.0.1 (/=?) :: Ord r => Interval r -> Interval r -> Bool infix 4 /=? -- | Does there exist an x in X, y in Y -- such that x < y? -- -- Since 1.0.0 ( Interval r -> Interval r -> Maybe (r, r) infix 4 x in X, y in Y -- such that x <= y? -- -- Since 1.0.0 (<=??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r) infix 4 <=?? -- | Does there exist an x in X, y in Y -- such that x == y? -- -- Since 1.0.0 (==??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r) infix 4 ==?? -- | Does there exist an x in X, y in Y -- such that x >= y? -- -- Since 1.0.0 (>=??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r) infix 4 >=?? -- | Does there exist an x in X, y in Y -- such that x > y? -- -- Since 1.0.0 (>??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r) infix 4 >?? -- | Does there exist an x in X, y in Y -- such that x /= y? -- -- Since 1.0.1 (/=??) :: (Real r, Fractional r) => Interval r -> Interval r -> Maybe (r, r) infix 4 /=?? -- | intersection of two intervals intersection :: forall r. Ord r => Interval r -> Interval r -> Interval r -- | intersection of a list of intervals. -- -- Since 0.6.0 intersections :: Ord r => [Interval r] -> Interval r -- | convex hull of two intervals hull :: forall r. Ord r => Interval r -> Interval r -> Interval r -- | convex hull of a list of intervals. -- -- Since 0.6.0 hulls :: Ord r => [Interval r] -> Interval r -- | mapMonotonic f i is the image of i under f, -- where f must be a strict monotone function. mapMonotonic :: (Ord a, Ord b) => (a -> b) -> Interval a -> Interval b -- | pick up an element from the interval if the interval is not empty. pickup :: (Real r, Fractional r) => Interval r -> Maybe r -- | simplestRationalWithin returns the simplest rational number -- within the interval. -- -- A rational number y is said to be simpler than another -- y' if -- -- -- -- (see also approxRational) -- -- Since 0.4.0 simplestRationalWithin :: RealFrac r => Interval r -> Maybe Rational instance GHC.Classes.Ord r => Algebra.Lattice.Lattice (Data.Interval.Internal.Interval r) instance GHC.Classes.Ord r => Algebra.Lattice.BoundedJoinSemiLattice (Data.Interval.Internal.Interval r) instance GHC.Classes.Ord r => Algebra.Lattice.BoundedMeetSemiLattice (Data.Interval.Internal.Interval r) instance (GHC.Classes.Ord r, GHC.Show.Show r) => GHC.Show.Show (Data.Interval.Internal.Interval r) instance (GHC.Classes.Ord r, GHC.Read.Read r) => GHC.Read.Read (Data.Interval.Internal.Interval r) instance (GHC.Num.Num r, GHC.Classes.Ord r) => GHC.Num.Num (Data.Interval.Internal.Interval r) instance (GHC.Real.Real r, GHC.Real.Fractional r) => GHC.Real.Fractional (Data.Interval.Internal.Interval r) -- | Interval datatype and interval arithmetic over integers. -- -- Since 1.2.0 -- -- For the purpose of abstract interpretation, it might be convenient to -- use Lattice instance. See also lattices package -- (http://hackage.haskell.org/package/lattices). module Data.IntegerInterval -- | The intervals (i.e. connected and convex subsets) over integers -- (Z). data IntegerInterval -- | Boundary of an interval may be open (excluding an endpoint) or closed -- (including an endpoint). data Boundary Open :: Boundary Closed :: Boundary -- | smart constructor for IntegerInterval interval :: (Extended Integer, Boundary) -> (Extended Integer, Boundary) -> IntegerInterval -- | closed interval [l,u] (<=..<=) :: Extended Integer -> Extended Integer -> IntegerInterval infix 5 <=..<= -- | left-open right-closed interval (l,u] (<..<=) :: Extended Integer -> Extended Integer -> IntegerInterval infix 5 <..<= -- | left-closed right-open interval [l, u) (<=..<) :: Extended Integer -> Extended Integer -> IntegerInterval infix 5 <=..< -- | open interval (l, u) (<..<) :: Extended Integer -> Extended Integer -> IntegerInterval infix 5 <..< -- | whole real number line (-∞, ∞) whole :: IntegerInterval -- | empty (contradicting) interval empty :: IntegerInterval -- | singleton set [x,x] singleton :: Integer -> IntegerInterval -- | Is the interval empty? null :: IntegerInterval -> Bool -- | Is the interval single point? isSingleton :: IntegerInterval -> Bool -- | Is the element in the interval? member :: Integer -> IntegerInterval -> Bool -- | Is the element not in the interval? notMember :: Integer -> IntegerInterval -> Bool -- | Is this a subset? (i1 `isSubsetOf` i2) tells whether -- i1 is a subset of i2. isSubsetOf :: IntegerInterval -> IntegerInterval -> Bool -- | Is this a proper subset? (i.e. a subset but not equal). isProperSubsetOf :: IntegerInterval -> IntegerInterval -> Bool -- | Lower endpoint (i.e. greatest lower bound) of the interval. -- -- lowerBound :: IntegerInterval -> Extended Integer -- | Upper endpoint (i.e. least upper bound) of the interval. -- -- upperBound :: IntegerInterval -> Extended Integer -- | lowerBound of the interval and whether it is included in the -- interval. The result is convenient to use as an argument for -- interval. lowerBound' :: IntegerInterval -> (Extended Integer, Boundary) -- | upperBound of the interval and whether it is included in the -- interval. The result is convenient to use as an argument for -- interval. upperBound' :: IntegerInterval -> (Extended Integer, Boundary) -- | Width of a interval. Width of an unbounded interval is -- undefined. width :: IntegerInterval -> Integer -- | For all x in X, y in Y. x -- < y? ( IntegerInterval -> Bool infix 4 x in X, y in Y. x -- <= y? (<=!) :: IntegerInterval -> IntegerInterval -> Bool infix 4 <=! -- | For all x in X, y in Y. x -- == y? (==!) :: IntegerInterval -> IntegerInterval -> Bool infix 4 ==! -- | For all x in X, y in Y. x -- >= y? (>=!) :: IntegerInterval -> IntegerInterval -> Bool infix 4 >=! -- | For all x in X, y in Y. x -- > y? (>!) :: IntegerInterval -> IntegerInterval -> Bool infix 4 >! -- | For all x in X, y in Y. x -- /= y? (/=!) :: IntegerInterval -> IntegerInterval -> Bool infix 4 /=! -- | Does there exist an x in X, y in Y -- such that x < y? ( IntegerInterval -> Bool infix 4 x in X, y in Y -- such that x <= y? (<=?) :: IntegerInterval -> IntegerInterval -> Bool infix 4 <=? -- | Does there exist an x in X, y in Y -- such that x == y? (==?) :: IntegerInterval -> IntegerInterval -> Bool infix 4 ==? -- | Does there exist an x in X, y in Y -- such that x >= y? (>=?) :: IntegerInterval -> IntegerInterval -> Bool infix 4 >=? -- | Does there exist an x in X, y in Y -- such that x > y? (>?) :: IntegerInterval -> IntegerInterval -> Bool infix 4 >? -- | Does there exist an x in X, y in Y -- such that x /= y? (/=?) :: IntegerInterval -> IntegerInterval -> Bool infix 4 /=? -- | Does there exist an x in X, y in Y -- such that x < y? ( IntegerInterval -> Maybe (Integer, Integer) infix 4 x in X, y in Y -- such that x <= y? (<=??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer) infix 4 <=?? -- | Does there exist an x in X, y in Y -- such that x == y? (==??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer) infix 4 ==?? -- | Does there exist an x in X, y in Y -- such that x >= y? (>=??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer) infix 4 >=?? -- | Does there exist an x in X, y in Y -- such that x > y? (>??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer) infix 4 >?? -- | Does there exist an x in X, y in Y -- such that x /= y? (/=??) :: IntegerInterval -> IntegerInterval -> Maybe (Integer, Integer) infix 4 /=?? -- | intersection of two intervals intersection :: IntegerInterval -> IntegerInterval -> IntegerInterval -- | intersection of a list of intervals. intersections :: [IntegerInterval] -> IntegerInterval -- | convex hull of two intervals hull :: IntegerInterval -> IntegerInterval -> IntegerInterval -- | convex hull of a list of intervals. hulls :: [IntegerInterval] -> IntegerInterval -- | mapMonotonic f i is the image of i under f, -- where f must be a strict monotone function. mapMonotonic :: (Integer -> Integer) -> IntegerInterval -> IntegerInterval -- | pick up an element from the interval if the interval is not empty. pickup :: IntegerInterval -> Maybe Integer -- | simplestIntegerWithin returns the simplest rational number -- within the interval. -- -- An integer y is said to be simpler than another -- y' if -- -- -- -- (see also approxRational and simplestRationalWithin) simplestIntegerWithin :: IntegerInterval -> Maybe Integer -- | Convert the interval to Interval data type. toInterval :: Real r => IntegerInterval -> Interval r -- | Conversion from Interval data type. fromInterval :: Interval Integer -> IntegerInterval -- | Given a Interval I over R, compute the smallest -- IntegerInterval J such that I ⊆ J. fromIntervalOver :: RealFrac r => Interval r -> IntegerInterval -- | Given a Interval I over R, compute the largest -- IntegerInterval J such that J ⊆ I. fromIntervalUnder :: RealFrac r => Interval r -> IntegerInterval instance Algebra.Lattice.Lattice Data.IntegerInterval.Internal.IntegerInterval instance Algebra.Lattice.BoundedJoinSemiLattice Data.IntegerInterval.Internal.IntegerInterval instance Algebra.Lattice.BoundedMeetSemiLattice Data.IntegerInterval.Internal.IntegerInterval instance GHC.Show.Show Data.IntegerInterval.Internal.IntegerInterval instance GHC.Read.Read Data.IntegerInterval.Internal.IntegerInterval instance GHC.Num.Num Data.IntegerInterval.Internal.IntegerInterval -- | Interval datatype and interval arithmetic. module Data.IntervalSet -- | A set comprising zero or more non-empty, disconnected -- intervals. -- -- Any connected intervals are merged together, and empty intervals are -- ignored. data IntervalSet r -- | whole real number line (-∞, ∞) whole :: Ord r => IntervalSet r -- | empty interval set empty :: Ord r => IntervalSet r -- | single interval singleton :: Ord r => Interval r -> IntervalSet r -- | Is the interval set empty? null :: IntervalSet r -> Bool -- | Is the element in the interval set? member :: Ord r => r -> IntervalSet r -> Bool -- | Is the element not in the interval set? notMember :: Ord r => r -> IntervalSet r -> Bool -- | Is this a subset? (is1 `isSubsetOf` is2) tells whether -- is1 is a subset of is2. isSubsetOf :: Ord r => IntervalSet r -> IntervalSet r -> Bool -- | Is this a proper subset? (i.e. a subset but not equal). isProperSubsetOf :: Ord r => IntervalSet r -> IntervalSet r -> Bool -- | convex hull of a set of intervals. span :: Ord r => IntervalSet r -> Interval r -- | Complement the interval set. complement :: Ord r => IntervalSet r -> IntervalSet r -- | Insert a new interval into the interval set. insert :: Ord r => Interval r -> IntervalSet r -> IntervalSet r -- | Delete an interval from the interval set. delete :: Ord r => Interval r -> IntervalSet r -> IntervalSet r -- | union of two interval sets union :: Ord r => IntervalSet r -> IntervalSet r -> IntervalSet r -- | union of a list of interval sets unions :: Ord r => [IntervalSet r] -> IntervalSet r -- | intersection of two interval sets intersection :: Ord r => IntervalSet r -> IntervalSet r -> IntervalSet r -- | intersection of a list of interval sets intersections :: Ord r => [IntervalSet r] -> IntervalSet r -- | difference of two interval sets difference :: Ord r => IntervalSet r -> IntervalSet r -> IntervalSet r -- | Build a interval set from a list of intervals. fromList :: Ord r => [Interval r] -> IntervalSet r -- | Convert a interval set into a list of intervals. toList :: Ord r => IntervalSet r -> [Interval r] -- | Convert a interval set into a list of intervals in ascending order. toAscList :: Ord r => IntervalSet r -> [Interval r] -- | Convert a interval set into a list of intervals in descending order. toDescList :: Ord r => IntervalSet r -> [Interval r] -- | Build a map from an ascending list of intervals. The precondition -- is not checked. fromAscList :: Ord r => [Interval r] -> IntervalSet r instance GHC.Classes.Eq r => GHC.Classes.Eq (Data.IntervalSet.IntervalSet r) instance (GHC.Classes.Ord r, GHC.Show.Show r) => GHC.Show.Show (Data.IntervalSet.IntervalSet r) instance (GHC.Classes.Ord r, GHC.Read.Read r) => GHC.Read.Read (Data.IntervalSet.IntervalSet r) instance (GHC.Classes.Ord r, Data.Data.Data r) => Data.Data.Data (Data.IntervalSet.IntervalSet r) instance Control.DeepSeq.NFData r => Control.DeepSeq.NFData (Data.IntervalSet.IntervalSet r) instance Data.Hashable.Class.Hashable r => Data.Hashable.Class.Hashable (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => Algebra.Lattice.Lattice (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => Algebra.Lattice.BoundedJoinSemiLattice (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => Algebra.Lattice.BoundedMeetSemiLattice (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => GHC.Base.Monoid (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => GHC.Base.Semigroup (Data.IntervalSet.IntervalSet r) instance (GHC.Num.Num r, GHC.Classes.Ord r) => GHC.Num.Num (Data.IntervalSet.IntervalSet r) instance (GHC.Real.Real r, GHC.Real.Fractional r) => GHC.Real.Fractional (Data.IntervalSet.IntervalSet r) instance GHC.Classes.Ord r => GHC.Exts.IsList (Data.IntervalSet.IntervalSet r) -- | Mapping from intervals to values. -- -- API of this module is strict in both the keys and the values. If you -- need value-lazy maps, use Data.IntervalMap.Lazy instead. The -- IntervalMap type itself is shared between the lazy and strict -- modules, meaning that the same IntervalMap value can be passed -- to functions in both modules (although that is rarely needed). -- -- These modules are intended to be imported qualified, to avoid name -- clashes with Prelude functions, e.g. -- -- 
--   import Data.IntervalMap.Strict (IntervalMap)
--   import qualified Data.IntervalMap.Strict as IntervalMap
--
module Data.IntervalMap.Strict -- | A Map from non-empty, disjoint intervals over k to values a. -- -- Unlike IntervalSet, IntervalMap never merge adjacent -- mappings, even if adjacent intervals are connected and mapped to the -- same value. data IntervalMap r a -- | Find the value at a key. Calls error when the element can not -- be found. (!) :: Ord k => IntervalMap k a -> k -> a infixl 9 ! -- | Same as difference. (\\) :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a infixl 9 \\ -- | Is the map empty? null :: Ord k => IntervalMap k a -> Bool -- | Is the key a member of the map? See also notMember. member :: Ord k => k -> IntervalMap k a -> Bool -- | Is the key not a member of the map? See also member. notMember :: Ord k => k -> IntervalMap k a -> Bool -- | Lookup the value at a key in the map. -- -- The function will return the corresponding value as (Just -- value), or Nothing if the key isn't in the map. lookup :: Ord k => k -> IntervalMap k a -> Maybe a -- | The expression (findWithDefault def k map) returns the -- value at key k or returns default value def when the -- key is not in the map. findWithDefault :: Ord k => a -> k -> IntervalMap k a -> a -- | convex hull of key intervals. span :: Ord k => IntervalMap k a -> Interval k -- | The map that maps whole range of k to a. whole :: Ord k => a -> IntervalMap k a -- | The empty map. empty :: Ord k => IntervalMap k a -- | A map with a single interval. singleton :: Ord k => Interval k -> a -> IntervalMap k a -- | insert a new key and value in the map. If the key is already present -- in the map, the associated value is replaced with the supplied value. insert :: Ord k => Interval k -> a -> IntervalMap k a -> IntervalMap k a -- | Insert with a function, combining new value and old value. -- insertWith f key value mp will insert the pair -- (interval, value) into mp. If the interval overlaps with -- existing entries, the value for the entry is replace with (f -- new_value old_value). insertWith :: Ord k => (a -> a -> a) -> Interval k -> a -> IntervalMap k a -> IntervalMap k a -- | Delete an interval and its value from the map. When the interval does -- not overlap with the map, the original map is returned. delete :: Ord k => Interval k -> IntervalMap k a -> IntervalMap k a -- | Update a value at a specific interval with the result of the provided -- function. When the interval does not overlatp with the map, the -- original map is returned. adjust :: Ord k => (a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k a -- | The expression (update f i map) updates the value -- x at i (if it is in the map). If (f x) is -- Nothing, the element is deleted. If it is (Just -- y), the key i is bound to the new value y. update :: Ord k => (a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a -- | The expression (alter f i map) alters the value -- x at i, or absence thereof. alter can be used -- to insert, delete, or update a value in a IntervalMap. alter :: Ord k => (Maybe a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a -- | The expression (union t1 t2) takes the left-biased -- union of t1 and t2. It prefers t1 when -- overlapping keys are encountered, union :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | Union with a combining function. unionWith :: Ord k => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | The union of a list of maps: (unions == foldl -- union empty). unions :: Ord k => [IntervalMap k a] -> IntervalMap k a -- | The union of a list of maps, with a combining operation: -- (unionsWith f == foldl (unionWith f) -- empty). unionsWith :: Ord k => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a -- | Intersection of two maps. Return data in the first map for the keys -- existing in both maps. intersection :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | Intersection with a combining function. intersectionWith :: Ord k => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c -- | Return elements of the first map not existing in the second map. difference :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a -- | Map a function over all values in the map. map :: (a -> b) -> IntervalMap k a -> IntervalMap k b -- | mapKeysMonotonic f s is the map obtained by applying -- f to each key of s. f must be strictly -- monotonic. That is, for any values x and y, if -- x < y then f x < f y. mapKeysMonotonic :: forall k1 k2 a. (Ord k1, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a -- | Return all elements of the map in the ascending order of their keys. elems :: IntervalMap k a -> [a] -- | Return all keys of the map in ascending order. Subject to list keys :: IntervalMap k a -> [Interval k] -- | An alias for toAscList. Return all key/value pairs in the map -- in ascending key order. assocs :: IntervalMap k a -> [(Interval k, a)] -- | The set of all keys of the map. keysSet :: Ord k => IntervalMap k a -> IntervalSet k -- | Build a map from a list of key/value pairs. If the list contains more -- than one value for the same key, the last value for the key is -- retained. fromList :: Ord k => [(Interval k, a)] -> IntervalMap k a -- | Build a map from a list of key/value pairs with a combining function. fromListWith :: Ord k => (a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a -- | Convert the map to a list of key/value pairs. toList :: IntervalMap k a -> [(Interval k, a)] -- | Convert the map to a list of key/value pairs where the keys are in -- ascending order. toAscList :: IntervalMap k a -> [(Interval k, a)] -- | Convert the map to a list of key/value pairs where the keys are in -- descending order. toDescList :: IntervalMap k a -> [(Interval k, a)] -- | Filter all values that satisfy some predicate. filter :: Ord k => (a -> Bool) -> IntervalMap k a -> IntervalMap k a -- | The expression (split i map) is a triple -- (map1,map2,map3) where the keys in map1 are smaller -- than i, the keys in map2 are included in i, -- and the keys in map3 are larger than i. split :: Ord k => Interval k -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a, IntervalMap k a) -- | This function is defined as (isSubmapOf = -- isSubmapOfBy (==)). isSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool -- | The expression (isSubmapOfBy f t1 t2) returns -- True if all keys in t1 are in tree t2, and -- when f returns True when applied to their respective -- values. isSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool -- | Is this a proper submap? (ie. a submap but not equal). Defined as -- (isProperSubmapOf = isProperSubmapOfBy (==)). isProperSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool -- | Is this a proper submap? (ie. a submap but not equal). The expression -- (isProperSubmapOfBy f m1 m2) returns True when -- m1 and m2 are not equal, all keys in m1 are -- in m2, and when f returns True when applied -- to their respective values. isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool -- | Mapping from intervals to values. -- -- API of this module is strict in the keys, but lazy in the values. If -- you need value-strict maps, use Data.IntervalMap.Strict -- instead. The IntervalMap type itself is shared between the lazy -- and strict modules, meaning that the same IntervalMap value can -- be passed to functions in both modules (although that is rarely -- needed). -- -- These modules are intended to be imported qualified, to avoid name -- clashes with Prelude functions, e.g. -- -- 
--   import Data.IntervalMap.Lazy (IntervalMap)
--   import qualified Data.IntervalMap.Lazy as IntervalMap
--
module Data.IntervalMap.Lazy -- | A Map from non-empty, disjoint intervals over k to values a. -- -- Unlike IntervalSet, IntervalMap never merge adjacent -- mappings, even if adjacent intervals are connected and mapped to the -- same value. data IntervalMap r a -- | Find the value at a key. Calls error when the element can not -- be found. (!) :: Ord k => IntervalMap k a -> k -> a infixl 9 ! -- | Same as difference. (\\) :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a infixl 9 \\ -- | Is the map empty? null :: Ord k => IntervalMap k a -> Bool -- | Is the key a member of the map? See also notMember. member :: Ord k => k -> IntervalMap k a -> Bool -- | Is the key not a member of the map? See also member. notMember :: Ord k => k -> IntervalMap k a -> Bool -- | Lookup the value at a key in the map. -- -- The function will return the corresponding value as (Just -- value), or Nothing if the key isn't in the map. lookup :: Ord k => k -> IntervalMap k a -> Maybe a -- | The expression (findWithDefault def k map) returns the -- value at key k or returns default value def when the -- key is not in the map. findWithDefault :: Ord k => a -> k -> IntervalMap k a -> a -- | convex hull of key intervals. span :: Ord k => IntervalMap k a -> Interval k -- | The map that maps whole range of k to a. whole :: Ord k => a -> IntervalMap k a -- | The empty map. empty :: Ord k => IntervalMap k a -- | A map with a single interval. singleton :: Ord k => Interval k -> a -> IntervalMap k a -- | insert a new key and value in the map. If the key is already present -- in the map, the associated value is replaced with the supplied value. insert :: Ord k => Interval k -> a -> IntervalMap k a -> IntervalMap k a -- | Insert with a function, combining new value and old value. -- insertWith f key value mp will insert the pair -- (interval, value) into mp. If the interval overlaps with -- existing entries, the value for the entry is replace with (f -- new_value old_value). insertWith :: Ord k => (a -> a -> a) -> Interval k -> a -> IntervalMap k a -> IntervalMap k a -- | Delete an interval and its value from the map. When the interval does -- not overlap with the map, the original map is returned. delete :: Ord k => Interval k -> IntervalMap k a -> IntervalMap k a -- | Update a value at a specific interval with the result of the provided -- function. When the interval does not overlatp with the map, the -- original map is returned. adjust :: Ord k => (a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k a -- | The expression (update f i map) updates the value -- x at i (if it is in the map). If (f x) is -- Nothing, the element is deleted. If it is (Just -- y), the key i is bound to the new value y. update :: Ord k => (a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a -- | The expression (alter f i map) alters the value -- x at i, or absence thereof. alter can be used -- to insert, delete, or update a value in a IntervalMap. alter :: Ord k => (Maybe a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a -- | The expression (union t1 t2) takes the left-biased -- union of t1 and t2. It prefers t1 when -- overlapping keys are encountered, union :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | Union with a combining function. unionWith :: Ord k => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | The union of a list of maps: (unions == foldl -- union empty). unions :: Ord k => [IntervalMap k a] -> IntervalMap k a -- | The union of a list of maps, with a combining operation: -- (unionsWith f == foldl (unionWith f) -- empty). unionsWith :: Ord k => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a -- | Intersection of two maps. Return data in the first map for the keys -- existing in both maps. intersection :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | Intersection with a combining function. intersectionWith :: Ord k => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c -- | Return elements of the first map not existing in the second map. difference :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a -- | Map a function over all values in the map. map :: (a -> b) -> IntervalMap k a -> IntervalMap k b -- | mapKeysMonotonic f s is the map obtained by applying -- f to each key of s. f must be strictly -- monotonic. That is, for any values x and y, if -- x < y then f x < f y. mapKeysMonotonic :: forall k1 k2 a. (Ord k1, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a -- | Return all elements of the map in the ascending order of their keys. elems :: IntervalMap k a -> [a] -- | Return all keys of the map in ascending order. Subject to list keys :: IntervalMap k a -> [Interval k] -- | An alias for toAscList. Return all key/value pairs in the map -- in ascending key order. assocs :: IntervalMap k a -> [(Interval k, a)] -- | The set of all keys of the map. keysSet :: Ord k => IntervalMap k a -> IntervalSet k -- | Build a map from a list of key/value pairs. If the list contains more -- than one value for the same key, the last value for the key is -- retained. fromList :: Ord k => [(Interval k, a)] -> IntervalMap k a -- | Build a map from a list of key/value pairs with a combining function. fromListWith :: Ord k => (a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a -- | Convert the map to a list of key/value pairs. toList :: IntervalMap k a -> [(Interval k, a)] -- | Convert the map to a list of key/value pairs where the keys are in -- ascending order. toAscList :: IntervalMap k a -> [(Interval k, a)] -- | Convert the map to a list of key/value pairs where the keys are in -- descending order. toDescList :: IntervalMap k a -> [(Interval k, a)] -- | Filter all values that satisfy some predicate. filter :: Ord k => (a -> Bool) -> IntervalMap k a -> IntervalMap k a -- | The expression (split i map) is a triple -- (map1,map2,map3) where the keys in map1 are smaller -- than i, the keys in map2 are included in i, -- and the keys in map3 are larger than i. split :: Ord k => Interval k -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a, IntervalMap k a) -- | This function is defined as (isSubmapOf = -- isSubmapOfBy (==)). isSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool -- | The expression (isSubmapOfBy f t1 t2) returns -- True if all keys in t1 are in tree t2, and -- when f returns True when applied to their respective -- values. isSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool -- | Is this a proper submap? (ie. a submap but not equal). Defined as -- (isProperSubmapOf = isProperSubmapOfBy (==)). isProperSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool -- | Is this a proper submap? (ie. a submap but not equal). The expression -- (isProperSubmapOfBy f m1 m2) returns True when -- m1 and m2 are not equal, all keys in m1 are -- in m2, and when f returns True when applied -- to their respective values. isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool