| Copyright | (c) Masahiro Sakai 2016 |
|---|---|
| License | BSD-style |
| Maintainer | masahiro.sakai@gmail.com |
| Stability | provisional |
| Portability | non-portable (BangPatterns, TupleSections) |
| Safe Haskell | Safe |
| Language | Haskell2010 |
Data.IntervalMap.Strict
Description
Mapping from intervals to values.
API of this module is 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).
These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.
import Data.IntervalMap.Strict (IntervalMap) import qualified Data.IntervalMap.Strict as IntervalMap
Synopsis
- data IntervalMap r a
- module Data.ExtendedReal
- (!) :: Ord k => IntervalMap k a -> k -> a
- (\\) :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a
- null :: Ord k => IntervalMap k a -> Bool
- member :: Ord k => k -> IntervalMap k a -> Bool
- notMember :: Ord k => k -> IntervalMap k a -> Bool
- lookup :: Ord k => k -> IntervalMap k a -> Maybe a
- findWithDefault :: Ord k => a -> k -> IntervalMap k a -> a
- span :: Ord k => IntervalMap k a -> Interval k
- whole :: Ord k => a -> IntervalMap k a
- empty :: Ord k => IntervalMap k a
- singleton :: Ord k => Interval k -> a -> IntervalMap k a
- insert :: Ord k => Interval k -> a -> IntervalMap k a -> IntervalMap k a
- insertWith :: Ord k => (a -> a -> a) -> Interval k -> a -> IntervalMap k a -> IntervalMap k a
- delete :: Ord k => Interval k -> IntervalMap k a -> IntervalMap k a
- adjust :: Ord k => (a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k a
- update :: Ord k => (a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a
- alter :: Ord k => ( Maybe a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a
- union :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a
- unionWith :: Ord k => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
- unions :: Ord k => [ IntervalMap k a] -> IntervalMap k a
- unionsWith :: Ord k => (a -> a -> a) -> [ IntervalMap k a] -> IntervalMap k a
- intersection :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a
- intersectionWith :: Ord k => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
- difference :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a
- map :: (a -> b) -> IntervalMap k a -> IntervalMap k b
- mapKeysMonotonic :: forall k1 k2 a. ( Ord k1, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a
- elems :: IntervalMap k a -> [a]
- keys :: IntervalMap k a -> [ Interval k]
- assocs :: IntervalMap k a -> [( Interval k, a)]
- keysSet :: Ord k => IntervalMap k a -> IntervalSet k
- fromList :: Ord k => [( Interval k, a)] -> IntervalMap k a
- fromListWith :: Ord k => (a -> a -> a) -> [( Interval k, a)] -> IntervalMap k a
- toList :: IntervalMap k a -> [( Interval k, a)]
- toAscList :: IntervalMap k a -> [( Interval k, a)]
- toDescList :: IntervalMap k a -> [( Interval k, a)]
- filter :: Ord k => (a -> Bool ) -> IntervalMap k a -> IntervalMap k a
- split :: Ord k => Interval k -> IntervalMap k a -> ( IntervalMap k a, IntervalMap k a, IntervalMap k a)
- isSubmapOf :: ( Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool
- isSubmapOfBy :: Ord k => (a -> b -> Bool ) -> IntervalMap k a -> IntervalMap k b -> Bool
- isProperSubmapOf :: ( Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool
- isProperSubmapOfBy :: Ord k => (a -> b -> Bool ) -> IntervalMap k a -> IntervalMap k b -> Bool
Strictness properties
This module satisfies the following strictness properties:
- Key arguments are evaluated to WHNF;
- Keys and values are evaluated to WHNF before they are stored in the map.
Here's an example illustrating the first property:
delete undefined m == undefined
Here are some examples that illustrate the second property:
map (\ v -> undefined) m == undefined -- m is not empty mapKeysMonotonic (\ k -> undefined) m == undefined -- m is not empty
IntervalMap type
data IntervalMap r a Source #
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.
Instances
module Data.ExtendedReal
Operators
(!) :: Ord k => IntervalMap k a -> k -> a infixl 9 Source #
Find the value at a key. Calls
error
when the element can not be found.
(\\) :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a infixl 9 Source #
Same as
difference
.
Query
member :: Ord k => k -> IntervalMap k a -> Bool Source #
Is the key a member of the map? See also
notMember
.
notMember :: Ord k => k -> IntervalMap k a -> Bool Source #
Is the key not a member of the map? See also
member
.
findWithDefault :: Ord k => a -> k -> IntervalMap k a -> a Source #
The expression
(
returns
the value at key
findWithDefault
def k map)
k
or returns default value
def
when the key is not in the map.
Construction
whole :: Ord k => a -> IntervalMap k a Source #
The map that maps whole range of k to a.
empty :: Ord k => IntervalMap k a Source #
The empty map.
Insertion
insert :: Ord k => Interval k -> a -> IntervalMap k a -> IntervalMap k a Source #
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.
insertWith :: Ord k => (a -> a -> a) -> Interval k -> a -> IntervalMap k a -> IntervalMap k a Source #
Insert with a function, combining new value and old value.
will insert the pair (interval, value) into
insertWith
f key value mp
mp
.
If the interval overlaps with existing entries, the value for the entry is replace
with
(f new_value old_value)
.
Delete/Update
delete :: Ord k => Interval k -> IntervalMap k a -> IntervalMap k a Source #
Delete an interval and its value from the map. When the interval does not overlap with the map, the original map is returned.
adjust :: Ord k => (a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k a Source #
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.
update :: Ord k => (a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a Source #
alter :: Ord k => ( Maybe a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a Source #
The expression (
) alters the value
alter
f i map
x
at
i
, or absence thereof.
alter
can be used to insert, delete, or update a value in a
IntervalMap
.
Combine
union :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a Source #
The expression (
) takes the left-biased union of
union
t1 t2
t1
and
t2
.
It prefers
t1
when overlapping keys are encountered,
unionWith :: Ord k => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a Source #
Union with a combining function.
unions :: Ord k => [ IntervalMap k a] -> IntervalMap k a Source #
unionsWith :: Ord k => (a -> a -> a) -> [ IntervalMap k a] -> IntervalMap k a Source #
The union of a list of maps, with a combining operation:
(
).
unionsWith
f ==
foldl
(
unionWith
f)
empty
intersection :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a Source #
Intersection of two maps. Return data in the first map for the keys existing in both maps.
intersectionWith :: Ord k => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c Source #
Intersection with a combining function.
difference :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a Source #
Return elements of the first map not existing in the second map.
Traversal
map :: (a -> b) -> IntervalMap k a -> IntervalMap k b Source #
Map a function over all values in the map.
mapKeysMonotonic :: forall k1 k2 a. ( Ord k1, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a Source #
is the map obtained by applying
mapKeysMonotonic
f s
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
.
Conversion
elems :: IntervalMap k a -> [a] Source #
Return all elements of the map in the ascending order of their keys.
keys :: IntervalMap k a -> [ Interval k] Source #
Return all keys of the map in ascending order. Subject to list
assocs :: IntervalMap k a -> [( Interval k, a)] Source #
An alias for
toAscList
. Return all key/value pairs in the map
in ascending key order.
keysSet :: Ord k => IntervalMap k a -> IntervalSet k Source #
The set of all keys of the map.
List
fromList :: Ord k => [( Interval k, a)] -> IntervalMap k a Source #
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.
fromListWith :: Ord k => (a -> a -> a) -> [( Interval k, a)] -> IntervalMap k a Source #
Build a map from a list of key/value pairs with a combining function.
toList :: IntervalMap k a -> [( Interval k, a)] Source #
Convert the map to a list of key/value pairs.
Ordered List
toAscList :: IntervalMap k a -> [( Interval k, a)] Source #
Convert the map to a list of key/value pairs where the keys are in ascending order.
toDescList :: IntervalMap k a -> [( Interval k, a)] Source #
Convert the map to a list of key/value pairs where the keys are in descending order.
Filter
filter :: Ord k => (a -> Bool ) -> IntervalMap k a -> IntervalMap k a Source #
Filter all values that satisfy some predicate.
split :: Ord k => Interval k -> IntervalMap k a -> ( IntervalMap k a, IntervalMap k a, IntervalMap k a) Source #
The expression (
) is a triple
split
i map
(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
.
Submap
isSubmapOf :: ( Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool Source #
This function is defined as (
).
isSubmapOf
=
isSubmapOfBy
(==)
isSubmapOfBy :: Ord k => (a -> b -> Bool ) -> IntervalMap k a -> IntervalMap k b -> Bool Source #
The expression (
) returns
isSubmapOfBy
f t1 t2
True
if
all keys in
t1
are in tree
t2
, and when
f
returns
True
when
applied to their respective values.
isProperSubmapOf :: ( Ord k, Eq a) => IntervalMap k a -> IntervalMap k a -> Bool Source #
Is this a proper submap? (ie. a submap but not equal).
Defined as (
).
isProperSubmapOf
=
isProperSubmapOfBy
(==)
isProperSubmapOfBy :: Ord k => (a -> b -> Bool ) -> IntervalMap k a -> IntervalMap k b -> Bool Source #
Is this a proper submap? (ie. a submap but not equal).
The expression (
) returns
isProperSubmapOfBy
f m1 m2
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.