Intervals with endpoints of type e. A minimal instance declaration for a closed interval needs only to define lowerBound and upperBound.

A set of intervals of type k.

Same as difference.

O(1). Is the set empty?

O(n). Number of keys in the set.

Caution: unlike size, this takes linear time!

O(log n). Does the set contain the given value? See also notMember.

O(log n). Does the set not contain the given value? See also member.

O(log n). Find the largest key smaller than the given one.

O(log n). Find the smallest key larger than the given one.

O(log n). Find the largest key equal to or smaller than the given one.

O(log n). Find the smallest key equal to or larger than the given one.

Return the set of all intervals containing the given point. This is the second element of the value of splitAt:

set `containing` p == let (_,s,_) = set `splitAt` p in s

O(n), since potentially all intervals could contain the point. O(log n) average case. This is also the worst case for sets containing no overlapping intervals.

Return the set of all intervals overlapping (intersecting) the given interval. This is the second element of the result of splitIntersecting:

set `intersecting` i == let (_,s,_) = set `splitIntersecting` i in s

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

Return 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) average case, if few keys are inside the interval.

O(1). The empty set.

O(1). A set with one entry.

O(log n). Insert a new value. If the set already contains an element equal to the value, it is replaced by the new value.

O(log n). Delete an element from the set. If the set does not contain the value, it is returned unchanged.

O(n+m). The expression (union t1 t2) takes the left-biased union of t1 and t2. It prefers t1 when duplicate elements are encountered.

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

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

O(n+m). Intersection of two sets. Return elements in the first set also existing in the second set.

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

The size of the result may be smaller if f maps two or more distinct elements to the same value.

O(n). mapMonotonic f s == map 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.

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

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

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.

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.

O(n log n). Build a new set by combining successive values.

O(n). Build a new set by combining successive values. Same as flattenWith, but works only when the combining functions returns strictly monotonic values.

O(n). List of all values in the set, in ascending order.

O(n). The list of all values in the set, in no particular order.

O(n log n). Build a set from a list of elements. See also fromAscList. If the list contains duplicate values, the last value is retained.

O(n). The list of all values contained in the set, in ascending order.

O(n). The list of all values in the set, in descending order.

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

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

O(n). Filter values satisfying a predicate.

O(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 split.

O(n). The expression (split 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.

O(n). The expression (splitMember k set) splits a set just like split but also returns member k set.

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

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.

O(n+m). Is the first set a subset of the second set? This is always true for equal sets.

O(n+m). Is the first set a proper subset of the second set? (i.e. a subset but not equal).

O(log n). Returns the minimal value in the set.

O(log n). Returns the maximal value in the set.

Returns the interval with the largest endpoint. If there is more than one interval with that endpoint, return the rightmost.

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

O(log n). Remove the smallest element from the set. Return the empty set if the set is empty.

O(log n). Remove the largest element from the set. Return the empty set if the set is empty.

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

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

O(log n). Retrieves the minimal element of the set, and the set stripped of that element, or Nothing if passed an empty set.

O(log n). Retrieves the maximal element of the set, and the set stripped of that element, or Nothing if passed an empty set.

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