Data.IntervalMap.Lazy

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.

re-export

data Interval a

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.

Constructors

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

Instances

Functor Interval

Defined in Data.IntervalMap.Interval

Methods

fmap :: (a -> b) -> Interval a -> Interval b

(<$) :: a -> Interval b -> Interval a

Eq a => Eq (Interval a)

Defined in Data.IntervalMap.Interval

Methods

(==) :: Interval a -> Interval a -> Bool

(/=) :: Interval a -> Interval a -> Bool

Ord a => Ord (Interval a)

Defined in Data.IntervalMap.Interval

Methods

compare :: Interval a -> Interval a -> Ordering

(<) :: Interval a -> Interval a -> Bool

(<=) :: Interval a -> Interval a -> Bool

(>) :: Interval a -> Interval a -> Bool

(>=) :: Interval a -> Interval a -> Bool

max :: Interval a -> Interval a -> Interval a

min :: Interval a -> Interval a -> Interval a

Read a => Read (Interval a)

Defined in Data.IntervalMap.Interval

Methods

readsPrec :: Int -> ReadS (Interval a)

readList :: ReadS [Interval a]

readPrec :: ReadPrec (Interval a)

readListPrec :: ReadPrec [Interval a]

Show a => Show (Interval a)

Defined in Data.IntervalMap.Interval

Methods

showsPrec :: Int -> Interval a -> ShowS

show :: Interval a -> String

showList :: [Interval a] -> ShowS

NFData a => NFData (Interval a)

Defined in Data.IntervalMap.Interval

Methods

rnf :: Interval a -> ()

Ord a => Interval (Interval a) a

Defined in Data.IntervalMap.Generic.Interval

Methods

lowerBound :: Interval a -> a

upperBound :: Interval a -> a

leftClosed :: Interval a -> Bool

rightClosed :: Interval a -> Bool

before :: Interval a -> Interval a -> Bool

after :: Interval a -> Interval a -> Bool

subsumes :: Interval a -> Interval a -> Bool

overlaps :: Interval a -> Interval a -> Bool

below :: a -> Interval a -> Bool

above :: a -> Interval a -> Bool

inside :: a -> Interval a -> Bool

isEmpty :: Interval a -> Bool

compareUpperBounds :: Interval a -> Interval a -> Ordering

Map type

type IntervalMap k v = IntervalMap (Interval k) v

Operators

(!) :: (Interval k e, Ord k) => IntervalMap k v -> k -> v infixl 9

O(log n). Lookup value for given key. Calls error if the key is not in the map.

Use lookup or findWithDefault instead of this function, unless you are absolutely sure that the key is present in the map.

(\\) :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a infixl 9

Same as difference.

Query

null :: IntervalMap k v -> Bool

O(1). Is the map empty?

size :: IntervalMap k v -> Int

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 => k -> IntervalMap k v -> Bool

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

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

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

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

O(log n). Look up the given key in the map, returning the value (Just value), or Nothing if the key is not in the map.

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

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

lookupLT :: Ord k => k -> IntervalMap k v -> Maybe (k, v)

O(log n). Find the largest key smaller than the given one and return it along with its value.

lookupGT :: Ord k => k -> IntervalMap k v -> Maybe (k, v)

O(log n). Find the smallest key larger than the given one and return it along with its value.

lookupLE :: Ord k => k -> IntervalMap k v -> Maybe (k, v)

O(log n). Find the largest key equal to or smaller than the given one and return it along with its value.

lookupGE :: Ord k => k -> IntervalMap k v -> Maybe (k, v)

O(log n). Find the smallest key larger than the given one and return it along with its value.

Interval query

containing :: Interval k e => IntervalMap k v -> e -> IntervalMap k v

Return the submap of key intervals containing the given point. This is the second element of the value of splitAt:

