Module Utils.IntSetSource

minimum s returns Some x where x is the smallest element of s, or None if s is empty.

maximum s returns Some x where x is the largest element of s, or None if s is empty.

fold_right f acc x computes f acc x for each element x of s, in descending order. The initial value of acc is seed; the final value is the returned value.

map f s returns the set whose elements are f x for each x in s.

exists f s returns true if f x is true for at least one element x in s.

for_all f s returns true if f x is true for all elements x in s.

diff s1 s2 returns the set of elements that are in s1 but not in s2.

compare_minimum s1 s2 compares two sets by their least elements. Returns a negative number if the least element of s1 is smaller, a positive number if the least element of s2 is smaller, or zero if both sets are empty or have equal least elements.

extract_unique_prefix s1 s2 splits s1 into two sets:

• The first set contains elements strictly smaller than all elements of s2
• The second set contains the remaining elements of s1

Raises if s2 is empty.

extract_shared_prefix s1 s2 decomposes s1 and s2 into:

• A common prefix (elements present in both s1 and s2)
• The remaining parts of s1 and s2

Returns (common, (rest1, rest2)) where:

• common contains elements that are part of both s1 and s2
• s1 = common U rest1 and s2 = common U rest2

sorted_union s computes the union of an ordered list of sets. This is an optimized special case of union that assumes the list is already sorted by the set order.

of_list xs creates a set from a list of elements.

init_interval i j creates a set containing all integers from i to j. The behavior is undefined if i > j.

init_subset i j f creates a set containing all elements x such that i ≤ x ≤ j and f x returns true.

filter f s returns the set of elements x in s such that f x returns true.

filter_map f s returns the set of elements y such that f x = Some y for some element x in s.

split x s returns (s1, found, s2) where:

• s1 contains all elements strictly smaller than x
• s2 contains all elements strictly larger than x
• found is true if x is in s
• s = s1 U {x} U s2 if found is true

find f s returns the first element x in s such that f x is true. Raises Not_found if no such element exists.

find_map f s returns Some y where y is the first element such that f x = Some y for some x in s, or None if no such element exists.

to_seq s returns a sequence of all elements in s in ascending order.

bind m f returns the union of f x for all elements x in m.

Split a set into consecutive "runs" of elements that share the same class.

Parameters

• cls : 'a element → 'b element that assigns a class to each element.
• xs : 'a t – the input set to be split.

Returns A list of pairs. Each pair is made of a class (the result of cls for the run) and the subset of the original elements that belong to that run (preserving the original order).

fused_inter_union s1 s2 ~acc returns union (inter s1 s2) acc. This is an optimized version that computes the intersection and union in a single pass.

rev_map_elements s f returns a list of f x for all elements x in s, built from the highest to the lowest element.

map_to_array s f returns an array of f x for all elements x in s.

rank x s returns the number of elements strictly smaller than x in the set s.