{-# OPTIONS_GHC -Wall #-}
{-# LANGUAGE CPP, 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
#if __GLASGOW_HASKELL__ < 710
import Control.Applicative ((<$>))
#endif
whole :: Ord k => a -> IntervalMap k a
whole :: a -> IntervalMap k a
whole !a
a = a -> IntervalMap k a
forall k a. Ord k => a -> IntervalMap k a
B.whole a
a
singleton :: Ord k => Interval k -> a -> IntervalMap k a
singleton :: Interval k -> a -> IntervalMap k a
singleton Interval k
i !a
a = Interval k -> a -> IntervalMap k 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 :: Interval k -> a -> IntervalMap k a -> IntervalMap k a
insert Interval k
i !a
a IntervalMap k a
m = Interval k -> a -> IntervalMap k a -> IntervalMap k a
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 :: (a -> a -> a)
-> Interval k -> a -> IntervalMap k a -> IntervalMap k a
insertWith a -> a -> a
_ Interval k
i a
_ IntervalMap k a
m | Interval k -> Bool
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 = (Maybe a -> Maybe a)
-> Interval k -> IntervalMap k a -> IntervalMap k a
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 = a -> Maybe a
forall a. a -> Maybe a
Just a
a
g (Just a
a') = a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
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 :: (a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k a
adjust a -> a
f = (a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a
forall k a.
Ord k =>
(a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a
update (a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> (a -> a) -> a -> Maybe a
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 :: (a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a
update a -> Maybe a
_ Interval k
i IntervalMap k a
m | Interval k -> Bool
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 Interval k
-> IntervalMap k a
-> (IntervalMap k a, IntervalMap k a, IntervalMap k a)
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) ->
Map (LB k) (Interval k, a) -> IntervalMap k a
forall r a. Map (LB r) (Interval r, a) -> IntervalMap r a
IntervalMap (Map (LB k) (Interval k, a) -> IntervalMap k a)
-> Map (LB k) (Interval k, a) -> IntervalMap k a
forall a b. (a -> b) -> a -> b
$ [Map (LB k) (Interval k, a)] -> Map (LB k) (Interval k, a)
forall (f :: * -> *) k a.
(Foldable f, Ord k) =>
f (Map k a) -> Map k a
Map.unions [Map (LB k) (Interval k, a)
m1, ((Interval k, a) -> Maybe (Interval k, a))
-> Map (LB k) (Interval k, a) -> Map (LB k) (Interval k, a)
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe (\(Interval k
j,a
a) -> (\a
b -> a -> (Interval k, a) -> (Interval k, a)
seq a
b (Interval k
j,a
b)) (a -> (Interval k, a)) -> Maybe a -> Maybe (Interval k, a)
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 :: (Maybe a -> Maybe a)
-> Interval k -> IntervalMap k a -> IntervalMap k a
alter Maybe a -> Maybe a
_ Interval k
i IntervalMap k a
m | Interval k -> Bool
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 Interval k
-> IntervalMap k a
-> (IntervalMap k a, IntervalMap k a, IntervalMap k a)
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' = ((Interval k, a) -> Maybe (Interval k, a))
-> Map (LB k) (Interval k, a) -> Map (LB k) (Interval k, a)
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe (\(Interval k
j,a
a) -> (\a
b -> a -> (Interval k, a) -> (Interval k, a)
seq a
b (Interval k
j,a
b)) (a -> (Interval k, a)) -> Maybe a -> Maybe (Interval k, a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe a -> Maybe a
f (a -> Maybe a
forall a. a -> Maybe a
Just a
a)) Map (LB k) (Interval k, a)
m2
js :: IntervalSet k
js = Interval k -> IntervalSet k
forall r. Ord r => Interval r -> IntervalSet r
IntervalSet.singleton Interval k
i IntervalSet k -> IntervalSet k -> IntervalSet k
forall r. Ord r => IntervalSet r -> IntervalSet r -> IntervalSet r
`IntervalSet.difference` IntervalMap k a -> IntervalSet k
forall k a. Ord k => IntervalMap k a -> IntervalSet k
keysSet (Map (LB k) (Interval k, a) -> IntervalMap k a
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 Maybe a
forall a. Maybe a
Nothing of
Maybe a
Nothing -> IntervalMap k a
forall k a. Ord k => IntervalMap k a
empty
Just !a
a -> [(Interval k, a)] -> IntervalMap k a
forall k a. Ord k => [(Interval k, a)] -> IntervalMap k a
B.fromList [(Interval k
j,a
a) | Interval k
j <- IntervalSet k -> [Interval k]
forall r. Ord r => IntervalSet r -> [Interval r]
IntervalSet.toList IntervalSet k
js]
in Map (LB k) (Interval k, a) -> IntervalMap k a -> IntervalMap k a
seq Map (LB k) (Interval k, a)
m2' (IntervalMap k a -> IntervalMap k a)
-> IntervalMap k a -> IntervalMap k a
forall a b. (a -> b) -> a -> b
$ Map (LB k) (Interval k, a) -> IntervalMap k a
forall r a. Map (LB r) (Interval r, a) -> IntervalMap r a
IntervalMap (Map (LB k) (Interval k, a) -> IntervalMap k a)
-> Map (LB k) (Interval k, a) -> IntervalMap k a
forall a b. (a -> b) -> a -> b
$ [Map (LB k) (Interval k, a)] -> Map (LB k) (Interval k, a)
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 :: (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 =
(IntervalMap k a -> (Interval k, a) -> IntervalMap k a)
-> IntervalMap k a -> [(Interval k, a)] -> IntervalMap k a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\IntervalMap k a
m (Interval k
i,a
a) -> (a -> a -> a)
-> Interval k -> a -> IntervalMap k a -> IntervalMap k 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 (IntervalMap k a -> [(Interval k, a)]
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 :: (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 (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((a -> a -> a)
-> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
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
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 :: (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)
| Map (LB k) (Interval k, a) -> Int
forall k a. Map k a -> Int
Map.size Map (LB k) (Interval k, a)
m1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Map (LB k) (Interval k, b) -> Int
forall k a. Map k a -> Int
Map.size Map (LB k) (Interval k, b)
m2 = (a -> b -> c)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
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 = (b -> a -> c)
-> IntervalMap k b -> IntervalMap k a -> IntervalMap k c
forall k a b c.
Ord k =>
(a -> b -> c)
-> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
g ((a -> b -> c) -> b -> a -> c
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 :: (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) = Map (LB k) (Interval k, c) -> IntervalMap k c
forall r a. Map (LB r) (Interval r, a) -> IntervalMap r a
IntervalMap (Map (LB k) (Interval k, c) -> IntervalMap k c)
-> Map (LB k) (Interval k, c) -> IntervalMap k c
forall a b. (a -> b) -> a -> b
$ [Map (LB k) (Interval k, c)] -> Map (LB k) (Interval k, c)
forall (f :: * -> *) k a.
(Foldable f, Ord k) =>
f (Map k a) -> Map k a
Map.unions ([Map (LB k) (Interval k, c)] -> Map (LB k) (Interval k, c))
-> [Map (LB k) (Interval k, c)] -> Map (LB k) (Interval k, c)
forall a b. (a -> b) -> a -> b
$ IntervalMap k a
-> [(Interval k, b)] -> [Map (LB k) (Interval k, c)]
forall k.
Ord k =>
IntervalMap k a
-> [(Interval k, b)] -> [Map (LB k) (Interval k, c)]
go IntervalMap k a
jm1 (Map (LB k) (Interval k, b) -> [(Interval k, b)]
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 Interval k
-> IntervalMap k a
-> (IntervalMap k a, IntervalMap k a, IntervalMap k a)
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) ->
((Interval k, a) -> (Interval k, c))
-> Map (LB k) (Interval k, a) -> Map (LB k) (Interval k, c)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map (\(Interval k
j, a
a) -> (Interval k
j,) (c -> (Interval k, c)) -> c -> (Interval k, c)
forall a b. (a -> b) -> a -> b
$! a -> b -> c
h a
a b
b) Map (LB k) (Interval k, a)
m Map (LB k) (Interval k, c)
-> [Map (LB k) (Interval k, c)] -> [Map (LB k) (Interval k, c)]
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 :: (a -> b) -> IntervalMap k a -> IntervalMap k b
map a -> b
f (IntervalMap Map (LB k) (Interval k, a)
m) = Map (LB k) (Interval k, b) -> IntervalMap k b
forall r a. Map (LB r) (Interval r, a) -> IntervalMap r a
IntervalMap (Map (LB k) (Interval k, b) -> IntervalMap k b)
-> Map (LB k) (Interval k, b) -> IntervalMap k b
forall a b. (a -> b) -> a -> b
$ ((Interval k, a) -> (Interval k, b))
-> Map (LB k) (Interval k, a) -> Map (LB k) (Interval k, b)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map (\(Interval k
i, a
a) -> (Interval k
i,) (b -> (Interval k, b)) -> b -> (Interval k, b)
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 :: [(Interval k, a)] -> IntervalMap k a
fromList = (IntervalMap k a -> (Interval k, a) -> IntervalMap k a)
-> IntervalMap k a -> [(Interval k, a)] -> IntervalMap k a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\IntervalMap k a
m (Interval k
i,a
a) -> Interval k -> a -> IntervalMap k a -> IntervalMap k 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) IntervalMap k a
forall k a. Ord k => IntervalMap k a
empty
fromListWith :: Ord k => (a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a
fromListWith :: (a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a
fromListWith a -> a -> a
f = (IntervalMap k a -> (Interval k, a) -> IntervalMap k a)
-> IntervalMap k a -> [(Interval k, a)] -> IntervalMap k a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\IntervalMap k a
m (Interval k
i,a
a) -> (a -> a -> a)
-> Interval k -> a -> IntervalMap k a -> IntervalMap k 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
forall k a. Ord k => IntervalMap k a
empty