-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Maps from Intervals to values, with efficient search. -- -- A map from intervals to values, with efficient search for all keys -- containing a point or overlapping an interval. See the example code on -- the home page for a quick introduction. @package IntervalMap @version 0.2.2 -- | A conservative implementation of Intervals, mostly for use as keys in -- a Data.IntervalMap. -- -- This should really be a typeclass, so you could have a tuple be an -- instance of Interval, but that is currently not possible in standard -- Haskell. -- -- The contructor names of the half-open intervals seem somewhat clumsy, -- and I'm open to suggestions for better names. module Data.IntervalMap.Interval -- | 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. data Interval a -- | Including lower bound, excluding upper IntervalCO :: !a -> !a -> Interval a -- | Closed at both ends ClosedInterval :: !a -> !a -> Interval a -- | Open at both ends OpenInterval :: !a -> !a -> Interval a -- | Excluding lower bound, including upper IntervalOC :: !a -> !a -> Interval a -- | Get the lower bound. lowerBound :: Interval a -> a -- | Get the upper bound. upperBound :: Interval a -> a -- | Does the interval include its lower bound? leftClosed :: Interval a -> Bool -- | Does the interval include its upper bound? rightClosed :: Interval a -> Bool -- | Is the interval empty? isEmpty :: Ord a => Interval a -> Bool -- | Do the two intervals overlap? overlaps :: Ord a => Interval a -> Interval a -> Bool -- | Does the first interval completely contain the second? subsumes :: Ord a => Interval a -> Interval a -> Bool -- | Interval strictly before another? True if the upper bound of the first -- interval is below the lower bound of the second. before :: Ord a => Interval a -> Interval a -> Bool -- | Interval strictly after another? Same as 'flip before'. after :: Ord a => Interval a -> Interval a -> Bool -- | Like compare, but considering the upper bound first. compareByUpper :: Ord a => Interval a -> Interval a -> Ordering -- | Is a point strictly less than lower bound? below :: Ord a => a -> Interval a -> Bool -- | Does the interval contain a given point? inside :: Ord a => a -> Interval a -> Bool -- | Is a point strictly greater than upper bound? above :: Ord a => a -> Interval a -> Bool instance Eq a => Eq (Interval a) instance NFData a => NFData (Interval a) instance Functor Interval instance Ord a => Ord (Interval a) instance Read a => Read (Interval a) instance Show a => Show (Interval a) -- | 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. module Data.IntervalMap -- | 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. data Interval a -- | Including lower bound, excluding upper IntervalCO :: !a -> !a -> Interval a -- | Closed at both ends ClosedInterval :: !a -> !a -> Interval a -- | Open at both ends OpenInterval :: !a -> !a -> Interval a -- | Excluding lower bound, including upper IntervalOC :: !a -> !a -> Interval a -- | A map from intervals with endpoints of type k to values of -- type v. data IntervalMap k v -- | O(log n). Lookup value for given key. Calls error if the -- key is not in the map. (!) :: Ord k => IntervalMap k v -> Interval k -> v -- | Same as difference. (\\) :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a -- | O(1). Is the map empty? null :: IntervalMap k v -> Bool -- | O(n). Number of keys in the map. size :: IntervalMap k v -> Int -- | O(log n). Does the map contain the given key? See also -- notMember. member :: Ord k => Interval k -> IntervalMap k v -> Bool -- | O(log n). Does the map not contain the given key? See also -- member. notMember :: Ord k => Interval k -> IntervalMap k v -> Bool -- | 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. lookup :: Ord k => Interval k -> IntervalMap k v -> Maybe v -- | 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. -- -- 
--   findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
--   findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
--
findWithDefault :: Ord k => a -> Interval k -> IntervalMap k a -> a -- | 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. containing :: Ord k => IntervalMap k v -> k -> [(Interval k, v)] -- | 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. intersecting :: Ord k => IntervalMap k v -> Interval k -> [(Interval k, v)] -- | 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. within :: Ord k => IntervalMap k v -> Interval k -> [(Interval k, v)] -- | O(1). The empty map. empty :: IntervalMap k v -- | O(1). A map with one entry. singleton :: Interval 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. insert :: Ord k => Interval 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). insertWith :: Ord k => (v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k v -- | Same as insertWith, but the combining function is applied -- strictly. This is often the most desirable behavior. insertWith' :: Ord k => (v -> v -> v) -> Interval 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. insertWithKey :: Ord k => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k v -- | Same as insertWithKey, but the combining function is applied -- strictly. insertWithKey' :: Ord k => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> IntervalMap k v -- | 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) -- | O(log n). A strict version of insertLookupWithKey. insertLookupWithKey' :: Ord k => (Interval k -> v -> v -> v) -> Interval k -> v -> IntervalMap k v -> (Maybe 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. delete :: Ord k => Interval k -> IntervalMap k v -> IntervalMap k v -- | 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. adjust :: Ord k => (a -> a) -> Interval 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. adjustWithKey :: Ord k => (Interval k -> a -> a) -> Interval 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. update :: Ord k => (a -> Maybe a) -> Interval 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. updateWithKey :: Ord k => (Interval k -> a -> Maybe a) -> Interval k -> IntervalMap k 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. updateLookupWithKey :: Ord k => (Interval k -> a -> Maybe a) -> Interval k -> IntervalMap k a -> (Maybe 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). alter :: Ord k => (Maybe a -> Maybe a) -> Interval k -> 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). union :: Ord k => IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | O(n+m). Union with a combining function. unionWith :: Ord k => (a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | O(n+m). Union with a combining function. unionWithKey :: Ord k => (Interval k -> a -> a -> a) -> IntervalMap k a -> IntervalMap k a -> IntervalMap k a -- | The union of a list of maps: (unions == -- Prelude.foldl union empty). unions :: Ord k => [IntervalMap k a] -> IntervalMap k a -- | The union of a list of maps, with a combining operation: -- (unionsWith f == Prelude.foldl (unionWith -- f) empty). unionsWith :: Ord k => (a -> a -> a) -> [IntervalMap k a] -> IntervalMap k a -- | O(n+m). Difference of two maps. Return elements of the first -- map not existing in the second map. difference :: Ord k => 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. differenceWith :: 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 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. differenceWithKey :: Ord k => (Interval k -> a -> b -> Maybe a) -> 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). intersection :: Ord k => IntervalMap k a -> IntervalMap k b -> IntervalMap k a -- | O(n+m). Intersection with a combining function. intersectionWith :: Ord k => (a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c -- | O(n+m). Intersection with a combining function. intersectionWithKey :: Ord k => (Interval k -> a -> b -> c) -> IntervalMap k a -> IntervalMap k b -> IntervalMap k c -- | O(n). Map a function over all values in the map. map :: (a -> b) -> IntervalMap k a -> IntervalMap k b -- | O(n). Map a function over all values in the map. mapWithKey :: (Interval k -> a -> b) -> IntervalMap k a -> IntervalMap k b -- | 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")])
--
mapAccum :: (a -> 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. -- -- 
--   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")])
--
mapAccumWithKey :: (a -> Interval k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c) -- | O(n). The function mapAccumR threads an accumulating -- argument through the map in descending order of keys. mapAccumRWithKey :: (a -> Interval k -> b -> (a, c)) -> a -> IntervalMap k b -> (a, IntervalMap k c) -- | 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. mapKeys :: Ord k2 => (Interval k1 -> Interval 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. mapKeysWith :: Ord k2 => (a -> a -> a) -> (Interval k1 -> Interval k2) -> IntervalMap k1 a -> IntervalMap k2 a -- | O(n log 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. -- -- This function is currently identical to mapKeys, but will -- eventually be rewritten to have better better performance -- (O(n)). mapKeysMonotonic :: Ord k2 => (Interval k1 -> Interval k2) -> IntervalMap k1 a -> IntervalMap k2 a -- | O(n). Fold the values in the map using the given -- right-associative binary operator, such that foldr f z == -- Prelude.foldr f z . elems. foldr :: (a -> b -> 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 == -- Prelude.foldl f z . elems. foldl :: (b -> a -> b) -> b -> IntervalMap k a -> b -- | 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. foldrWithKey :: (Interval k -> v -> a -> 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 == Prelude.foldl (\z' (kx, x) -> f z' kx x) z . -- toAscList. foldlWithKey :: (a -> Interval k -> v -> a) -> a -> IntervalMap k v -> a -- | 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. foldl' :: (b -> a -> b) -> b -> IntervalMap k a -> b -- | 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. foldr' :: (a -> b -> b) -> b -> IntervalMap k a -> b -- | 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. foldrWithKey' :: (Interval k -> v -> a -> a) -> a -> IntervalMap k v -> a -- | 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. foldlWithKey' :: (a -> Interval k -> v -> a) -> a -> IntervalMap k v -> a -- | O(n). List of all values in the map, in ascending order of -- their keys. elems :: IntervalMap k v -> [v] -- | O(n). List of all keys in the map, in ascending order. keys :: IntervalMap k v -> [Interval k] -- | O(n). Set of the keys. keysSet :: Ord k => IntervalMap k v -> Set (Interval k) -- | Same as toAscList. assocs :: IntervalMap k v -> [(Interval k, v)] -- | O(n). The list of all key/value pairs contained in the map, in -- no particular order. toList :: IntervalMap k v -> [(Interval 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. fromList :: Ord k => [(Interval k, v)] -> IntervalMap k v -- | O(n log n). Build a map from a list of key/value pairs with a -- combining function. See also fromAscListWith. fromListWith :: Ord k => (a -> a -> a) -> [(Interval 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 :: Ord k => (Interval k -> a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a -- | O(n). The list of all key/value pairs contained in the map, in -- ascending order of keys. toAscList :: IntervalMap k v -> [(Interval k, v)] -- | O(n). The list of all key/value pairs contained in the map, in -- descending order of keys. toDescList :: IntervalMap k v -> [(Interval k, v)] -- | O(n). Build a map from an ascending list in linear time. The -- precondition (input list is ascending) is not checked. fromAscList :: Ord k => [(Interval k, v)] -> IntervalMap k v -- | 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. fromAscListWith :: Ord k => (a -> a -> a) -> [(Interval 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 :: Ord k => (Interval k -> a -> a -> a) -> [(Interval k, a)] -> IntervalMap k a -- | O(n). Build a map from an ascending list of elements with -- distinct keys in linear time. The precondition is not checked. fromDistinctAscList :: Ord k => [(Interval k, v)] -> IntervalMap k v -- | O(n). Filter values satisfying a predicate. filter :: Ord k => (a -> Bool) -> IntervalMap k a -> IntervalMap k a -- | O(n). Filter keys/values satisfying a predicate. filterWithKey :: Ord k => (Interval k -> a -> Bool) -> 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. partition :: Ord 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. partitionWithKey :: Ord k => (Interval k -> a -> Bool) -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a) -- | O(n). Map values and collect the Just results. mapMaybe :: Ord k => (a -> Maybe b) -> IntervalMap k a -> IntervalMap k b -- | O(n). Map keys/values and collect the Just results. mapMaybeWithKey :: Ord k => (Interval k -> a -> Maybe b) -> IntervalMap k a -> IntervalMap k b -- | O(n). Map values and separate the Left and Right -- results. mapEither :: Ord k => (a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c) -- | O(n). Map keys/values and separate the Left and -- Right results. mapEitherWithKey :: Ord k => (Interval k -> a -> Either b c) -> IntervalMap k a -> (IntervalMap k b, IntervalMap k c) -- | 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. split :: Ord k => Interval k -> IntervalMap k a -> (IntervalMap k a, IntervalMap k a) -- | O(n). The expression (splitLookup k map) splits -- a map just like split but also returns lookup k -- map. splitLookup :: Ord k => Interval k -> IntervalMap k a -> (IntervalMap k a, Maybe a, IntervalMap k a) -- | O(log n). Returns the smallest key and its associated value. -- Calls error if the map is empty. findMin :: IntervalMap k v -> (Interval k, v) -- | O(log n). Returns the largest key and its associated value. -- Calls error if the map is empty. findMax :: IntervalMap k v -> (Interval k, v) -- | 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. findLast :: Eq k => IntervalMap k v -> (Interval k, v) -- | O(log n). Remove the smallest key from the map. Return the -- empty map if the map is empty. deleteMin :: 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. deleteMax :: Ord k => IntervalMap k v -> IntervalMap k v -- | O(log n). Delete and return the smallest key. deleteFindMin :: Ord k => IntervalMap k v -> ((Interval k, v), IntervalMap k v) -- | O(log n). Delete and return the largest key. deleteFindMax :: Ord k => IntervalMap k v -> ((Interval k, v), IntervalMap k v) -- | O(log n). Update or delete value at minimum key. updateMin :: Ord k => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v -- | O(log n). Update or delete value at maximum key. updateMax :: Ord k => (v -> Maybe v) -> IntervalMap k v -> IntervalMap k v -- | O(log n). Update or delete value at minimum key. updateMinWithKey :: Ord k => (Interval k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v -- | O(log n). Update or delete value at maximum key. updateMaxWithKey :: Ord k => (Interval k -> v -> Maybe v) -> IntervalMap k v -> IntervalMap k v -- | Check red-black-tree and interval search augmentation invariants. valid :: Ord k => IntervalMap k v -> Bool -- | The height of the tree. For testing/debugging only. height :: IntervalMap k v -> Int -- | The maximum height of a red-black tree with the given number of nodes. maxHeight :: Int -> Int -- | Tree statistics (size, height, maxHeight size) showStats :: IntervalMap k a -> (Int, Int, Int) instance Eq Color instance Read Color instance Show Color instance (Show k, Show a) => Show (IntervalMap k a) instance (Ord k, Read k, Read e) => Read (IntervalMap k e) instance (NFData k, NFData a) => NFData (IntervalMap k a) instance Foldable (IntervalMap k) instance Traversable (IntervalMap k) instance Ord k => Monoid (IntervalMap k v) instance Functor (IntervalMap k) instance (Ord k, Ord v) => Ord (IntervalMap k v) instance (Eq k, Eq v) => Eq (IntervalMap k v)