Portability | portable |
---|---|

Stability | experimental |

Maintainer | chbreitkopf@googlemail.com |

Safe Haskell | Safe-Infered |

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.

An IntervalMap cannot contain duplicate keys - if you need to map a key
to muiltiple values, use a collection as the value type, for
example: `IntervalMap `

.
*k* [*v*]

It is an error to insert an empty interval into a map. This precondition is not checked by the various construction functions.

Since many function names (but not the type name) clash with
*Prelude* names, this module is usually imported `qualified`

, e.g.

import Data.IntervalMap (IvMap) import qualified Data.IntervalMap as IvMap

It offers most of the same functions as `Map`

, but uses `Interval`

*k* instead of
just *k* as the key type. Some of the functions need stricter type constraints to
maintain the additional information for efficient interval searching,
for example `fromDistinctAscList`

needs an `Ord`

*k* constraint.
Also, some functions differ in asymptotic performance (for example `size`

) or have not
been tuned for efficiency as much as their equivalents in `Map`

(in
particular the various set functions).

In addition, there are functions specific to maps of intervals, for example to search for all keys containing a given point or contained in a given interval.

To stay compatible with standard Haskell, this implementation uses a fixed data
type for intervals, and not a multi-parameter type class. Thus, it's currently
not possible to define e.g. a 2-tuple as an instance of interval and use that
map key. Instead, you must convert your keys to `Interval`

.

The implementation is a red-black tree augmented with the maximum upper bound of all keys.

Parts of this implementation are based on code from the `Map`

implementation,
(c) Daan Leijen 2002, (c) Andriy Palamarchuk 2008.
The red-black tree deletion is based on code from llrbtree by Kazu Yamamoto.
Of course, any errors are mine.

- data Interval a
- = IntervalCO !a !a
- | ClosedInterval !a !a
- | OpenInterval !a !a
- | IntervalOC !a !a

