!       !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ (c) Christoph Breitkopf 2011 BSD-stylechbreitkopf@gmail.com experimentalportableSafe# IntervalMap!Intervals with endpoints of type a. and $ 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. IntervalMap&Including lower bound, excluding upper IntervalMapClosed at both ends IntervalMapOpen at both ends IntervalMap&Excluding lower bound, including upper IntervalMapLike (, but considering the upper bound first. IntervalMapGet the lower bound. IntervalMapGet the upper bound. IntervalMapIs the interval empty?  IntervalMap*Does the interval include its lower bound?  IntervalMap*Does the interval include its upper bound?  IntervalMapDo the two intervals overlap?  IntervalMap6Does the first interval completely contain the second?  IntervalMapxInterval strictly before another? True if the upper bound of the first interval is below the lower bound of the second. IntervalMap8Interval strictly after another? Same as 'flip before'. IntervalMap(Does the interval contain a given point? IntervalMap*Is a point strictly less than lower bound? IntervalMap-Is a point strictly greater than upper bound? IntervalMap/If the intervals overlap combine them into one.   (c) Christoph Breitkopf 2014 BSD-stylechbreitkopf@gmail.com experimentalnon-portable (MPTC with FD)Safe=?@AC4  IntervalMap!Intervals with endpoints of type eN. A minimal instance declaration for a closed interval needs only to define  and . IntervalMap lower bound IntervalMap upper bound IntervalMapbDoes the interval include its lower bound? Default is True for all values, i.e. closed intervals. IntervalMaphDoes the interval include its upper bound bound? Default is True for all values, i.e. closed intervals. IntervalMapxInterval strictly before another? True if the upper bound of the first interval is below the lower bound of the second. IntervalMap8Interval strictly after another? Same as 'flip before'.  IntervalMap6Does the first interval completely contain the second?! IntervalMapDo the two intervals overlap?" IntervalMap*Is a point strictly less than lower bound?# IntervalMap-Is a point strictly greater than upper bound?$ IntervalMap(Does the interval contain a given point?% IntervalMapIs the interval empty?%! "$#&'(%! "$#&'( (c) Christoph Breitkopf 2014 BSD-stylechbreitkopf@gmail.com experimentalnon-portable (MPTC with FD)Safe=>?n* IntervalMapA map from intervals of type k to values of type v.+ IntervalMapO(log n)$. Lookup value for given key. Calls  if the key is not in the map.Use 6 or 7^ instead of this function, unless you are absolutely sure that the key is present in the map., IntervalMapSame as g.- IntervalMapO(1). The empty map.. IntervalMapO(1). A map with one entry./ IntervalMapO(1). Is the map empty?0 IntervalMapO(n). Number of keys in the map.Caution: unlike  C, which takes constant time, this is linear in the number of keys!1 IntervalMap3The height of the tree. For testing/debugging only.2 IntervalMapcThe maximum height of a red-black tree with the given number of nodes. For testing/debugging only.3 IntervalMapLTree statistics (size, height, maxHeight size). For testing/debugging only.4 IntervalMapO(log n)/. Does the map contain the given key? See also 5.5 IntervalMapO(log n)3. Does the map not contain the given key? See also 4.6 IntervalMapO(log n)8. Look up the given key in the map, returning the value (  value), or   if the key is not in the map.7 IntervalMapO(log n). The expression (7 def k map) returns the value at key k or returns default value def! when the key is not in the map.8 IntervalMapO(log n)V. Find the largest key smaller than the given one and return it along with its value.9 IntervalMapO(log n)V. Find the smallest key larger than the given one and return it along with its value.: IntervalMapO(log n)b. Find the largest key equal to or smaller than the given one and return it along with its value.; IntervalMapO(log n)V. Find the smallest key larger than the given one and return it along with its value.< IntervalMapkReturn the submap of key intervals containing the given point. This is the second element of the value of : 6m `containing` p == let (_,m',_) = m `splitAt` p in m'O(n)7, since potentially all keys could contain the point. O(log n)S average case. This is also the worst case for maps containing no overlapping keys.= IntervalMap~Return the submap of key intervals overlapping (intersecting) the given interval. This is the second element of the value of : Bm `intersecting` i == let (_,m',_) = m `splitIntersecting` i in m'O(n)<, since potentially all keys could intersect the interval. O(log n)2 average case, if few keys intersect the interval.> IntervalMapHReturn the submap of key intervals completely inside the given interval.O(n)<, since potentially all keys could be inside the interval. O(log n)3 average case, if few keys are inside the interval.? IntervalMapO(log n)k. Insert a new key/value pair. If the map already contains the key, its value is changed to the new value.@ IntervalMapO(log n)>. Insert with a function, combining new value and old value. @ 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).A IntervalMapO(log n)C. Insert with a function, combining key, new value and old value. A 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 A.B IntervalMapO(log n)+. Combine insert with old values retrieval.C IntervalMapO(log n)<. Returns the smallest key and its associated value. Calls  if the map is empty.D IntervalMapO(log n);. Returns the largest key and its associated value. Calls  if the map is empty.E IntervalMapO(log n)4. Returns the smallest key and its associated value.F IntervalMapO(log n)3. Returns the largest key and its associated value.G IntervalMapReturns 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)0, since all keys could have the same endpoint. O(log n) average case.H IntervalMapReturns 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)0, since all keys could have the same endpoint. O(log n) average case.I IntervalMapO(log n)Q. Remove the smallest key from the map. Return the empty map if the map is empty.J IntervalMapO(log n)P. Remove the largest key from the map. Return the empty map if the map is empty.K IntervalMapO(log n)%. Delete and return the smallest key.L IntervalMapO(log n)$. Delete and return the largest key.M IntervalMapO(log n)(. Update or delete value at minimum key.N IntervalMapO(log n)(. Update or delete value at maximum key.O IntervalMapO(log n)(. Update or delete value at minimum key.P IntervalMapO(log n)(. Update or delete value at maximum key.Q IntervalMapO(log n)_. Retrieves the minimal (key,value) pair of the map, and the map stripped of that element, or   if passed an empty map. minViewWithKey (fromList [([5,6],"a"), ([3,4],"b")]) == Just (([3,4],"b"), singleton [5,6] "a") minViewWithKey empty == NothingR IntervalMapO(log n)_. Retrieves the maximal (key,value) pair of the map, and the map stripped of that element, or   if passed an empty map.S IntervalMapO(log n)h. Retrieves the value associated with minimal key of the map, and the map stripped of that element, or   if passed an empty map.T IntervalMapO(log n)h. Retrieves the value associated with maximal key of the map, and the map stripped of that element, or   if passed an empty map.U IntervalMapO(n)[. Fold the values in the map using the given right-associative binary operator, such that U f z ==   f z . w.  IntervalMapO(n). A strict version of U. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.V IntervalMapO(n)Z. Fold the values in the map using the given left-associative binary operator, such that V f z ==   f z . w.  IntervalMapO(n). A strict version of V. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.W IntervalMapO(n)e. Fold the keys and values in the map using the given right-associative binary operator, such that W f z ==   (  f) z . m. IntervalMapO(n). A strict version of W. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.X IntervalMapO(n)d. Fold the keys and values in the map using the given left-associative binary operator, such that X f z ==   (\z' (kx, x) -> f z' kx x) z . m. IntervalMapO(n). A strict version of X. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.Y IntervalMap O(n log n):. Build a new map by combining successive key/value pairs.Z IntervalMapO(n)D. Build a new map by combining successive key/value pairs. Same as YU, but works only when the combining functions returns strictly monotonic key values.[ IntervalMapO(log n)\. Delete a key from the map. If the map does not contain the key, it is returned unchanged.\ IntervalMapO(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.] IntervalMapO(log n)k. Adjust a value at a specific key. When the key is not a member of the map, the original map is returned.^ IntervalMapO(log n). The expression (^ f k map) updates the value x at k (if it is in the map). If (f x) is  %, the element is deleted. If it is (  y ), the key k is bound to the new value y._ IntervalMapO(log n). The expression (_ f k map) updates the value x at k (if it is in the map). If (f k x) is  %, the element is deleted. If it is (  y ), the key k is bound to the new value y.` IntervalMapO(log n). Lookup and update. See also _u. The function returns changed value, if it is updated. Returns the original key value if the map entry is deleted.a IntervalMapO(log n). The expression (a f k map) alters the value x at k, or absence thereof. a7 can be used to insert, delete, or update a value in a Map. In short : 6 k (a f k m) = f (6 k m).b IntervalMapO(n+m). The expression (b t1 t2!) takes the left-biased union of t1 and t2. It prefers t1- when duplicate keys are encountered, i.e. (b == c ).c IntervalMapO(n+m)". Union with a combining function.d IntervalMapO(n+m)". Union with a combining function.e IntervalMap!The union of a list of maps: (e ==   b -).f IntervalMap=The union of a list of maps, with a combining operation: (f f ==   (c f) -).g IntervalMapO(n+m)\. Difference of two maps. Return elements of the first map not existing in the second map.h IntervalMapO(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  D, the element is discarded (proper set difference). If it returns (  y+), the element is updated with a new value y. i IntervalMapO(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  D, the element is discarded (proper set difference). If it returns (  y+), the element is updated with a new value y. j IntervalMapO(n+m)`. Intersection of two maps. Return data in the first map for the keys existing in both maps. (j m1 m2 == k  m1 m2).k IntervalMapO(n+m)). Intersection with a combining function.l IntervalMapO(n+m)). Intersection with a combining function.m IntervalMapO(n)S. The list of all key/value pairs contained in the map, in ascending order of keys.n IntervalMapO(n)O. The list of all key/value pairs contained in the map, in no particular order.o IntervalMapO(n)T. The list of all key/value pairs contained in the map, in descending order of keys.p IntervalMap O(n log n)7. Build a map from a list of key/value pairs. See also sf. If the list contains more than one value for the same key, the last value for the key is retained.q IntervalMap O(n log n)Q. Build a map from a list of key/value pairs with a combining function. See also t.r IntervalMap O(n log n)Q. Build a map from a list of key/value pairs with a combining function. See also t.s IntervalMapO(n)6. Build a map from an ascending list in linear time. :The precondition (input list is ascending) is not checked.t IntervalMapO(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.u IntervalMapO(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.v IntervalMapO(n)U. Build a map from an ascending list of elements with distinct keys in linear time.  The precondition is not checked.w IntervalMapO(n)B. List of all values in the map, in ascending order of their keys.x IntervalMapO(n)2. List of all keys in the map, in ascending order.y IntervalMapO(n). Set of the keys.z IntervalMapSame as m.{ IntervalMapO(n),. Map a function over all values in the map.| IntervalMapO(n),. Map a function over all values in the map.} IntervalMapO(n). The function }N threads an accumulating argument through the map in ascending order of keys.~ IntervalMapO(n). The function ~N threads an accumulating argument through the map in ascending order of keys. IntervalMapO(n). The function O threads an accumulating argument through the map in descending order of keys. IntervalMap O(n log n).  f s! is the map obtained by applying f to each key of s.)The size of the result may be smaller if fy maps two or more distinct keys to the same new key. In this case the value at the smallest of these keys is retained. IntervalMap O(n log n).  c f s! is the map obtained by applying f to each key of s.)The size of the result may be smaller if fr maps two or more distinct keys to the same new key. In this case the associated values will be combined using c. IntervalMapO(n).  f s ==  f s, but works only when f2 is strictly monotonic. That is, for any values x and y, if x < y then f x < f y.  The precondition is not checked. IntervalMapO(n)'. Filter values satisfying a predicate. IntervalMapO(n),. Filter keys/values satisfying a predicate. IntervalMapO(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 . IntervalMapO(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 . IntervalMapO(n). Map values and collect the   results. IntervalMapO(n)". Map keys/values and collect the   results. IntervalMapO(n). Map values and separate the  and  results. IntervalMapO(n)#. Map keys/values and separate the  and  results. IntervalMapO(n). The expression ( 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. IntervalMapO(n). The expression ( k map) splits a map just like  but also returns 6 k map. IntervalMapO(n). Split around a point. Splits the map into three submaps: intervals below the point, intervals containing the point, and intervals above the point. IntervalMapO(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. IntervalMapO(n+m). This function is defined as ( =  (==)). IntervalMapO(n+m). The expression ( f t1 t2 ) returns  if all keys in t1 are in tree t2, and f returns * when applied to their respective values. IntervalMapO(n+m)G. Is this a proper submap? (ie. a submap but not equal). Defined as ( =  (==)). IntervalMapO(n+m)J. Is this a proper submap? (ie. a submap but not equal). The expression ( f m1 m2 ) returns  when m1 and m2 are not equal, all keys in m1 are in m2 , and when f returns * when applied to their respective values. IntervalMap^Check red-black-tree and interval search augmentation invariants. For testing/debugging only.%! "$#&*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTU V WXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~+9 ,9 (c) Christoph Breitkopf 2014 BSD-stylechbreitkopf@gmail.com experimentalnon-portable (MPTC with FD)Safeu' IntervalMapO(1). A map with one entry. IntervalMapO(log n). The expression ( def k map) returns the value at key k or returns default value def! when the key is not in the map. ufindWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x' findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a' IntervalMapO(log n)k. Insert a new key/value pair. If the map already contains the key, its value is changed to the new value. IntervalMapO(log n)>. Insert with a function, combining new value and old value.  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). IntervalMapO(log n)C. Insert with a function, combining key, new value and old value.  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 . IntervalMapO(log n)+. Combine insert with old values retrieval. IntervalMapO(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. IntervalMapO(log n)k. Adjust a value at a specific key. When the key is not a member of the map, the original map is returned. IntervalMapO(log n)(. Update or delete value at minimum key. IntervalMapO(log n)(. Update or delete value at maximum key. IntervalMapO(log n)(. Update or delete value at minimum key. IntervalMapO(log n)(. Update or delete value at maximum key. IntervalMap O(n log n)7. Build a map from a list of key/value pairs. See also f. If the list contains more than one value for the same key, the last value for the key is retained. IntervalMap O(n log n)Q. Build a map from a list of key/value pairs with a combining function. See also . IntervalMap O(n log n)Q. Build a map from a list of key/value pairs with a combining function. See also . IntervalMapO(n)6. Build a map from an ascending list in linear time. :The precondition (input list is ascending) is not checked. IntervalMapO(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. IntervalMapO(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. IntervalMapO(n),. Map a function over all values in the map. IntervalMapO(n),. Map a function over all values in the map. IntervalMapO(n). The function N 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")]) IntervalMapO(n). The function N 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")]) IntervalMapO(n). The function O threads an accumulating argument through the map in descending order of keys. IntervalMapO(n). Map values and collect the   results. IntervalMapO(n)". Map keys/values and collect the   results. IntervalMapO(n). Map values and separate the  and  results. IntervalMapO(n)#. Map keys/values and separate the  and  results. IntervalMapO(log n). The expression ( f k map) alters the value x at k, or absence thereof. 7 can be used to insert, delete, or update a value in a Map. In short : 6 k ( f k m) = f (6 k m). IntervalMap O(n log n).  c f s! is the map obtained by applying f to each key of s.)The size of the result may be smaller if fr maps two or more distinct keys to the same new key. In this case the associated values will be combined using c. IntervalMapO(log n). The expression ( f k map) updates the value x at k (if it is in the map). If (f x) is  %, the element is deleted. If it is (  y ), the key k is bound to the new value y. IntervalMapO(log n). The expression ( f k map) updates the value x at k (if it is in the map). If (f k x) is  %, the element is deleted. If it is (  y ), the key k is bound to the new value y. IntervalMapO(log n). Lookup and update. See also u. The function returns changed value, if it is updated. Returns the original key value if the map entry is deleted. IntervalMapO(n+m)". Union with a combining function. IntervalMapO(n+m)". Union with a combining function. IntervalMap=The union of a list of maps, with a combining operation: ( f ==   ( f) -). IntervalMapO(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  D, the element is discarded (proper set difference). If it returns (  y+), the element is updated with a new value y.  IntervalMapO(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  D, the element is discarded (proper set difference). If it returns (  y+), the element is updated with a new value y.  IntervalMapO(n+m)). Intersection with a combining function. IntervalMapO(n+m)). Intersection with a combining function.x%! "$#&*+,-/012345689:;<=>CDEFGHIJKLQRSTUVWXYZ[begjmnovwxyzx%! "$#&*+,/045689:;<=>-[begjUVWXYZwxyznmovCDGEFHIJKLSTQR123(c) Christoph Breitkopf 2014 BSD-stylechbreitkopf@gmail.com experimentalnon-portable (MPTC with FD)Safe{xx%! "$#&*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~x%! "$#&*+,/0456789:;<=>-.?@AB[\]^_`abcdefghijkl{|}~UVWXYZwxyznpqrmostuvCDGEFHIJKLMNOPSTQR123(c) Christoph Breitkopf 2011 BSD-stylechbreitkopf@gmail.com experimentalportableSafe IntervalMapO(n)". Join overlapping intervals with . ]flattenWith (+) (fromList [([1,3],5), ([4,6],2), ([5,8],9)]) == mkMap [([1,3],5), ([4,8],11)]n+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWX[\]^_`abcdefghijklmnopqrstuvwxyz{|}~n+,/0456789:;<=>-.?@AB[\]^_`abcdefghijkl{|}~UVWXwxyznpqrmostuvCDGEFHIJKLMNOPSTQR123(c) Christoph Breitkopf 2011 BSD-stylechbreitkopf@gmail.com experimentalportableSafe< IntervalMapO(n)". Join overlapping intervals with . ]flattenWith (+) (fromList [([1,3],5), ([4,6],2), ([5,8],9)]) == mkMap [([1,3],5), ([4,8],11)]n+,-/012345689:;<=>CDEFGHIJKLQRSTUVWX[begjmnovwxyzn+,/045689:;<=>-[begjUVWXwxyznmovCDGEFHIJKLSTQR123(c) Christoph Breitkopf 2011 BSD-stylechbreitkopf@gmail.com experimentalportableSafe IntervalMap Deprecated. As of version 0.3, replaced by .O(log n) . Same as @^, but the combining function is applied strictly. This is often the most desirable behavior.!For example, to update a counter: insertWith' (+) k 1 m IntervalMap Deprecated. As of version 0.3, replaced by .O(log n) . Same as A2, but the combining function is applied strictly. IntervalMap Deprecated.! As of version 0.3, replaced by .O(log n). A strict version of B. IntervalMap Deprecated. As of version 0.5, replaced by U.O(n)s. Fold the values in the map using the given right-associative binary operator. This function is an equivalent of U( and is present for compatibility only. IntervalMap Deprecated. As of version 0.3, replaced by W.O(n)|. Fold the keys and values in the map using the given right-associative binary operator. This function is an equivalent of W( and is present for compatibility only.s+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWX[\]^_`abcdefghijklmnopqrstuvwxyz{|}~#(c) Christoph Breitkopf 2015 - 2017 BSD-stylechbreitkopf@gmail.com experimentalnon-portable (MPTC with FD)Safe=>? u9 IntervalMapA set of intervals of type k. IntervalMapThe Color of a tree node. IntervalMapSame as . IntervalMapO(1). The empty set. IntervalMapO(1). A set with one entry. IntervalMapO(1). Is the set empty? IntervalMapO(n). Number of keys in the set.Caution: unlike  , this takes linear time! IntervalMapO(log n)1. Does the set contain the given value? See also . IntervalMapO(log n)5. Does the set not contain the given value? See also . IntervalMapO(log n)2. Find the largest key smaller than the given one. IntervalMapO(log n)2. Find the smallest key larger than the given one. IntervalMapO(log n)>. Find the largest key equal to or smaller than the given one. IntervalMapO(log n)>. Find the smallest key equal to or larger than the given one. IntervalMaphReturn the set of all intervals containing the given point. This is the second element of the value of : 8set `containing` p == let (_,s,_) = set `splitAt` p in sO(n)<, since potentially all intervals could contain the point. O(log n)X average case. This is also the worst case for sets containing no overlapping intervals. IntervalMap|Return the set of all intervals overlapping (intersecting) the given interval. This is the second element of the result of : Dset `intersecting` i == let (_,s,_) = set `splitIntersecting` i in sO(n)>, since potentially all values could intersect the interval. O(log n)4 average case, if few values intersect the interval. IntervalMapOReturn the set of all intervals which are completely inside the given interval.O(n)>, since potentially all values could be inside the interval. O(log n)3 average case, if few keys are inside the interval. IntervalMapO(log n)r. Insert a new value. If the set already contains an element equal to the value, it is replaced by the new value. IntervalMapO(log n)'. Returns the minimal value in the set. IntervalMapO(log n)'. Returns the maximal value in the set. IntervalMap~Returns the interval with the largest endpoint. If there is more than one interval with that endpoint, return the rightmost.O(n)5, since all intervals could have the same endpoint. O(log n) average case. IntervalMapO(log n)U. Remove the smallest element from the set. Return the empty set if the set is empty. IntervalMapO(log n)T. Remove the largest element from the set. Return the empty set if the set is empty. IntervalMapO(log n)). Delete and return the smallest element. IntervalMapO(log n)(. Delete and return the largest element. IntervalMapO(log n)V. Retrieves the minimal element of the set, and the set stripped of that element, or   if passed an empty set. IntervalMapO(log n)V. Retrieves the maximal element of the set, and the set stripped of that element, or   if passed an empty set. IntervalMapO(n)[. Fold the values in the set using the given right-associative binary operator, such that  f z ==   f z . . IntervalMapO(n). A strict version of . Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value. IntervalMapO(n)Z. Fold the values in the set using the given left-associative binary operator, such that  f z ==   f z . . IntervalMapO(n). A strict version of . Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value. IntervalMapO(log n)c. Delete an element from the set. If the set does not contain the value, it is returned unchanged. IntervalMapO(n+m). The expression ( t1 t2!) takes the left-biased union of t1 and t2. It prefers t1) when duplicate elements are encountered. IntervalMap!The union of a list of sets: ( ==    ). IntervalMapO(n+m)[. Difference of two sets. Return elements of the first set not existing in the second set. IntervalMapO(n+m)^. Intersection of two sets. Return elements in the first set also existing in the second set. IntervalMapO(n)B. The list of all values contained in the set, in ascending order. IntervalMapO(n)<. The list of all values in the set, in no particular order. IntervalMapO(n)9. The list of all values in the set, in descending order. IntervalMap O(n log n)0. Build a set from a list of elements. See also E. If the list contains duplicate values, the last value is retained. IntervalMapO(n)6. Build a set from an ascending list in linear time. :The precondition (input list is ascending) is not checked. IntervalMapO(n)K. Build a set from an ascending list of distinct elements in linear time.  The precondition is not checked. IntervalMapO(n)4. List of all values in the set, in ascending order. IntervalMap O(n log n),. Map a function over all values in the set.)The size of the result may be smaller if f7 maps two or more distinct elements to the same value. IntervalMapO(n).  f s ==  f s, but works only when f2 is strictly monotonic. That is, for any values x and y, if x < y then f x < f y.  The precondition is not checked. IntervalMapO(n)'. Filter values satisfying a predicate. IntervalMapO(n). Partition the set according to a predicate. The first set contains all elements that satisfy the predicate, the second all elements that fail the predicate. See also . IntervalMapO(n). The expression ( k set ) is a pair  (set1,set2) where the elements in set1 are smaller than k and the elements in set2 larger than k. Any key equal to k is found in neither set1 nor set2. IntervalMapO(n). The expression ( k set) splits a set just like  but also returns  k set. IntervalMapO(n). Split around a point. Splits the set into three subsets: intervals below the point, intervals containing the point, and intervals above the point. IntervalMapO(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. IntervalMapO(n+m)S. Is the first set a subset of the second set? This is always true for equal sets. IntervalMapO(n+m)U. Is the first set a proper subset of the second set? (i.e. a subset but not equal). IntervalMap O(n log n)1. Build a new set by combining successive values. IntervalMapO(n);. Build a new set by combining successive values. Same as Q, but works only when the combining functions returns strictly monotonic values. IntervalMap3The height of the tree. For testing/debugging only.  IntervalMapcThe maximum height of a red-black tree with the given number of nodes. For testing/debugging only. IntervalMap^Check red-black-tree and interval search augmentation invariants. For testing/debugging only.F%! "$#&F%! "$#&9 ! !"#$%&'( !)*+, - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V  W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~  19ABCD\]OPQRpqrstu{|}~a^_`cdfhikl-Y-Y/012 67:;<=>?@AEFIKLMNUV [begjmnopsvw{YZ       34*IntervalMap-0.6.1.1-J9lbfuJrmiTBxdkIPgqIF1Data.IntervalMap.Interval!Data.IntervalMap.Generic.IntervalData.IntervalMap.Generic.StrictData.IntervalMap.Generic.LazyData.IntervalMap.LazyData.IntervalMap.StrictData.IntervalMapData.IntervalSetData.IntervalMap.Generic.BaseData.MapsizePreludefoldrfoldlData.SetInterval IntervalCOClosedInterval OpenInterval IntervalOCcompareByUpper lowerBound upperBoundisEmpty leftClosed rightClosedoverlapssubsumesbeforeafterinsidebelowabovecombine$fNFDataInterval$fFunctorInterval $fOrdInterval$fReadInterval$fShowInterval $fEqIntervalcompareUpperBounds genericEqualsgenericCompare$fIntervalIntervala IntervalMap!\\empty singletonnullheight maxHeight showStatsmember notMemberlookupfindWithDefaultlookupLTlookupGTlookupLElookupGE containing intersectingwithininsert insertWith insertWithKeyinsertLookupWithKeyfindMinfindMax lookupMin lookupMaxfindLast lookupLast deleteMin deleteMax deleteFindMin deleteFindMax updateMin updateMaxupdateMinWithKeyupdateMaxWithKeyminViewWithKeymaxViewWithKeyminViewmaxView foldrWithKey foldlWithKey flattenWithflattenWithMonotonicdeleteadjust adjustWithKeyupdate updateWithKeyupdateLookupWithKeyalterunion unionWith unionWithKeyunions unionsWith differencedifferenceWithdifferenceWithKey intersectionintersectionWithintersectionWithKey toAscListtoList toDescListfromList fromListWithfromListWithKey fromAscListfromAscListWithfromAscListWithKeyfromDistinctAscListelemskeyskeysSetassocsmap mapWithKeymapAccummapAccumWithKeymapAccumRWithKeymapKeys mapKeysWithmapKeysMonotonicfilter filterWithKey partitionpartitionWithKeymapMaybemapMaybeWithKey mapEithermapEitherWithKeysplit splitLookupsplitAtsplitIntersecting isSubmapOf isSubmapOfByisProperSubmapOfisProperSubmapOfByvalid insertWith'insertWithKey'insertLookupWithKey'fold foldWithKey IntervalSetNilNodefoldr'foldl' mapMonotonic splitMember isSubsetOfisProperSubsetOf$fShowIntervalSet$fReadIntervalSet$fNFDataIntervalSet$fFoldableIntervalSet$fMonoidIntervalSet$fSemigroupIntervalSet$fOrdIntervalSet$fEqIntervalSet $fEqColorbaseGHC.ReadReadGHC.ShowShowghc-prim GHC.ClassescompareGHC.Errerror GHC.MaybeJustNothing Data.Tupleuncurry foldrWithKey' foldlWithKey'GHC.Baseconst Data.EitherLeftRight GHC.TypesTrueColorRB turnBlackbalanceLbalanceR setMinValue setMaxValue