-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Containers for intervals, with efficient search.
--   
--   Ordered containers of intervals, with efficient search for all keys
--   containing a point or overlapping an interval. See the example code on
--   the home page for a quick introduction.
@package IntervalMap
@version 0.5.0.0


-- | A conservative implementation of Intervals, mostly for use as keys in
--   a <a>IntervalMap</a>.
--   
--   This should really be a typeclass, so you could have a tuple be an
--   instance of Interval, but that is currently not possible in standard
--   Haskell.
--   
--   The contructor names of the half-open intervals seem somewhat clumsy,
--   and I'm open to suggestions for better names.
module Data.IntervalMap.Interval

-- | Intervals with endpoints of type <tt>a</tt>.
--   
--   <a>Read</a> and <a>Show</a> use mathematical notation with square
--   brackets for closed and parens for open intervals. This is better for
--   human readability, but is not a valid Haskell expression. Closed
--   intervals look like a list, open intervals look like a tuple, and
--   half-open intervals look like mismatched parens.
data Interval a

-- | Including lower bound, excluding upper
IntervalCO :: !a -> !a -> Interval a

-- | Closed at both ends
ClosedInterval :: !a -> !a -> Interval a

-- | Open at both ends
OpenInterval :: !a -> !a -> Interval a

-- | Excluding lower bound, including upper
IntervalOC :: !a -> !a -> Interval a

-- | Get the lower bound.
lowerBound :: Interval a -> a

-- | Get the upper bound.
upperBound :: Interval a -> a

-- | Does the interval include its lower bound?
leftClosed :: Interval a -> Bool

-- | Does the interval include its upper bound?
rightClosed :: Interval a -> Bool

-- | Is the interval empty?
isEmpty :: (Ord a) => Interval a -> Bool

-- | Do the two intervals overlap?
overlaps :: (Ord a) => Interval a -> Interval a -> Bool

-- | Does the first interval completely contain the second?
subsumes :: (Ord a) => Interval a -> Interval a -> Bool

-- | Interval strictly before another? True if the upper bound of the first
--   interval is below the lower bound of the second.
before :: Ord a => Interval a -> Interval a -> Bool

-- | Interval strictly after another? Same as 'flip before'.
after :: Ord a => Interval a -> Interval a -> Bool

-- | Like <a>compare</a>, but considering the upper bound first.
compareByUpper :: Ord a => Interval a -> Interval a -> Ordering

-- | If the intervals overlap combine them into one.
combine :: (Ord a) => Interval a -> Interval a -> Maybe (Interval a)

-- | Is a point strictly less than lower bound?
below :: (Ord a) => a -> Interval a -> Bool

-- | Does the interval contain a given point?
inside :: (Ord a) => a -> Interval a -> Bool

-- | Is a point strictly greater than upper bound?
above :: (Ord a) => a -> Interval a -> Bool
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.IntervalMap.Interval.Interval a)
instance GHC.Show.Show a => GHC.Show.Show (Data.IntervalMap.Interval.Interval a)
instance GHC.Read.Read a => GHC.Read.Read (Data.IntervalMap.Interval.Interval a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.IntervalMap.Interval.Interval a)
instance GHC.Base.Functor Data.IntervalMap.Interval.Interval
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.IntervalMap.Interval.Interval a)


-- | Type class for IntervalMap keys.
--   
--   As there is no sensible default, no instances for prelude types are
--   provided (E.g. you might want to have tuples as closed intervals in
--   one case, and open in another).
--   
--   Empty intervals, i.e. intervals where 'lowerBound &gt;= upperBound'
--   should be avoided if possible. If you must use empty intervals, you
--   need to provide implementations for all operations, as the default
--   implementations do not necessarily work correctly. for example, the
--   default implementation of <a>inside</a> returns <a>True</a> if the
--   point is equal to the lowerBound of a left-closed interval even if it
--   is larger than the upper bound.
module Data.IntervalMap.Generic.Interval

-- | Intervals with endpoints of type <tt>e</tt>. A minimal instance
--   declaration for a closed interval needs only to define
--   <a>lowerBound</a> and <a>upperBound</a>.
class Ord e => Interval i e | i -> e where leftClosed _ = True rightClosed _ = True a `before` b = upperBound a < lowerBound b || (upperBound a == lowerBound b && not (rightClosed a && leftClosed b)) a `after` b = b `before` a a `subsumes` b = (lowerBound a < lowerBound b || (lowerBound a == lowerBound b && (leftClosed a || not (leftClosed b)))) && (upperBound a > upperBound b || (upperBound a == upperBound b && (rightClosed a || not (rightClosed b)))) a `overlaps` b = (lowerBound a < upperBound b || (lowerBound a == upperBound b && leftClosed a && rightClosed b)) && (upperBound a > lowerBound b || (upperBound a == lowerBound b && rightClosed a && leftClosed b)) p `below` i = case compare p (lowerBound i) of { LT -> True EQ -> not (leftClosed i) GT -> False } p `above` i = case compare p (upperBound i) of { LT -> False EQ -> not (rightClosed i) GT -> True } p `inside` i = not ((p `above` i) || (p `below` i)) isEmpty i | leftClosed i && rightClosed i = lowerBound i > upperBound i | otherwise = lowerBound i >= upperBound i

-- | lower bound
lowerBound :: Interval i e => i -> e

-- | upper bound
upperBound :: Interval i e => i -> e

-- | Does the interval include its lower bound? Default is True for all
--   values, i.e. closed intervals.
leftClosed :: Interval i e => i -> Bool

-- | Does the interval include its upper bound bound? Default is True for
--   all values, i.e. closed intervals.
rightClosed :: Interval i e => i -> Bool

-- | Interval strictly before another? True if the upper bound of the first
--   interval is below the lower bound of the second.
before :: Interval i e => i -> i -> Bool

-- | Interval strictly after another? Same as 'flip before'.
after :: Interval i e => i -> i -> Bool

-- | Does the first interval completely contain the second?
subsumes :: Interval i e => i -> i -> Bool

-- | Do the two intervals overlap?
overlaps :: Interval i e => i -> i -> Bool

-- | Is a point strictly less than lower bound?
below :: Interval i e => e -> i -> Bool

-- | Is a point strictly greater than upper bound?
above :: Interval i e => e -> i -> Bool

-- | Does the interval contain a given point?
inside :: Interval i e => e -> i -> Bool

-- | Is the interval empty?
isEmpty :: Interval i e => i -> Bool
genericEquals :: (Interval i e, Eq e) => i -> i -> Bool
genericCompare :: (Interval i e, Ord e) => i -> i -> Ordering
instance GHC.Classes.Ord a => Data.IntervalMap.Generic.Interval.Interval (Data.IntervalMap.Interval.Interval a) a


-- | An implementation of maps from intervals to values. The key intervals
--   may overlap, and the implementation contains efficient search
--   functions for all keys containing a point or overlapping an interval.
--   Closed, open, and half-open intervals can be contained in the same
--   map.
--   
--   This module implements the same functions as
--   <a>Data.IntervalMap.Generic.Strict</a>, but with value-lazy semantics.
module Data.IntervalMap.Generic.Lazy

-- | Intervals with endpoints of type <tt>e</tt>. A minimal instance
--   declaration for a closed interval needs only to define
--   <a>lowerBound</a> and <a>upperBound</a>.
class Ord e => Interval i e | i -> e where leftClosed _ = True rightClosed _ = True a `before` b = upperBound a < lowerBound b || (upperBound a == lowerBound b && not (rightClosed a && leftClosed b)) a `after` b = b `before` a a `subsumes` b = (lowerBound a < lowerBound b || (lowerBound a == lowerBound b && (leftClosed a || not (leftClosed b)))) && (upperBound a > upperBound b || (upperBound a == upperBound b && (rightClosed a || not (rightClosed b)))) a `overlaps` b = (lowerBound a < upperBound b || (lowerBound a == upperBound b && leftClosed a && rightClosed b)) && (upperBound a > lowerBound b || (upperBound a == lowerBound b && rightClosed a && leftClosed b)) p `below` i = case compare p (lowerBound i) of { LT -> True EQ -> not (leftClosed i) GT -> False } p `above` i = case compare p (upperBound i) of { LT -> False EQ -> not (rightClosed i) GT -> True } p `inside` i = not ((p `above` i) || (p `below` i)) isEmpty i | leftClosed i && rightClosed i = lowerBound i > upperBound i | otherwise = lowerBound i >= upperBound i

-- | lower bound
lowerBound :: Interval i e => i -> e

-- | upper bound
upperBound :: Interval i e => i -> e

-- | Does the interval include its lower bound? Default is True for all
--   values, i.e. closed intervals.
leftClosed :: Interval i e => i -> Bool

-- | Does the interval include its upper bound bound? Default is True for
--   all values, i.e. closed intervals.
rightClosed :: Interval i e => i -> Bool

-- | Interval strictly before another? True if the upper bound of the first
--   interval is below the lower bound of the second.
before :: Interval i e => i -> i -> Bool

-- | Interval strictly after another? Same as 'flip before'.
after :: Interval i e => i -> i -> Bool

-- | Does the first interval completely contain the second?
subsumes :: Interval i e => i -> i -> Bool

-- | Do the two intervals overlap?
overlaps :: Interval i e => i -> i -> Bool

-- | Is a point strictly less than lower bound?
below :: Interval i e => e -> i -> Bool

-- | Is a point strictly greater than upper bound?
above :: Interval i e => e -> i -> Bool

-- | Does the interval contain a given point?
inside :: Interval i e => e -> i -> Bool

-- | Is the interval empty?
isEmpty :: Interval i e => i -> Bool

-- | A map from intervals of type <tt>k</tt> to values of type <tt>v</tt>.
data IntervalMap k v

-- | <i>O(log n)</i>. Lookup value for given key. Calls <a>error</a> if the
--   key is not in the map.
--   
--   Use <a>lookup</a> or <a>findWithDefault</a> instead of this function,
--   unless you are absolutely sure that the key is present in the map.
(!) :: (Interval k e, Ord k) => IntervalMap k v -> k -> v

-- | Same as <a>difference</a>.
(\\) :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(1)</i>. Is the map empty?
null :: IntervalMap k v -> Bool

-- | <i>O(n)</i>. Number of keys in the map.
--   
--   Caution: unlike <a>size</a>, which takes constant time, this is linear
--   in the number of keys!
size :: IntervalMap k v -> Int

-- | <i>O(log n)</i>. Does the map contain the given key? See also
--   <a>notMember</a>.
member :: (Ord k) => k -> IntervalMap k v -> Bool

-- | <i>O(log n)</i>. Does the map not contain the given key? See also
--   <a>member</a>.
notMember :: (Ord k) => k -> IntervalMap k v -> Bool

-- | <i>O(log n)</i>. Look up the given key in the map, returning the value
--   <tt>(<a>Just</a> value)</tt>, or <a>Nothing</a> if the key is not in
--   the map.
lookup :: (Ord k) => k -> IntervalMap k v -> Maybe v

-- | <i>O(log n)</i>. The expression <tt>(<a>findWithDefault</a> def k
--   map)</tt> returns the value at key <tt>k</tt> or returns default value
--   <tt>def</tt> when the key is not in the map.
findWithDefault :: Ord k => a -> k -> IntervalMap k a -> a

