msakai / data-interval / 74

{-# OPTIONS_GHC -Wall #-}

{-# LANGUAGE CPP, LambdaCase, ScopedTypeVariables, TypeFamilies, DeriveDataTypeable, MultiWayIf, GeneralizedNewtypeDeriving #-}

{-# LANGUAGE Trustworthy #-}

{-# LANGUAGE RoleAnnotations #-}

-----------------------------------------------------------------------------

-- |

-- Module      :  Data.IntervalMap.Base

-- Copyright   :  (c) Masahiro Sakai 2016

-- License     :  BSD-style

--

-- Maintainer  :  masahiro.sakai@gmail.com

-- Stability   :  provisional

-- Portability :  non-portable (CPP, ScopedTypeVariables, TypeFamilies, DeriveDataTypeable, MultiWayIf, GeneralizedNewtypeDeriving)

--

-- Interval datatype and interval arithmetic.

--

-----------------------------------------------------------------------------

module Data.IntervalMap.Base

  (

  -- * IntervalMap type

    IntervalMap (..)

  , module Data.ExtendedReal

  -- * Operators

  , (!)

  , (\\)

  -- * Query

  , null

  , member

  , notMember

  , lookup

  , findWithDefault

  , span

  -- * Construction

  , whole

  , empty

  , singleton

  -- ** Insertion

  , insert

  , insertWith

  -- ** Delete\/Update

  , delete

  , adjust

  , update

  , alter

  -- * Combine

  , union

  , unionWith

  , unions

  , unionsWith

  , intersection

  , intersectionWith

  , difference

  -- * Traversal

  , map

  , mapKeysMonotonic

  -- * Conversion

  , elems

  , keys

  , assocs

  , keysSet

  -- ** List

  , fromList

  , fromListWith

  , toList

  -- ** Ordered List

  , toAscList

  , toDescList

  -- * Filter

  , filter

  , split

  -- * Submap

  , isSubmapOf

  , isSubmapOfBy

  , isProperSubmapOf

  , isProperSubmapOfBy

  )

  where

import Prelude hiding (null, lookup, map, filter, span, and)

import Control.DeepSeq

import Data.Data

import Data.ExtendedReal

import Data.Hashable

import Data.Foldable hiding (null, toList)

import Data.Map (Map)

import qualified Data.Map as Map

import Data.Maybe

import qualified Data.Semigroup as Semigroup

import Data.Interval (Interval)

import qualified Data.Interval as Interval

import Data.IntervalSet (IntervalSet)

import qualified Data.IntervalSet as IntervalSet

#if __GLASGOW_HASKELL__ < 804

import Data.Monoid (Monoid(..))

#endif

import qualified GHC.Exts as GHCExts

-- ------------------------------------------------------------------------

-- The IntervalMap type

-- | A Map from non-empty, disjoint intervals over k to values a.

--

-- Unlike 'IntervalSet', 'IntervalMap' never merge adjacent mappings,

-- even if adjacent intervals are connected and mapped to the same value.

newtype IntervalMap r a = IntervalMap (Map (LB r) (Interval r, a))

  deriving

      -- ^ Note that this Ord is derived and not semantically meaningful.

      -- The primary intended use case is to allow using 'IntervalSet'

      -- in maps and sets that require ordering.

    , Typeable

    )

type role IntervalMap nominal representational

instance (Ord k, Show k, Show a) => Show (IntervalMap k a) where

instance (Ord k, Read k, Read a) => Read (IntervalMap k a) where

appPrec :: Int

-- This instance preserves data abstraction at the cost of inefficiency.

-- We provide limited reflection services for the sake of data abstraction.

instance (Data k, Data a, Ord k) => Data (IntervalMap k a) where

fromListConstr :: Constr

mapDataType :: DataType

instance (NFData k, NFData a) => NFData (IntervalMap k a) where

instance (Hashable k, Hashable a) => Hashable (IntervalMap k a) where

instance Ord k => Monoid (IntervalMap k a) where

instance Ord k => Semigroup.Semigroup (IntervalMap k a) where

instance Ord k => GHCExts.IsList (IntervalMap k a) where

  type Item (IntervalMap k a) = (Interval k, a)

-- ------------------------------------------------------------------------

newtype LB r = LB (Extended r, Interval.Boundary)

instance Ord r => Ord (LB r) where

    -- inclusive lower endpoint shuold be considered smaller

-- ------------------------------------------------------------------------

-- Operators

infixl 9 !,\\ --

-- | Find the value at a key. Calls 'error' when the element can not be found.

(!) :: Ord k => IntervalMap k a -> k -> a

-- | Same as 'difference'.

(\\) :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- ------------------------------------------------------------------------

-- Query

-- | Is the map empty?

null :: Ord k => IntervalMap k a -> Bool

-- | Is the key a member of the map? See also 'notMember'.

member :: Ord k => k -> IntervalMap k a -> Bool

-- | Is the key not a member of the map? See also 'member'.

notMember :: Ord k => k -> IntervalMap k a -> Bool

-- | Lookup the value at a key in the map.

--

-- The function will return the corresponding value as @('Just' value)@,

-- or 'Nothing' if the key isn't in the map.

lookup :: Ord k => k -> IntervalMap k a -> Maybe a

-- | 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 :: Ord k => a -> k -> IntervalMap k a -> a

lookupInterval :: Ord k => Interval k -> IntervalMap k a -> Maybe a

-- | convex hull of key intervals.

span :: Ord k => IntervalMap k a -> Interval k

-- ------------------------------------------------------------------------

-- Construction

-- | The empty map.

empty :: Ord k => IntervalMap k a

-- | The map that maps whole range of k to a.

whole :: Ord k => a -> IntervalMap k a

  where

-- | A map with a single interval.

singleton :: Ord k => Interval k -> a -> IntervalMap k a

-- ------------------------------------------------------------------------

-- Insertion

-- | insert a new key and value in the map.

-- If the key is already present in the map, the associated value is

-- replaced with the supplied value.

insert :: Ord k => Interval k -> a -> IntervalMap k a -> IntervalMap k a

insert i a m =

    (IntervalMap m1, _, IntervalMap m2) ->

-- | Insert with a function, combining new value and old value.

-- @'insertWith' f key value mp@ will insert the pair (interval, value) into @mp@.

-- If the interval overlaps with existing entries, the value for the entry is replace

-- with @(f new_value old_value)@.

insertWith :: Ord k => (a -> a -> a) -> Interval k -> a -> IntervalMap k a -> IntervalMap k a

  where

-- ------------------------------------------------------------------------

-- Delete/Update

-- | Delete an interval and its value from the map.

-- When the interval does not overlap with the map, the original map is returned.

delete :: Ord k => Interval k -> IntervalMap k a -> IntervalMap k a

delete i m =

    (IntervalMap m1, _, IntervalMap m2) ->

-- | Update a value at a specific interval with the result of the provided function.

-- When the interval does not overlatp with the map, the original map is returned.

adjust :: Ord k => (a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k a

-- | The expression (@'update' f i map@) updates the value @x@

-- at @i@ (if it is in the map). If (@f x@) is 'Nothing', the element is

-- deleted. If it is (@'Just' y@), the key @i@ is bound to the new value @y@.

update :: Ord k => (a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a

update f i m =

    (IntervalMap m1, IntervalMap m2, IntervalMap m3) ->

-- | The expression (@'alter' f i map@) alters the value @x@ at @i@, or absence thereof.

-- 'alter' can be used to insert, delete, or update a value in a 'IntervalMap'.

alter :: Ord k => (Maybe a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a

alter f i m =

    (IntervalMap m1, IntervalMap m2, IntervalMap m3) ->

          IntervalMap m2'' =

-- ------------------------------------------------------------------------

-- Combine

-- | The expression (@'union' t1 t2@) takes the left-biased union of @t1@ and @t2@.

-- It prefers @t1@ when overlapping keys are encountered,

union :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | Union with a combining function.

unionWith :: Ord k => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | The union of a list of maps:

--   (@'unions' == 'Prelude.foldl' 'union' 'empty'@).

unions :: Ord k => [IntervalMap k a] -> IntervalMap k a

-- | The union of a list of maps, with a combining operation:

--   (@'unionsWith' f == 'Prelude.foldl' ('unionWith' f) 'empty'@).

unionsWith :: Ord k => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a

-- | Return elements of the first map not existing in the second map.

difference :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

-- | Intersection of two maps.

-- Return data in the first map for the keys existing in both maps.

intersection :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a

-- | Intersection with a combining function.

intersectionWith :: Ord k => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c

  where

    g :: Ord k => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c

      where

        go im ((i,b) : xs) =

            (_, IntervalMap m, jm2) ->

-- ------------------------------------------------------------------------

-- Traversal

instance Ord k => Functor (IntervalMap k) where

instance Ord k => Foldable (IntervalMap k) where

instance Ord k => Traversable (IntervalMap k) where

-- | Map a function over all values in the map.

map :: (a -> b) -> IntervalMap k a -> IntervalMap k b

-- | @'mapKeysMonotonic' f s@ is the map obtained by applying @f@ to each key of @s@.

-- @f@ must be strictly monotonic.

-- That is, for any values @x@ and @y@, if @x@ < @y@ then @f x@ < @f y@.

mapKeysMonotonic :: forall k1 k2 a. (Ord k1, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

  where

    g :: (Interval k1, a) -> (Interval k2, a)

-- ------------------------------------------------------------------------

-- | Return all elements of the map in the ascending order of their keys.

elems :: IntervalMap k a -> [a]

-- | Return all keys of the map in ascending order. Subject to list

keys :: IntervalMap k a -> [Interval k]

-- | An alias for 'toAscList'. Return all key\/value pairs in the map

-- in ascending key order.

assocs :: IntervalMap k a -> [(Interval k, a)]

-- | The set of all keys of the map.

keysSet :: Ord k => IntervalMap k a -> IntervalSet k

-- | Convert the map to a list of key\/value pairs.

toList :: IntervalMap k a -> [(Interval k, a)]

-- | Convert the map to a list of key/value pairs where the keys are in ascending order.

toAscList :: IntervalMap k a -> [(Interval k, a)]

-- | Convert the map to a list of key/value pairs where the keys are in descending order.

toDescList :: IntervalMap k a -> [(Interval k, a)]

-- | Build a map from a list of key\/value pairs.

-- If the list contains more than one value for the same key, the last value

-- for the key is retained.

fromList :: Ord k => [(Interval k, a)] -> IntervalMap k a

-- | Build a map from a list of key\/value pairs with a combining function.

fromListWith :: Ord k => (a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a

-- ------------------------------------------------------------------------

-- Filter

-- | Filter all values that satisfy some predicate.

filter :: Ord k => (a -> Bool) -> IntervalMap k a -> IntervalMap k a

-- | The expression (@'split' i map@) is a triple @(map1,map2,map3)@ where

-- the keys in @map1@ are smaller than @i@, the keys in @map2@ are included in @i@, and the keys in @map3@ are larger than @i@.

split :: Ord k => Interval k -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a, IntervalMap k a)

    (smaller, m1, xs) ->

        (middle, m2, larger) ->

                Just (j,b) ->

              ]

              ]

          )

-- ------------------------------------------------------------------------

-- Submap

-- | This function is defined as (@'isSubmapOf' = 'isSubmapOfBy' (==)@).

isSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool

-- |  The expression (@'isSubmapOfBy' f t1 t2@) returns 'True' if

-- all keys in @t1@ are in tree @t2@, and when @f@ returns 'True' when

-- applied to their respective values.

isSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool

-- |  Is this a proper submap? (ie. a submap but not equal).

-- Defined as (@'isProperSubmapOf' = 'isProperSubmapOfBy' (==)@).

isProperSubmapOf :: (Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool

-- | Is this a proper submap? (ie. a submap but not equal).

-- The expression (@'isProperSubmapOfBy' f m1 m2@) returns 'True' when

-- @m1@ and @m2@ are not equal,

-- all keys in @m1@ are in @m2@, and when @f@ returns 'True' when

-- applied to their respective values.

isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool

-- ------------------------------------------------------------------------

splitLookupLE :: Ord k => k -> Map k v -> (Map k v, Maybe v, Map k v)

    (smaller, Nothing, larger) ->

upTo :: Ord r => Interval r -> Interval r

    (Finite lb, incl) ->

downTo :: Ord r => Interval r -> Interval r

    (Finite ub, incl) ->

notB :: Interval.Boundary -> Interval.Boundary