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

Stability | experimental |

Maintainer | chbreitkopf@googlemail.com |

An implementation of maps from intervals to values. The key intervals may overlap, and the implementation supports an efficient stabbing query.

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 functions in Data.Map, but `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.

Index-based access and some set functions have not been implemented, and many non-core functions, for example the set operations, have not been tuned for efficiency yet.

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 `Data.IntervalMap.Interval`

.

Closed, open, and half-open intervals can be contained in the same map.

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

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 `Data.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)
- 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
- 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.

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 == `Prelude.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.*

This function is currently identical to `mapKeys`

, but will eventually be rewritten to have better
better performance (*O(n)*).

## 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 == `Prelude.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 == `Prelude.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

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

# Debugging

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

Check red-black-tree and interval search augmentation invariants.

# Testing

height :: IntervalMap k v -> IntSource

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