m `containing` p == let (_,m',_) = m `splitAt` p in m'

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 :: Interval k e => IntervalMap k v -> k -> IntervalMap k v

Return the submap of key intervals overlapping (intersecting) the given interval. This is the second element of the value of splitIntersecting:

m `intersecting` i == let (_,m',_) = m `splitIntersecting` i in m'

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

within :: Interval k e => IntervalMap k v -> k -> IntervalMap k v

Return the submap of key intervals completely inside the given interval.

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 v

O(1). The empty map.

singleton :: k -> v -> IntervalMap k v

O(1). A map with one entry.

Insertion

insert :: (Interval k e, Ord k) => k -> v -> IntervalMap k v -> IntervalMap k v

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 :: (Interval k e, Ord k) => (v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v

O(log n). Insert with a function, combining new value and old value. insertWith f key value mp will insert the pair (key, value) into 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).

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

O(log n). Insert with a function, combining key, new value and old value. insertWithKey f key value mp will insert the pair (key, value) into 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.

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

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

Delete/Update

delete :: (Interval k e, Ord k) => k -> IntervalMap k v -> IntervalMap k v

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) -> k -> IntervalMap k a -> IntervalMap k a

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 => (k -> a -> a) -> k -> IntervalMap k a -> IntervalMap k a

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 :: (Interval k e, Ord k) => (a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

O(log n). The expression (update f k map) updates the value x at k (if it is in the map). If (f x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y.

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

O(log n). The expression (updateWithKey f k map) updates the value x at k (if it is in the map). If (f k x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y.

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

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 :: (Interval k e, Ord k) => (Maybe a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a

O(log n). The expression (alter f k map) alters the value x at k, or absence thereof. alter can be used to insert, delete, or update a value in a Map. In short : lookup k (alter f k m) = f (lookup k m).

Combine

Union

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

O(n+m). The expression (union t1 t2) takes the left-biased union of t1 and t2. It prefers t1 when duplicate keys are encountered, i.e. (union == unionWith const).

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

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

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

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

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

The union of a list of maps: (unions == foldl union empty).

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

The union of a list of maps, with a combining operation: (unionsWith f == foldl (unionWith f) empty).

Difference

difference :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

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

differenceWith :: (Interval k e, Ord k) => (a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a

O(n+m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y.

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

O(n+m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the key and both values. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y.

Intersection

intersection :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a

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 :: (Interval k e, Ord k) => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c

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

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

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

Traversal

Map

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

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

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

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

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

O(n). The function mapAccum threads an accumulating argument through the map in ascending order of keys.

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

O(n). The function mapAccumWithKey threads an accumulating argument through the map in ascending order of keys.

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

O(n). The function mapAccumRWithKey threads an accumulating argument through the map in descending order of keys.

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

O(n log n). mapKeys f s is the map obtained by applying 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 :: (Interval k2 e, Ord k2) => (a -> a -> a) -> (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

O(n log n). mapKeysWith c f s is the map obtained by applying 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 :: (Interval k2 e, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a

O(n). mapKeysMonotonic f s == mapKeys f s, but works only when 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 -> b

O(n). Fold the values in the map using the given right-associative binary operator, such that foldr f z == foldr f z . elems.

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

O(n). Fold the values in the map using the given left-associative binary operator, such that foldl f z == foldl f z . elems.

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

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 -> k -> v -> a) -> a -> IntervalMap k v -> a

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.

Flatten

flattenWith :: Ord k => (v -> v -> v) -> IntervalMap k v -> IntervalMap 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)]

Conversion

elems :: IntervalMap k v -> [v]

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

keys :: IntervalMap k v -> [k]

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

keysSet :: IntervalMap k v -> Set k

O(n). Set of the keys.

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

Same as toAscList.

Lists

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

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

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

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 :: (Interval k e, Ord k) => (a -> a -> a) -> [(k, a)] -> IntervalMap k a

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

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

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 -> [(k, v)]

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

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

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

fromAscList :: (Interval k e, Eq k) => [(k, v)] -> IntervalMap k v

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

fromAscListWith :: (Interval k e, Eq k) => (a -> a -> a) -> [(k, a)] -> IntervalMap k a

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 :: (Interval k e, Eq k) => (k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a

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 :: Interval k e => [(k, v)] -> IntervalMap k v

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

Filter

filter :: Interval k e => (a -> Bool) -> IntervalMap k a -> IntervalMap k a

O(n). Filter values satisfying a predicate.

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

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

partition :: Interval k e => (a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)

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 :: Interval k e => (k -> a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)

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 :: Interval k e => (a -> Maybe b) -> IntervalMap k a -> IntervalMap k b

O(n). Map values and collect the Just results.

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

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

mapEither :: Interval k e => (a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)

O(n). Map values and separate the Left and Right results.

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

O(n). Map keys/values and separate the Left and Right results.

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

O(n). The expression (split k map) is a pair (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 :: (Interval i k, Ord i) => i -> IntervalMap i a -> (IntervalMap i a, Maybe a, IntervalMap i a)

O(n). The expression (splitLookup k map) splits a map just like split but also returns lookup k map.

splitAt :: Interval i k => IntervalMap i a -> k -> (IntervalMap i a, IntervalMap i a, IntervalMap i a)

O(n). Split around a point. Splits the map into three submaps: intervals below the point, intervals containing the point, and intervals above the point.

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

O(n). Split around an interval. Splits the set into three subsets: intervals below the given interval, intervals intersecting the given interval, and intervals above the given interval.

Submap

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

O(n+m). This function is defined as (isSubmapOf = isSubmapOfBy (==)).

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

O(n+m). The expression (isSubmapOfBy f t1 t2) returns 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 -> Bool

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 -> Bool

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

Min/Max

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

O(log n). Returns the smallest key and its associated value. Calls error if the map is empty.

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

O(log n). Returns the largest key and its associated value. Calls error if the map is empty.

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

Returns the key with the largest endpoint and its associated value. If there is more than one key with that endpoint, return the rightmost.

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

lookupMin :: IntervalMap k v -> Maybe (k, v)

O(log n). Returns the smallest key and its associated value.

lookupMax :: IntervalMap k v -> Maybe (k, v)

O(log n). Returns the largest key and its associated value.

lookupLast :: Interval k e => IntervalMap k v -> Maybe (k, v)

Returns the key with the largest endpoint and its associated value. If there is more than one key with that endpoint, return the rightmost.

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

deleteMin :: (Interval k e, Ord k) => IntervalMap k v -> IntervalMap k v

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

deleteMax :: (Interval k e, Ord k) => IntervalMap k v -> IntervalMap k v

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

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

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

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

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

updateMin :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

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

updateMax :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v

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

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

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

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

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

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

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 :: (Interval k e, Ord k) => IntervalMap k a -> Maybe (a, IntervalMap k a)

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 :: (Interval k e, Ord k) => IntervalMap k a -> Maybe ((k, a), IntervalMap k a)

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,6],"a"), ([3,4],"b")]) == Just (([3,4],"b"), singleton [5,6] "a")
minViewWithKey empty == Nothing

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

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 :: (Interval i k, Ord i) => IntervalMap i v -> Bool

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

Testing

height :: IntervalMap k v -> Int

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

maxHeight :: Int -> Int

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

showStats :: IntervalMap k a -> (Int, Int, Int)

Tree statistics (size, height, maxHeight size). For testing/debugging only.