{- |
Module      :  Data.IntervalMap.Generic.Strict
Copyright   :  (c) Christoph Breitkopf 2014
License     :  BSD-style
Maintainer  :  chbreitkopf@gmail.com
Stability   :  experimental
Portability :  non-portable (MPTC with FD)

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 "Data.IntervalMap.Lazy"
instead. The IntervalMap type itself is shared between the lazy and
strict modules, meaning that the same IntervalMap value can be passed
to functions in both modules (although that is rarely needed).

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: @IntervalMap /k/ [/v/]@.

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 /Prelude/
names, this module is usually imported @qualified@, e.g.

>  import Data.Generic.IntervalMap.Strict (IntervalMap)
>  import qualified Data.Generic.IntervalMap.Strict as IM

It offers most of the same functions as 'Data.Map', but the
key type must be an instance of 'Interval'.
Some functions differ in asymptotic performance (for example 'size') or
have not been tuned for efficiency as much as their equivalents in
'Data.Map' (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 'Data.Map'
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 (
            -- * re-export
            Interval(..)
            -- * Map type
            , IntervalMap      -- instance Eq,Show,Read

            -- * Operators
            , (!), (\\)

            -- * Query
            , null
            , size
            , member
            , notMember
            , lookup
            , findWithDefault
            , lookupLT
            , lookupGT
            , lookupLE
            , lookupGE

            -- ** Interval query
            , containing
            , intersecting
            , within
            
            -- * Construction
            , empty
            , singleton

            -- ** Insertion
            , insert
            , insertWith
            , insertWithKey
            , insertLookupWithKey
            
            -- ** Delete\/Update
            , delete
            , adjust
            , adjustWithKey
            , update
            , updateWithKey
            , updateLookupWithKey
            , alter

            -- * Combine

            -- ** Union
            , union
            , unionWith
            , unionWithKey
            , unions
            , unionsWith

            -- ** Difference
            , difference
            , differenceWith
            , differenceWithKey
            
            -- ** Intersection
            , intersection
            , intersectionWith
            , intersectionWithKey

            -- * Traversal
            -- ** Map
            , map
            , mapWithKey
            , mapAccum
            , mapAccumWithKey
            , mapAccumRWithKey
            , mapKeys
            , mapKeysWith
            , mapKeysMonotonic

            -- ** Fold
            , foldr, foldl
            , foldrWithKey, foldlWithKey
            , flattenWith, flattenWithMonotonic

            -- * Conversion
            , elems
            , keys
            , keysSet
            , assocs

            -- ** Lists
            , toList
            , fromList
            , fromListWith
            , fromListWithKey

            -- ** Ordered lists
            , toAscList
            , toDescList
            , fromAscList
            , fromAscListWith
            , fromAscListWithKey
            , fromDistinctAscList

            -- * Filter
            , filter
            , filterWithKey
            , partition
            , partitionWithKey

            , mapMaybe
            , mapMaybeWithKey
            , mapEither
            , mapEitherWithKey

            , split
            , splitLookup
            , splitAt
            , splitIntersecting

            -- * Submap
            , isSubmapOf, isSubmapOfBy
            , isProperSubmapOf, isProperSubmapOfBy

            -- * Min\/Max
            , findMin
            , findMax
            , findLast
            , lookupMin
            , lookupMax
            , lookupLast
            , deleteMin
            , deleteMax
            , deleteFindMin
            , deleteFindMax
            , updateMin
            , updateMax
            , updateMinWithKey
            , updateMaxWithKey
            , minView
            , maxView
            , minViewWithKey
            , maxViewWithKey

            -- * Debugging
            , valid

            -- * Testing
            , height, maxHeight, showStats

            ) where

import Prelude hiding (null, lookup, map, filter, foldr, foldl, splitAt)
import qualified Data.List as L
import Data.Maybe (fromMaybe)
import Data.IntervalMap.Generic.Base as M hiding (
      singleton
    , insert
    , insertWith
    , insertWithKey
    , findWithDefault
    , insertLookupWithKey
    , adjust
    , adjustWithKey
    , update
    , updateWithKey
    , updateLookupWithKey
    , alter
    , unionWith
    , unionWithKey
    , unionsWith
    , differenceWith
    , differenceWithKey
    , intersectionWith
    , intersectionWithKey
    , map
    , mapWithKey
    , mapAccum
    , mapAccumWithKey
    , mapAccumRWithKey
    , mapKeysWith
    , fromList
    , fromListWith
    , fromListWithKey
    , fromAscList
    , fromAscListWith
    , fromAscListWithKey
    , mapMaybe
    , mapMaybeWithKey
    , mapEither
    , mapEitherWithKey
    , updateMin
    , updateMax
    , updateMinWithKey
    , updateMaxWithKey
  )

-- | /O(1)/. A map with one entry.
singleton :: k -> v -> IntervalMap k v
singleton :: forall k v. k -> v -> IntervalMap k v
singleton k
k v
v = v
v v -> IntervalMap k v -> IntervalMap k v
forall a b. a -> b -> b
`seq` Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
forall k v.
Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
Node Color
B k
k k
k v
v IntervalMap k v
forall k v. IntervalMap k v
Nil IntervalMap k v
forall k v. IntervalMap k v
Nil


-- | /O(log n)/. The expression @('findWithDefault' def k map)@ returns
-- the value at key @k@ or returns default value @def@
-- when the key is not in the map.
--
-- > findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
-- > findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
findWithDefault :: Ord k => a -> k -> IntervalMap k a -> a
findWithDefault :: forall k a. Ord k => a -> k -> IntervalMap k a -> a
findWithDefault a
def k
k IntervalMap k a
m = a
def a -> a -> a
forall a b. a -> b -> b
`seq` a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe a
def (k -> IntervalMap k a -> Maybe a
forall k v. Ord k => k -> IntervalMap k v -> Maybe v
M.lookup k
k IntervalMap k a
m)

-- | /O(log n)/. 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
insert :: forall k e v.
(Interval k e, Ord k) =>
k -> v -> IntervalMap k v -> IntervalMap k v
insert =  (k -> v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v
forall k e v.
(Interval k e, Ord k) =>
(k -> v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v
insertWithKey (\k
_ v
v v
_ -> v
v)

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

-- | /O(log n)/. Insert with a function, combining key, new value and old value.
-- @'insertWithKey' f key value mp@ 
-- will insert the pair (key, value) into @mp@ if key does
-- not exist in the map. If the key does exist, the function will
-- insert the pair @(key, f key new_value old_value)@.
-- Note that the key passed to f is the same key passed to 'insertWithKey'.
insertWithKey :: (Interval k e, Ord k) => (k -> v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v
insertWithKey :: forall k e v.
(Interval k e, Ord k) =>
(k -> v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v
insertWithKey k -> v -> v -> v
f k
key v
value IntervalMap k v
mp  =  k
key k -> IntervalMap k v -> IntervalMap k v
forall a b. a -> b -> b
`seq` IntervalMap k v -> IntervalMap k v
forall k v. IntervalMap k v -> IntervalMap k v
turnBlack (IntervalMap k v -> IntervalMap k v
ins IntervalMap k v
mp)
  where
    singletonR :: k -> v -> IntervalMap k v
singletonR k
k v
v = Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
forall k v.
Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
Node Color
R k
k k
k v
v IntervalMap k v
forall k v. IntervalMap k v
Nil IntervalMap k v
forall k v. IntervalMap k v
Nil
    ins :: IntervalMap k v -> IntervalMap k v
ins IntervalMap k v
Nil = v
value v -> IntervalMap k v -> IntervalMap k v
forall a b. a -> b -> b
`seq` k -> v -> IntervalMap k v
forall k v. k -> v -> IntervalMap k v
singletonR k
key v
value
    ins (Node Color
color k
k k
m v
v IntervalMap k v
l IntervalMap k v
r) =
      case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
key k
k of
        Ordering
LT -> Color
-> k -> v -> IntervalMap k v -> IntervalMap k v -> IntervalMap k v
forall k e v.
Interval k e =>
Color
-> k -> v -> IntervalMap k v -> IntervalMap k v -> IntervalMap k v
balanceL Color
color k
k v
v (IntervalMap k v -> IntervalMap k v
ins IntervalMap k v
l) IntervalMap k v
r
        Ordering
GT -> Color
-> k -> v -> IntervalMap k v -> IntervalMap k v -> IntervalMap k v
forall k e v.
Interval k e =>
Color
-> k -> v -> IntervalMap k v -> IntervalMap k v -> IntervalMap k v
balanceR Color
color k
k v
v IntervalMap k v
l (IntervalMap k v -> IntervalMap k v
ins IntervalMap k v
r)
        Ordering
EQ -> let v' :: v
v' = k -> v -> v -> v
f k
k v
value v
v in v
v' v -> IntervalMap k v -> IntervalMap k v
forall a b. a -> b -> b
`seq` Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
forall k v.
Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
Node Color
color k
k k
m v
v' IntervalMap k v
l IntervalMap k v
r


-- | /O(log n)/. 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)
insertLookupWithKey :: forall k e v.
(Interval k e, Ord k) =>
(k -> v -> v -> v)
-> k -> v -> IntervalMap k v -> (Maybe v, IntervalMap k v)
insertLookupWithKey k -> v -> v -> v
f k
key v
value IntervalMap k v
mp  =  k
key k -> (Maybe v, IntervalMap k v) -> (Maybe v, IntervalMap k v)
forall a b. a -> b -> b
`seq` (Maybe v
oldval, IntervalMap k v -> IntervalMap k v
forall k v. IntervalMap k v -> IntervalMap k v
turnBlack IntervalMap k v
mp')
  where
    (Maybe v
oldval, IntervalMap k v
mp') = IntervalMap k v -> (Maybe v, IntervalMap k v)
ins IntervalMap k v
mp
    singletonR :: k -> v -> IntervalMap k v
singletonR k
k v
v = Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
forall k v.
Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
Node Color
R k
k k
k v
v IntervalMap k v
forall k v. IntervalMap k v
Nil IntervalMap k v
forall k v. IntervalMap k v
Nil
    ins :: IntervalMap k v -> (Maybe v, IntervalMap k v)
ins IntervalMap k v
Nil = v
value v -> (Maybe v, IntervalMap k v) -> (Maybe v, IntervalMap k v)
forall a b. a -> b -> b
`seq` (Maybe v
forall a. Maybe a
Nothing, k -> v -> IntervalMap k v
forall k v. k -> v -> IntervalMap k v
singletonR k
key v
value)
    ins (Node Color
color k
k k
m v
v IntervalMap k v
l IntervalMap k v
r) =
      case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
key k
k of
        Ordering
LT -> case IntervalMap k v -> (Maybe v, IntervalMap k v)
ins IntervalMap k v
l of
                 (x :: Maybe v
x@(Just v
_), IntervalMap k v
t') -> (Maybe v
x, Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
forall k v.
Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
Node Color
color k
k k
m v
v IntervalMap k v
t' IntervalMap k v
r)
                 (Maybe v
Nothing, IntervalMap k v
t') -> (Maybe v
forall a. Maybe a
Nothing, Color
-> k -> v -> IntervalMap k v -> IntervalMap k v -> IntervalMap k v
forall k e v.
Interval k e =>
Color
-> k -> v -> IntervalMap k v -> IntervalMap k v -> IntervalMap k v
balanceL Color
color k
k v
v IntervalMap k v
t' IntervalMap k v
r)
        Ordering
GT -> case IntervalMap k v -> (Maybe v, IntervalMap k v)
ins IntervalMap k v
r of
                 (x :: Maybe v
x@(Just v
_), IntervalMap k v
t') -> (Maybe v
x, Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
forall k v.
Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
Node Color
color k
k k
m v
v IntervalMap k v
l IntervalMap k v
t')
                 (Maybe v
Nothing, IntervalMap k v
t') -> (Maybe v
forall a. Maybe a
Nothing, Color
-> k -> v -> IntervalMap k v -> IntervalMap k v -> IntervalMap k v
forall k e v.
Interval k e =>
Color
-> k -> v -> IntervalMap k v -> IntervalMap k v -> IntervalMap k v
balanceR Color
color k
k v
v IntervalMap k v
l IntervalMap k v
t')
        Ordering
EQ -> let v' :: v
v' = k -> v -> v -> v
f k
k v
value v
v in v
v' v -> (Maybe v, IntervalMap k v) -> (Maybe v, IntervalMap k v)
forall a b. a -> b -> b
`seq` (v -> Maybe v
forall a. a -> Maybe a
Just v
v, Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
forall k v.
Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
Node Color
color k
k k
m v
v' IntervalMap k v
l IntervalMap k v
r)


-- | /O(log n)/. 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
adjust :: forall k a.
Ord k =>
(a -> a) -> k -> IntervalMap k a -> IntervalMap k a
adjust a -> a
f k
k IntervalMap k a
m = (k -> a -> a) -> k -> IntervalMap k a -> IntervalMap k a
forall k a.
Ord k =>
(k -> a -> a) -> k -> IntervalMap k a -> IntervalMap k a
adjustWithKey (\k
_ a
v -> a -> a
f a
v) k
k IntervalMap k a
m

-- | /O(log n)/. 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
adjustWithKey :: forall k a.
Ord k =>
(k -> a -> a) -> k -> IntervalMap k a -> IntervalMap k a
adjustWithKey k -> a -> a
_ k
_ IntervalMap k a
Nil = IntervalMap k a
forall k v. IntervalMap k v
Nil
adjustWithKey k -> a -> a
f k
x (Node Color
c k
k k
m a
v IntervalMap k a
l IntervalMap k a
r) =
  case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
x k
k of
    Ordering
LT -> Color
-> k
-> k
-> a
-> IntervalMap k a
-> IntervalMap k a
-> IntervalMap k a
forall k v.
Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
Node Color
c k
k k
m a
v ((k -> a -> a) -> k -> IntervalMap k a -> IntervalMap k a
forall k a.
Ord k =>
(k -> a -> a) -> k -> IntervalMap k a -> IntervalMap k a
adjustWithKey k -> a -> a
f k
x IntervalMap k a
l) IntervalMap k a
r
    Ordering
GT -> Color
-> k
-> k
-> a
-> IntervalMap k a
-> IntervalMap k a
-> IntervalMap k a
forall k v.
Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
Node Color
c k
k k
m a
v IntervalMap k a
l ((k -> a -> a) -> k -> IntervalMap k a -> IntervalMap k a
forall k a.
Ord k =>
(k -> a -> a) -> k -> IntervalMap k a -> IntervalMap k a
adjustWithKey k -> a -> a
f k
x IntervalMap k a
r)
    Ordering
EQ -> let v' :: a
v' = k -> a -> a
f k
k a
v in a
v' a -> IntervalMap k a -> IntervalMap k a
forall a b. a -> b -> b
`seq` Color
-> k
-> k
-> a
-> IntervalMap k a
-> IntervalMap k a
-> IntervalMap k a
forall k v.
Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
Node Color
c k
k k
m a
v' IntervalMap k a
l IntervalMap k a
r

-- | /O(log n)/. Update or delete value at minimum key.
updateMin :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
updateMin :: forall k e v.
(Interval k e, Ord k) =>
(v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
updateMin v -> Maybe v
f IntervalMap k v
m = (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
forall k e v.
(Interval k e, Ord k) =>
(k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
updateMinWithKey (\k
_ v
v -> v -> Maybe v
f v
v) IntervalMap k v
m

-- | /O(log n)/. Update or delete value at maximum key.
updateMax :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
updateMax :: forall k e v.
(Interval k e, Ord k) =>
(v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
updateMax v -> Maybe v
f IntervalMap k v
m = (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
forall k e v.
(Interval k e, Ord k) =>
(k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
updateMaxWithKey (\k
_ v
v -> v -> Maybe v
f v
v) IntervalMap k v
m

-- | /O(log n)/. Update or delete value at minimum key.
updateMinWithKey :: (Interval k e, Ord k) => (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
updateMinWithKey :: forall k e v.
(Interval k e, Ord k) =>
(k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
updateMinWithKey k -> v -> Maybe v
_ IntervalMap k v
Nil = IntervalMap k v
forall k v. IntervalMap k v
Nil
updateMinWithKey k -> v -> Maybe v
f IntervalMap k v
m = let (k
k,v
v) = IntervalMap k v -> (k, v)
forall k v. IntervalMap k v -> (k, v)
findMin IntervalMap k v
m in
                       case k -> v -> Maybe v
f k
k v
v of
                         Just v
v' -> v
v' v -> IntervalMap k v -> IntervalMap k v
forall a b. a -> b -> b
`seq` v -> IntervalMap k v -> IntervalMap k v
forall v k. v -> IntervalMap k v -> IntervalMap k v
setMinValue v
v' IntervalMap k v
m
                         Maybe v
Nothing -> IntervalMap k v -> IntervalMap k v
forall k e v.
(Interval k e, Ord k) =>
IntervalMap k v -> IntervalMap k v
deleteMin IntervalMap k v
m

-- | /O(log n)/. Update or delete value at maximum key.
updateMaxWithKey :: (Interval k e, Ord k) => (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
updateMaxWithKey :: forall k e v.
(Interval k e, Ord k) =>
(k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
updateMaxWithKey k -> v -> Maybe v
_ IntervalMap k v
Nil = IntervalMap k v
forall k v. IntervalMap k v
Nil
updateMaxWithKey k -> v -> Maybe v
f IntervalMap k v
m = let (k
k,v
v) = IntervalMap k v -> (k, v)
forall k v. IntervalMap k v -> (k, v)
findMax IntervalMap k v
m in
                       case k -> v -> Maybe v
f k
k v
v of
                         Just v
v' -> v
v' v -> IntervalMap k v -> IntervalMap k v
forall a b. a -> b -> b
`seq` v -> IntervalMap k v -> IntervalMap k v
forall v k. v -> IntervalMap k v -> IntervalMap k v
setMaxValue v
v' IntervalMap k v
m
                         Maybe v
Nothing -> IntervalMap k v -> IntervalMap k v
forall k e v.
(Interval k e, Ord k) =>
IntervalMap k v -> IntervalMap k v
deleteMax IntervalMap k v
m

-- | /O(n log n)/. Build a map from a list of key\/value pairs. See also 'fromAscList'.
-- 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
fromList :: forall k e v. (Interval k e, Ord k) => [(k, v)] -> IntervalMap k v
fromList [(k, v)]
xs = (IntervalMap k v -> (k, v) -> IntervalMap k v)
-> IntervalMap k v -> [(k, v)] -> IntervalMap k v
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl' (\IntervalMap k v
m (k
k,v
v) -> k -> v -> IntervalMap k v -> IntervalMap k v
forall k e v.
(Interval k e, Ord k) =>
k -> v -> IntervalMap k v -> IntervalMap k v
insert k
k v
v IntervalMap k v
m) IntervalMap k v
forall k v. IntervalMap k v
empty [(k, v)]
xs

-- | /O(n log n)/. Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWith'.
fromListWith :: (Interval k e, Ord k) => (a -> a -> a) -> [(k,a)] -> IntervalMap k a
fromListWith :: forall k e a.
(Interval k e, Ord k) =>
(a -> a -> a) -> [(k, a)] -> IntervalMap k a
fromListWith a -> a -> a
f [(k, a)]
xs = (k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a
forall k e a.
(Interval k e, Ord k) =>
(k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a
fromListWithKey (\k
_ a
x a
y -> a -> a -> a
f a
x a
y) [(k, a)]
xs

-- | /O(n log n)/. Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWith'.
fromListWithKey :: (Interval k e, Ord k) => (k -> a -> a -> a) -> [(k,a)] -> IntervalMap k a
fromListWithKey :: forall k e a.
(Interval k e, Ord k) =>
(k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a
fromListWithKey k -> a -> a -> a
f [(k, a)]
xs = (IntervalMap k a -> (k, a) -> IntervalMap k a)
-> IntervalMap k a -> [(k, a)] -> IntervalMap k a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl' IntervalMap k a -> (k, a) -> IntervalMap k a
ins IntervalMap k a
forall k v. IntervalMap k v
empty [(k, a)]
xs
  where
    ins :: IntervalMap k a -> (k, a) -> IntervalMap k a
ins IntervalMap k a
t (k
k,a
x) = (k -> a -> a -> a) -> k -> a -> IntervalMap k a -> IntervalMap k a
forall k e v.
(Interval k e, Ord k) =>
(k -> v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v
insertWithKey k -> a -> a -> a
f k
k a
x IntervalMap k a
t

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

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

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

combineEq :: Eq k => (k -> a -> a -> a) -> [(k,a)] -> [(k,a)]
combineEq :: forall k a. Eq k => (k -> a -> a -> a) -> [(k, a)] -> [(k, a)]
combineEq k -> a -> a -> a
_ [] = []
combineEq k -> a -> a -> a
_ xs :: [(k, a)]
xs@[(k, a)
_] = [(k, a)]
xs
combineEq k -> a -> a -> a
f (x :: (k, a)
x@(k
xk,a
xv) : xs :: [(k, a)]
xs@((k
yk,a
yv) : [(k, a)]
xs'))
  | k
xk k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
yk  = let v' :: a
v' = k -> a -> a -> a
f k
xk a
xv a
yv in a
v' a -> [(k, a)] -> [(k, a)]
forall a b. a -> b -> b
`seq` (k -> a -> a -> a) -> [(k, a)] -> [(k, a)]
forall k a. Eq k => (k -> a -> a -> a) -> [(k, a)] -> [(k, a)]
combineEq k -> a -> a -> a
f ((k
xk, a
v') (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: [(k, a)]
xs')
  | Bool
otherwise = (k, a)
x (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: (k -> a -> a -> a) -> [(k, a)] -> [(k, a)]
forall k a. Eq k => (k -> a -> a -> a) -> [(k, a)] -> [(k, a)]
combineEq k -> a -> a -> a
f [(k, a)]
xs


-- | /O(n)/. Map a function over all values in the map.
map :: (a -> b) -> IntervalMap k a -> IntervalMap k b
map :: forall a b k. (a -> b) -> IntervalMap k a -> IntervalMap k b
map a -> b
f = (k -> a -> b) -> IntervalMap k a -> IntervalMap k b
forall k a b. (k -> a -> b) -> IntervalMap k a -> IntervalMap k b
mapWithKey (\k
_ a
x -> a -> b
f a
x)

-- | /O(n)/. Map a function over all values in the map.
mapWithKey :: (k -> a -> b) -> IntervalMap k a -> IntervalMap k b
mapWithKey :: forall k a b. (k -> a -> b) -> IntervalMap k a -> IntervalMap k b
mapWithKey k -> a -> b
f = IntervalMap k a -> IntervalMap k b
go
  where
    go :: IntervalMap k a -> IntervalMap k b
go IntervalMap k a
Nil = IntervalMap k b
forall k v. IntervalMap k v
Nil
    go (Node Color
c k
k k
m a
v IntervalMap k a
l IntervalMap k a
r) = let v' :: b
v' = k -> a -> b
f k
k a
v in b
v' b -> IntervalMap k b -> IntervalMap k b
forall a b. a -> b -> b
`seq` Color
-> k
-> k
-> b
-> IntervalMap k b
-> IntervalMap k b
-> IntervalMap k b
forall k v.
Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
Node Color
c k
k k
m b
v' (IntervalMap k a -> IntervalMap k b
go IntervalMap k a
l) (IntervalMap k a -> IntervalMap k b
go IntervalMap k a
r)

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

-- | /O(n)/. The function 'mapAccumWithKey' threads an accumulating
-- argument through the map in ascending order of keys.
--
-- > 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")])
mapAccumWithKey :: (a -> k -> b -> (a,c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)
mapAccumWithKey :: forall a k b c.
(a -> k -> b -> (a, c))
-> a -> IntervalMap k b -> (a, IntervalMap k c)
mapAccumWithKey a -> k -> b -> (a, c)
f = a -> IntervalMap k b -> (a, IntervalMap k c)
go
  where
    go :: a -> IntervalMap k b -> (a, IntervalMap k c)
go a
a IntervalMap k b
Nil               = (a
a,IntervalMap k c
forall k v. IntervalMap k v
Nil)
    go a
a (Node Color
c k
kx k
m b
x IntervalMap k b
l IntervalMap k b
r) =
                 let (a
a1,IntervalMap k c
l') = a -> IntervalMap k b -> (a, IntervalMap k c)
go a
a IntervalMap k b
l
                     (a
a2,c
x') = a -> k -> b -> (a, c)
f a
a1 k
kx b
x
                     (a
a3,IntervalMap k c
r') = a -> IntervalMap k b -> (a, IntervalMap k c)
go a
a2 IntervalMap k b
r
                 in c
x' c -> (a, IntervalMap k c) -> (a, IntervalMap k c)
forall a b. a -> b -> b
`seq` (a
a3, Color
-> k
-> k
-> c
-> IntervalMap k c
-> IntervalMap k c
-> IntervalMap k c
forall k v.
Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
Node Color
c k
kx k
m c
x' IntervalMap k c
l' IntervalMap k c
r')

-- | /O(n)/. The function 'mapAccumRWithKey' 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)
mapAccumRWithKey :: forall a k b c.
(a -> k -> b -> (a, c))
-> a -> IntervalMap k b -> (a, IntervalMap k c)
mapAccumRWithKey a -> k -> b -> (a, c)
f = a -> IntervalMap k b -> (a, IntervalMap k c)
go
  where
    go :: a -> IntervalMap k b -> (a, IntervalMap k c)
go a
a IntervalMap k b
Nil = (a
a, IntervalMap k c
forall k v. IntervalMap k v
Nil)
    go a
a (Node Color
c k
kx k
m b
x IntervalMap k b
l IntervalMap k b
r) =
                 let (a
a1,IntervalMap k c
r') = a -> IntervalMap k b -> (a, IntervalMap k c)
go a
a IntervalMap k b
r
                     (a
a2,c
x') = a -> k -> b -> (a, c)
f a
a1 k
kx b
x
                     (a
a3,IntervalMap k c
l') = a -> IntervalMap k b -> (a, IntervalMap k c)
go a
a2 IntervalMap k b
l
                 in c
x' c -> (a, IntervalMap k c) -> (a, IntervalMap k c)
forall a b. a -> b -> b
`seq` (a
a3, Color
-> k
-> k
-> c
-> IntervalMap k c
-> IntervalMap k c
-> IntervalMap k c
forall k v.
Color
-> k
-> k
-> v
-> IntervalMap k v
-> IntervalMap k v
-> IntervalMap k v
Node Color
c k
kx k
m c
x' IntervalMap k c
l' IntervalMap k c
r')


-- | /O(n)/. Map values and collect the 'Just' results.
mapMaybe :: (Interval k e) => (a -> Maybe b) -> IntervalMap k a -> IntervalMap k b
mapMaybe :: forall k e a b.
Interval k e =>
(a -> Maybe b) -> IntervalMap k a -> IntervalMap k b
mapMaybe a -> Maybe b
f IntervalMap k a
m = (k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b
forall k e a b.
Interval k e =>
(k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b
mapMaybeWithKey (\k
_ a
v -> a -> Maybe b
f a
v) IntervalMap k a
m

-- | /O(n)/. Map keys\/values and collect the 'Just' results.
mapMaybeWithKey :: (Interval k e) => (k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b
mapMaybeWithKey :: forall k e a b.
Interval k e =>
(k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b
mapMaybeWithKey k -> a -> Maybe b
f IntervalMap k a
m = [(k, b)] -> IntervalMap k b
forall k e v. Interval k e => [(k, v)] -> IntervalMap k v
fromDistinctAscList ([(k, b)] -> IntervalMap k a -> [(k, b)]
mapf [] IntervalMap k a
m)
  where
    mapf :: [(k, b)] -> IntervalMap k a -> [(k, b)]
mapf [(k, b)]
z IntervalMap k a
Nil = [(k, b)]
z
    mapf [(k, b)]
z (Node Color
_ k
k k
_ a
v IntervalMap k a
l IntervalMap k a
r) = [(k, b)] -> IntervalMap k a -> [(k, b)]
mapf (k -> a -> [(k, b)] -> IntervalMap k a -> [(k, b)]
f' k
k a
v [(k, b)]
z IntervalMap k a
r) IntervalMap k a
l
    f' :: k -> a -> [(k, b)] -> IntervalMap k a -> [(k, b)]
f' k
k a
v [(k, b)]
z IntervalMap k a
r = case k -> a -> Maybe b
f k
k a
v of
                   Maybe b
Nothing -> [(k, b)] -> IntervalMap k a -> [(k, b)]
mapf [(k, b)]
z IntervalMap k a
r
                   Just b
v' -> b
v' b -> [(k, b)] -> [(k, b)]
forall a b. a -> b -> b
`seq` (k
k,b
v') (k, b) -> [(k, b)] -> [(k, b)]
forall a. a -> [a] -> [a]
: [(k, b)] -> IntervalMap k a -> [(k, b)]
mapf [(k, b)]
z IntervalMap k a
r

-- | /O(n)/. Map values and separate the 'Left' and 'Right' results.
mapEither :: (Interval k e) => (a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)
mapEither :: forall k e a b c.
Interval k e =>
(a -> Either b c)
-> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)
mapEither a -> Either b c
f IntervalMap k a
m = (k -> a -> Either b c)
-> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)
forall k e a b c.
Interval k e =>
(k -> a -> Either b c)
-> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)
mapEitherWithKey (\k
_ a
v -> a -> Either b c
f a
v) IntervalMap k a
m

-- | /O(n)/. Map keys\/values and separate the 'Left' and 'Right' results.
mapEitherWithKey :: (Interval k e) => (k -> a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)
mapEitherWithKey :: forall k e a b c.
Interval k e =>
(k -> a -> Either b c)
-> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)
mapEitherWithKey k -> a -> Either b c
f IntervalMap k a
m = ([(k, b)] -> IntervalMap k b
forall k e v. Interval k e => [(k, v)] -> IntervalMap k v
fromDistinctAscList [(k, b)]
l, [(k, c)] -> IntervalMap k c
forall k e v. Interval k e => [(k, v)] -> IntervalMap k v
fromDistinctAscList [(k, c)]
r)
  where
    ([(k, b)]
l, [(k, c)]
r) = [(k, b)] -> [(k, c)] -> [(k, a)] -> ([(k, b)], [(k, c)])
part [] [] (IntervalMap k a -> [(k, a)]
forall k v. IntervalMap k v -> [(k, v)]
toDescList IntervalMap k a
m)
    part :: [(k, b)] -> [(k, c)] -> [(k, a)] -> ([(k, b)], [(k, c)])
part [(k, b)]
ls [(k, c)]
rs [] = ([(k, b)]
ls, [(k, c)]
rs)
    part [(k, b)]
ls [(k, c)]
rs ((k
k,a
v):[(k, a)]
xs) = case k -> a -> Either b c
f k
k a
v of
                              Left b
v'  -> b
v' b -> ([(k, b)], [(k, c)]) -> ([(k, b)], [(k, c)])
forall a b. a -> b -> b
`seq` [(k, b)] -> [(k, c)] -> [(k, a)] -> ([(k, b)], [(k, c)])
part ((k
k,b
v')(k, b) -> [(k, b)] -> [(k, b)]
forall a. a -> [a] -> [a]
:[(k, b)]
ls) [(k, c)]
rs [(k, a)]
xs
                              Right c
v' -> c
v' c -> ([(k, b)], [(k, c)]) -> ([(k, b)], [(k, c)])
forall a b. a -> b -> b
`seq` [(k, b)] -> [(k, c)] -> [(k, a)] -> ([(k, b)], [(k, c)])
part [(k, b)]
ls ((k
k,c
v')(k, c) -> [(k, c)] -> [(k, c)]
forall a. a -> [a] -> [a]
:[(k, c)]
rs) [(k, a)]
xs


-- | /O(log n)/. The expression (@'alter' f k map@) alters the value @x@ at @k@, or absence thereof.
-- 'alter' can be used to insert, delete, or update a value in a 'Map'.
-- In short : @'lookup' k ('alter' f k m) = f ('lookup' k m)@.
alter :: (Interval k e, Ord k) => (Maybe a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a
alter :: forall k e a.
(Interval k e, Ord k) =>
(Maybe a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a
alter Maybe a -> Maybe a
f k
x IntervalMap k a
m = case k -> IntervalMap k a -> Maybe a
forall k v. Ord k => k -> IntervalMap k v -> Maybe v
lookup k
x IntervalMap k a
m of
                Maybe a
Nothing -> case Maybe a -> Maybe a
f Maybe a
forall a. Maybe a
Nothing of
                             Maybe a
Nothing -> IntervalMap k a
m
                             Just a
v -> k -> a -> IntervalMap k a -> IntervalMap k a
forall k e v.
(Interval k e, Ord k) =>
k -> v -> IntervalMap k v -> IntervalMap k v
insert k
x a
v IntervalMap k a
m
                Maybe a
y       -> case Maybe a -> Maybe a
f Maybe a
y of
                             Maybe a
Nothing -> k -> IntervalMap k a -> IntervalMap k a
forall k e v.
(Interval k e, Ord k) =>
k -> IntervalMap k v -> IntervalMap k v
delete k
x IntervalMap k a
m
                             Just a
v' -> (a -> a) -> k -> IntervalMap k a -> IntervalMap k a
forall k a.
Ord k =>
(a -> a) -> k -> IntervalMap k a -> IntervalMap k a
adjust (a -> a -> a
forall a b. a -> b -> a
const a
v') k
x IntervalMap k a
m


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

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

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

-- | /O(log n)/. Lookup and update. See also 'updateWithKey'.
-- 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)
updateLookupWithKey :: forall k e a.
(Interval k e, Ord k) =>
(k -> a -> Maybe a)
-> k -> IntervalMap k a -> (Maybe a, IntervalMap k a)
updateLookupWithKey k -> a -> Maybe a
f k
x IntervalMap k a
m = case k -> IntervalMap k a -> Maybe a
forall k v. Ord k => k -> IntervalMap k v -> Maybe v
lookup k
x IntervalMap k a
m of
                              Maybe a
Nothing -> (Maybe a
forall a. Maybe a
Nothing, IntervalMap k a
m)
                              r :: Maybe a
r@(Just a
v) -> case k -> a -> Maybe a
f k
x a
v of
                                              Maybe a
Nothing -> (Maybe a
r, k -> IntervalMap k a -> IntervalMap k a
forall k e v.
(Interval k e, Ord k) =>
k -> IntervalMap k v -> IntervalMap k v
delete k
x IntervalMap k a
m)
                                              r' :: Maybe a
r'@(Just a
v') -> (Maybe a
r', (a -> a) -> k -> IntervalMap k a -> IntervalMap k a
forall k a.
Ord k =>
(a -> a) -> k -> IntervalMap k a -> IntervalMap k a
adjust (a -> a -> a
forall a b. a -> b -> a
const a
v') k
x IntervalMap k a
m)


-- | /O(n+m)/. Union with a combining function.
unionWith :: (Interval k e, Ord k) => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
unionWith :: forall k e a.
(Interval k e, Ord k) =>
(a -> a -> a)
-> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
unionWith a -> a -> a
f IntervalMap k a
m1 IntervalMap k a
m2 = (k -> a -> a -> a)
-> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
forall k e a.
(Interval k e, Ord k) =>
(k -> a -> a -> a)
-> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
unionWithKey (\k
_ a
v1 a
v2 -> a -> a -> a
f a
v1 a
v2) IntervalMap k a
m1 IntervalMap k a
m2

-- | /O(n+m)/. Union with a combining function.
unionWithKey :: (Interval k e, Ord k) => (k -> a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
unionWithKey :: forall k e a.
(Interval k e, Ord k) =>
(k -> a -> a -> a)
-> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
unionWithKey k -> a -> a -> a
f IntervalMap k a
m1 IntervalMap k a
m2 = [(k, a)] -> IntervalMap k a
forall k e v. Interval k e => [(k, v)] -> IntervalMap k v
fromDistinctAscList ((k -> a -> a -> a) -> [(k, a)] -> [(k, a)] -> [(k, a)]
forall k a.
Ord k =>
(k -> a -> a -> a) -> [(k, a)] -> [(k, a)] -> [(k, a)]
ascListUnion k -> a -> a -> a
f (IntervalMap k a -> [(k, a)]
forall k v. IntervalMap k v -> [(k, v)]
toAscList IntervalMap k a
m1) (IntervalMap k a -> [(k, a)]
forall k v. IntervalMap k v -> [(k, v)]
toAscList IntervalMap k a
m2))

-- | The union of a list of maps, with a combining operation:
--   (@'unionsWith' f == 'Prelude.foldl' ('unionWith' f) 'empty'@).
unionsWith :: (Interval k e, Ord k) => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a
unionsWith :: forall k e a.
(Interval k e, Ord k) =>
(a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a
unionsWith a -> a -> a
f = (IntervalMap k a -> IntervalMap k a -> IntervalMap k a)
-> IntervalMap k a -> [IntervalMap k a] -> IntervalMap k a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl ((a -> a -> a)
-> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
forall k e a.
(Interval k e, Ord k) =>
(a -> a -> a)
-> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
unionWith a -> a -> a
f) IntervalMap k a
forall k v. IntervalMap k v
empty

-- | /O(n+m)/. 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 'Nothing', the element is discarded (proper set difference). If
-- it returns (@'Just' y@), the element is updated with a new value @y@. 
differenceWith :: (Interval k e, Ord k) => (a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a
differenceWith :: forall k e a b.
(Interval k e, Ord k) =>
(a -> b -> Maybe a)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k a
differenceWith a -> b -> Maybe a
f IntervalMap k a
m1 IntervalMap k b
m2 = (k -> a -> b -> Maybe a)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k a
forall k e a b.
(Interval k e, Ord k) =>
(k -> a -> b -> Maybe a)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k a
differenceWithKey (\k
_ a
v1 b
v2 -> a -> b -> Maybe a
f a
v1 b
v2) IntervalMap k a
m1 IntervalMap k b
m2

-- | /O(n+m)/. 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 'Nothing', the element is discarded (proper set difference). If
-- it returns (@'Just' y@), the element is updated with a new value @y@. 
differenceWithKey :: (Interval k e, Ord k) => (k -> a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a
differenceWithKey :: forall k e a b.
(Interval k e, Ord k) =>
(k -> a -> b -> Maybe a)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k a
differenceWithKey k -> a -> b -> Maybe a
f IntervalMap k a
m1 IntervalMap k b
m2 = [(k, a)] -> IntervalMap k a
forall k e v. Interval k e => [(k, v)] -> IntervalMap k v
fromDistinctAscList ((k -> a -> b -> Maybe a) -> [(k, a)] -> [(k, b)] -> [(k, a)]
forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> [(k, a)] -> [(k, b)] -> [(k, a)]
ascListDifference k -> a -> b -> Maybe a
f (IntervalMap k a -> [(k, a)]
forall k v. IntervalMap k v -> [(k, v)]
toAscList IntervalMap k a
m1) (IntervalMap k b -> [(k, b)]
forall k v. IntervalMap k v -> [(k, v)]
toAscList IntervalMap k b
m2))

-- | /O(n+m)/. Intersection with a combining function.
intersectionWith :: (Interval k e, Ord k) => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
intersectionWith :: forall k e a b c.
(Interval k e, Ord k) =>
(a -> b -> c)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
intersectionWith a -> b -> c
f IntervalMap k a
m1 IntervalMap k b
m2 = (k -> a -> b -> c)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
forall k e a b c.
(Interval k e, Ord k) =>
(k -> a -> b -> c)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
intersectionWithKey (\k
_ a
v1 b
v2 -> a -> b -> c
f a
v1 b
v2) IntervalMap k a
m1 IntervalMap k b
m2

-- | /O(n+m)/. Intersection with a combining function.
intersectionWithKey :: (Interval k e, Ord k) => (k -> a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
intersectionWithKey :: forall k e a b c.
(Interval k e, Ord k) =>
(k -> a -> b -> c)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
intersectionWithKey k -> a -> b -> c
f IntervalMap k a
m1 IntervalMap k b
m2 = [(k, c)] -> IntervalMap k c
forall k e v. Interval k e => [(k, v)] -> IntervalMap k v
fromDistinctAscList ((k -> a -> b -> c) -> [(k, a)] -> [(k, b)] -> [(k, c)]
forall k a b c.
Ord k =>
(k -> a -> b -> c) -> [(k, a)] -> [(k, b)] -> [(k, c)]
ascListIntersection k -> a -> b -> c
f (IntervalMap k a -> [(k, a)]
forall k v. IntervalMap k v -> [(k, v)]
toAscList IntervalMap k a
m1) (IntervalMap k b -> [(k, b)]
forall k v. IntervalMap k v -> [(k, v)]
toAscList IntervalMap k b
m2))


ascListUnion :: Ord k => (k -> a -> a -> a) -> [(k,a)] -> [(k,a)] -> [(k,a)]
ascListUnion :: forall k a.
Ord k =>
(k -> a -> a -> a) -> [(k, a)] -> [(k, a)] -> [(k, a)]
ascListUnion k -> a -> a -> a
_ [] [] = []
ascListUnion k -> a -> a -> a
_ [] [(k, a)]
ys = [(k, a)]
ys
ascListUnion k -> a -> a -> a
_ [(k, a)]
xs [] = [(k, a)]
xs
ascListUnion k -> a -> a -> a
f xs :: [(k, a)]
xs@(x :: (k, a)
x@(k
xk,a
xv):[(k, a)]
xs') ys :: [(k, a)]
ys@(y :: (k, a)
y@(k
yk,a
yv):[(k, a)]
ys') =
  case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
xk k
yk of
    Ordering
LT -> (k, a)
x (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: (k -> a -> a -> a) -> [(k, a)] -> [(k, a)] -> [(k, a)]
forall k a.
Ord k =>
(k -> a -> a -> a) -> [(k, a)] -> [(k, a)] -> [(k, a)]
ascListUnion k -> a -> a -> a
f [(k, a)]
xs' [(k, a)]
ys
    Ordering
GT -> (k, a)
y (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: (k -> a -> a -> a) -> [(k, a)] -> [(k, a)] -> [(k, a)]
forall k a.
Ord k =>
(k -> a -> a -> a) -> [(k, a)] -> [(k, a)] -> [(k, a)]
ascListUnion k -> a -> a -> a
f [(k, a)]
xs [(k, a)]
ys'
    Ordering
EQ -> let v' :: a
v' = k -> a -> a -> a
f k
xk a
xv a
yv in a
v' a -> [(k, a)] -> [(k, a)]
forall a b. a -> b -> b
`seq` (k
xk, a
v') (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: (k -> a -> a -> a) -> [(k, a)] -> [(k, a)] -> [(k, a)]
forall k a.
Ord k =>
(k -> a -> a -> a) -> [(k, a)] -> [(k, a)] -> [(k, a)]
ascListUnion k -> a -> a -> a
f [(k, a)]
xs' [(k, a)]
ys'

ascListDifference :: Ord k => (k -> a -> b -> Maybe a) -> [(k,a)] -> [(k,b)] -> [(k,a)]
ascListDifference :: forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> [(k, a)] -> [(k, b)] -> [(k, a)]
ascListDifference k -> a -> b -> Maybe a
_ [] [(k, b)]
_  = []
ascListDifference k -> a -> b -> Maybe a
_ [(k, a)]
xs [] = [(k, a)]
xs
ascListDifference k -> a -> b -> Maybe a
f xs :: [(k, a)]
xs@(x :: (k, a)
x@(k
xk,a
xv):[(k, a)]
xs') ys :: [(k, b)]
ys@((k
yk,b
yv):[(k, b)]
ys') =
  case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
xk k
yk of
    Ordering
LT -> (k, a)
x (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: (k -> a -> b -> Maybe a) -> [(k, a)] -> [(k, b)] -> [(k, a)]
forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> [(k, a)] -> [(k, b)] -> [(k, a)]
ascListDifference k -> a -> b -> Maybe a
f [(k, a)]
xs' [(k, b)]
ys
    Ordering
GT -> (k -> a -> b -> Maybe a) -> [(k, a)] -> [(k, b)] -> [(k, a)]
forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> [(k, a)] -> [(k, b)] -> [(k, a)]
ascListDifference k -> a -> b -> Maybe a
f [(k, a)]
xs [(k, b)]
ys'
    Ordering
EQ -> case k -> a -> b -> Maybe a
f k
xk a
xv b
yv of
            Maybe a
Nothing -> (k -> a -> b -> Maybe a) -> [(k, a)] -> [(k, b)] -> [(k, a)]
forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> [(k, a)] -> [(k, b)] -> [(k, a)]
ascListDifference k -> a -> b -> Maybe a
f [(k, a)]
xs' [(k, b)]
ys'
            Just a
v' -> a
v' a -> [(k, a)] -> [(k, a)]
forall a b. a -> b -> b
`seq` (k
xk,a
v') (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: (k -> a -> b -> Maybe a) -> [(k, a)] -> [(k, b)] -> [(k, a)]
forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> [(k, a)] -> [(k, b)] -> [(k, a)]
ascListDifference k -> a -> b -> Maybe a
f [(k, a)]
xs' [(k, b)]
ys'

ascListIntersection :: Ord k => (k -> a -> b -> c) -> [(k,a)] -> [(k,b)] -> [(k,c)]
ascListIntersection :: forall k a b c.
Ord k =>
(k -> a -> b -> c) -> [(k, a)] -> [(k, b)] -> [(k, c)]
ascListIntersection k -> a -> b -> c
_ [] [(k, b)]
_ = []
ascListIntersection k -> a -> b -> c
_ [(k, a)]
_ [] = []
ascListIntersection k -> a -> b -> c
f xs :: [(k, a)]
xs@((k
xk,a
xv):[(k, a)]
xs') ys :: [(k, b)]
ys@((k
yk,b
yv):[(k, b)]
ys') =
  case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
xk k
yk of
    Ordering
LT -> (k -> a -> b -> c) -> [(k, a)] -> [(k, b)] -> [(k, c)]
forall k a b c.
Ord k =>
(k -> a -> b -> c) -> [(k, a)] -> [(k, b)] -> [(k, c)]
ascListIntersection k -> a -> b -> c
f [(k, a)]
xs' [(k, b)]
ys
    Ordering
GT -> (k -> a -> b -> c) -> [(k, a)] -> [(k, b)] -> [(k, c)]
forall k a b c.
Ord k =>
(k -> a -> b -> c) -> [(k, a)] -> [(k, b)] -> [(k, c)]
ascListIntersection k -> a -> b -> c
f [(k, a)]
xs [(k, b)]
ys'
    Ordering
EQ -> let v' :: c
v' = k -> a -> b -> c
f k
xk a
xv b
yv in c
v' c -> [(k, c)] -> [(k, c)]
forall a b. a -> b -> b
`seq` (k
xk, c
v') (k, c) -> [(k, c)] -> [(k, c)]
forall a. a -> [a] -> [a]
: (k -> a -> b -> c) -> [(k, a)] -> [(k, b)] -> [(k, c)]
forall k a b c.
Ord k =>
(k -> a -> b -> c) -> [(k, a)] -> [(k, b)] -> [(k, c)]
ascListIntersection k -> a -> b -> c
f [(k, a)]
xs' [(k, b)]
ys'