Copyright | (c) Christoph Breitkopf 2014 |
---|---|
License | BSD-style |
Maintainer | chbreitkopf@gmail.com |
Stability | experimental |
Portability | non-portable (MPTC with FD) |
Safe Haskell | Safe |
Language | Haskell2010 |
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.
The functions in this module are 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).
An IntervalMap cannot contain duplicate keys - if you need to map a
key to multiple 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.Generic.IntervalMap.Strict (IntervalMap) import qualified Data.Generic.IntervalMap.Strict as IM
It offers most of the same functions as Map
, but the
key type must be an instance of Interval
.
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.
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.
Synopsis
- class Ord e => Interval i e | i -> e where
- lowerBound :: i -> e
- upperBound :: i -> e
- leftClosed :: i -> Bool
- rightClosed :: i -> Bool
- before :: i -> i -> Bool
- after :: i -> i -> Bool
- subsumes :: i -> i -> Bool
- overlaps :: i -> i -> Bool
- below :: e -> i -> Bool
- above :: e -> i -> Bool
- inside :: e -> i -> Bool
- isEmpty :: i -> Bool
- compareUpperBounds :: i -> i -> Ordering
- data IntervalMap k v
- (!) :: Ord k => IntervalMap k v -> k -> v
- (\\) :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a
- null :: IntervalMap k v -> Bool
- size :: IntervalMap k v -> Int
- member :: Ord k => k -> IntervalMap k v -> Bool
- notMember :: Ord k => k -> IntervalMap k v -> Bool
- lookup :: Ord k => k -> IntervalMap k v -> Maybe v
- findWithDefault :: Ord k => a -> k -> IntervalMap k a -> a
- lookupLT :: Ord k => k -> IntervalMap k v -> Maybe (k, v)
- lookupGT :: Ord k => k -> IntervalMap k v -> Maybe (k, v)
- lookupLE :: Ord k => k -> IntervalMap k v -> Maybe (k, v)
- lookupGE :: Ord k => k -> IntervalMap k v -> Maybe (k, v)
- containing :: Interval k e => IntervalMap k v -> e -> IntervalMap k v
- intersecting :: Interval k e => IntervalMap k v -> k -> IntervalMap k v
- within :: Interval k e => IntervalMap k v -> k -> IntervalMap k v
- empty :: IntervalMap k v
- singleton :: k -> v -> IntervalMap k v
- insert :: (Interval k e, Ord k) => k -> v -> IntervalMap k v -> IntervalMap k v
- insertWith :: (Interval k e, Ord k) => (v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v
- insertWithKey :: (Interval k e, Ord k) => (k -> v -> v -> v) -> k -> v -> IntervalMap k v -> IntervalMap k v
- insertLookupWithKey :: (Interval k e, Ord k) => (k -> v -> v -> v) -> k -> v -> IntervalMap k v -> (Maybe v, IntervalMap k v)
- delete :: (Interval k e, Ord k) => k -> IntervalMap k v -> IntervalMap k v
- adjust :: Ord k => (a -> a) -> k -> IntervalMap k a -> IntervalMap k a
- adjustWithKey :: Ord k => (k -> a -> a) -> k -> IntervalMap k a -> IntervalMap k a
- update :: (Interval k e, Ord k) => (a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a
- updateWithKey :: (Interval k e, Ord k) => (k -> a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a
- updateLookupWithKey :: (Interval k e, Ord k) => (k -> a -> Maybe a) -> k -> IntervalMap k a -> (Maybe a, IntervalMap k a)
- alter :: (Interval k e, Ord k) => (Maybe a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a
- union :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k a -> IntervalMap k a
- unionWith :: (Interval k e, Ord k) => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
- unionWithKey :: (Interval k e, Ord k) => (k -> a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a
- unions :: (Interval k e, Ord k) => [IntervalMap k a] -> IntervalMap k a
- unionsWith :: (Interval k e, Ord k) => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a
- difference :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a
- differenceWith :: (Interval k e, Ord k) => (a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a
- differenceWithKey :: (Interval k e, Ord k) => (k -> a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a
- intersection :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a
- intersectionWith :: (Interval k e, Ord k) => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
- intersectionWithKey :: (Interval k e, Ord k) => (k -> a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c
- map :: (a -> b) -> IntervalMap k a -> IntervalMap k b
- mapWithKey :: (k -> a -> b) -> IntervalMap k a -> IntervalMap k b
- mapAccum :: (a -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)
- mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)
- mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c)
- mapKeys :: (Interval k2 e, Ord k2) => (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a
- mapKeysWith :: (Interval k2 e, Ord k2) => (a -> a -> a) -> (k1 -> k2) -> IntervalMap k1 a -> IntervalMap k2 a
- mapKeysMonotonic :: (Interval k2 e, Ord k2) => (k1 -> 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 :: (k -> v -> a -> a) -> a -> IntervalMap k v -> a
- foldlWithKey :: (a -> k -> v -> a) -> a -> IntervalMap k v -> a
- flattenWith :: (Ord k, Interval k e) => ((k, v) -> (k, v) -> Maybe (k, v)) -> IntervalMap k v -> IntervalMap k v
- flattenWithMonotonic :: Interval k e => ((k, v) -> (k, v) -> Maybe (k, v)) -> IntervalMap k v -> IntervalMap k v
- elems :: IntervalMap k v -> [v]
- keys :: IntervalMap k v -> [k]
- keysSet :: IntervalMap k v -> Set k
- assocs :: IntervalMap k v -> [(k, v)]
- toList :: IntervalMap k v -> [(k, v)]
- fromList :: (Interval k e, Ord k) => [(k, v)] -> IntervalMap k v
- fromListWith :: (Interval k e, Ord k) => (a -> a -> a) -> [(k, a)] -> IntervalMap k a
- fromListWithKey :: (Interval k e, Ord k) => (k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a
- toAscList :: IntervalMap k v -> [(k, v)]
- toDescList :: IntervalMap k v -> [(k, v)]
- fromAscList :: (Interval k e, Eq k) => [(k, v)] -> IntervalMap k v
- fromAscListWith :: (Interval k e, Eq k) => (a -> a -> a) -> [(k, a)] -> IntervalMap k a
- fromAscListWithKey :: (Interval k e, Eq k) => (k -> a -> a -> a) -> [(k, a)] -> IntervalMap k a
- fromDistinctAscList :: Interval k e => [(k, v)] -> IntervalMap k v
- filter :: Interval k e => (a -> Bool) -> IntervalMap k a -> IntervalMap k a
- filterWithKey :: Interval k e => (k -> a -> Bool) -> IntervalMap k a -> IntervalMap k a
- partition :: Interval k e => (a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)
- partitionWithKey :: Interval k e => (k -> a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a)
- mapMaybe :: Interval k e => (a -> Maybe b) -> IntervalMap k a -> IntervalMap k b
- mapMaybeWithKey :: Interval k e => (k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b
- mapEither :: Interval k e => (a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)
- mapEitherWithKey :: Interval k e => (k -> a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c)
- split :: (Interval i k, Ord i) => i -> IntervalMap i a -> (IntervalMap i a, IntervalMap i a)
- splitLookup :: (Interval i k, Ord i) => i -> IntervalMap i a -> (IntervalMap i a, Maybe a, IntervalMap i a)
- splitAt :: Interval i k => IntervalMap i a -> k -> (IntervalMap i a, IntervalMap i a, IntervalMap i a)
- splitIntersecting :: (Interval i k, Ord i) => IntervalMap i a -> i -> (IntervalMap i a, IntervalMap i a, IntervalMap i 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 -> (k, v)
- findMax :: IntervalMap k v -> (k, v)
- findLast :: Interval k e => IntervalMap k v -> (k, v)
- lookupMin :: IntervalMap k v -> Maybe (k, v)
- lookupMax :: IntervalMap k v -> Maybe (k, v)
- lookupLast :: Interval k e => IntervalMap k v -> Maybe (k, v)
- deleteMin :: (Interval k e, Ord k) => IntervalMap k v -> IntervalMap k v
- deleteMax :: (Interval k e, Ord k) => IntervalMap k v -> IntervalMap k v
- deleteFindMin :: (Interval k e, Ord k) => IntervalMap k v -> ((k, v), IntervalMap k v)
- deleteFindMax :: (Interval k e, Ord k) => IntervalMap k v -> ((k, v), IntervalMap k v)
- updateMin :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
- updateMax :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
- updateMinWithKey :: (Interval k e, Ord k) => (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
- updateMaxWithKey :: (Interval k e, Ord k) => (k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v
- minView :: (Interval k e, Ord k) => IntervalMap k a -> Maybe (a, IntervalMap k a)
- maxView :: (Interval k e, Ord k) => IntervalMap k a -> Maybe (a, IntervalMap k a)
- minViewWithKey :: (Interval k e, Ord k) => IntervalMap k a -> Maybe ((k, a), IntervalMap k a)
- maxViewWithKey :: (Interval k e, Ord k) => IntervalMap k a -> Maybe ((k, a), IntervalMap k a)
- valid :: (Interval i k, Ord i) => IntervalMap i v -> Bool
- height :: IntervalMap k v -> Int
- maxHeight :: Int -> Int
- showStats :: IntervalMap k a -> (Int, Int, Int)
re-export
class Ord e => Interval i e | i -> e where Source #
Intervals with endpoints of type e
.
A minimal instance declaration for a closed interval needs only
to define lowerBound
and upperBound
.
lowerBound :: i -> e Source #
lower bound
upperBound :: i -> e Source #
upper bound
leftClosed :: i -> Bool Source #
Does the interval include its lower bound? Default is True for all values, i.e. closed intervals.
rightClosed :: i -> Bool Source #
Does the interval include its upper bound bound? Default is True for all values, i.e. closed intervals.
before :: i -> i -> Bool Source #
Interval strictly before another? True if the upper bound of the first interval is below the lower bound of the second.
after :: i -> i -> Bool Source #
Interval strictly after another? Same as 'flip before'.
subsumes :: i -> i -> Bool Source #
Does the first interval completely contain the second?
overlaps :: i -> i -> Bool Source #
Do the two intervals overlap?
below :: e -> i -> Bool Source #
Is a point strictly less than lower bound?
above :: e -> i -> Bool Source #
Is a point strictly greater than upper bound?
inside :: e -> i -> Bool Source #
Does the interval contain a given point?
Is the interval empty?
compareUpperBounds :: i -> i -> Ordering Source #
Instances
Ord a => Interval (Interval a) a Source # | |
Defined in Data.IntervalMap.Generic.Interval lowerBound :: Interval a -> a Source # upperBound :: Interval a -> a Source # leftClosed :: Interval a -> Bool Source # rightClosed :: Interval a -> Bool Source # before :: Interval a -> Interval a -> Bool Source # after :: Interval a -> Interval a -> Bool Source # subsumes :: Interval a -> Interval a -> Bool Source # overlaps :: Interval a -> Interval a -> Bool Source # below :: a -> Interval a -> Bool Source # above :: a -> Interval a -> Bool Source # inside :: a -> Interval a -> Bool Source # isEmpty :: Interval a -> Bool Source # compareUpperBounds :: Interval a -> Interval a -> Ordering Source # |
Map type
data IntervalMap k v Source #
A map from intervals of type k
to values of type v
.
Instances
Operators
(!) :: Ord k => IntervalMap k v -> k -> v infixl 9 Source #
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 Source #
Same as difference
.
Query
null :: IntervalMap k v -> Bool Source #
O(1). Is the map empty?
size :: IntervalMap k v -> Int Source #
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 Source #
O(log n). Does the map contain the given key? See also notMember
.
notMember :: Ord k => k -> IntervalMap k v -> Bool Source #
O(log n). Does the map not contain the given key? See also member
.
findWithDefault :: Ord k => a -> k -> IntervalMap k a -> a Source #
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'
lookupLT :: Ord k => k -> IntervalMap k v -> Maybe (k, v) Source #
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) Source #
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) Source #
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) Source #
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 Source #
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 Source #
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 Source #
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 Source #
O(1). The empty map.
singleton :: k -> v -> IntervalMap k v Source #
O(1). A map with one entry.
Insertion
insert :: (Interval k e, Ord k) => k -> v -> IntervalMap k v -> IntervalMap k v Source #
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 Source #
O(log n). Insert with a function, combining new value and old value.
will insert the pair (key, value) into insertWith
f key value mpmp
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 Source #
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 mpmp
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) Source #
O(log n). Combine insert with old values retrieval.
Delete/Update
delete :: (Interval k e, Ord k) => k -> IntervalMap k v -> IntervalMap k v Source #
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 Source #
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 Source #
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 Source #
updateWithKey :: (Interval k e, Ord k) => (k -> a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a Source #
O(log n). The expression (
) updates the
value updateWithKey
f k mapx
at k
(if it is in the map). If (f k x
) is Nothing
,
the element is deleted. If it is (
), the key Just
yk
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) 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 :: (Interval k e, Ord k) => (Maybe a -> Maybe a) -> k -> IntervalMap k a -> IntervalMap k a Source #
Combine
Union
union :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k a -> IntervalMap k a Source #
unionWith :: (Interval k e, Ord k) => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a Source #
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 Source #
O(n+m). Union with a combining function.
unions :: (Interval k e, Ord k) => [IntervalMap k a] -> IntervalMap k a Source #
unionsWith :: (Interval k e, 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
Difference
difference :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a Source #
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 Source #
differenceWithKey :: (Interval k e, Ord k) => (k -> a -> b -> Maybe a) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k a Source #
Intersection
intersection :: (Interval k e, Ord k) => IntervalMap k a -> IntervalMap k b -> IntervalMap k a Source #
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 Source #
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 Source #
O(n+m). Intersection with a combining function.
Traversal
Map
map :: (a -> b) -> IntervalMap k a -> IntervalMap k b Source #
O(n). Map a function over all values in the map.
mapWithKey :: (k -> a -> b) -> IntervalMap k a -> IntervalMap k b Source #
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 -> 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 -> k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c) Source #
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 Source #
O(n log n).
is the map obtained by applying mapKeys
f sf
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 Source #
O(n log n).
is the map obtained by applying mapKeysWith
c f sf
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 Source #
O(n).
, but works only when mapKeysMonotonic
f s == mapKeys
f sf
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 Source #
foldl :: (b -> a -> b) -> b -> IntervalMap k a -> b Source #
foldrWithKey :: (k -> v -> a -> a) -> a -> IntervalMap k v -> a Source #
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 Source #
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
flattenWith :: (Ord k, Interval k e) => ((k, v) -> (k, v) -> Maybe (k, v)) -> IntervalMap k v -> IntervalMap k v Source #
O(n log n). Build a new map by combining successive key/value pairs.
flattenWithMonotonic :: Interval k e => ((k, v) -> (k, v) -> Maybe (k, v)) -> IntervalMap k v -> IntervalMap k v Source #
O(n). Build a new map by combining successive key/value pairs.
Same as flattenWith
, but works only when the combining functions returns
strictly monotonic key values.
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 -> [k] Source #
O(n). List of all keys in the map, in ascending order.
keysSet :: IntervalMap k v -> Set k Source #
O(n). Set of the keys.
assocs :: IntervalMap k v -> [(k, v)] Source #
Same as toAscList
.
Lists
toList :: IntervalMap k v -> [(k, v)] Source #
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 Source #
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 Source #
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 Source #
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)] Source #
O(n). The list of all key/value pairs contained in the map, in ascending order of keys.
toDescList :: IntervalMap k v -> [(k, v)] Source #
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 Source #
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 Source #
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 Source #
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 Source #
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 Source #
O(n). Filter values satisfying a predicate.
filterWithKey :: Interval k e => (k -> a -> Bool) -> IntervalMap k a -> IntervalMap k a Source #
O(n). Filter keys/values satisfying a predicate.
partition :: Interval k e => (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 :: Interval k e => (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 :: Interval k e => (a -> Maybe b) -> IntervalMap k a -> IntervalMap k b Source #
O(n). Map values and collect the Just
results.
mapMaybeWithKey :: Interval k e => (k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b Source #
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) Source #
mapEitherWithKey :: Interval k e => (k -> a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c) Source #
split :: (Interval i k, Ord i) => i -> IntervalMap i a -> (IntervalMap i a, IntervalMap i 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 :: (Interval i k, Ord i) => i -> IntervalMap i a -> (IntervalMap i a, Maybe a, IntervalMap i a) Source #
O(n). The expression (
) splits a map just
like splitLookup
k mapsplit
but also returns
.lookup
k map
splitAt :: Interval i k => IntervalMap i a -> k -> (IntervalMap i a, IntervalMap i a, IntervalMap i a) Source #
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) Source #
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 Source #
O(n+m). This function is defined as (
).isSubmapOf
= isSubmapOfBy
(==)
isSubmapOfBy :: Ord k => (a -> b -> Bool) -> IntervalMap k a -> IntervalMap k b -> Bool Source #
O(n+m).
The expression (
) returns isSubmapOfBy
f t1 t2True
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 Source #
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 Source #
O(n+m). Is this a proper submap? (ie. a submap but not equal).
The expression (
) returns isProperSubmapOfBy
f m1 m2True
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) Source #
O(log n). Returns the smallest key and its associated value.
Calls error
if the map is empty.
findMax :: IntervalMap k v -> (k, v) Source #
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) Source #
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) Source #
O(log n). Returns the smallest key and its associated value.
lookupMax :: IntervalMap k v -> Maybe (k, v) Source #
O(log n). Returns the largest key and its associated value.
lookupLast :: Interval k e => IntervalMap k v -> Maybe (k, v) Source #
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 Source #
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 Source #
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) Source #
O(log n). Delete and return the smallest key.
deleteFindMax :: (Interval k e, Ord k) => IntervalMap k v -> ((k, v), IntervalMap k v) Source #
O(log n). Delete and return the largest key.
updateMin :: (Interval k e, Ord k) => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v Source #
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 Source #
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 Source #
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 Source #
O(log n). Update or delete value at maximum key.
minView :: (Interval k e, 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 :: (Interval k e, 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 :: (Interval k e, Ord k) => IntervalMap k a -> Maybe ((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,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) 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 :: (Interval i k, Ord i) => IntervalMap i v -> Bool Source #
Check red-black-tree and interval search augmentation invariants. For testing/debugging only.
Testing
height :: IntervalMap k v -> Int Source #
The height of the tree. For testing/debugging only.