{- |
Module      :  Data.IntervalMap.Lazy
Copyright   :  (c) Christoph Breitkopf 2011
License     :  BSD-style
Maintainer  :  chbreitkopf@gmail.com
Stability   :  experimental
Portability :  portable

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 "Data.IntervalMap.Strict",
but with value-lazy semantics.
-}
module Data.IntervalMap.Lazy (
            -- * re-export
            I.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

            -- * Flatten
            , flattenWith

            -- * 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 (filter, foldl, foldr, lookup, map, null, splitAt)
import Data.IntervalMap.Interval as I
import Data.IntervalMap.Generic.Lazy hiding (IntervalMap, flattenWith)
import qualified Data.IntervalMap.Generic.Lazy as M


type IntervalMap k v = M.IntervalMap (I.Interval k) v

-- | /O(n)/. Join overlapping intervals with 'combine'.
--
-- > flattenWith (+) (fromList [([1,3],5), ([4,6],2), ([5,8],9)]) == mkMap [([1,3],5), ([4,8],11)]
flattenWith :: (Ord k) => (v -> v -> v) -> IntervalMap k v -> IntervalMap k v
flattenWith :: forall k v.
Ord k =>
(v -> v -> v) -> IntervalMap k v -> IntervalMap k v
flattenWith v -> v -> v
f IntervalMap k v
m = ((Interval k, v) -> (Interval k, v) -> Maybe (Interval k, v))
-> IntervalMap k v -> IntervalMap k v
forall k e v.
Interval k e =>
((k, v) -> (k, v) -> Maybe (k, v))
-> IntervalMap k v -> IntervalMap k v
M.flattenWithMonotonic (Interval k, v) -> (Interval k, v) -> Maybe (Interval k, v)
forall {a}.
Ord a =>
(Interval a, v) -> (Interval a, v) -> Maybe (Interval a, v)
f' IntervalMap k v
m
  where
    f' :: (Interval a, v) -> (Interval a, v) -> Maybe (Interval a, v)
f' (Interval a
k1,v
v1) (Interval a
k2,v
v2) = case Interval a -> Interval a -> Maybe (Interval a)
forall a. Ord a => Interval a -> Interval a -> Maybe (Interval a)
combine Interval a
k1 Interval a
k2 of
                           Maybe (Interval a)
Nothing -> Maybe (Interval a, v)
forall a. Maybe a
Nothing
                           Just Interval a
k' -> (Interval a, v) -> Maybe (Interval a, v)
forall a. a -> Maybe a
Just (Interval a
k', v -> v -> v
f v
v1 v
v2)