-- | Return the submap of key intervals containing the given point. This is
--   the second element of the value of <a>splitAt</a>:
--   
--   <pre>
--   m `containing` p == let (_,m',_) = m `splitAt` p in m'
--   </pre>
--   
--   <i>O(n)</i>, since potentially all keys could contain the point.
--   <i>O(log n)</i> average case. This is also the worst case for maps
--   containing no overlapping keys.
containing :: (Interval k e) => IntervalMap k v -> e -> IntervalMap k v

-- | Return the submap of key intervals overlapping (intersecting) the
--   given interval. This is the second element of the value of
--   <a>splitIntersecting</a>:
--   
--   <pre>
--   m `intersecting` i == let (_,m',_) = m `splitIntersecting` i in m'
--   </pre>
--   
--   <i>O(n)</i>, since potentially all keys could intersect the interval.
--   <i>O(log n)</i> average case, if few keys intersect the interval.
intersecting :: (Interval k e) => IntervalMap k v -> k -> IntervalMap k v

-- | Return the submap of key intervals completely inside the given
--   interval.
--   
--   <i>O(n)</i>, since potentially all keys could be inside the interval.
--   <i>O(log n)</i> average case, if few keys are inside the interval.
within :: (Interval k e) => IntervalMap k v -> k -> IntervalMap k v

-- | <i>O(1)</i>. The empty map.
empty :: IntervalMap k v

-- | <i>O(1)</i>. A map with one entry.
singleton :: k -> v -> IntervalMap k v

-- | <i>O(log n)</i>. Insert a new key/value pair. If the map already
--   contains the key, its value is changed to the new value.
insert :: (Interval k e, Ord k) => k -> v -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Insert with a function, combining new value and old
--   value. <tt><a>insertWith</a> f key value mp</tt> will insert the pair
--   (key, value) into <tt>mp</tt> if key does not exist in the map. If the
--   key does exist, the function will insert the pair <tt>(key, f
--   new_value old_value)</tt>.
insertWith :: (Interval k e, Ord k) => (v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Insert with a function, combining key, new value and
--   old value. <tt><a>insertWithKey</a> f key value mp</tt> will insert
--   the pair (key, value) into <tt>mp</tt> if key does not exist in the
--   map. If the key does exist, the function will insert the pair
--   <tt>(key, f key new_value old_value)</tt>. Note that the key passed to
--   f is the same key passed to <a>insertWithKey</a>.
insertWithKey :: (Interval k e, Ord k) => (k -> v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Combine insert with old values retrieval.
insertLookupWithKey :: (Interval k e, Ord k) => (k -> v -> v -> v) -> k -> v -> IntervalMap k v -> (Maybe v, IntervalMap k v)

-- | <i>O(log n)</i>. Delete a key from the map. If the map does not
--   contain the key, it is returned unchanged.
delete :: (Interval k e, Ord k) => k -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update a value at a specific key with the result of
--   the provided function. When the key is not a member of the map, the
--   original map is returned.
adjust :: Ord k => (a -> a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. Adjust a value at a specific key. When the key is not
--   a member of the map, the original map is returned.
adjustWithKey :: Ord k => (k -> a -> a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. The expression (<tt><a>update</a> f k map</tt>)
--   updates the value <tt>x</tt> at <tt>k</tt> (if it is in the map). If
--   (<tt>f x</tt>) is <a>Nothing</a>, the element is deleted. If it is
--   (<tt><a>Just</a> y</tt>), the key <tt>k</tt> is bound to the new value
--   <tt>y</tt>.
update :: (Interval k e, Ord k) => (a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. The expression (<tt><a>updateWithKey</a> f k
--   map</tt>) updates the value <tt>x</tt> at <tt>k</tt> (if it is in the
--   map). If (<tt>f k x</tt>) is <a>Nothing</a>, the element is deleted.
--   If it is (<tt><a>Just</a> y</tt>), the key <tt>k</tt> is bound to the
--   new value <tt>y</tt>.
updateWithKey :: (Interval k e, Ord k) => (k -> a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. Lookup and update. See also <a>updateWithKey</a>. The
--   function returns changed value, if it is updated. Returns the original
--   key value if the map entry is deleted.
updateLookupWithKey :: (Interval k e, Ord k) => (k -> a -> Maybe a) -> k -> IntervalMap k a -> (Maybe a, IntervalMap k a)

-- | <i>O(log n)</i>. The expression (<tt><a>alter</a> f k map</tt>) alters
--   the value <tt>x</tt> at <tt>k</tt>, or absence thereof. <a>alter</a>
--   can be used to insert, delete, or update a value in a <tt>Map</tt>. In
--   short : <tt><a>lookup</a> k (<a>alter</a> f k m) = f (<a>lookup</a> k
--   m)</tt>.
alter :: (Interval k e, Ord k) => (Maybe a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n+m)</i>. The expression (<tt><a>union</a> t1 t2</tt>) takes the
--   left-biased union of <tt>t1</tt> and <tt>t2</tt>. It prefers
--   <tt>t1</tt> when duplicate keys are encountered, i.e.
--   (<tt><a>union</a> == <a>unionWith</a> <a>const</a></tt>).
union :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n+m)</i>. Union with a combining function.
unionWith :: (Interval k e, Ord k) => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n+m)</i>. Union with a combining function.
unionWithKey :: (Interval k e, Ord k) => (k -> a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | The union of a list of maps: (<tt><a>unions</a> == <a>foldl</a>
--   <a>union</a> <a>empty</a></tt>).
unions :: (Interval k e, Ord k) => [IntervalMap k a] -> IntervalMap k a

-- | The union of a list of maps, with a combining operation:
--   (<tt><a>unionsWith</a> f == <a>foldl</a> (<a>unionWith</a> f)
--   <a>empty</a></tt>).
unionsWith :: (Interval k e, Ord k) => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a

-- | <i>O(n+m)</i>. Difference of two maps. Return elements of the first
--   map not existing in the second map.
difference :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Difference with a combining function. When two equal
--   keys are encountered, the combining function is applied to the values
--   of these keys. If it returns <a>Nothing</a>, the element is discarded
--   (proper set difference). If it returns (<tt><a>Just</a> y</tt>), the
--   element is updated with a new value <tt>y</tt>.
differenceWith :: (Interval k e, Ord k) => (a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Difference with a combining function. When two equal
--   keys are encountered, the combining function is applied to the key and
--   both values. If it returns <a>Nothing</a>, the element is discarded
--   (proper set difference). If it returns (<tt><a>Just</a> y</tt>), the
--   element is updated with a new value <tt>y</tt>.
differenceWithKey :: (Interval k e, Ord k) => (k -> a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Intersection of two maps. Return data in the first map
--   for the keys existing in both maps. (<tt><a>intersection</a> m1 m2 ==
--   <a>intersectionWith</a> <a>const</a> m1 m2</tt>).
intersection :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Intersection with a combining function.
intersectionWith :: (Interval k e, Ord k) => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c

-- | <i>O(n+m)</i>. Intersection with a combining function.
intersectionWithKey :: (Interval k e, Ord k) => (k -> a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c

-- | <i>O(n)</i>. Map a function over all values in the map.
map :: (a -> b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. Map a function over all values in the map.
mapWithKey :: (k -> a -> b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. The function <a>mapAccum</a> threads an accumulating
--   argument through the map in ascending order of keys.
mapAccum :: (a -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)

-- | <i>O(n)</i>. The function <a>mapAccumWithKey</a> threads an
--   accumulating argument through the map in ascending order of keys.
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)

-- | <i>O(n)</i>. The function <a>mapAccumRWithKey</a> threads an
--   accumulating argument through the map in descending order of keys.
mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)

-- | <i>O(n log n)</i>. <tt><a>mapKeys</a> f s</tt> is the map obtained by
--   applying <tt>f</tt> to each key of <tt>s</tt>.
--   
--   The size of the result may be smaller if <tt>f</tt> maps two or more
--   distinct keys to the same new key. In this case the value at the
--   smallest of these keys is retained.
mapKeys :: (Interval k2 e, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

-- | <i>O(n log n)</i>. <tt><a>mapKeysWith</a> c f s</tt> is the map
--   obtained by applying <tt>f</tt> to each key of <tt>s</tt>.
--   
--   The size of the result may be smaller if <tt>f</tt> maps two or more
--   distinct keys to the same new key. In this case the associated values
--   will be combined using <tt>c</tt>.
mapKeysWith :: (Interval k2 e, Ord k2) => (a -> a -> a) -> (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

-- | <i>O(n)</i>. <tt><a>mapKeysMonotonic</a> f s == <a>mapKeys</a> f
--   s</tt>, but works only when <tt>f</tt> is strictly monotonic. That is,
--   for any values <tt>x</tt> and <tt>y</tt>, if <tt>x</tt> &lt;
--   <tt>y</tt> then <tt>f x</tt> &lt; <tt>f y</tt>. <i>The precondition is
--   not checked.</i>
mapKeysMonotonic :: (Interval k2 e, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

-- | <i>O(n)</i>. Fold the values in the map using the given
--   right-associative binary operator, such that <tt><a>foldr</a> f z ==
--   <a>foldr</a> f z . <a>elems</a></tt>.
foldr :: (a -> b -> b) -> b -> IntervalMap k a -> b

-- | <i>O(n)</i>. Fold the values in the map using the given
--   left-associative binary operator, such that <tt><a>foldl</a> f z ==
--   <a>foldl</a> f z . <a>elems</a></tt>.
foldl :: (b -> a -> b) -> b -> IntervalMap k a -> b

-- | <i>O(n)</i>. Fold the keys and values in the map using the given
--   right-associative binary operator, such that <tt><a>foldrWithKey</a> f
--   z == <a>foldr</a> (<a>uncurry</a> f) z . <a>toAscList</a></tt>.
foldrWithKey :: (k -> v -> a -> a) -> a -> IntervalMap k v -> a

-- | <i>O(n)</i>. Fold the keys and values in the map using the given
--   left-associative binary operator, such that <tt><a>foldlWithKey</a> f
--   z == <a>foldl</a> (\z' (kx, x) -&gt; f z' kx x) z .
--   <a>toAscList</a></tt>.
foldlWithKey :: (a -> k -> v -> a) -> a -> IntervalMap k v -> a

-- | <i>O(n log n)</i>. Build a new map by combining successive key/value
--   pairs.
flattenWith :: (Ord k, Interval k e) => ((k, v) -> (k, v) -> Maybe (k, v)) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(n)</i>. Build a new map by combining successive key/value pairs.
--   Same as <a>flattenWith</a>, but works only when the combining
--   functions returns strictly monotonic key values.
flattenWithMonotonic :: (Interval k e) => ((k, v) -> (k, v) -> Maybe (k, v)) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(n)</i>. List of all values in the map, in ascending order of
--   their keys.
elems :: IntervalMap k v -> [v]

-- | <i>O(n)</i>. List of all keys in the map, in ascending order.
keys :: IntervalMap k v -> [k]

-- | <i>O(n)</i>. Set of the keys.
keysSet :: (Ord k) => IntervalMap k v -> Set k

-- | Same as <a>toAscList</a>.
assocs :: IntervalMap k v -> [(k, v)]

-- | <i>O(n)</i>. The list of all key/value pairs contained in the map, in
--   no particular order.
toList :: IntervalMap k v -> [(k, v)]

-- | <i>O(n log n)</i>. Build a map from a list of key/value pairs. See
--   also <a>fromAscList</a>. If the list contains more than one value for
--   the same key, the last value for the key is retained.
fromList :: (Interval k e, Ord k) => [(k, v)] -> IntervalMap k v

-- | <i>O(n log n)</i>. Build a map from a list of key/value pairs with a
--   combining function. See also <a>fromAscListWith</a>.
fromListWith :: (Interval k e, Ord k) => (a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n log n)</i>. Build a map from a list of key/value pairs with a
--   combining function. See also <a>fromAscListWith</a>.
fromListWithKey :: (Interval k e, Ord k) => (k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n)</i>. The list of all key/value pairs contained in the map, in
--   ascending order of keys.
toAscList :: IntervalMap k v -> [(k, v)]

-- | <i>O(n)</i>. The list of all key/value pairs contained in the map, in
--   descending order of keys.
toDescList :: IntervalMap k v -> [(k, v)]

-- | <i>O(n)</i>. Build a map from an ascending list in linear time. <i>The
--   precondition (input list is ascending) is not checked.</i>
fromAscList :: (Interval k e, Eq k) => [(k, v)] -> IntervalMap k v

-- | <i>O(n)</i>. Build a map from an ascending list in linear time with a
--   combining function for equal keys. <i>The precondition (input list is
--   ascending) is not checked.</i>
fromAscListWith :: (Interval k e, Eq k) => (a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n)</i>. Build a map from an ascending list in linear time with a
--   combining function for equal keys. <i>The precondition (input list is
--   ascending) is not checked.</i>
fromAscListWithKey :: (Interval k e, Eq k) => (k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n)</i>. Build a map from an ascending list of elements with
--   distinct keys in linear time. <i>The precondition is not checked.</i>
fromDistinctAscList :: (Interval k e) => [(k, v)] -> IntervalMap k v

-- | <i>O(n)</i>. Filter values satisfying a predicate.
filter :: (Interval k e) => (a -> Bool) -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n)</i>. Filter keys/values satisfying a predicate.
filterWithKey :: (Interval k e) => (k -> a -> Bool) -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n)</i>. Partition the map according to a predicate. The first map
--   contains all elements that satisfy the predicate, the second all
--   elements that fail the predicate. See also <a>split</a>.
partition :: (Interval k e) => (a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)

-- | <i>O(n)</i>. Partition the map according to a predicate. The first map
--   contains all elements that satisfy the predicate, the second all
--   elements that fail the predicate. See also <a>split</a>.
partitionWithKey :: (Interval k e) => (k -> a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)

-- | <i>O(n)</i>. Map values and collect the <a>Just</a> results.
mapMaybe :: (Interval k e) => (a -> Maybe b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. Map keys/values and collect the <a>Just</a> results.
mapMaybeWithKey :: (Interval k e) => (k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. Map values and separate the <a>Left</a> and <a>Right</a>
--   results.
mapEither :: (Interval k e) => (a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)

-- | <i>O(n)</i>. Map keys/values and separate the <a>Left</a> and
--   <a>Right</a> results.
mapEitherWithKey :: (Interval i k) => (i -> a -> Either b c) -> IntervalMap i a -> (IntervalMap i b, IntervalMap i c)

-- | <i>O(n)</i>. The expression (<tt><a>split</a> k map</tt>) is a pair
--   <tt>(map1,map2)</tt> where the keys in <tt>map1</tt> are smaller than
--   <tt>k</tt> and the keys in <tt>map2</tt> larger than <tt>k</tt>. Any
--   key equal to <tt>k</tt> is found in neither <tt>map1</tt> nor
--   <tt>map2</tt>.
split :: (Interval i k, Ord i) => i -> IntervalMap i a -> (IntervalMap i a, IntervalMap i a)

-- | <i>O(n)</i>. The expression (<tt><a>splitLookup</a> k map</tt>) splits
--   a map just like <a>split</a> but also returns <tt><a>lookup</a> k
--   map</tt>.
splitLookup :: (Interval i k, Ord i) => i -> IntervalMap i a -> (IntervalMap i a, Maybe a, IntervalMap i a)

-- | <i>O(n)</i>. Split around a point. Splits the map into three submaps:
--   intervals below the point, intervals containing the point, and
--   intervals above the point.
splitAt :: (Interval i k, Ord i) => IntervalMap i a -> k -> (IntervalMap i a, IntervalMap i a, IntervalMap i a)

-- | <i>O(n)</i>. Split around an interval. Splits the set into three
--   subsets: intervals below the given interval, intervals intersecting
--   the given interval, and intervals above the given interval.
splitIntersecting :: (Interval i k, Ord i) => IntervalMap i a -> i -> (IntervalMap i a, IntervalMap i a, IntervalMap i a)

-- | <i>O(n+m)</i>. This function is defined as (<tt><a>isSubmapOf</a> =
--   <a>isSubmapOfBy</a> (==)</tt>).
isSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool

-- | <i>O(n+m)</i>. The expression (<tt><a>isSubmapOfBy</a> f t1 t2</tt>)
--   returns <a>True</a> if all keys in <tt>t1</tt> are in tree
--   <tt>t2</tt>, and <tt>f</tt> returns <a>True</a> when applied to their
--   respective values.
isSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool

-- | <i>O(n+m)</i>. Is this a proper submap? (ie. a submap but not equal).
--   Defined as (<tt><a>isProperSubmapOf</a> = <a>isProperSubmapOfBy</a>
--   (==)</tt>).
isProperSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool

-- | <i>O(n+m)</i>. Is this a proper submap? (ie. a submap but not equal).
--   The expression (<tt><a>isProperSubmapOfBy</a> f m1 m2</tt>) returns
--   <a>True</a> when <tt>m1</tt> and <tt>m2</tt> are not equal, all keys
--   in <tt>m1</tt> are in <tt>m2</tt>, and when <tt>f</tt> returns
--   <a>True</a> when applied to their respective values.
isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool

-- | <i>O(log n)</i>. Returns the smallest key and its associated value.
--   Calls <a>error</a> if the map is empty.
findMin :: IntervalMap k v -> (k, v)

-- | <i>O(log n)</i>. Returns the largest key and its associated value.
--   Calls <a>error</a> if the map is empty.
findMax :: IntervalMap k v -> (k, v)

-- | Returns the key with the largest endpoint and its associated value. If
--   there is more than one key with that endpoint, return the rightmost.
--   
--   <i>O(n)</i>, since all keys could have the same endpoint. <i>O(log
--   n)</i> average case.
findLast :: (Interval k e) => IntervalMap k v -> (k, v)

-- | <i>O(log n)</i>. Remove the smallest key from the map. Return the
--   empty map if the map is empty.
deleteMin :: (Interval k e, Ord k) => IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Remove the largest key from the map. Return the empty
--   map if the map is empty.
deleteMax :: (Interval k e, Ord k) => IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Delete and return the smallest key.
deleteFindMin :: (Interval k e, Ord k) => IntervalMap k v -> ((k, v), IntervalMap k v)

-- | <i>O(log n)</i>. Delete and return the largest key.
deleteFindMax :: (Interval k e, Ord k) => IntervalMap k v -> ((k, v), IntervalMap k v)

-- | <i>O(log n)</i>. Update or delete value at minimum key.
updateMin :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update or delete value at maximum key.
updateMax :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update or delete value at minimum key.
updateMinWithKey :: (Interval k e, Ord k) => (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update or delete value at maximum key.
updateMaxWithKey :: (Interval k e, Ord k) => (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Retrieves the value associated with minimal key of
--   the map, and the map stripped of that element, or <a>Nothing</a> if
--   passed an empty map.
minView :: (Interval k e, Ord k) => IntervalMap k a -> Maybe (a, IntervalMap k a)

-- | <i>O(log n)</i>. Retrieves the value associated with maximal key of
--   the map, and the map stripped of that element, or <a>Nothing</a> if
--   passed an empty map.
maxView :: (Interval k e, Ord k) => IntervalMap k a -> Maybe (a, IntervalMap k a)

-- | <i>O(log n)</i>. Retrieves the minimal (key,value) pair of the map,
--   and the map stripped of that element, or <a>Nothing</a> if passed an
--   empty map.
--   
--   <pre>
--   minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
--   minViewWithKey empty == Nothing
--   </pre>
minViewWithKey :: (Interval k e, Ord k) => IntervalMap k a -> Maybe ((k, a), IntervalMap k a)

-- | <i>O(log n)</i>. Retrieves the maximal (key,value) pair of the map,
--   and the map stripped of that element, or <a>Nothing</a> if passed an
--   empty map.
maxViewWithKey :: (Interval k e, Ord k) => IntervalMap k a -> Maybe ((k, a), IntervalMap k a)

-- | Check red-black-tree and interval search augmentation invariants. For
--   testing/debugging only.
valid :: (Interval i k, Ord i) => IntervalMap i v -> Bool

-- | The height of the tree. For testing/debugging only.
height :: IntervalMap k v -> Int

-- | The maximum height of a red-black tree with the given number of nodes.
--   For testing/debugging only.
maxHeight :: Int -> Int

-- | Tree statistics (size, height, maxHeight size). For testing/debugging
--   only.
showStats :: IntervalMap k a -> (Int, Int, Int)


-- | An implementation of maps from intervals to values. The key intervals
--   may overlap, and the implementation contains efficient search
--   functions for all keys containing a point or overlapping an interval.
--   Closed, open, and half-open intervals can be contained in the same
--   map.
--   
--   The functions in this module are strict in both the keys and the
--   values. If you need value-lazy maps, use <a>Data.IntervalMap.Lazy</a>
--   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).
--   
--   An IntervalMap cannot contain duplicate keys - if you need to map a
--   key to multiple values, use a collection as the value type, for
--   example: <tt>IntervalMap <i>k</i> [<i>v</i>]</tt>.
--   
--   It is an error to insert an empty interval into a map. This
--   precondition is not checked by the various construction functions.
--   
--   Since many function names (but not the type name) clash with
--   <i>Prelude</i> names, this module is usually imported
--   <tt>qualified</tt>, e.g.
--   
--   <pre>
--   import Data.Generic.IntervalMap.Strict (IntervalMap)
--   import qualified Data.Generic.IntervalMap.Strict as IM
--   </pre>
--   
--   It offers most of the same functions as <a>Map</a>, but the key type
--   must be an instance of <a>Interval</a>. Some functions differ in
--   asymptotic performance (for example <a>size</a>) or have not been
--   tuned for efficiency as much as their equivalents in <a>Map</a> (in
--   particular the various set functions).
--   
--   In addition, there are functions specific to maps of intervals, for
--   example to search for all keys containing a given point or contained
--   in a given interval.
--   
--   The implementation is a red-black tree augmented with the maximum
--   upper bound of all keys.
--   
--   Parts of this implementation are based on code from the <a>Map</a>
--   implementation, (c) Daan Leijen 2002, (c) Andriy Palamarchuk 2008. The
--   red-black tree deletion is based on code from llrbtree by Kazu
--   Yamamoto. Of course, any errors are mine.
module Data.IntervalMap.Generic.Strict

-- | Intervals with endpoints of type <tt>e</tt>. A minimal instance
--   declaration for a closed interval needs only to define
--   <a>lowerBound</a> and <a>upperBound</a>.
class Ord e => Interval i e | i -> e where leftClosed _ = True rightClosed _ = True a `before` b = upperBound a < lowerBound b || (upperBound a == lowerBound b && not (rightClosed a && leftClosed b)) a `after` b = b `before` a a `subsumes` b = (lowerBound a < lowerBound b || (lowerBound a == lowerBound b && (leftClosed a || not (leftClosed b)))) && (upperBound a > upperBound b || (upperBound a == upperBound b && (rightClosed a || not (rightClosed b)))) a `overlaps` b = (lowerBound a < upperBound b || (lowerBound a == upperBound b && leftClosed a && rightClosed b)) && (upperBound a > lowerBound b || (upperBound a == lowerBound b && rightClosed a && leftClosed b)) p `below` i = case compare p (lowerBound i) of { LT -> True EQ -> not (leftClosed i) GT -> False } p `above` i = case compare p (upperBound i) of { LT -> False EQ -> not (rightClosed i) GT -> True } p `inside` i = not ((p `above` i) || (p `below` i)) isEmpty i | leftClosed i && rightClosed i = lowerBound i > upperBound i | otherwise = lowerBound i >= upperBound i

-- | lower bound
lowerBound :: Interval i e => i -> e

-- | upper bound
upperBound :: Interval i e => i -> e

-- | Does the interval include its lower bound? Default is True for all
--   values, i.e. closed intervals.
leftClosed :: Interval i e => i -> Bool

-- | Does the interval include its upper bound bound? Default is True for
--   all values, i.e. closed intervals.
rightClosed :: Interval i e => i -> Bool

-- | Interval strictly before another? True if the upper bound of the first
--   interval is below the lower bound of the second.
before :: Interval i e => i -> i -> Bool

-- | Interval strictly after another? Same as 'flip before'.
after :: Interval i e => i -> i -> Bool

-- | Does the first interval completely contain the second?
subsumes :: Interval i e => i -> i -> Bool

-- | Do the two intervals overlap?
overlaps :: Interval i e => i -> i -> Bool

-- | Is a point strictly less than lower bound?
below :: Interval i e => e -> i -> Bool

-- | Is a point strictly greater than upper bound?
above :: Interval i e => e -> i -> Bool

-- | Does the interval contain a given point?
inside :: Interval i e => e -> i -> Bool

-- | Is the interval empty?
isEmpty :: Interval i e => i -> Bool

-- | A map from intervals of type <tt>k</tt> to values of type <tt>v</tt>.
data IntervalMap k v

-- | <i>O(log n)</i>. Lookup value for given key. Calls <a>error</a> if the
--   key is not in the map.
--   
--   Use <a>lookup</a> or <a>findWithDefault</a> instead of this function,
--   unless you are absolutely sure that the key is present in the map.
(!) :: (Interval k e, Ord k) => IntervalMap k v -> k -> v

-- | Same as <a>difference</a>.
(\\) :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(1)</i>. Is the map empty?
null :: IntervalMap k v -> Bool

-- | <i>O(n)</i>. Number of keys in the map.
--   
--   Caution: unlike <a>size</a>, which takes constant time, this is linear
--   in the number of keys!
size :: IntervalMap k v -> Int

-- | <i>O(log n)</i>. Does the map contain the given key? See also
--   <a>notMember</a>.
member :: (Ord k) => k -> IntervalMap k v -> Bool

-- | <i>O(log n)</i>. Does the map not contain the given key? See also
--   <a>member</a>.
notMember :: (Ord k) => k -> IntervalMap k v -> Bool

-- | <i>O(log n)</i>. Look up the given key in the map, returning the value
--   <tt>(<a>Just</a> value)</tt>, or <a>Nothing</a> if the key is not in
--   the map.
lookup :: (Ord k) => k -> IntervalMap k v -> Maybe v

-- | <i>O(log n)</i>. The expression <tt>(<a>findWithDefault</a> def k
--   map)</tt> returns the value at key <tt>k</tt> or returns default value
--   <tt>def</tt> when the key is not in the map.
--   
--   <pre>
--   findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
--   findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
--   </pre>
findWithDefault :: Ord k => a -> k -> IntervalMap k a -> a

-- | Return the submap of key intervals containing the given point. This is
--   the second element of the value of <a>splitAt</a>:
--   
--   <pre>
--   m `containing` p == let (_,m',_) = m `splitAt` p in m'
--   </pre>
--   
--   <i>O(n)</i>, since potentially all keys could contain the point.
--   <i>O(log n)</i> average case. This is also the worst case for maps
--   containing no overlapping keys.
containing :: (Interval k e) => IntervalMap k v -> e -> IntervalMap k v

-- | Return the submap of key intervals overlapping (intersecting) the
--   given interval. This is the second element of the value of
--   <a>splitIntersecting</a>:
--   
--   <pre>
--   m `intersecting` i == let (_,m',_) = m `splitIntersecting` i in m'
--   </pre>
--   
--   <i>O(n)</i>, since potentially all keys could intersect the interval.
--   <i>O(log n)</i> average case, if few keys intersect the interval.
intersecting :: (Interval k e) => IntervalMap k v -> k -> IntervalMap k v

-- | Return the submap of key intervals completely inside the given
--   interval.
--   
--   <i>O(n)</i>, since potentially all keys could be inside the interval.
--   <i>O(log n)</i> average case, if few keys are inside the interval.
within :: (Interval k e) => IntervalMap k v -> k -> IntervalMap k v

-- | <i>O(1)</i>. The empty map.
empty :: IntervalMap k v

-- | <i>O(1)</i>. A map with one entry.
singleton :: k -> v -> IntervalMap k v

-- | <i>O(log n)</i>. Insert a new key/value pair. If the map already
--   contains the key, its value is changed to the new value.
insert :: (Interval k e, Ord k) => k -> v -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Insert with a function, combining new value and old
--   value. <tt><a>insertWith</a> f key value mp</tt> will insert the pair
--   (key, value) into <tt>mp</tt> if key does not exist in the map. If the
--   key does exist, the function will insert the pair <tt>(key, f
--   new_value old_value)</tt>.
insertWith :: (Interval k e, Ord k) => (v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Insert with a function, combining key, new value and
--   old value. <tt><a>insertWithKey</a> f key value mp</tt> will insert
--   the pair (key, value) into <tt>mp</tt> if key does not exist in the
--   map. If the key does exist, the function will insert the pair
--   <tt>(key, f key new_value old_value)</tt>. Note that the key passed to
--   f is the same key passed to <a>insertWithKey</a>.
insertWithKey :: (Interval k e, Ord k) => (k -> v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Combine insert with old values retrieval.
insertLookupWithKey :: (Interval k e, Ord k) => (k -> v -> v -> v) -> k -> v -> IntervalMap k v -> (Maybe v, IntervalMap k v)

-- | <i>O(log n)</i>. Delete a key from the map. If the map does not
--   contain the key, it is returned unchanged.
delete :: (Interval k e, Ord k) => k -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update a value at a specific key with the result of
--   the provided function. When the key is not a member of the map, the
--   original map is returned.
adjust :: Ord k => (a -> a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. Adjust a value at a specific key. When the key is not
--   a member of the map, the original map is returned.
adjustWithKey :: Ord k => (k -> a -> a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. The expression (<tt><a>update</a> f k map</tt>)
--   updates the value <tt>x</tt> at <tt>k</tt> (if it is in the map). If
--   (<tt>f x</tt>) is <a>Nothing</a>, the element is deleted. If it is
--   (<tt><a>Just</a> y</tt>), the key <tt>k</tt> is bound to the new value
--   <tt>y</tt>.
update :: (Interval k e, Ord k) => (a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. The expression (<tt><a>updateWithKey</a> f k
--   map</tt>) updates the value <tt>x</tt> at <tt>k</tt> (if it is in the
--   map). If (<tt>f k x</tt>) is <a>Nothing</a>, the element is deleted.
--   If it is (<tt><a>Just</a> y</tt>), the key <tt>k</tt> is bound to the
--   new value <tt>y</tt>.
updateWithKey :: (Interval k e, Ord k) => (k -> a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. Lookup and update. See also <a>updateWithKey</a>. The
--   function returns changed value, if it is updated. Returns the original
--   key value if the map entry is deleted.
updateLookupWithKey :: (Interval k e, Ord k) => (k -> a -> Maybe a) -> k -> IntervalMap k a -> (Maybe a, IntervalMap k a)

-- | <i>O(log n)</i>. The expression (<tt><a>alter</a> f k map</tt>) alters
--   the value <tt>x</tt> at <tt>k</tt>, or absence thereof. <a>alter</a>
--   can be used to insert, delete, or update a value in a <tt>Map</tt>. In
--   short : <tt><a>lookup</a> k (<a>alter</a> f k m) = f (<a>lookup</a> k
--   m)</tt>.
alter :: (Interval k e, Ord k) => (Maybe a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n+m)</i>. The expression (<tt><a>union</a> t1 t2</tt>) takes the
--   left-biased union of <tt>t1</tt> and <tt>t2</tt>. It prefers
--   <tt>t1</tt> when duplicate keys are encountered, i.e.
--   (<tt><a>union</a> == <a>unionWith</a> <a>const</a></tt>).
union :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n+m)</i>. Union with a combining function.
unionWith :: (Interval k e, Ord k) => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n+m)</i>. Union with a combining function.
unionWithKey :: (Interval k e, Ord k) => (k -> a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | The union of a list of maps: (<tt><a>unions</a> == <a>foldl</a>
--   <a>union</a> <a>empty</a></tt>).
unions :: (Interval k e, Ord k) => [IntervalMap k a] -> IntervalMap k a

-- | The union of a list of maps, with a combining operation:
--   (<tt><a>unionsWith</a> f == <a>foldl</a> (<a>unionWith</a> f)
--   <a>empty</a></tt>).
unionsWith :: (Interval k e, Ord k) => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a

-- | <i>O(n+m)</i>. Difference of two maps. Return elements of the first
--   map not existing in the second map.
difference :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Difference with a combining function. When two equal
--   keys are encountered, the combining function is applied to the values
--   of these keys. If it returns <a>Nothing</a>, the element is discarded
--   (proper set difference). If it returns (<tt><a>Just</a> y</tt>), the
--   element is updated with a new value <tt>y</tt>.
differenceWith :: (Interval k e, Ord k) => (a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Difference with a combining function. When two equal
--   keys are encountered, the combining function is applied to the key and
--   both values. If it returns <a>Nothing</a>, the element is discarded
--   (proper set difference). If it returns (<tt><a>Just</a> y</tt>), the
--   element is updated with a new value <tt>y</tt>.
differenceWithKey :: (Interval k e, Ord k) => (k -> a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Intersection of two maps. Return data in the first map
--   for the keys existing in both maps. (<tt><a>intersection</a> m1 m2 ==
--   <a>intersectionWith</a> <a>const</a> m1 m2</tt>).
intersection :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Intersection with a combining function.
intersectionWith :: (Interval k e, Ord k) => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c

-- | <i>O(n+m)</i>. Intersection with a combining function.
intersectionWithKey :: (Interval k e, Ord k) => (k -> a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c

-- | <i>O(n)</i>. Map a function over all values in the map.
map :: (a -> b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. Map a function over all values in the map.
mapWithKey :: (k -> a -> b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. The function <a>mapAccum</a> threads an accumulating
--   argument through the map in ascending order of keys.
--   
--   <pre>
--   let f a b = (a ++ b, b ++ "X")
--   mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
--   </pre>
mapAccum :: (a -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)

-- | <i>O(n)</i>. The function <a>mapAccumWithKey</a> threads an
--   accumulating argument through the map in ascending order of keys.
--   
--   <pre>
--   let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
--   mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
--   </pre>
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)

-- | <i>O(n)</i>. The function <a>mapAccumRWithKey</a> threads an
--   accumulating argument through the map in descending order of keys.
mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)

-- | <i>O(n log n)</i>. <tt><a>mapKeys</a> f s</tt> is the map obtained by
--   applying <tt>f</tt> to each key of <tt>s</tt>.
--   
--   The size of the result may be smaller if <tt>f</tt> maps two or more
--   distinct keys to the same new key. In this case the value at the
--   smallest of these keys is retained.
mapKeys :: (Interval k2 e, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

-- | <i>O(n log n)</i>. <tt><a>mapKeysWith</a> c f s</tt> is the map
--   obtained by applying <tt>f</tt> to each key of <tt>s</tt>.
--   
--   The size of the result may be smaller if <tt>f</tt> maps two or more
--   distinct keys to the same new key. In this case the associated values
--   will be combined using <tt>c</tt>.
mapKeysWith :: (Interval k2 e, Ord k2) => (a -> a -> a) -> (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

-- | <i>O(n)</i>. <tt><a>mapKeysMonotonic</a> f s == <a>mapKeys</a> f
--   s</tt>, but works only when <tt>f</tt> is strictly monotonic. That is,
--   for any values <tt>x</tt> and <tt>y</tt>, if <tt>x</tt> &lt;
--   <tt>y</tt> then <tt>f x</tt> &lt; <tt>f y</tt>. <i>The precondition is
--   not checked.</i>
mapKeysMonotonic :: (Interval k2 e, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

-- | <i>O(n)</i>. Fold the values in the map using the given
--   right-associative binary operator, such that <tt><a>foldr</a> f z ==
--   <a>foldr</a> f z . <a>elems</a></tt>.
foldr :: (a -> b -> b) -> b -> IntervalMap k a -> b

-- | <i>O(n)</i>. Fold the values in the map using the given
--   left-associative binary operator, such that <tt><a>foldl</a> f z ==
--   <a>foldl</a> f z . <a>elems</a></tt>.
foldl :: (b -> a -> b) -> b -> IntervalMap k a -> b

-- | <i>O(n)</i>. Fold the keys and values in the map using the given
--   right-associative binary operator, such that <tt><a>foldrWithKey</a> f
--   z == <a>foldr</a> (<a>uncurry</a> f) z . <a>toAscList</a></tt>.
foldrWithKey :: (k -> v -> a -> a) -> a -> IntervalMap k v -> a

-- | <i>O(n)</i>. Fold the keys and values in the map using the given
--   left-associative binary operator, such that <tt><a>foldlWithKey</a> f
--   z == <a>foldl</a> (\z' (kx, x) -&gt; f z' kx x) z .
--   <a>toAscList</a></tt>.
foldlWithKey :: (a -> k -> v -> a) -> a -> IntervalMap k v -> a

-- | <i>O(n log n)</i>. Build a new map by combining successive key/value
--   pairs.
flattenWith :: (Ord k, Interval k e) => ((k, v) -> (k, v) -> Maybe (k, v)) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(n)</i>. Build a new map by combining successive key/value pairs.
--   Same as <a>flattenWith</a>, but works only when the combining
--   functions returns strictly monotonic key values.
flattenWithMonotonic :: (Interval k e) => ((k, v) -> (k, v) -> Maybe (k, v)) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(n)</i>. List of all values in the map, in ascending order of
--   their keys.
elems :: IntervalMap k v -> [v]

-- | <i>O(n)</i>. List of all keys in the map, in ascending order.
keys :: IntervalMap k v -> [k]

-- | <i>O(n)</i>. Set of the keys.
keysSet :: (Ord k) => IntervalMap k v -> Set k

-- | Same as <a>toAscList</a>.
assocs :: IntervalMap k v -> [(k, v)]

-- | <i>O(n)</i>. The list of all key/value pairs contained in the map, in
--   no particular order.
toList :: IntervalMap k v -> [(k, v)]

-- | <i>O(n log n)</i>. Build a map from a list of key/value pairs. See
--   also <a>fromAscList</a>. If the list contains more than one value for
--   the same key, the last value for the key is retained.
fromList :: (Interval k e, Ord k) => [(k, v)] -> IntervalMap k v

-- | <i>O(n log n)</i>. Build a map from a list of key/value pairs with a
--   combining function. See also <a>fromAscListWith</a>.
fromListWith :: (Interval k e, Ord k) => (a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n log n)</i>. Build a map from a list of key/value pairs with a
--   combining function. See also <a>fromAscListWith</a>.
fromListWithKey :: (Interval k e, Ord k) => (k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n)</i>. The list of all key/value pairs contained in the map, in
--   ascending order of keys.
toAscList :: IntervalMap k v -> [(k, v)]

-- | <i>O(n)</i>. The list of all key/value pairs contained in the map, in
--   descending order of keys.
toDescList :: IntervalMap k v -> [(k, v)]

-- | <i>O(n)</i>. Build a map from an ascending list in linear time. <i>The
--   precondition (input list is ascending) is not checked.</i>
fromAscList :: (Interval k e, Eq k) => [(k, v)] -> IntervalMap k v

-- | <i>O(n)</i>. Build a map from an ascending list in linear time with a
--   combining function for equal keys. <i>The precondition (input list is
--   ascending) is not checked.</i>
fromAscListWith :: (Interval k e, Eq k) => (a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n)</i>. Build a map from an ascending list in linear time with a
--   combining function for equal keys. <i>The precondition (input list is
--   ascending) is not checked.</i>
fromAscListWithKey :: (Interval k e, Eq k) => (k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n)</i>. Build a map from an ascending list of elements with
--   distinct keys in linear time. <i>The precondition is not checked.</i>
fromDistinctAscList :: (Interval k e) => [(k, v)] -> IntervalMap k v

-- | <i>O(n)</i>. Filter values satisfying a predicate.
filter :: (Interval k e) => (a -> Bool) -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n)</i>. Filter keys/values satisfying a predicate.
filterWithKey :: (Interval k e) => (k -> a -> Bool) -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n)</i>. Partition the map according to a predicate. The first map
--   contains all elements that satisfy the predicate, the second all
--   elements that fail the predicate. See also <a>split</a>.
partition :: (Interval k e) => (a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)

-- | <i>O(n)</i>. Partition the map according to a predicate. The first map
--   contains all elements that satisfy the predicate, the second all
--   elements that fail the predicate. See also <a>split</a>.
partitionWithKey :: (Interval k e) => (k -> a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)

-- | <i>O(n)</i>. Map values and collect the <a>Just</a> results.
mapMaybe :: (Interval k e) => (a -> Maybe b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. Map keys/values and collect the <a>Just</a> results.
mapMaybeWithKey :: (Interval k e) => (k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. Map values and separate the <a>Left</a> and <a>Right</a>
--   results.
mapEither :: (Interval k e) => (a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)

-- | <i>O(n)</i>. Map keys/values and separate the <a>Left</a> and
--   <a>Right</a> results.
mapEitherWithKey :: (Interval k e) => (k -> a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)

-- | <i>O(n)</i>. The expression (<tt><a>split</a> k map</tt>) is a pair
--   <tt>(map1,map2)</tt> where the keys in <tt>map1</tt> are smaller than
--   <tt>k</tt> and the keys in <tt>map2</tt> larger than <tt>k</tt>. Any
--   key equal to <tt>k</tt> is found in neither <tt>map1</tt> nor
--   <tt>map2</tt>.
split :: (Interval i k, Ord i) => i -> IntervalMap i a -> (IntervalMap i a, IntervalMap i a)

-- | <i>O(n)</i>. The expression (<tt><a>splitLookup</a> k map</tt>) splits
--   a map just like <a>split</a> but also returns <tt><a>lookup</a> k
--   map</tt>.
splitLookup :: (Interval i k, Ord i) => i -> IntervalMap i a -> (IntervalMap i a, Maybe a, IntervalMap i a)

-- | <i>O(n)</i>. Split around a point. Splits the map into three submaps:
--   intervals below the point, intervals containing the point, and
--   intervals above the point.
splitAt :: (Interval i k, Ord i) => IntervalMap i a -> k -> (IntervalMap i a, IntervalMap i a, IntervalMap i a)

-- | <i>O(n)</i>. Split around an interval. Splits the set into three
--   subsets: intervals below the given interval, intervals intersecting
--   the given interval, and intervals above the given interval.
splitIntersecting :: (Interval i k, Ord i) => IntervalMap i a -> i -> (IntervalMap i a, IntervalMap i a, IntervalMap i a)

-- | <i>O(n+m)</i>. This function is defined as (<tt><a>isSubmapOf</a> =
--   <a>isSubmapOfBy</a> (==)</tt>).
isSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool

-- | <i>O(n+m)</i>. The expression (<tt><a>isSubmapOfBy</a> f t1 t2</tt>)
--   returns <a>True</a> if all keys in <tt>t1</tt> are in tree
--   <tt>t2</tt>, and <tt>f</tt> returns <a>True</a> when applied to their
--   respective values.
isSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool

-- | <i>O(n+m)</i>. Is this a proper submap? (ie. a submap but not equal).
--   Defined as (<tt><a>isProperSubmapOf</a> = <a>isProperSubmapOfBy</a>
--   (==)</tt>).
isProperSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool

-- | <i>O(n+m)</i>. Is this a proper submap? (ie. a submap but not equal).
--   The expression (<tt><a>isProperSubmapOfBy</a> f m1 m2</tt>) returns
--   <a>True</a> when <tt>m1</tt> and <tt>m2</tt> are not equal, all keys
--   in <tt>m1</tt> are in <tt>m2</tt>, and when <tt>f</tt> returns
--   <a>True</a> when applied to their respective values.
isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool

-- | <i>O(log n)</i>. Returns the smallest key and its associated value.
--   Calls <a>error</a> if the map is empty.
findMin :: IntervalMap k v -> (k, v)

-- | <i>O(log n)</i>. Returns the largest key and its associated value.
--   Calls <a>error</a> if the map is empty.
findMax :: IntervalMap k v -> (k, v)

-- | Returns the key with the largest endpoint and its associated value. If
--   there is more than one key with that endpoint, return the rightmost.
--   
--   <i>O(n)</i>, since all keys could have the same endpoint. <i>O(log
--   n)</i> average case.
findLast :: (Interval k e) => IntervalMap k v -> (k, v)

-- | <i>O(log n)</i>. Remove the smallest key from the map. Return the
--   empty map if the map is empty.
deleteMin :: (Interval k e, Ord k) => IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Remove the largest key from the map. Return the empty
--   map if the map is empty.
deleteMax :: (Interval k e, Ord k) => IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Delete and return the smallest key.
deleteFindMin :: (Interval k e, Ord k) => IntervalMap k v -> ((k, v), IntervalMap k v)

-- | <i>O(log n)</i>. Delete and return the largest key.
deleteFindMax :: (Interval k e, Ord k) => IntervalMap k v -> ((k, v), IntervalMap k v)

-- | <i>O(log n)</i>. Update or delete value at minimum key.
updateMin :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update or delete value at maximum key.
updateMax :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update or delete value at minimum key.
updateMinWithKey :: (Interval k e, Ord k) => (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update or delete value at maximum key.
updateMaxWithKey :: (Interval k e, Ord k) => (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Retrieves the value associated with minimal key of
--   the map, and the map stripped of that element, or <a>Nothing</a> if
--   passed an empty map.
minView :: (Interval k e, Ord k) => IntervalMap k a -> Maybe (a, IntervalMap k a)

-- | <i>O(log n)</i>. Retrieves the value associated with maximal key of
--   the map, and the map stripped of that element, or <a>Nothing</a> if
--   passed an empty map.
maxView :: (Interval k e, Ord k) => IntervalMap k a -> Maybe (a, IntervalMap k a)

-- | <i>O(log n)</i>. Retrieves the minimal (key,value) pair of the map,
--   and the map stripped of that element, or <a>Nothing</a> if passed an
--   empty map.
--   
--   <pre>
--   minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
--   minViewWithKey empty == Nothing
--   </pre>
minViewWithKey :: (Interval k e, Ord k) => IntervalMap k a -> Maybe ((k, a), IntervalMap k a)

-- | <i>O(log n)</i>. Retrieves the maximal (key,value) pair of the map,
--   and the map stripped of that element, or <a>Nothing</a> if passed an
--   empty map.
maxViewWithKey :: (Interval k e, Ord k) => IntervalMap k a -> Maybe ((k, a), IntervalMap k a)

-- | Check red-black-tree and interval search augmentation invariants. For
--   testing/debugging only.
valid :: (Interval i k, Ord i) => IntervalMap i v -> Bool

-- | The height of the tree. For testing/debugging only.
height :: IntervalMap k v -> Int

-- | The maximum height of a red-black tree with the given number of nodes.
--   For testing/debugging only.
maxHeight :: Int -> Int

-- | Tree statistics (size, height, maxHeight size). For testing/debugging
--   only.
showStats :: IntervalMap k a -> (Int, Int, Int)


-- | An implementation of sets of intervals. The intervals may overlap, and
--   the implementation contains efficient search functions for all
--   intervals containing a point or overlapping a given interval. Closed,
--   open, and half-open intervals can be contained in the same set.
--   
--   It is an error to insert an empty interval into a set. This
--   precondition is not checked by the various construction functions.
--   
--   Since many function names (but not the type name) clash with
--   <i>Prelude</i> names, this module is usually imported
--   <tt>qualified</tt>, e.g.
--   
--   <pre>
--   import Data.IntervalSet.Strict (IntervalSet)
--   import qualified Data.IntervalSet.Strict as IS
--   </pre>
--   
--   It offers most of the same functions as <a>Set</a>, but the member
--   type must be an instance of <a>Interval</a>. The <a>findMin</a> and
--   <a>findMax</a> functions deviate from their set counterparts in being
--   total and returning a <a>Maybe</a> value. Some functions differ in
--   asymptotic performance (for example <a>size</a>) or have not been
--   tuned for efficiency as much as their equivalents in <a>Set</a>.
--   
--   In addition, there are functions specific to sets of intervals, for
--   example to search for all intervals containing a given point or
--   contained in a given interval.
--   
--   The implementation is a red-black tree augmented with the maximum
--   upper bound of all keys.
--   
--   Parts of this implementation are based on code from the <a>Map</a>
--   implementation, (c) Daan Leijen 2002, (c) Andriy Palamarchuk 2008. The
--   red-black tree deletion is based on code from llrbtree by Kazu
--   Yamamoto. Of course, any errors are mine.
module Data.IntervalSet

-- | Intervals with endpoints of type <tt>e</tt>. A minimal instance
--   declaration for a closed interval needs only to define
--   <a>lowerBound</a> and <a>upperBound</a>.
class Ord e => Interval i e | i -> e where leftClosed _ = True rightClosed _ = True a `before` b = upperBound a < lowerBound b || (upperBound a == lowerBound b && not (rightClosed a && leftClosed b)) a `after` b = b `before` a a `subsumes` b = (lowerBound a < lowerBound b || (lowerBound a == lowerBound b && (leftClosed a || not (leftClosed b)))) && (upperBound a > upperBound b || (upperBound a == upperBound b && (rightClosed a || not (rightClosed b)))) a `overlaps` b = (lowerBound a < upperBound b || (lowerBound a == upperBound b && leftClosed a && rightClosed b)) && (upperBound a > lowerBound b || (upperBound a == lowerBound b && rightClosed a && leftClosed b)) p `below` i = case compare p (lowerBound i) of { LT -> True EQ -> not (leftClosed i) GT -> False } p `above` i = case compare p (upperBound i) of { LT -> False EQ -> not (rightClosed i) GT -> True } p `inside` i = not ((p `above` i) || (p `below` i)) isEmpty i | leftClosed i && rightClosed i = lowerBound i > upperBound i | otherwise = lowerBound i >= upperBound i

-- | lower bound
lowerBound :: Interval i e => i -> e

-- | upper bound
upperBound :: Interval i e => i -> e

-- | Does the interval include its lower bound? Default is True for all
--   values, i.e. closed intervals.
leftClosed :: Interval i e => i -> Bool

-- | Does the interval include its upper bound bound? Default is True for
--   all values, i.e. closed intervals.
rightClosed :: Interval i e => i -> Bool

-- | Interval strictly before another? True if the upper bound of the first
--   interval is below the lower bound of the second.
before :: Interval i e => i -> i -> Bool

-- | Interval strictly after another? Same as 'flip before'.
after :: Interval i e => i -> i -> Bool

-- | Does the first interval completely contain the second?
subsumes :: Interval i e => i -> i -> Bool

-- | Do the two intervals overlap?
overlaps :: Interval i e => i -> i -> Bool

-- | Is a point strictly less than lower bound?
below :: Interval i e => e -> i -> Bool

-- | Is a point strictly greater than upper bound?
above :: Interval i e => e -> i -> Bool

-- | Does the interval contain a given point?
inside :: Interval i e => e -> i -> Bool

-- | Is the interval empty?
isEmpty :: Interval i e => i -> Bool

-- | A set of intervals of type <tt>k</tt>.
data IntervalSet k
Nil :: IntervalSet k
Node :: !Color -> !k -> !k -> !(IntervalSet k) -> !(IntervalSet k) -> IntervalSet k

-- | Same as <a>difference</a>.
(\\) :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k -> IntervalSet k

-- | <i>O(1)</i>. Is the set empty?
null :: IntervalSet k -> Bool

-- | <i>O(n)</i>. Number of keys in the set.
--   
--   Caution: unlike <a>size</a>, this takes linear time!
size :: IntervalSet k -> Int

-- | <i>O(log n)</i>. Does the set contain the given value? See also
--   <a>notMember</a>.
member :: (Ord k) => k -> IntervalSet k -> Bool

-- | <i>O(log n)</i>. Does the set not contain the given value? See also
--   <a>member</a>.
notMember :: (Ord k) => k -> IntervalSet k -> Bool

-- | Return the set of all intervals containing the given point. This is
--   the second element of the value of <a>splitAt</a>:
--   
--   <pre>
--   set `containing` p == let (_,s,_) = set `splitAt` p in s
--   </pre>
--   
--   <i>O(n)</i>, since potentially all intervals could contain the point.
--   <i>O(log n)</i> average case. This is also the worst case for sets
--   containing no overlapping intervals.
containing :: (Interval k e) => IntervalSet k -> e -> IntervalSet k

-- | Return the set of all intervals overlapping (intersecting) the given
--   interval. This is the second element of the result of
--   <a>splitIntersecting</a>:
--   
--   <pre>
--   set `intersecting` i == let (_,s,_) = set `splitIntersecting` i in s
--   </pre>
--   
--   <i>O(n)</i>, since potentially all values could intersect the
--   interval. <i>O(log n)</i> average case, if few values intersect the
--   interval.
intersecting :: (Interval k e) => IntervalSet k -> k -> IntervalSet k

-- | Return the set of all intervals which are completely inside the given
--   interval.
--   
--   <i>O(n)</i>, since potentially all values could be inside the
--   interval. <i>O(log n)</i> average case, if few keys are inside the
--   interval.
within :: (Interval k e) => IntervalSet k -> k -> IntervalSet k

-- | <i>O(1)</i>. The empty set.
empty :: IntervalSet k

-- | <i>O(1)</i>. A set with one entry.
singleton :: k -> IntervalSet k

-- | <i>O(log n)</i>. Insert a new value. If the set already contains an
--   element equal to the value, it is replaced by the new value.
insert :: (Interval k e, Ord k) => k -> IntervalSet k -> IntervalSet k

-- | <i>O(log n)</i>. Delete an element from the set. If the set does not
--   contain the value, it is returned unchanged.
delete :: (Interval k e, Ord k) => k -> IntervalSet k -> IntervalSet k

-- | <i>O(n+m)</i>. The expression (<tt><a>union</a> t1 t2</tt>) takes the
--   left-biased union of <tt>t1</tt> and <tt>t2</tt>. It prefers
--   <tt>t1</tt> when duplicate elements are encountered.
union :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k -> IntervalSet k

-- | The union of a list of sets: (<tt><a>unions</a> == <a>foldl</a>
--   <a>union</a> <a>empty</a></tt>).
unions :: (Interval k e, Ord k) => [IntervalSet k] -> IntervalSet k

-- | <i>O(n+m)</i>. Difference of two sets. Return elements of the first
--   set not existing in the second set.
difference :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k -> IntervalSet k

-- | <i>O(n+m)</i>. Intersection of two sets. Return elements in the first
--   set also existing in the second set.
intersection :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k -> IntervalSet k

-- | <i>O(n log n)</i>. Map a function over all values in the set.
--   
--   The size of the result may be smaller if <tt>f</tt> maps two or more
--   distinct elements to the same value.
map :: (Interval a e1, Interval b e2, Ord b) => (a -> b) -> IntervalSet a -> IntervalSet b

-- | <i>O(n)</i>. <tt><a>mapMonotonic</a> f s == <a>map</a> f s</tt>, but
--   works only when <tt>f</tt> is strictly monotonic. That is, for any
--   values <tt>x</tt> and <tt>y</tt>, if <tt>x</tt> &lt; <tt>y</tt> then
--   <tt>f x</tt> &lt; <tt>f y</tt>. <i>The precondition is not
--   checked.</i>
mapMonotonic :: (Interval k2 e, Ord k2) => (k1 -> k2) -> IntervalSet k1 -> IntervalSet k2

-- | <i>O(n)</i>. Fold the values in the set using the given
--   right-associative binary operator, such that <tt><a>foldr</a> f z ==
--   <a>foldr</a> f z . <a>elems</a></tt>.
foldr :: (k -> b -> b) -> b -> IntervalSet k -> b

-- | <i>O(n)</i>. Fold the values in the set using the given
--   left-associative binary operator, such that <tt><a>foldl</a> f z ==
--   <a>foldl</a> f z . <a>elems</a></tt>.
foldl :: (b -> k -> b) -> b -> IntervalSet k -> b

-- | <i>O(n)</i>. A strict version of <a>foldl</a>. Each application of the
--   operator is evaluated before using the result in the next application.
--   This function is strict in the starting value.
foldl' :: (b -> k -> b) -> b -> IntervalSet k -> b

-- | <i>O(n)</i>. A strict version of <a>foldr</a>. Each application of the
--   operator is evaluated before using the result in the next application.
--   This function is strict in the starting value.
foldr' :: (k -> b -> b) -> b -> IntervalSet k -> b

-- | <i>O(n log n)</i>. Build a new set by combining successive values.
flattenWith :: (Ord a, Interval a e) => (a -> a -> Maybe a) -> IntervalSet a -> IntervalSet a

-- | <i>O(n)</i>. Build a new set by combining successive values. Same as
--   <a>flattenWith</a>, but works only when the combining functions
--   returns strictly monotonic values.
flattenWithMonotonic :: (Interval a e) => (a -> a -> Maybe a) -> IntervalSet a -> IntervalSet a

-- | <i>O(n)</i>. List of all values in the set, in ascending order.
elems :: IntervalSet k -> [k]

-- | <i>O(n)</i>. The list of all values in the set, in no particular
--   order.
toList :: IntervalSet k -> [k]

-- | <i>O(n log n)</i>. Build a set from a list of elements. See also
--   <a>fromAscList</a>. If the list contains duplicate values, the last
--   value is retained.
fromList :: (Interval k e, Ord k) => [k] -> IntervalSet k

-- | <i>O(n)</i>. The list of all values contained in the set, in ascending
--   order.
toAscList :: IntervalSet k -> [k]

-- | <i>O(n)</i>. The list of all values in the set, in descending order.
toDescList :: IntervalSet k -> [k]

-- | <i>O(n)</i>. Build a set from an ascending list in linear time. <i>The
--   precondition (input list is ascending) is not checked.</i>
fromAscList :: (Interval k e, Eq k) => [k] -> IntervalSet k

-- | <i>O(n)</i>. Build a set from an ascending list of distinct elements
--   in linear time. <i>The precondition is not checked.</i>
fromDistinctAscList :: (Interval k e) => [k] -> IntervalSet k

-- | <i>O(n)</i>. Filter values satisfying a predicate.
filter :: (Interval k e) => (k -> Bool) -> IntervalSet k -> IntervalSet k

-- | <i>O(n)</i>. Partition the set according to a predicate. The first set
--   contains all elements that satisfy the predicate, the second all
--   elements that fail the predicate. See also <a>split</a>.
partition :: (Interval k e) => (k -> Bool) -> IntervalSet k -> (IntervalSet k, IntervalSet k)

-- | <i>O(n)</i>. The expression (<tt><a>split</a> k set</tt>) is a pair
--   <tt>(set1,set2)</tt> where the elements in <tt>set1</tt> are smaller
--   than <tt>k</tt> and the elements in <tt>set2</tt> larger than
--   <tt>k</tt>. Any key equal to <tt>k</tt> is found in neither
--   <tt>set1</tt> nor <tt>set2</tt>.
split :: (Interval i k, Ord i) => i -> IntervalSet i -> (IntervalSet i, IntervalSet i)

-- | <i>O(n)</i>. The expression (<tt><a>splitMember</a> k set</tt>) splits
--   a set just like <a>split</a> but also returns <tt><a>member</a> k
--   set</tt>.
splitMember :: (Interval i k, Ord i) => i -> IntervalSet i -> (IntervalSet i, Bool, IntervalSet i)

-- | <i>O(n)</i>. Split around a point. Splits the set into three subsets:
--   intervals below the point, intervals containing the point, and
--   intervals above the point.
splitAt :: (Interval i k, Ord i) => IntervalSet i -> k -> (IntervalSet i, IntervalSet i, IntervalSet i)

-- | <i>O(n)</i>. Split around an interval. Splits the set into three
--   subsets: intervals below the given interval, intervals intersecting
--   the given interval, and intervals above the given interval.
splitIntersecting :: (Interval i k, Ord i) => IntervalSet i -> i -> (IntervalSet i, IntervalSet i, IntervalSet i)

-- | <i>O(n+m)</i>. Is the first set a subset of the second set? This is
--   always true for equal sets.
isSubsetOf :: (Ord k) => IntervalSet k -> IntervalSet k -> Bool

-- | <i>O(n+m)</i>. Is the first set a proper subset of the second set?
--   (i.e. a subset but not equal).
isProperSubsetOf :: (Ord k) => IntervalSet k -> IntervalSet k -> Bool

-- | <i>O(log n)</i>. Returns the minimal value in the set.
findMin :: IntervalSet k -> Maybe k

-- | <i>O(log n)</i>. Returns the maximal value in the set.
findMax :: IntervalSet k -> Maybe k

-- | Returns the interval with the largest endpoint. If there is more than
--   one interval with that endpoint, return the rightmost.
--   
--   <i>O(n)</i>, since all intervals could have the same endpoint.
--   <i>O(log n)</i> average case.
findLast :: (Interval k e) => IntervalSet k -> Maybe k

-- | <i>O(log n)</i>. Remove the smallest element from the set. Return the
--   empty set if the set is empty.
deleteMin :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k

-- | <i>O(log n)</i>. Remove the largest element from the set. Return the
--   empty set if the set is empty.
deleteMax :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k

-- | <i>O(log n)</i>. Delete and return the smallest element.
deleteFindMin :: (Interval k e, Ord k) => IntervalSet k -> (k, IntervalSet k)

-- | <i>O(log n)</i>. Delete and return the largest element.
deleteFindMax :: (Interval k e, Ord k) => IntervalSet k -> (k, IntervalSet k)

-- | <i>O(log n)</i>. Retrieves the minimal element of the set, and the set
--   stripped of that element, or <a>Nothing</a> if passed an empty set.
minView :: (Interval k e, Ord k) => IntervalSet k -> Maybe (k, IntervalSet k)

-- | <i>O(log n)</i>. Retrieves the maximal element of the set, and the set
--   stripped of that element, or <a>Nothing</a> if passed an empty set.
maxView :: (Interval k e, Ord k) => IntervalSet k -> Maybe (k, IntervalSet k)

-- | Check red-black-tree and interval search augmentation invariants. For
--   testing/debugging only.
valid :: (Interval i k, Ord i) => IntervalSet i -> Bool
instance GHC.Classes.Eq Data.IntervalSet.Color
instance GHC.Classes.Eq k => GHC.Classes.Eq (Data.IntervalSet.IntervalSet k)
instance GHC.Classes.Ord k => GHC.Classes.Ord (Data.IntervalSet.IntervalSet k)
instance (Data.IntervalMap.Generic.Interval.Interval i k, GHC.Classes.Ord i) => GHC.Base.Monoid (Data.IntervalSet.IntervalSet i)
instance Data.Foldable.Foldable Data.IntervalSet.IntervalSet
instance Control.DeepSeq.NFData k => Control.DeepSeq.NFData (Data.IntervalSet.IntervalSet k)
instance (GHC.Classes.Ord k, GHC.Read.Read k, Data.IntervalMap.Generic.Interval.Interval i k, GHC.Classes.Ord i, GHC.Read.Read i) => GHC.Read.Read (Data.IntervalSet.IntervalSet i)
instance GHC.Show.Show k => GHC.Show.Show (Data.IntervalSet.IntervalSet k)


-- | An implementation of maps from intervals to values. The key intervals
--   may overlap, and the implementation contains efficient search
--   functions for all keys containing a point or overlapping an interval.
--   Closed, open, and half-open intervals can be contained in the same
--   map.
--   
--   The functions in this module are strict in both the keys and the
--   values. If you need value-lazy maps, use <a>Data.IntervalMap.Lazy</a>
--   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).
--   
--   An IntervalMap cannot contain duplicate keys - if you need to map a
--   key to multiple values, use a collection as the value type, for
--   example: <tt>IntervalMap <i>k</i> [<i>v</i>]</tt>.
--   
--   It is an error to insert an empty interval into a map. This
--   precondition is not checked by the various construction functions.
--   
--   Since many function names (but not the type name) clash with
--   <i>Prelude</i> names, this module is usually imported
--   <tt>qualified</tt>, e.g.
--   
--   <pre>
--   import Data.IntervalMap (IvMap)
--   import qualified Data.IntervalMap as IvMap
--   </pre>
--   
--   It offers most of the same functions as <a>Map</a>, but uses
--   <a>Interval</a> <i>k</i> instead of just <i>k</i> as the key type.
--   Some of the functions need stricter type constraints to maintain the
--   additional information for efficient interval searching, for example
--   <a>fromDistinctAscList</a> needs an <a>Ord</a> <i>k</i> constraint.
--   Also, some functions differ in asymptotic performance (for example
--   <a>size</a>) or have not been tuned for efficiency as much as their
--   equivalents in <a>Map</a> (in particular the various set functions).
--   
--   In addition, there are functions specific to maps of intervals, for
--   example to search for all keys containing a given point or contained
--   in a given interval.
--   
--   To stay compatible with standard Haskell, this implementation uses a
--   fixed data type for intervals, and not a multi-parameter type class.
--   Thus, it's currently not possible to define e.g. a 2-tuple as an
--   instance of interval and use that map key. Instead, you must convert
--   your keys to <a>Interval</a>.
--   
--   The implementation is a red-black tree augmented with the maximum
--   upper bound of all keys.
--   
--   Parts of this implementation are based on code from the <a>Map</a>
--   implementation, (c) Daan Leijen 2002, (c) Andriy Palamarchuk 2008. The
--   red-black tree deletion is based on code from llrbtree by Kazu
--   Yamamoto. Of course, any errors are mine.
module Data.IntervalMap.Strict

-- | Intervals with endpoints of type <tt>a</tt>.
--   
--   <a>Read</a> and <a>Show</a> use mathematical notation with square
--   brackets for closed and parens for open intervals. This is better for
--   human readability, but is not a valid Haskell expression. Closed
--   intervals look like a list, open intervals look like a tuple, and
--   half-open intervals look like mismatched parens.
data Interval a

-- | Including lower bound, excluding upper
IntervalCO :: !a -> !a -> Interval a

-- | Closed at both ends
ClosedInterval :: !a -> !a -> Interval a

-- | Open at both ends
OpenInterval :: !a -> !a -> Interval a

-- | Excluding lower bound, including upper
IntervalOC :: !a -> !a -> Interval a
type IntervalMap k v = IntervalMap (Interval k) v

-- | <i>O(log n)</i>. Lookup value for given key. Calls <a>error</a> if the
--   key is not in the map.
--   
--   Use <a>lookup</a> or <a>findWithDefault</a> instead of this function,
--   unless you are absolutely sure that the key is present in the map.
(!) :: (Interval k e, Ord k) => IntervalMap k v -> k -> v

-- | Same as <a>difference</a>.
(\\) :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | Test whether the structure is empty. The default implementation is
--   optimized for structures that are similar to cons-lists, because there
--   is no general way to do better.
null :: Foldable t => forall a. t a -> Bool

-- | <i>O(n)</i>. Number of keys in the map.
--   
--   Caution: unlike <a>size</a>, which takes constant time, this is linear
--   in the number of keys!
size :: IntervalMap k v -> Int

-- | <i>O(log n)</i>. Does the map contain the given key? See also
--   <a>notMember</a>.
member :: (Ord k) => k -> IntervalMap k v -> Bool

-- | <i>O(log n)</i>. Does the map not contain the given key? See also
--   <a>member</a>.
notMember :: (Ord k) => k -> IntervalMap k v -> Bool

-- | <a>lookup</a> <tt>key assocs</tt> looks up a key in an association
--   list.
lookup :: Eq a => a -> [(a, b)] -> Maybe b

-- | <i>O(log n)</i>. The expression <tt>(<a>findWithDefault</a> def k
--   map)</tt> returns the value at key <tt>k</tt> or returns default value
--   <tt>def</tt> when the key is not in the map.
--   
--   <pre>
--   findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
--   findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
--   </pre>
findWithDefault :: Ord k => a -> k -> IntervalMap k a -> a

-- | Return the submap of key intervals containing the given point. This is
--   the second element of the value of <a>splitAt</a>:
--   
--   <pre>
--   m `containing` p == let (_,m',_) = m `splitAt` p in m'
--   </pre>
--   
--   <i>O(n)</i>, since potentially all keys could contain the point.
--   <i>O(log n)</i> average case. This is also the worst case for maps
--   containing no overlapping keys.
containing :: (Interval k e) => IntervalMap k v -> e -> IntervalMap k v

-- | Return the submap of key intervals overlapping (intersecting) the
--   given interval. This is the second element of the value of
--   <a>splitIntersecting</a>:
--   
--   <pre>
--   m `intersecting` i == let (_,m',_) = m `splitIntersecting` i in m'
--   </pre>
--   
--   <i>O(n)</i>, since potentially all keys could intersect the interval.
--   <i>O(log n)</i> average case, if few keys intersect the interval.
intersecting :: (Interval k e) => IntervalMap k v -> k -> IntervalMap k v

-- | Return the submap of key intervals completely inside the given
--   interval.
--   
--   <i>O(n)</i>, since potentially all keys could be inside the interval.
--   <i>O(log n)</i> average case, if few keys are inside the interval.
within :: (Interval k e) => IntervalMap k v -> k -> IntervalMap k v

-- | <i>O(1)</i>. The empty map.
empty :: IntervalMap k v

-- | <i>O(1)</i>. A map with one entry.
singleton :: k -> v -> IntervalMap k v

-- | <i>O(log n)</i>. Insert a new key/value pair. If the map already
--   contains the key, its value is changed to the new value.
insert :: (Interval k e, Ord k) => k -> v -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Insert with a function, combining new value and old
--   value. <tt><a>insertWith</a> f key value mp</tt> will insert the pair
--   (key, value) into <tt>mp</tt> if key does not exist in the map. If the
--   key does exist, the function will insert the pair <tt>(key, f
--   new_value old_value)</tt>.
insertWith :: (Interval k e, Ord k) => (v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Insert with a function, combining key, new value and
--   old value. <tt><a>insertWithKey</a> f key value mp</tt> will insert
--   the pair (key, value) into <tt>mp</tt> if key does not exist in the
--   map. If the key does exist, the function will insert the pair
--   <tt>(key, f key new_value old_value)</tt>. Note that the key passed to
--   f is the same key passed to <a>insertWithKey</a>.
insertWithKey :: (Interval k e, Ord k) => (k -> v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Combine insert with old values retrieval.
insertLookupWithKey :: (Interval k e, Ord k) => (k -> v -> v -> v) -> k -> v -> IntervalMap k v -> (Maybe v, IntervalMap k v)

-- | <i>O(log n)</i>. Delete a key from the map. If the map does not
--   contain the key, it is returned unchanged.
delete :: (Interval k e, Ord k) => k -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update a value at a specific key with the result of
--   the provided function. When the key is not a member of the map, the
--   original map is returned.
adjust :: Ord k => (a -> a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. Adjust a value at a specific key. When the key is not
--   a member of the map, the original map is returned.
adjustWithKey :: Ord k => (k -> a -> a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. The expression (<tt><a>update</a> f k map</tt>)
--   updates the value <tt>x</tt> at <tt>k</tt> (if it is in the map). If
--   (<tt>f x</tt>) is <a>Nothing</a>, the element is deleted. If it is
--   (<tt><a>Just</a> y</tt>), the key <tt>k</tt> is bound to the new value
--   <tt>y</tt>.
update :: (Interval k e, Ord k) => (a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. The expression (<tt><a>updateWithKey</a> f k
--   map</tt>) updates the value <tt>x</tt> at <tt>k</tt> (if it is in the
--   map). If (<tt>f k x</tt>) is <a>Nothing</a>, the element is deleted.
--   If it is (<tt><a>Just</a> y</tt>), the key <tt>k</tt> is bound to the
--   new value <tt>y</tt>.
updateWithKey :: (Interval k e, Ord k) => (k -> a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. Lookup and update. See also <a>updateWithKey</a>. The
--   function returns changed value, if it is updated. Returns the original
--   key value if the map entry is deleted.
updateLookupWithKey :: (Interval k e, Ord k) => (k -> a -> Maybe a) -> k -> IntervalMap k a -> (Maybe a, IntervalMap k a)

-- | <i>O(log n)</i>. The expression (<tt><a>alter</a> f k map</tt>) alters
--   the value <tt>x</tt> at <tt>k</tt>, or absence thereof. <a>alter</a>
--   can be used to insert, delete, or update a value in a <tt>Map</tt>. In
--   short : <tt><a>lookup</a> k (<a>alter</a> f k m) = f (<a>lookup</a> k
--   m)</tt>.
alter :: (Interval k e, Ord k) => (Maybe a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n+m)</i>. The expression (<tt><a>union</a> t1 t2</tt>) takes the
--   left-biased union of <tt>t1</tt> and <tt>t2</tt>. It prefers
--   <tt>t1</tt> when duplicate keys are encountered, i.e.
--   (<tt><a>union</a> == <a>unionWith</a> <a>const</a></tt>).
union :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n+m)</i>. Union with a combining function.
unionWith :: (Interval k e, Ord k) => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n+m)</i>. Union with a combining function.
unionWithKey :: (Interval k e, Ord k) => (k -> a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | The union of a list of maps: (<tt><a>unions</a> == <a>foldl</a>
--   <a>union</a> <a>empty</a></tt>).
unions :: (Interval k e, Ord k) => [IntervalMap k a] -> IntervalMap k a

-- | The union of a list of maps, with a combining operation:
--   (<tt><a>unionsWith</a> f == <a>foldl</a> (<a>unionWith</a> f)
--   <a>empty</a></tt>).
unionsWith :: (Interval k e, Ord k) => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a

-- | <i>O(n+m)</i>. Difference of two maps. Return elements of the first
--   map not existing in the second map.
difference :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Difference with a combining function. When two equal
--   keys are encountered, the combining function is applied to the values
--   of these keys. If it returns <a>Nothing</a>, the element is discarded
--   (proper set difference). If it returns (<tt><a>Just</a> y</tt>), the
--   element is updated with a new value <tt>y</tt>.
differenceWith :: (Interval k e, Ord k) => (a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Difference with a combining function. When two equal
--   keys are encountered, the combining function is applied to the key and
--   both values. If it returns <a>Nothing</a>, the element is discarded
--   (proper set difference). If it returns (<tt><a>Just</a> y</tt>), the
--   element is updated with a new value <tt>y</tt>.
differenceWithKey :: (Interval k e, Ord k) => (k -> a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Intersection of two maps. Return data in the first map
--   for the keys existing in both maps. (<tt><a>intersection</a> m1 m2 ==
--   <a>intersectionWith</a> <a>const</a> m1 m2</tt>).
intersection :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Intersection with a combining function.
intersectionWith :: (Interval k e, Ord k) => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c

-- | <i>O(n+m)</i>. Intersection with a combining function.
intersectionWithKey :: (Interval k e, Ord k) => (k -> a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c

-- | <a>map</a> <tt>f xs</tt> is the list obtained by applying <tt>f</tt>
--   to each element of <tt>xs</tt>, i.e.,
--   
--   <pre>
--   map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
--   map f [x1, x2, ...] == [f x1, f x2, ...]
--   </pre>
map :: (a -> b) -> [a] -> [b]

-- | <i>O(n)</i>. Map a function over all values in the map.
mapWithKey :: (k -> a -> b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. The function <a>mapAccum</a> threads an accumulating
--   argument through the map in ascending order of keys.
--   
--   <pre>
--   let f a b = (a ++ b, b ++ "X")
--   mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
--   </pre>
mapAccum :: (a -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)

-- | <i>O(n)</i>. The function <a>mapAccumWithKey</a> threads an
--   accumulating argument through the map in ascending order of keys.
--   
--   <pre>
--   let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
--   mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
--   </pre>
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)

-- | <i>O(n)</i>. The function <a>mapAccumRWithKey</a> threads an
--   accumulating argument through the map in descending order of keys.
mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)

-- | <i>O(n log n)</i>. <tt><a>mapKeys</a> f s</tt> is the map obtained by
--   applying <tt>f</tt> to each key of <tt>s</tt>.
--   
--   The size of the result may be smaller if <tt>f</tt> maps two or more
--   distinct keys to the same new key. In this case the value at the
--   smallest of these keys is retained.
mapKeys :: (Interval k2 e, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

-- | <i>O(n log n)</i>. <tt><a>mapKeysWith</a> c f s</tt> is the map
--   obtained by applying <tt>f</tt> to each key of <tt>s</tt>.
--   
--   The size of the result may be smaller if <tt>f</tt> maps two or more
--   distinct keys to the same new key. In this case the associated values
--   will be combined using <tt>c</tt>.
mapKeysWith :: (Interval k2 e, Ord k2) => (a -> a -> a) -> (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

-- | <i>O(n)</i>. <tt><a>mapKeysMonotonic</a> f s == <a>mapKeys</a> f
--   s</tt>, but works only when <tt>f</tt> is strictly monotonic. That is,
--   for any values <tt>x</tt> and <tt>y</tt>, if <tt>x</tt> &lt;
--   <tt>y</tt> then <tt>f x</tt> &lt; <tt>f y</tt>. <i>The precondition is
--   not checked.</i>
mapKeysMonotonic :: (Interval k2 e, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

-- | Right-associative fold of a structure.
--   
--   <pre>
--   <a>foldr</a> f z = <a>foldr</a> f z . <a>toList</a>
--   </pre>
foldr :: Foldable t => forall a b. (a -> b -> b) -> b -> t a -> b

-- | Left-associative fold of a structure.
--   
--   <pre>
--   <a>foldl</a> f z = <a>foldl</a> f z . <a>toList</a>
--   </pre>
foldl :: Foldable t => forall b a. (b -> a -> b) -> b -> t a -> b

-- | <i>O(n)</i>. Fold the keys and values in the map using the given
--   right-associative binary operator, such that <tt><a>foldrWithKey</a> f
--   z == <a>foldr</a> (<a>uncurry</a> f) z . <a>toAscList</a></tt>.
foldrWithKey :: (k -> v -> a -> a) -> a -> IntervalMap k v -> a

-- | <i>O(n)</i>. Fold the keys and values in the map using the given
--   left-associative binary operator, such that <tt><a>foldlWithKey</a> f
--   z == <a>foldl</a> (\z' (kx, x) -&gt; f z' kx x) z .
--   <a>toAscList</a></tt>.
foldlWithKey :: (a -> k -> v -> a) -> a -> IntervalMap k v -> a

-- | <i>O(n)</i>. Combine overlapping intervals.
flattenWith :: (Ord k) => (v -> v -> v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(n)</i>. List of all values in the map, in ascending order of
--   their keys.
elems :: IntervalMap k v -> [v]

-- | <i>O(n)</i>. List of all keys in the map, in ascending order.
keys :: IntervalMap k v -> [k]

-- | <i>O(n)</i>. Set of the keys.
keysSet :: (Ord k) => IntervalMap k v -> Set k

-- | Same as <a>toAscList</a>.
assocs :: IntervalMap k v -> [(k, v)]

-- | <i>O(n)</i>. The list of all key/value pairs contained in the map, in
--   no particular order.
toList :: IntervalMap k v -> [(k, v)]

-- | <i>O(n log n)</i>. Build a map from a list of key/value pairs. See
--   also <a>fromAscList</a>. If the list contains more than one value for
--   the same key, the last value for the key is retained.
fromList :: (Interval k e, Ord k) => [(k, v)] -> IntervalMap k v

-- | <i>O(n log n)</i>. Build a map from a list of key/value pairs with a
--   combining function. See also <a>fromAscListWith</a>.
fromListWith :: (Interval k e, Ord k) => (a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n log n)</i>. Build a map from a list of key/value pairs with a
--   combining function. See also <a>fromAscListWith</a>.
fromListWithKey :: (Interval k e, Ord k) => (k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n)</i>. The list of all key/value pairs contained in the map, in
--   ascending order of keys.
toAscList :: IntervalMap k v -> [(k, v)]

-- | <i>O(n)</i>. The list of all key/value pairs contained in the map, in
--   descending order of keys.
toDescList :: IntervalMap k v -> [(k, v)]

-- | <i>O(n)</i>. Build a map from an ascending list in linear time. <i>The
--   precondition (input list is ascending) is not checked.</i>
fromAscList :: (Interval k e, Eq k) => [(k, v)] -> IntervalMap k v

-- | <i>O(n)</i>. Build a map from an ascending list in linear time with a
--   combining function for equal keys. <i>The precondition (input list is
--   ascending) is not checked.</i>
fromAscListWith :: (Interval k e, Eq k) => (a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n)</i>. Build a map from an ascending list in linear time with a
--   combining function for equal keys. <i>The precondition (input list is
--   ascending) is not checked.</i>
fromAscListWithKey :: (Interval k e, Eq k) => (k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n)</i>. Build a map from an ascending list of elements with
--   distinct keys in linear time. <i>The precondition is not checked.</i>
fromDistinctAscList :: (Interval k e) => [(k, v)] -> IntervalMap k v

-- | <a>filter</a>, applied to a predicate and a list, returns the list of
--   those elements that satisfy the predicate; i.e.,
--   
--   <pre>
--   filter p xs = [ x | x &lt;- xs, p x]
--   </pre>
filter :: (a -> Bool) -> [a] -> [a]

-- | <i>O(n)</i>. Filter keys/values satisfying a predicate.
filterWithKey :: (Interval k e) => (k -> a -> Bool) -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n)</i>. Partition the map according to a predicate. The first map
--   contains all elements that satisfy the predicate, the second all
--   elements that fail the predicate. See also <a>split</a>.
partition :: (Interval k e) => (a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)

-- | <i>O(n)</i>. Partition the map according to a predicate. The first map
--   contains all elements that satisfy the predicate, the second all
--   elements that fail the predicate. See also <a>split</a>.
partitionWithKey :: (Interval k e) => (k -> a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)

-- | <i>O(n)</i>. Map values and collect the <a>Just</a> results.
mapMaybe :: (Interval k e) => (a -> Maybe b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. Map keys/values and collect the <a>Just</a> results.
mapMaybeWithKey :: (Interval k e) => (k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. Map values and separate the <a>Left</a> and <a>Right</a>
--   results.
mapEither :: (Interval k e) => (a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)

-- | <i>O(n)</i>. Map keys/values and separate the <a>Left</a> and
--   <a>Right</a> results.
mapEitherWithKey :: (Interval k e) => (k -> a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)

-- | <i>O(n)</i>. The expression (<tt><a>split</a> k map</tt>) is a pair
--   <tt>(map1,map2)</tt> where the keys in <tt>map1</tt> are smaller than
--   <tt>k</tt> and the keys in <tt>map2</tt> larger than <tt>k</tt>. Any
--   key equal to <tt>k</tt> is found in neither <tt>map1</tt> nor
--   <tt>map2</tt>.
split :: (Interval i k, Ord i) => i -> IntervalMap i a -> (IntervalMap i a, IntervalMap i a)

-- | <i>O(n)</i>. The expression (<tt><a>splitLookup</a> k map</tt>) splits
--   a map just like <a>split</a> but also returns <tt><a>lookup</a> k
--   map</tt>.
splitLookup :: (Interval i k, Ord i) => i -> IntervalMap i a -> (IntervalMap i a, Maybe a, IntervalMap i a)

-- | <i>O(n)</i>. Split around a point. Splits the map into three submaps:
--   intervals below the point, intervals containing the point, and
--   intervals above the point.
splitAt :: (Interval i k, Ord i) => IntervalMap i a -> k -> (IntervalMap i a, IntervalMap i a, IntervalMap i a)

-- | <i>O(n)</i>. Split around an interval. Splits the set into three
--   subsets: intervals below the given interval, intervals intersecting
--   the given interval, and intervals above the given interval.
splitIntersecting :: (Interval i k, Ord i) => IntervalMap i a -> i -> (IntervalMap i a, IntervalMap i a, IntervalMap i a)

-- | <i>O(n+m)</i>. This function is defined as (<tt><a>isSubmapOf</a> =
--   <a>isSubmapOfBy</a> (==)</tt>).
isSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool

-- | <i>O(n+m)</i>. The expression (<tt><a>isSubmapOfBy</a> f t1 t2</tt>)
--   returns <a>True</a> if all keys in <tt>t1</tt> are in tree
--   <tt>t2</tt>, and <tt>f</tt> returns <a>True</a> when applied to their
--   respective values.
isSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool

-- | <i>O(n+m)</i>. Is this a proper submap? (ie. a submap but not equal).
--   Defined as (<tt><a>isProperSubmapOf</a> = <a>isProperSubmapOfBy</a>
--   (==)</tt>).
isProperSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool

-- | <i>O(n+m)</i>. Is this a proper submap? (ie. a submap but not equal).
--   The expression (<tt><a>isProperSubmapOfBy</a> f m1 m2</tt>) returns
--   <a>True</a> when <tt>m1</tt> and <tt>m2</tt> are not equal, all keys
--   in <tt>m1</tt> are in <tt>m2</tt>, and when <tt>f</tt> returns
--   <a>True</a> when applied to their respective values.
isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool

-- | <i>O(log n)</i>. Returns the smallest key and its associated value.
--   Calls <a>error</a> if the map is empty.
findMin :: IntervalMap k v -> (k, v)

-- | <i>O(log n)</i>. Returns the largest key and its associated value.
--   Calls <a>error</a> if the map is empty.
findMax :: IntervalMap k v -> (k, v)

-- | Returns the key with the largest endpoint and its associated value. If
--   there is more than one key with that endpoint, return the rightmost.
--   
--   <i>O(n)</i>, since all keys could have the same endpoint. <i>O(log
--   n)</i> average case.
findLast :: (Interval k e) => IntervalMap k v -> (k, v)

-- | <i>O(log n)</i>. Remove the smallest key from the map. Return the
--   empty map if the map is empty.
deleteMin :: (Interval k e, Ord k) => IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Remove the largest key from the map. Return the empty
--   map if the map is empty.
deleteMax :: (Interval k e, Ord k) => IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Delete and return the smallest key.
deleteFindMin :: (Interval k e, Ord k) => IntervalMap k v -> ((k, v), IntervalMap k v)

-- | <i>O(log n)</i>. Delete and return the largest key.
deleteFindMax :: (Interval k e, Ord k) => IntervalMap k v -> ((k, v), IntervalMap k v)

-- | <i>O(log n)</i>. Update or delete value at minimum key.
updateMin :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update or delete value at maximum key.
updateMax :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update or delete value at minimum key.
updateMinWithKey :: (Interval k e, Ord k) => (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update or delete value at maximum key.
updateMaxWithKey :: (Interval k e, Ord k) => (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Retrieves the value associated with minimal key of
--   the map, and the map stripped of that element, or <a>Nothing</a> if
--   passed an empty map.
minView :: (Interval k e, Ord k) => IntervalMap k a -> Maybe (a, IntervalMap k a)

-- | <i>O(log n)</i>. Retrieves the value associated with maximal key of
--   the map, and the map stripped of that element, or <a>Nothing</a> if
--   passed an empty map.
maxView :: (Interval k e, Ord k) => IntervalMap k a -> Maybe (a, IntervalMap k a)

-- | <i>O(log n)</i>. Retrieves the minimal (key,value) pair of the map,
--   and the map stripped of that element, or <a>Nothing</a> if passed an
--   empty map.
--   
--   <pre>
--   minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
--   minViewWithKey empty == Nothing
--   </pre>
minViewWithKey :: (Interval k e, Ord k) => IntervalMap k a -> Maybe ((k, a), IntervalMap k a)

-- | <i>O(log n)</i>. Retrieves the maximal (key,value) pair of the map,
--   and the map stripped of that element, or <a>Nothing</a> if passed an
--   empty map.
maxViewWithKey :: (Interval k e, Ord k) => IntervalMap k a -> Maybe ((k, a), IntervalMap k a)

-- | Check red-black-tree and interval search augmentation invariants. For
--   testing/debugging only.
valid :: (Interval i k, Ord i) => IntervalMap i v -> Bool

-- | The height of the tree. For testing/debugging only.
height :: IntervalMap k v -> Int

-- | The maximum height of a red-black tree with the given number of nodes.
--   For testing/debugging only.
maxHeight :: Int -> Int

-- | Tree statistics (size, height, maxHeight size). For testing/debugging
--   only.
showStats :: IntervalMap k a -> (Int, Int, Int)


-- | An implementation of maps from intervals to values. The key intervals
--   may overlap, and the implementation contains efficient search
--   functions for all keys containing a point or overlapping an interval.
--   Closed, open, and half-open intervals can be contained in the same
--   map.
--   
--   This module implements the same functions as
--   <a>Data.IntervalMap.Strict</a>, but with value-lazy semantics.
module Data.IntervalMap.Lazy

-- | Intervals with endpoints of type <tt>a</tt>.
--   
--   <a>Read</a> and <a>Show</a> use mathematical notation with square
--   brackets for closed and parens for open intervals. This is better for
--   human readability, but is not a valid Haskell expression. Closed
--   intervals look like a list, open intervals look like a tuple, and
--   half-open intervals look like mismatched parens.
data Interval a

-- | Including lower bound, excluding upper
IntervalCO :: !a -> !a -> Interval a

-- | Closed at both ends
ClosedInterval :: !a -> !a -> Interval a

-- | Open at both ends
OpenInterval :: !a -> !a -> Interval a

-- | Excluding lower bound, including upper
IntervalOC :: !a -> !a -> Interval a
type IntervalMap k v = IntervalMap (Interval k) v

-- | <i>O(log n)</i>. Lookup value for given key. Calls <a>error</a> if the
--   key is not in the map.
--   
--   Use <a>lookup</a> or <a>findWithDefault</a> instead of this function,
--   unless you are absolutely sure that the key is present in the map.
(!) :: (Interval k e, Ord k) => IntervalMap k v -> k -> v

-- | Same as <a>difference</a>.
(\\) :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(1)</i>. Is the map empty?
null :: IntervalMap k v -> Bool

-- | <i>O(n)</i>. Number of keys in the map.
--   
--   Caution: unlike <a>size</a>, which takes constant time, this is linear
--   in the number of keys!
size :: IntervalMap k v -> Int

-- | <i>O(log n)</i>. Does the map contain the given key? See also
--   <a>notMember</a>.
member :: (Ord k) => k -> IntervalMap k v -> Bool

-- | <i>O(log n)</i>. Does the map not contain the given key? See also
--   <a>member</a>.
notMember :: (Ord k) => k -> IntervalMap k v -> Bool

-- | <i>O(log n)</i>. Look up the given key in the map, returning the value
--   <tt>(<a>Just</a> value)</tt>, or <a>Nothing</a> if the key is not in
--   the map.
lookup :: (Ord k) => k -> IntervalMap k v -> Maybe v

-- | <i>O(log n)</i>. The expression <tt>(<a>findWithDefault</a> def k
--   map)</tt> returns the value at key <tt>k</tt> or returns default value
--   <tt>def</tt> when the key is not in the map.
findWithDefault :: Ord k => a -> k -> IntervalMap k a -> a

-- | Return the submap of key intervals containing the given point. This is
--   the second element of the value of <a>splitAt</a>:
--   
--   <pre>
--   m `containing` p == let (_,m',_) = m `splitAt` p in m'
--   </pre>
--   
--   <i>O(n)</i>, since potentially all keys could contain the point.
--   <i>O(log n)</i> average case. This is also the worst case for maps
--   containing no overlapping keys.
containing :: (Interval k e) => IntervalMap k v -> e -> IntervalMap k v

-- | Return the submap of key intervals overlapping (intersecting) the
--   given interval. This is the second element of the value of
--   <a>splitIntersecting</a>:
--   
--   <pre>
--   m `intersecting` i == let (_,m',_) = m `splitIntersecting` i in m'
--   </pre>
--   
--   <i>O(n)</i>, since potentially all keys could intersect the interval.
--   <i>O(log n)</i> average case, if few keys intersect the interval.
intersecting :: (Interval k e) => IntervalMap k v -> k -> IntervalMap k v

-- | Return the submap of key intervals completely inside the given
--   interval.
--   
--   <i>O(n)</i>, since potentially all keys could be inside the interval.
--   <i>O(log n)</i> average case, if few keys are inside the interval.
within :: (Interval k e) => IntervalMap k v -> k -> IntervalMap k v

-- | <i>O(1)</i>. The empty map.
empty :: IntervalMap k v

-- | <i>O(1)</i>. A map with one entry.
singleton :: k -> v -> IntervalMap k v

-- | <i>O(log n)</i>. Insert a new key/value pair. If the map already
--   contains the key, its value is changed to the new value.
insert :: (Interval k e, Ord k) => k -> v -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Insert with a function, combining new value and old
--   value. <tt><a>insertWith</a> f key value mp</tt> will insert the pair
--   (key, value) into <tt>mp</tt> if key does not exist in the map. If the
--   key does exist, the function will insert the pair <tt>(key, f
--   new_value old_value)</tt>.
insertWith :: (Interval k e, Ord k) => (v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Insert with a function, combining key, new value and
--   old value. <tt><a>insertWithKey</a> f key value mp</tt> will insert
--   the pair (key, value) into <tt>mp</tt> if key does not exist in the
--   map. If the key does exist, the function will insert the pair
--   <tt>(key, f key new_value old_value)</tt>. Note that the key passed to
--   f is the same key passed to <a>insertWithKey</a>.
insertWithKey :: (Interval k e, Ord k) => (k -> v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Combine insert with old values retrieval.
insertLookupWithKey :: (Interval k e, Ord k) => (k -> v -> v -> v) -> k -> v -> IntervalMap k v -> (Maybe v, IntervalMap k v)

-- | <i>O(log n)</i>. Delete a key from the map. If the map does not
--   contain the key, it is returned unchanged.
delete :: (Interval k e, Ord k) => k -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update a value at a specific key with the result of
--   the provided function. When the key is not a member of the map, the
--   original map is returned.
adjust :: Ord k => (a -> a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. Adjust a value at a specific key. When the key is not
--   a member of the map, the original map is returned.
adjustWithKey :: Ord k => (k -> a -> a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. The expression (<tt><a>update</a> f k map</tt>)
--   updates the value <tt>x</tt> at <tt>k</tt> (if it is in the map). If
--   (<tt>f x</tt>) is <a>Nothing</a>, the element is deleted. If it is
--   (<tt><a>Just</a> y</tt>), the key <tt>k</tt> is bound to the new value
--   <tt>y</tt>.
update :: (Interval k e, Ord k) => (a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. The expression (<tt><a>updateWithKey</a> f k
--   map</tt>) updates the value <tt>x</tt> at <tt>k</tt> (if it is in the
--   map). If (<tt>f k x</tt>) is <a>Nothing</a>, the element is deleted.
--   If it is (<tt><a>Just</a> y</tt>), the key <tt>k</tt> is bound to the
--   new value <tt>y</tt>.
updateWithKey :: (Interval k e, Ord k) => (k -> a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(log n)</i>. Lookup and update. See also <a>updateWithKey</a>. The
--   function returns changed value, if it is updated. Returns the original
--   key value if the map entry is deleted.
updateLookupWithKey :: (Interval k e, Ord k) => (k -> a -> Maybe a) -> k -> IntervalMap k a -> (Maybe a, IntervalMap k a)

-- | <i>O(log n)</i>. The expression (<tt><a>alter</a> f k map</tt>) alters
--   the value <tt>x</tt> at <tt>k</tt>, or absence thereof. <a>alter</a>
--   can be used to insert, delete, or update a value in a <tt>Map</tt>. In
--   short : <tt><a>lookup</a> k (<a>alter</a> f k m) = f (<a>lookup</a> k
--   m)</tt>.
alter :: (Interval k e, Ord k) => (Maybe a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n+m)</i>. The expression (<tt><a>union</a> t1 t2</tt>) takes the
--   left-biased union of <tt>t1</tt> and <tt>t2</tt>. It prefers
--   <tt>t1</tt> when duplicate keys are encountered, i.e.
--   (<tt><a>union</a> == <a>unionWith</a> <a>const</a></tt>).
union :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n+m)</i>. Union with a combining function.
unionWith :: (Interval k e, Ord k) => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n+m)</i>. Union with a combining function.
unionWithKey :: (Interval k e, Ord k) => (k -> a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | The union of a list of maps: (<tt><a>unions</a> == <a>foldl</a>
--   <a>union</a> <a>empty</a></tt>).
unions :: (Interval k e, Ord k) => [IntervalMap k a] -> IntervalMap k a

-- | The union of a list of maps, with a combining operation:
--   (<tt><a>unionsWith</a> f == <a>foldl</a> (<a>unionWith</a> f)
--   <a>empty</a></tt>).
unionsWith :: (Interval k e, Ord k) => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a

-- | <i>O(n+m)</i>. Difference of two maps. Return elements of the first
--   map not existing in the second map.
difference :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Difference with a combining function. When two equal
--   keys are encountered, the combining function is applied to the values
--   of these keys. If it returns <a>Nothing</a>, the element is discarded
--   (proper set difference). If it returns (<tt><a>Just</a> y</tt>), the
--   element is updated with a new value <tt>y</tt>.
differenceWith :: (Interval k e, Ord k) => (a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Difference with a combining function. When two equal
--   keys are encountered, the combining function is applied to the key and
--   both values. If it returns <a>Nothing</a>, the element is discarded
--   (proper set difference). If it returns (<tt><a>Just</a> y</tt>), the
--   element is updated with a new value <tt>y</tt>.
differenceWithKey :: (Interval k e, Ord k) => (k -> a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Intersection of two maps. Return data in the first map
--   for the keys existing in both maps. (<tt><a>intersection</a> m1 m2 ==
--   <a>intersectionWith</a> <a>const</a> m1 m2</tt>).
intersection :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | <i>O(n+m)</i>. Intersection with a combining function.
intersectionWith :: (Interval k e, Ord k) => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c

-- | <i>O(n+m)</i>. Intersection with a combining function.
intersectionWithKey :: (Interval k e, Ord k) => (k -> a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c

-- | <i>O(n)</i>. Map a function over all values in the map.
map :: (a -> b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. Map a function over all values in the map.
mapWithKey :: (k -> a -> b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. The function <a>mapAccum</a> threads an accumulating
--   argument through the map in ascending order of keys.
mapAccum :: (a -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)

-- | <i>O(n)</i>. The function <a>mapAccumWithKey</a> threads an
--   accumulating argument through the map in ascending order of keys.
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)

-- | <i>O(n)</i>. The function <a>mapAccumRWithKey</a> threads an
--   accumulating argument through the map in descending order of keys.
mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)

-- | <i>O(n log n)</i>. <tt><a>mapKeys</a> f s</tt> is the map obtained by
--   applying <tt>f</tt> to each key of <tt>s</tt>.
--   
--   The size of the result may be smaller if <tt>f</tt> maps two or more
--   distinct keys to the same new key. In this case the value at the
--   smallest of these keys is retained.
mapKeys :: (Interval k2 e, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

-- | <i>O(n log n)</i>. <tt><a>mapKeysWith</a> c f s</tt> is the map
--   obtained by applying <tt>f</tt> to each key of <tt>s</tt>.
--   
--   The size of the result may be smaller if <tt>f</tt> maps two or more
--   distinct keys to the same new key. In this case the associated values
--   will be combined using <tt>c</tt>.
mapKeysWith :: (Interval k2 e, Ord k2) => (a -> a -> a) -> (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

-- | <i>O(n)</i>. <tt><a>mapKeysMonotonic</a> f s == <a>mapKeys</a> f
--   s</tt>, but works only when <tt>f</tt> is strictly monotonic. That is,
--   for any values <tt>x</tt> and <tt>y</tt>, if <tt>x</tt> &lt;
--   <tt>y</tt> then <tt>f x</tt> &lt; <tt>f y</tt>. <i>The precondition is
--   not checked.</i>
mapKeysMonotonic :: (Interval k2 e, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

-- | <i>O(n)</i>. Fold the values in the map using the given
--   right-associative binary operator, such that <tt><a>foldr</a> f z ==
--   <a>foldr</a> f z . <a>elems</a></tt>.
foldr :: (a -> b -> b) -> b -> IntervalMap k a -> b

-- | <i>O(n)</i>. Fold the values in the map using the given
--   left-associative binary operator, such that <tt><a>foldl</a> f z ==
--   <a>foldl</a> f z . <a>elems</a></tt>.
foldl :: (b -> a -> b) -> b -> IntervalMap k a -> b

-- | <i>O(n)</i>. Fold the keys and values in the map using the given
--   right-associative binary operator, such that <tt><a>foldrWithKey</a> f
--   z == <a>foldr</a> (<a>uncurry</a> f) z . <a>toAscList</a></tt>.
foldrWithKey :: (k -> v -> a -> a) -> a -> IntervalMap k v -> a

-- | <i>O(n)</i>. Fold the keys and values in the map using the given
--   left-associative binary operator, such that <tt><a>foldlWithKey</a> f
--   z == <a>foldl</a> (\z' (kx, x) -&gt; f z' kx x) z .
--   <a>toAscList</a></tt>.
foldlWithKey :: (a -> k -> v -> a) -> a -> IntervalMap k v -> a

-- | <i>O(n)</i>. The list of all key/value pairs contained in the map, in
--   descending order of keys.
flattenWith :: (Ord k) => (v -> v -> v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(n)</i>. List of all values in the map, in ascending order of
--   their keys.
elems :: IntervalMap k v -> [v]

-- | <i>O(n)</i>. List of all keys in the map, in ascending order.
keys :: IntervalMap k v -> [k]

-- | <i>O(n)</i>. Set of the keys.
keysSet :: (Ord k) => IntervalMap k v -> Set k

-- | Same as <a>toAscList</a>.
assocs :: IntervalMap k v -> [(k, v)]

-- | <i>O(n)</i>. The list of all key/value pairs contained in the map, in
--   no particular order.
toList :: IntervalMap k v -> [(k, v)]

-- | <i>O(n log n)</i>. Build a map from a list of key/value pairs. See
--   also <a>fromAscList</a>. If the list contains more than one value for
--   the same key, the last value for the key is retained.
fromList :: (Interval k e, Ord k) => [(k, v)] -> IntervalMap k v

-- | <i>O(n log n)</i>. Build a map from a list of key/value pairs with a
--   combining function. See also <a>fromAscListWith</a>.
fromListWith :: (Interval k e, Ord k) => (a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n log n)</i>. Build a map from a list of key/value pairs with a
--   combining function. See also <a>fromAscListWith</a>.
fromListWithKey :: (Interval k e, Ord k) => (k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n)</i>. The list of all key/value pairs contained in the map, in
--   ascending order of keys.
toAscList :: IntervalMap k v -> [(k, v)]

-- | <i>O(n)</i>. The list of all key/value pairs contained in the map, in
--   descending order of keys.
toDescList :: IntervalMap k v -> [(k, v)]

-- | <i>O(n)</i>. Build a map from an ascending list in linear time. <i>The
--   precondition (input list is ascending) is not checked.</i>
fromAscList :: (Interval k e, Eq k) => [(k, v)] -> IntervalMap k v

-- | <i>O(n)</i>. Build a map from an ascending list in linear time with a
--   combining function for equal keys. <i>The precondition (input list is
--   ascending) is not checked.</i>
fromAscListWith :: (Interval k e, Eq k) => (a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n)</i>. Build a map from an ascending list in linear time with a
--   combining function for equal keys. <i>The precondition (input list is
--   ascending) is not checked.</i>
fromAscListWithKey :: (Interval k e, Eq k) => (k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a

-- | <i>O(n)</i>. Build a map from an ascending list of elements with
--   distinct keys in linear time. <i>The precondition is not checked.</i>
fromDistinctAscList :: (Interval k e) => [(k, v)] -> IntervalMap k v

-- | <i>O(n)</i>. Filter values satisfying a predicate.
filter :: (Interval k e) => (a -> Bool) -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n)</i>. Filter keys/values satisfying a predicate.
filterWithKey :: (Interval k e) => (k -> a -> Bool) -> IntervalMap k a -> IntervalMap k a

-- | <i>O(n)</i>. Partition the map according to a predicate. The first map
--   contains all elements that satisfy the predicate, the second all
--   elements that fail the predicate. See also <a>split</a>.
partition :: (Interval k e) => (a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)

-- | <i>O(n)</i>. Partition the map according to a predicate. The first map
--   contains all elements that satisfy the predicate, the second all
--   elements that fail the predicate. See also <a>split</a>.
partitionWithKey :: (Interval k e) => (k -> a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)

-- | <i>O(n)</i>. Map values and collect the <a>Just</a> results.
mapMaybe :: (Interval k e) => (a -> Maybe b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. Map keys/values and collect the <a>Just</a> results.
mapMaybeWithKey :: (Interval k e) => (k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b

-- | <i>O(n)</i>. Map values and separate the <a>Left</a> and <a>Right</a>
--   results.
mapEither :: (Interval k e) => (a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)

-- | <i>O(n)</i>. Map keys/values and separate the <a>Left</a> and
--   <a>Right</a> results.
mapEitherWithKey :: (Interval i k) => (i -> a -> Either b c) -> IntervalMap i a -> (IntervalMap i b, IntervalMap i c)

-- | <i>O(n)</i>. The expression (<tt><a>split</a> k map</tt>) is a pair
--   <tt>(map1,map2)</tt> where the keys in <tt>map1</tt> are smaller than
--   <tt>k</tt> and the keys in <tt>map2</tt> larger than <tt>k</tt>. Any
--   key equal to <tt>k</tt> is found in neither <tt>map1</tt> nor
--   <tt>map2</tt>.
split :: (Interval i k, Ord i) => i -> IntervalMap i a -> (IntervalMap i a, IntervalMap i a)

-- | <i>O(n)</i>. The expression (<tt><a>splitLookup</a> k map</tt>) splits
--   a map just like <a>split</a> but also returns <tt><a>lookup</a> k
--   map</tt>.
splitLookup :: (Interval i k, Ord i) => i -> IntervalMap i a -> (IntervalMap i a, Maybe a, IntervalMap i a)

-- | <i>O(n)</i>. Split around a point. Splits the map into three submaps:
--   intervals below the point, intervals containing the point, and
--   intervals above the point.
splitAt :: (Interval i k, Ord i) => IntervalMap i a -> k -> (IntervalMap i a, IntervalMap i a, IntervalMap i a)

-- | <i>O(n)</i>. Split around an interval. Splits the set into three
--   subsets: intervals below the given interval, intervals intersecting
--   the given interval, and intervals above the given interval.
splitIntersecting :: (Interval i k, Ord i) => IntervalMap i a -> i -> (IntervalMap i a, IntervalMap i a, IntervalMap i a)

-- | <i>O(n+m)</i>. This function is defined as (<tt><a>isSubmapOf</a> =
--   <a>isSubmapOfBy</a> (==)</tt>).
isSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool

-- | <i>O(n+m)</i>. The expression (<tt><a>isSubmapOfBy</a> f t1 t2</tt>)
--   returns <a>True</a> if all keys in <tt>t1</tt> are in tree
--   <tt>t2</tt>, and <tt>f</tt> returns <a>True</a> when applied to their
--   respective values.
isSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool

-- | <i>O(n+m)</i>. Is this a proper submap? (ie. a submap but not equal).
--   Defined as (<tt><a>isProperSubmapOf</a> = <a>isProperSubmapOfBy</a>
--   (==)</tt>).
isProperSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool

-- | <i>O(n+m)</i>. Is this a proper submap? (ie. a submap but not equal).
--   The expression (<tt><a>isProperSubmapOfBy</a> f m1 m2</tt>) returns
--   <a>True</a> when <tt>m1</tt> and <tt>m2</tt> are not equal, all keys
--   in <tt>m1</tt> are in <tt>m2</tt>, and when <tt>f</tt> returns
--   <a>True</a> when applied to their respective values.
isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool

-- | <i>O(log n)</i>. Returns the smallest key and its associated value.
--   Calls <a>error</a> if the map is empty.
findMin :: IntervalMap k v -> (k, v)

-- | <i>O(log n)</i>. Returns the largest key and its associated value.
--   Calls <a>error</a> if the map is empty.
findMax :: IntervalMap k v -> (k, v)

-- | Returns the key with the largest endpoint and its associated value. If
--   there is more than one key with that endpoint, return the rightmost.
--   
--   <i>O(n)</i>, since all keys could have the same endpoint. <i>O(log
--   n)</i> average case.
findLast :: (Interval k e) => IntervalMap k v -> (k, v)

-- | <i>O(log n)</i>. Remove the smallest key from the map. Return the
--   empty map if the map is empty.
deleteMin :: (Interval k e, Ord k) => IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Remove the largest key from the map. Return the empty
--   map if the map is empty.
deleteMax :: (Interval k e, Ord k) => IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Delete and return the smallest key.
deleteFindMin :: (Interval k e, Ord k) => IntervalMap k v -> ((k, v), IntervalMap k v)

-- | <i>O(log n)</i>. Delete and return the largest key.
deleteFindMax :: (Interval k e, Ord k) => IntervalMap k v -> ((k, v), IntervalMap k v)

-- | <i>O(log n)</i>. Update or delete value at minimum key.
updateMin :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update or delete value at maximum key.
updateMax :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update or delete value at minimum key.
updateMinWithKey :: (Interval k e, Ord k) => (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Update or delete value at maximum key.
updateMaxWithKey :: (Interval k e, Ord k) => (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

-- | <i>O(log n)</i>. Retrieves the value associated with minimal key of
--   the map, and the map stripped of that element, or <a>Nothing</a> if
--   passed an empty map.
minView :: (Interval k e, Ord k) => IntervalMap k a -> Maybe (a, IntervalMap k a)

-- | <i>O(log n)</i>. Retrieves the value associated with maximal key of
--   the map, and the map stripped of that element, or <a>Nothing</a> if
--   passed an empty map.
maxView :: (Interval k e, Ord k) => IntervalMap k a -> Maybe (a, IntervalMap k a)

-- | <i>O(log n)</i>. Retrieves the minimal (key,value) pair of the map,
--   and the map stripped of that element, or <a>Nothing</a> if passed an
--   empty map.
--   
--   <pre>
--   minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
--   minViewWithKey empty == Nothing
--   </pre>
minViewWithKey :: (Interval k e, Ord k) => IntervalMap k a -> Maybe ((k, a), IntervalMap k a)

-- | <i>O(log n)</i>. Retrieves the maximal (key,value) pair of the map,
--   and the map stripped of that element, or <a>Nothing</a> if passed an
--   empty map.
maxViewWithKey :: (Interval k e, Ord k) => IntervalMap k a -> Maybe ((k, a), IntervalMap k a)

-- | Check red-black-tree and interval search augmentation invariants. For
--   testing/debugging only.
valid :: (Interval i k, Ord i) => IntervalMap i v -> Bool

-- | The height of the tree. For testing/debugging only.
height :: IntervalMap k v -> Int

-- | The maximum height of a red-black tree with the given number of nodes.
--   For testing/debugging only.
maxHeight :: Int -> Int

-- | Tree statistics (size, height, maxHeight size). For testing/debugging
--   only.
showStats :: IntervalMap k a -> (Int, Int, Int)


-- | An implementation of maps from intervals to values. The key intervals
--   may overlap, and the implementation contains efficient search
--   functions for all keys containing a point or overlapping an interval.
--   Closed, open, and half-open intervals can be contained in the same
--   map.
--   
--   This module re-exports the value lazy <a>Data.IntervalMap.Lazy</a>
--   API, plus several value strict functions from
--   <a>Data.IntervalMap.Strict</a>.
module Data.IntervalMap

-- | <i>Deprecated.</i> As of version 0.3, replaced by <a>insertWith</a>.
--   
--   <i>O(log n)</i>. Same as <a>insertWith</a>, but the combining function
--   is applied strictly. This is often the most desirable behavior.
--   
--   For example, to update a counter:
--   
--   <pre>
--   insertWith' (+) k 1 m
--   </pre>
insertWith' :: Ord k => (a -> a -> a) -> Interval k -> a -> IntervalMap k a -> IntervalMap k a

-- | <i>Deprecated.</i> As of version 0.3, replaced by
--   <a>insertWithKey</a>.
--   
--   <i>O(log n)</i>. Same as <a>insertWithKey</a>, but the combining
--   function is applied strictly.
insertWithKey' :: Ord k => (Interval k -> a -> a -> a) -> Interval k -> a -> IntervalMap k a -> IntervalMap k a

-- | <i>Deprecated.</i> As of version 0.3, replaced by
--   <a>insertLookupWithKey</a>.
--   
--   <i>O(log n)</i>. A strict version of <a>insertLookupWithKey</a>.
insertLookupWithKey' :: Ord k => (Interval k -> a -> a -> a) -> Interval k -> a -> IntervalMap k a -> (Maybe a, IntervalMap k a)

-- | <i>Deprecated.</i> As of version 0.5, replaced by <a>foldr</a>.
--   
--   <i>O(n)</i>. Fold the values in the map using the given
--   right-associative binary operator. This function is an equivalent of
--   <a>foldr</a> and is present for compatibility only.
fold :: (a -> b -> b) -> b -> IntervalMap k a -> b

-- | <i>Deprecated.</i> As of version 0.3, replaced by <a>foldrWithKey</a>.
--   
--   <i>O(n)</i>. Fold the keys and values in the map using the given
--   right-associative binary operator. This function is an equivalent of
--   <a>foldrWithKey</a> and is present for compatibility only.
foldWithKey :: (Interval k -> a -> b -> b) -> b -> IntervalMap k a -> b