- data IntervalMap k v
- (!) :: Ord k => IntervalMap k v -> Interval k -> v
- (\\) :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a
- null :: IntervalMap k v -> Bool
- size :: IntervalMap k v -> Int
- member :: Ord k => Interval k -> IntervalMap k v -> Bool
- notMember :: Ord k => Interval k -> IntervalMap k v -> Bool
- lookup :: Ord k => Interval k -> IntervalMap k v -> Maybe v
- findWithDefault :: Ord k => a -> Interval k -> IntervalMap k a -> a
- containing :: Ord k => IntervalMap k v -> k -> [(Interval k, v)]
- intersecting :: Ord k => IntervalMap k v -> Interval k -> [(Interval k, v)]
- within :: Ord k => IntervalMap k v -> Interval k -> [(Interval k, v)]
- empty :: IntervalMap k v
- singleton :: Interval k -> v -> IntervalMap k v
- insert :: Ord k => Interval k -> v -> IntervalMap k v -> IntervalMap k v
- insertWith :: Ord k => (v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k v
- insertWith' :: Ord k => (v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k v
- insertWithKey :: Ord k => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k v
- insertWithKey' :: Ord k => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k v
- insertLookupWithKey :: Ord k => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> (Maybe v, IntervalMap k v)
- insertLookupWithKey' :: Ord k => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> (Maybe v, IntervalMap k v)
- delete :: Ord k => Interval k -> IntervalMap k v -> IntervalMap k v
- adjust :: Ord k => (a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k a
- adjustWithKey :: Ord k => (Interval 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
- updateWithKey :: Ord k => (Interval k -> a -> Maybe a) -> Interval k -> IntervalMap k a -> IntervalMap k a
- updateLookupWithKey :: Ord k => (Interval k -> a -> Maybe a) -> Interval k -> IntervalMap k a -> (Maybe 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
- unionWithKey :: Ord k => (Interval 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
- difference :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a
- differenceWith :: Ord k => (a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a
- differenceWithKey :: Ord k => (Interval k -> a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a
- intersection :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a
- intersectionWith :: Ord k => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
- intersectionWithKey :: Ord k => (Interval k -> a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
- map :: (a -> b) -> IntervalMap k a -> IntervalMap k b
- mapWithKey :: (Interval k -> a -> b) -> IntervalMap k a -> IntervalMap k b
- mapAccum :: (a -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)
- mapAccumWithKey :: (a -> Interval k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)
- mapAccumRWithKey :: (a -> Interval k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)
- mapKeys :: Ord k2 => (Interval k1 -> Interval k2) -> IntervalMap k1 a -> IntervalMap k2 a
- mapKeysWith :: Ord k2 => (a -> a -> a) -> (Interval k1 -> Interval k2) -> IntervalMap k1 a -> IntervalMap k2 a
- mapKeysMonotonic :: Ord k2 => (Interval k1 -> Interval k2) -> IntervalMap k1 a -> IntervalMap k2 a
- foldr :: (a -> b -> b) -> b -> IntervalMap k a -> b
- foldl :: (b -> a -> b) -> b -> IntervalMap k a -> b
- foldrWithKey :: (Interval k -> v -> a -> a) -> a -> IntervalMap k v -> a
- foldlWithKey :: (a -> Interval k -> v -> a) -> a -> IntervalMap k v -> a
- foldl' :: (b -> a -> b) -> b -> IntervalMap k a -> b
- foldr' :: (a -> b -> b) -> b -> IntervalMap k a -> b
- foldrWithKey' :: (Interval k -> v -> a -> a) -> a -> IntervalMap k v -> a
- foldlWithKey' :: (a -> Interval k -> v -> a) -> a -> IntervalMap k v -> a
- elems :: IntervalMap k v -> [v]
- keys :: IntervalMap k v -> [Interval k]
- keysSet :: Ord k => IntervalMap k v -> Set (Interval k)
- assocs :: IntervalMap k v -> [(Interval k, v)]
- toList :: IntervalMap k v -> [(Interval k, v)]
- fromList :: Ord k => [(Interval k, v)] -> IntervalMap k v
- fromListWith :: Ord k => (a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a
- fromListWithKey :: Ord k => (Interval k -> a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a
- toAscList :: IntervalMap k v -> [(Interval k, v)]
- toDescList :: IntervalMap k v -> [(Interval k, v)]
- fromAscList :: Ord k => [(Interval k, v)] -> IntervalMap k v
- fromAscListWith :: Ord k => (a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a
- fromAscListWithKey :: Ord k => (Interval k -> a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a
- fromDistinctAscList :: Ord k => [(Interval k, v)] -> IntervalMap k v
- filter :: Ord k => (a -> Bool) -> IntervalMap k a -> IntervalMap k a
- filterWithKey :: Ord k => (Interval k -> a -> Bool) -> IntervalMap k a -> IntervalMap k a
- partition :: Ord k => (a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)
- partitionWithKey :: Ord k => (Interval k -> a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)
- mapMaybe :: Ord k => (a -> Maybe b) -> IntervalMap k a -> IntervalMap k b
- mapMaybeWithKey :: Ord k => (Interval k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b
- mapEither :: Ord k => (a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)
- mapEitherWithKey :: Ord k => (Interval k -> a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)
- split :: Ord k => Interval k -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)
- splitLookup :: Ord k => Interval k -> IntervalMap k a -> (IntervalMap k a, Maybe 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
- findMin :: IntervalMap k v -> (Interval k, v)
- findMax :: IntervalMap k v -> (Interval k, v)
- findLast :: Eq k => IntervalMap k v -> (Interval k, v)
- deleteMin :: Ord k => IntervalMap k v -> IntervalMap k v
- deleteMax :: Ord k => IntervalMap k v -> IntervalMap k v
- deleteFindMin :: Ord k => IntervalMap k v -> ((Interval k, v), IntervalMap k v)
- deleteFindMax :: Ord k => IntervalMap k v -> ((Interval k, v), IntervalMap k v)
- updateMin :: Ord k => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
- updateMax :: Ord k => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
- updateMinWithKey :: Ord k => (Interval k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
- updateMaxWithKey :: Ord k => (Interval k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
- minView :: Ord k => IntervalMap k a -> Maybe (a, IntervalMap k a)
- maxView :: Ord k => IntervalMap k a -> Maybe (a, IntervalMap k a)
- minViewWithKey :: Ord k => IntervalMap k a -> Maybe ((Interval k, a), IntervalMap k a)
- maxViewWithKey :: Ord k => IntervalMap k a -> Maybe ((Interval k, a), IntervalMap k a)
- valid :: Ord k => IntervalMap k v -> Bool
- height :: IntervalMap k v -> Int
- maxHeight :: Int -> Int
- showStats :: IntervalMap k a -> (Int, Int, Int)

# re-export

Intervals with endpoints of type `a`

.

`Read`

and `Show`

use mathematical notation with square brackets for closed
and parens for open intervals.
This is better for human readability, but is not a valid Haskell expression.
Closed intervals look like a list, open intervals look like a tuple,
and half-open intervals look like mismatched parens.

IntervalCO !a !a | Including lower bound, excluding upper |

ClosedInterval !a !a | Closed at both ends |

OpenInterval !a !a | Open at both ends |

IntervalOC !a !a | Excluding lower bound, including upper |

# Map type

data IntervalMap k v Source

A map from intervals with endpoints of type `k`

to values of type `v`

.

Functor (IntervalMap k) | |

Foldable (IntervalMap k) | |

Traversable (IntervalMap k) | |

(Eq k, Eq v) => Eq (IntervalMap k v) | |

(Ord k, Ord v) => Ord (IntervalMap k v) | |

(Ord k, Read k, Read e) => Read (IntervalMap k e) | |

(Show k, Show a) => Show (IntervalMap k a) | |

Ord k => Monoid (IntervalMap k v) | |

(NFData k, NFData a) => NFData (IntervalMap k a) |

# Operators

(!) :: Ord k => IntervalMap k v -> Interval k -> vSource

*O(log n)*. Lookup value for given key. Calls `error`

if the key is not in the map.

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

Same as `difference`

.

# Query

null :: IntervalMap k v -> BoolSource

*O(1)*. Is the map empty?

size :: IntervalMap k v -> IntSource

*O(n)*. Number of keys in the map.

Caution: unlike `size`

, which takes constant time, this is linear in the
number of keys!

member :: Ord k => Interval k -> IntervalMap k v -> BoolSource

*O(log n)*. Does the map contain the given key? See also `notMember`

.

notMember :: Ord k => Interval k -> IntervalMap k v -> BoolSource

*O(log n)*. Does the map not contain the given key? See also `member`

.

findWithDefault :: Ord k => a -> Interval k -> IntervalMap k a -> aSource

*O(log n)*. 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.

findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x' findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'

## Interval query

containing :: Ord k => IntervalMap k v -> k -> [(Interval k, v)]Source

Return all key/value pairs where the key intervals contain the given point. The elements are returned in ascending key order.

*O(n)*, since potentially all keys could contain the point.
*O(log n)* average case. This is also the worst case for maps containing no overlapping keys.

intersecting :: Ord k => IntervalMap k v -> Interval k -> [(Interval k, v)]Source

Return all key/value pairs where the key intervals overlap (intersect) the given interval. The elements are returned in ascending key order.

*O(n)*, since potentially all keys could intersect the interval.
*O(log n)* average case, if few keys intersect the interval.

within :: Ord k => IntervalMap k v -> Interval k -> [(Interval k, v)]Source

Return all key/value pairs where the key intervals are completely inside the given interval. The elements are returned in ascending key order.

*O(n)*, since potentially all keys could be inside the interval.
*O(log n)* average case, if few keys are inside the interval.

# Construction

empty :: IntervalMap k vSource

*O(1)*. The empty map.

singleton :: Interval k -> v -> IntervalMap k vSource

*O(1)*. A map with one entry.

## Insertion

insert :: Ord k => Interval k -> v -> IntervalMap k v -> IntervalMap k vSource

*O(log n)*. Insert a new key/value pair. If the map already contains the key, its value is
changed to the new value.

insertWith :: Ord k => (v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k vSource

*O(log n)*. Insert with a function, combining new value and old value.

will insert the pair (key, value) into `insertWith`

f key value mp`mp`

if key does
not exist in the map. If the key does exist, the function will
insert the pair `(key, f new_value old_value)`

.

insertWith' :: Ord k => (v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k vSource

Same as `insertWith`

, but the combining function is applied strictly.
This is often the most desirable behavior.

insertWithKey :: Ord k => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k vSource

*O(log n)*. Insert with a function, combining key, new value and old value.

will insert the pair (key, value) into `insertWithKey`

f key value mp`mp`

if key does
not exist in the map. If the key does exist, the function will
insert the pair `(key, f key new_value old_value)`

.
Note that the key passed to f is the same key passed to `insertWithKey`

.

insertWithKey' :: Ord k => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k vSource

Same as `insertWithKey`

, but the combining function is applied strictly.

insertLookupWithKey :: Ord k => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> (Maybe v, IntervalMap k v)Source

*O(log n)*. Combine insert with old values retrieval.

insertLookupWithKey' :: Ord k => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> (Maybe v, IntervalMap k v)Source

*O(log n)*. A strict version of `insertLookupWithKey`

.

## Delete/Update

delete :: Ord k => Interval k -> IntervalMap k v -> IntervalMap k vSource

*O(log n)*. Delete a key from the map. If the map does not contain the key,
it is returned unchanged.

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

*O(log n)*. Update a value at a specific key with the result of the provided function.
When the key is not
a member of the map, the original map is returned.

adjustWithKey :: Ord k => (Interval k -> a -> a) -> Interval k -> IntervalMap k a -> IntervalMap k aSource

*O(log n)*. Adjust a value at a specific key. When the key is not
a member of the map, the original map is returned.

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

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

*O(log n)*. The expression (

) updates the
value `updateWithKey`

f k map`x`

at `k`

(if it is in the map). If (`f k x`

) is `Nothing`

,
the element is deleted. If it is (

), the key `Just`

y`k`

is bound
to the new value `y`

.

updateLookupWithKey :: Ord k => (Interval k -> a -> Maybe a) -> Interval k -> IntervalMap k a -> (Maybe a, IntervalMap k a)Source

*O(log n)*. Lookup and update. See also `updateWithKey`

.
The function returns changed value, if it is updated.
Returns the original key value if the map entry is deleted.

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

# Combine

## Union

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

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

*O(n+m)*. Union with a combining function.

unionWithKey :: Ord k => (Interval k -> a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k aSource

*O(n+m)*. Union with a combining function.

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

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

The union of a list of maps, with a combining operation:
(

).
`unionsWith`

f == `foldl`

(`unionWith`

f) `empty`

## Difference

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

*O(n+m)*. Difference of two maps.
Return elements of the first map not existing in the second map.

differenceWith :: Ord k => (a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k aSource

differenceWithKey :: Ord k => (Interval k -> a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k aSource

## Intersection

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

*O(n+m)*. Intersection of two maps.
Return data in the first map for the keys existing in both maps.
(

).
`intersection`

m1 m2 == `intersectionWith`

`const`

m1 m2

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

*O(n+m)*. Intersection with a combining function.

intersectionWithKey :: Ord k => (Interval k -> a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k cSource

*O(n+m)*. Intersection with a combining function.

# Traversal

## Map

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

*O(n)*. Map a function over all values in the map.

mapWithKey :: (Interval k -> a -> b) -> IntervalMap k a -> IntervalMap k bSource

*O(n)*. Map a function over all values in the map.

mapAccum :: (a -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)Source

*O(n)*. The function `mapAccum`

threads an accumulating
argument through the map in ascending order of keys.

let f a b = (a ++ b, b ++ "X") mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])

mapAccumWithKey :: (a -> Interval k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)Source

*O(n)*. The function `mapAccumWithKey`

threads an accumulating
argument through the map in ascending order of keys.

let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X") mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])

mapAccumRWithKey :: (a -> Interval k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)Source

*O(n)*. The function `mapAccumR`

threads an accumulating
argument through the map in descending order of keys.

mapKeys :: Ord k2 => (Interval k1 -> Interval k2) -> IntervalMap k1 a -> IntervalMap k2 aSource

*O(n log n)*.

is the map obtained by applying `mapKeys`

f s`f`

to each key of `s`

.

The size of the result may be smaller if `f`

maps two or more distinct
keys to the same new key. In this case the value at the smallest of
these keys is retained.

mapKeysWith :: Ord k2 => (a -> a -> a) -> (Interval k1 -> Interval k2) -> IntervalMap k1 a -> IntervalMap k2 aSource

*O(n log n)*.

is the map obtained by applying `mapKeysWith`

c f s`f`

to each key of `s`

.

The size of the result may be smaller if `f`

maps two or more distinct
keys to the same new key. In this case the associated values will be
combined using `c`

.

mapKeysMonotonic :: Ord k2 => (Interval k1 -> Interval k2) -> IntervalMap k1 a -> IntervalMap k2 aSource

*O(n log n)*.

, but works only when `mapKeysMonotonic`

f s == `mapKeys`

f s`f`

is strictly monotonic.
That is, for any values `x`

and `y`

, if `x`

< `y`

then `f x`

< `f y`

.
*The precondition is not checked.*

## Fold

foldr :: (a -> b -> b) -> b -> IntervalMap k a -> bSource

foldl :: (b -> a -> b) -> b -> IntervalMap k a -> bSource

foldrWithKey :: (Interval k -> v -> a -> a) -> a -> IntervalMap k v -> aSource

*O(n)*. Fold the keys and values in the map using the given right-associative
binary operator, such that

.
`foldrWithKey`

f z == `foldr`

(`uncurry`

f) z . `toAscList`

foldlWithKey :: (a -> Interval k -> v -> a) -> a -> IntervalMap k v -> aSource

*O(n)*. Fold the keys and values in the map using the given left-associative
binary operator, such that

.
`foldlWithKey`

f z == `foldl`

(\z' (kx, x) -> f z' kx x) z . `toAscList`

foldl' :: (b -> a -> b) -> b -> IntervalMap k a -> bSource

*O(n)*. A strict version of `foldl`

. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.

foldr' :: (a -> b -> b) -> b -> IntervalMap k a -> bSource

*O(n)*. A strict version of `foldr`

. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.

foldrWithKey' :: (Interval k -> v -> a -> a) -> a -> IntervalMap k v -> aSource

*O(n)*. A strict version of `foldrWithKey`

. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.

foldlWithKey' :: (a -> Interval k -> v -> a) -> a -> IntervalMap k v -> aSource

*O(n)*. A strict version of `foldlWithKey`

. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.

# Conversion

elems :: IntervalMap k v -> [v]Source

*O(n)*. List of all values in the map, in ascending order of their keys.

keys :: IntervalMap k v -> [Interval k]Source

*O(n)*. List of all keys in the map, in ascending order.

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

Same as `toAscList`

.

## Lists

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

*O(n)*. The list of all key/value pairs contained in the map, in no particular order.

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

*O(n log n)*. Build a map from a list of key/value pairs. See also `fromAscList`

.
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 aSource

*O(n log n)*. Build a map from a list of key/value pairs with a combining function. See also `fromAscListWith`

.

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

*O(n log n)*. Build a map from a list of key/value pairs with a combining function. See also `fromAscListWith`

.

## Ordered lists

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

*O(n)*. The list of all key/value pairs contained in the map, in ascending order of keys.

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

*O(n)*. The list of all key/value pairs contained in the map, in descending order of keys.

fromAscList :: Ord k => [(Interval k, v)] -> IntervalMap k vSource

*O(n)*. Build a map from an ascending list in linear time.
*The precondition (input list is ascending) is not checked.*

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

*O(n)*. Build a map from an ascending list in linear time with a combining function for equal keys.
*The precondition (input list is ascending) is not checked.*

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

*O(n)*. Build a map from an ascending list in linear time with a combining function for equal keys.
*The precondition (input list is ascending) is not checked.*

fromDistinctAscList :: Ord k => [(Interval k, v)] -> IntervalMap k vSource

*O(n)*. Build a map from an ascending list of elements with distinct keys in linear time.
*The precondition is not checked.*

# Filter

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

*O(n)*. Filter values satisfying a predicate.

filterWithKey :: Ord k => (Interval k -> a -> Bool) -> IntervalMap k a -> IntervalMap k aSource

*O(n)*. Filter keys/values satisfying a predicate.

partition :: Ord k => (a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)Source

*O(n)*. Partition the map according to a predicate. The first
map contains all elements that satisfy the predicate, the second all
elements that fail the predicate. See also `split`

.

partitionWithKey :: Ord k => (Interval k -> a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)Source

*O(n)*. Partition the map according to a predicate. The first
map contains all elements that satisfy the predicate, the second all
elements that fail the predicate. See also `split`

.

mapMaybe :: Ord k => (a -> Maybe b) -> IntervalMap k a -> IntervalMap k bSource

*O(n)*. Map values and collect the `Just`

results.

mapMaybeWithKey :: Ord k => (Interval k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k bSource

*O(n)*. Map keys/values and collect the `Just`

results.

mapEither :: Ord k => (a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)Source

mapEitherWithKey :: Ord k => (Interval k -> a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)Source

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

*O(n)*. The expression (

) is a pair `split`

k map`(map1,map2)`

where
the keys in `map1`

are smaller than `k`

and the keys in `map2`

larger than `k`

.
Any key equal to `k`

is found in neither `map1`

nor `map2`

.

splitLookup :: Ord k => Interval k -> IntervalMap k a -> (IntervalMap k a, Maybe a, IntervalMap k a)Source

*O(n)*. The expression (

) splits a map just
like `splitLookup`

k map`split`

but also returns

.
`lookup`

k map

# Submap

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

*O(n+m)*. This function is defined as (

).
`isSubmapOf`

= `isSubmapOfBy`

(==)

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

*O(n+m)*.
The expression (

) returns `isSubmapOfBy`

f t1 t2`True`

if
all keys in `t1`

are in tree `t2`

, and `f`

returns `True`

when
applied to their respective values.

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

*O(n+m)*. 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 -> BoolSource

*O(n+m)*. 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.

# Min/Max

findMin :: IntervalMap k v -> (Interval k, v)Source

*O(log n)*. Returns the smallest key and its associated value.
Calls `error`

if the map is empty.

findMax :: IntervalMap k v -> (Interval k, v)Source

*O(log n)*. Returns the largest key and its associated value.
Calls `error`

if the map is empty.

findLast :: Eq k => IntervalMap k v -> (Interval k, v)Source

Returns the interval with the largest endpoint. If there is more than one interval with that endpoint, return the rightmost.

*O(n)*, since all keys could have the same endpoint.
*O(log n)* average case.

deleteMin :: Ord k => IntervalMap k v -> IntervalMap k vSource

*O(log n)*. Remove the smallest key from the map. Return the empty map if the map is empty.

deleteMax :: Ord k => IntervalMap k v -> IntervalMap k vSource

*O(log n)*. Remove the largest key from the map. Return the empty map if the map is empty.

deleteFindMin :: Ord k => IntervalMap k v -> ((Interval k, v), IntervalMap k v)Source

*O(log n)*. Delete and return the smallest key.

deleteFindMax :: Ord k => IntervalMap k v -> ((Interval k, v), IntervalMap k v)Source

*O(log n)*. Delete and return the largest key.

updateMin :: Ord k => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k vSource

*O(log n)*. Update or delete value at minimum key.

updateMax :: Ord k => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k vSource

*O(log n)*. Update or delete value at maximum key.

updateMinWithKey :: Ord k => (Interval k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k vSource

*O(log n)*. Update or delete value at minimum key.

updateMaxWithKey :: Ord k => (Interval k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k vSource

*O(log n)*. Update or delete value at maximum key.

minView :: Ord k => IntervalMap k a -> Maybe (a, IntervalMap k a)Source

*O(log n)*. Retrieves the value associated with minimal key of the
map, and the map stripped of that element, or `Nothing`

if passed an
empty map.

maxView :: Ord k => IntervalMap k a -> Maybe (a, IntervalMap k a)Source

*O(log n)*. Retrieves the value associated with maximal key of the
map, and the map stripped of that element, or `Nothing`

if passed an
empty map.

minViewWithKey :: Ord k => IntervalMap k a -> Maybe ((Interval k, a), IntervalMap k a)Source

*O(log n)*. Retrieves the minimal (key,value) pair of the map, and
the map stripped of that element, or `Nothing`

if passed an empty map.

minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a") minViewWithKey empty == Nothing

maxViewWithKey :: Ord k => IntervalMap k a -> Maybe ((Interval k, a), IntervalMap k a)Source

*O(log n)*. Retrieves the maximal (key,value) pair of the map, and
the map stripped of that element, or `Nothing`

if passed an empty map.

# Debugging

valid :: Ord k => IntervalMap k v -> BoolSource

Check red-black-tree and interval search augmentation invariants. For testing/debugging only.

# Testing

height :: IntervalMap k v -> IntSource

The height of the tree. For testing/debugging only.

The maximum height of a red-black tree with the given number of nodes. For testing/debugging only.