{-# OPTIONS_GHC -Wall #-}
{-# LANGUAGE BangPatterns, TupleSections #-}
{-# LANGUAGE Safe #-}
module Data.IntervalMap.Strict
(
IntervalMap
, module Data.ExtendedReal
, (!)
, (\\)
, null
, member
, notMember
, lookup
, findWithDefault
, span
, whole
, empty
, singleton
, insert
, insertWith
, delete
, adjust
, update
, alter
, union
, unionWith
, unions
, unionsWith
, intersection
, intersectionWith
, difference
, map
, mapKeysMonotonic
, elems
, keys
, assocs
, keysSet
, fromList
, fromListWith
, toList
, toAscList
, toDescList
, filter
, split
, isSubmapOf
, isSubmapOfBy
, isProperSubmapOf
, isProperSubmapOfBy
)
where
import Prelude hiding (null, lookup, map, filter, span)
import Data.ExtendedReal
import Data.Interval (Interval)
import qualified Data.Interval as Interval
import Data.IntervalMap.Base hiding
( whole
, singleton
, insert
, insertWith
, adjust
, update
, alter
, unionWith
, unionsWith
, intersectionWith
, map
, fromList
, fromListWith
)
import qualified Data.IntervalMap.Base as B
import qualified Data.IntervalSet as IntervalSet
import Data.List (foldl')
import qualified Data.Map.Strict as Map
whole :: Ord k => a -> IntervalMap k a
whole :: forall k a. Ord k => a -> IntervalMap k a
whole !a
a = forall k a. Ord k => a -> IntervalMap k a
B.whole a
a
singleton :: Ord k => Interval k -> a -> IntervalMap k a
singleton :: forall k a. Ord k => Interval k -> a -> IntervalMap k a
singleton Interval k
i !a
a = forall k a. Ord k => Interval k -> a -> IntervalMap k a
B.singleton Interval k
i a
a
insert :: Ord k => Interval k -> a -> IntervalMap k a -> IntervalMap k a
insert :: forall k a.
Ord k =>
Interval k -> a -> IntervalMap k a -> IntervalMap k a
insert Interval k
i !a
a IntervalMap k a
m = forall k a.
Ord k =>
Interval k -> a -> IntervalMap k a -> IntervalMap k a
B.insert Interval k
i a
a IntervalMap k a
m
insertWith :: Ord k => (a -> a -> a) -> Interval k -> a -> IntervalMap k a -> IntervalMap k a
insertWith :: forall k a.
Ord k =>
(a -> a -> a)
-> Interval k -> a -> IntervalMap k a -> IntervalMap k a
insertWith a -> a -> a
_ Interval k
i a
_ IntervalMap k a
m | forall r. Ord r => Interval r -> Bool
Interval.null Interval k
i = IntervalMap k a
m
insertWith a -> a -> a
f Interval k
i !a
a IntervalMap k a
m = forall k a.
Ord k =>
(Maybe a -> Maybe a)
-> Interval k -> IntervalMap k a -> IntervalMap k a
alter Maybe a -> Maybe a
g Interval k
i IntervalMap k a
m
where
g :: Maybe a -> Maybe a
g Maybe a
Nothing = forall a. a -> Maybe a
Just a
a
g (Just a
a') = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! a -> a -> a
f a
a a
a'
adjust :: Ord k => (a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k a
adjust :: forall k a.
Ord k =>
(a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k a
adjust a -> a
f = forall k a.
Ord k =>
(a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a
update (forall a. a -> Maybe a
Just forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
f)
update :: Ord k => (a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a
update :: forall k a.
Ord k =>
(a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a
update a -> Maybe a
_ Interval k
i IntervalMap k a
m | forall r. Ord r => Interval r -> Bool
Interval.null Interval k
i = IntervalMap k a
m
update a -> Maybe a
f Interval k
i IntervalMap k a
m =
case forall k a.
Ord k =>
Interval k
-> IntervalMap k a
-> (IntervalMap k a, IntervalMap k a, IntervalMap k a)
split Interval k
i IntervalMap k a
m of
(IntervalMap Map (LB k) (Interval k, a)
m1, IntervalMap Map (LB k) (Interval k, a)
m2, IntervalMap Map (LB k) (Interval k, a)
m3) ->
forall r a. Map (LB r) (Interval r, a) -> IntervalMap r a
IntervalMap forall a b. (a -> b) -> a -> b
$ forall (f :: * -> *) k a.
(Foldable f, Ord k) =>
f (Map k a) -> Map k a
Map.unions [Map (LB k) (Interval k, a)
m1, forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe (\(Interval k
j,a
a) -> (\a
b -> seq :: forall a b. a -> b -> b
seq a
b (Interval k
j,a
b)) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> Maybe a
f a
a) Map (LB k) (Interval k, a)
m2, Map (LB k) (Interval k, a)
m3]
alter :: Ord k => (Maybe a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a
alter :: forall k a.
Ord k =>
(Maybe a -> Maybe a)
-> Interval k -> IntervalMap k a -> IntervalMap k a
alter Maybe a -> Maybe a
_ Interval k
i IntervalMap k a
m | forall r. Ord r => Interval r -> Bool
Interval.null Interval k
i = IntervalMap k a
m
alter Maybe a -> Maybe a
f Interval k
i IntervalMap k a
m =
case forall k a.
Ord k =>
Interval k
-> IntervalMap k a
-> (IntervalMap k a, IntervalMap k a, IntervalMap k a)
split Interval k
i IntervalMap k a
m of
(IntervalMap Map (LB k) (Interval k, a)
m1, IntervalMap Map (LB k) (Interval k, a)
m2, IntervalMap Map (LB k) (Interval k, a)
m3) ->
let m2' :: Map (LB k) (Interval k, a)
m2' = forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe (\(Interval k
j,a
a) -> (\a
b -> seq :: forall a b. a -> b -> b
seq a
b (Interval k
j,a
b)) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe a -> Maybe a
f (forall a. a -> Maybe a
Just a
a)) Map (LB k) (Interval k, a)
m2
js :: IntervalSet k
js = forall r. Ord r => Interval r -> IntervalSet r
IntervalSet.singleton Interval k
i forall r. Ord r => IntervalSet r -> IntervalSet r -> IntervalSet r
`IntervalSet.difference` forall k a. Ord k => IntervalMap k a -> IntervalSet k
keysSet (forall r a. Map (LB r) (Interval r, a) -> IntervalMap r a
IntervalMap Map (LB k) (Interval k, a)
m2)
IntervalMap Map (LB k) (Interval k, a)
m2'' =
case Maybe a -> Maybe a
f forall a. Maybe a
Nothing of
Maybe a
Nothing -> forall k a. Ord k => IntervalMap k a
empty
Just !a
a -> forall k a. Ord k => [(Interval k, a)] -> IntervalMap k a
B.fromList [(Interval k
j,a
a) | Interval k
j <- forall r. Ord r => IntervalSet r -> [Interval r]
IntervalSet.toList IntervalSet k
js]
in seq :: forall a b. a -> b -> b
seq Map (LB k) (Interval k, a)
m2' forall a b. (a -> b) -> a -> b
$ forall r a. Map (LB r) (Interval r, a) -> IntervalMap r a
IntervalMap forall a b. (a -> b) -> a -> b
$ forall (f :: * -> *) k a.
(Foldable f, Ord k) =>
f (Map k a) -> Map k a
Map.unions [Map (LB k) (Interval k, a)
m1, Map (LB k) (Interval k, a)
m2', Map (LB k) (Interval k, a)
m2'', Map (LB k) (Interval k, a)
m3]
unionWith :: Ord k => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
unionWith :: forall k a.
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 =
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\IntervalMap k a
m (Interval k
i,a
a) -> forall k a.
Ord k =>
(a -> a -> a)
-> Interval k -> a -> IntervalMap k a -> IntervalMap k a
insertWith a -> a -> a
f Interval k
i a
a IntervalMap k a
m) IntervalMap k a
m2 (forall k a. IntervalMap k a -> [(Interval k, a)]
toList IntervalMap k a
m1)
unionsWith :: Ord k => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a
unionsWith :: forall k a.
Ord k =>
(a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a
unionsWith a -> a -> a
f = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (forall k a.
Ord k =>
(a -> a -> a)
-> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
unionWith a -> a -> a
f) forall k a. Ord k => IntervalMap k a
empty
intersectionWith :: Ord k => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
intersectionWith :: forall k a b c.
Ord k =>
(a -> b -> c)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
intersectionWith a -> b -> c
f im1 :: IntervalMap k a
im1@(IntervalMap Map (LB k) (Interval k, a)
m1) im2 :: IntervalMap k b
im2@(IntervalMap Map (LB k) (Interval k, b)
m2)
| forall k a. Map k a -> Int
Map.size Map (LB k) (Interval k, a)
m1 forall a. Ord a => a -> a -> Bool
>= forall k a. Map k a -> Int
Map.size Map (LB k) (Interval k, b)
m2 = forall k a b c.
Ord k =>
(a -> b -> c)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
g a -> b -> c
f IntervalMap k a
im1 IntervalMap k b
im2
| Bool
otherwise = forall k a b c.
Ord k =>
(a -> b -> c)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
g (forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> c
f) IntervalMap k b
im2 IntervalMap k a
im1
where
g :: Ord k => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
g :: forall k a b c.
Ord k =>
(a -> b -> c)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
g a -> b -> c
h IntervalMap k a
jm1 (IntervalMap Map (LB k) (Interval k, b)
m3) = forall r a. Map (LB r) (Interval r, a) -> IntervalMap r a
IntervalMap forall a b. (a -> b) -> a -> b
$ forall (f :: * -> *) k a.
(Foldable f, Ord k) =>
f (Map k a) -> Map k a
Map.unions forall a b. (a -> b) -> a -> b
$ forall {k}.
Ord k =>
IntervalMap k a
-> [(Interval k, b)] -> [Map (LB k) (Interval k, c)]
go IntervalMap k a
jm1 (forall k a. Map k a -> [a]
Map.elems Map (LB k) (Interval k, b)
m3)
where
go :: IntervalMap k a
-> [(Interval k, b)] -> [Map (LB k) (Interval k, c)]
go IntervalMap k a
_ [] = []
go IntervalMap k a
im ((Interval k
i,b
b) : [(Interval k, b)]
xs) =
case forall k a.
Ord k =>
Interval k
-> IntervalMap k a
-> (IntervalMap k a, IntervalMap k a, IntervalMap k a)
split Interval k
i IntervalMap k a
im of
(IntervalMap k a
_, IntervalMap Map (LB k) (Interval k, a)
m, IntervalMap k a
jm2) ->
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map (\(Interval k
j, a
a) -> (Interval k
j,) forall a b. (a -> b) -> a -> b
$! a -> b -> c
h a
a b
b) Map (LB k) (Interval k, a)
m forall a. a -> [a] -> [a]
: IntervalMap k a
-> [(Interval k, b)] -> [Map (LB k) (Interval k, c)]
go IntervalMap k a
jm2 [(Interval k, b)]
xs
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 (IntervalMap Map (LB k) (Interval k, a)
m) = forall r a. Map (LB r) (Interval r, a) -> IntervalMap r a
IntervalMap forall a b. (a -> b) -> a -> b
$ forall a b k. (a -> b) -> Map k a -> Map k b
Map.map (\(Interval k
i, a
a) -> (Interval k
i,) forall a b. (a -> b) -> a -> b
$! a -> b
f a
a) Map (LB k) (Interval k, a)
m
fromList :: Ord k => [(Interval k, a)] -> IntervalMap k a
fromList :: forall k a. Ord k => [(Interval k, a)] -> IntervalMap k a
fromList = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\IntervalMap k a
m (Interval k
i,a
a) -> forall k a.
Ord k =>
Interval k -> a -> IntervalMap k a -> IntervalMap k a
insert Interval k
i a
a IntervalMap k a
m) forall k a. Ord k => IntervalMap k a
empty
fromListWith :: Ord k => (a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a
fromListWith :: forall k a.
Ord k =>
(a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a
fromListWith a -> a -> a
f = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\IntervalMap k a
m (Interval k
i,a
a) -> forall k a.
Ord k =>
(a -> a -> a)
-> Interval k -> a -> IntervalMap k a -> IntervalMap k a
insertWith a -> a -> a
f Interval k
i a
a IntervalMap k a
m) forall k a. Ord k => IntervalMap k a
empty