Module Utils.IndexSetSource

Module for sets of indices. This module provides a type-safe abstraction over the underlying IntSet implementation.

include SetSig.S1 with type 'a t = private IntSet.t and type 'a element = 'a Fix.Indexing.index
type 'a element = 'a Fix.Indexing.index
type 'a t = private IntSet.t
val empty : 'a t
val is_empty : 'a t -> bool
val is_not_empty : 'a t -> bool
val singleton : 'a element -> 'a t
val is_singleton : 'a t -> bool
val cardinal : 'a t -> int
val choose : 'a t -> 'a element
val minimum : 'a t -> 'a element option

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

val maximum : 'a t -> 'a element option

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

val mem : 'a element -> 'a t -> bool
val add : 'a element -> 'a t -> 'a t
val remove : 'a element -> 'a t -> 'a t
val union : 'a t -> 'a t -> 'a t
val inter : 'a t -> 'a t -> 'a t
val disjoint : 'a t -> 'a t -> bool
val iter : ('a element -> unit) -> 'a t -> unit
val iteri : (int -> 'a element -> unit) -> 'a t -> unit
val rev_iter : ('a element -> unit) -> 'a t -> unit
val fold : ('a element -> 'b -> 'b) -> 'a t -> 'b -> 'b
val fold_right : ('a -> 'b element -> 'a) -> 'a -> 'b t -> 'a

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.

val map : ('a element -> 'b element) -> 'a t -> 'b t

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

val exists : ('a element -> bool) -> 'a t -> bool

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

val for_all : ('a element -> bool) -> 'a t -> bool

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

val elements : 'a t -> 'a element list
val compare : 'a t -> 'a t -> int
val equal : 'a t -> 'a t -> bool
val subset : 'a t -> 'a t -> bool
val quick_subset : 'a t -> 'a t -> bool
val diff : 'a t -> 'a t -> 'a t

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

Decomposing sets

These functions implement the Refine.DECOMPOSABLE interface. We cannot reference it here as Refine is implemented using bitsets, that would create a reference cycle.

val compare_minimum : 'a t -> 'a t -> int

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.

val extract_unique_prefix : 'a t -> 'a t -> 'a t * 'a t

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.

val extract_shared_prefix : 'a t -> 'a t -> 'a t * ('a t * 'a t)

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
val sorted_union : 'a t list -> 'a t

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.

val of_list : 'a element list -> 'a t

of_list xs creates a set from a list of elements.

val init_interval : 'a element -> 'a element -> 'a t

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

val init_subset : 'a element -> 'a element -> ('a element -> bool) -> 'a t

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

val filter : ('a element -> bool) -> 'a t -> 'a t

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

val filter_map : ('a element -> 'b element option) -> 'a t -> 'b t

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

val split : 'a element -> 'a t -> 'a t * bool * 'a t

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
val find : ('a element -> bool) -> 'a t -> 'a element

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

val find_map : ('a element -> 'b option) -> 'a t -> 'b option

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.

val to_seq : 'a t -> 'a element Stdlib.Seq.t

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

val bind : 'a t -> ('a element -> 'b t) -> 'b t

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

val split_by_run : ('a element -> 'b element) -> 'a t -> ('b element * 'a t) list

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).

val fused_inter_union : 'a t -> 'a t -> acc:'a t -> 'a t

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.

val rev_map_elements : 'a t -> ('a element -> 'b) -> 'b list

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.

val map_to_array : 'a t -> ('a element -> 'b) -> 'b array

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

val rank : 'a element -> 'a t -> int

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

Sourceval lift_sum : 'a t -> ('a, _) Fix.Indexing.Sum.n t

lift_sum s lifts the index set s to a sum type. This is used when working with sum types in the type system.

  • parameter s

    The set to lift.

val unsafe_of_intset : IntSet.t -> 'a t

unsafe_of_intset s converts an IntSet.t to an index set of type 'a. This is unsafe as it changes the index type.

  • parameter s

    The IntSet to convert.

Sourceval all : 'a Fix.Indexing.cardinal -> 'a t

all n returns the set of all indices in the finite set of cardinal n.

Sourceval init_from_set : 'a Fix.Indexing.cardinal -> ('a Fix.Indexing.index -> bool) -> 'a t

init_from_set c f creates a set of indices from a cardinal c and a predicate f. The set contains all indices i in 0, c-1 such that f i returns true.

module Set : SetSig.StdSetS1 with type 'a t = private IntSetSet.t and type 'a elt = 'a t

Module for sets of index sets.

module Map : SetSig.StdMapS1 with type ('n, 'a) t = private 'a IntSetMap.t and type 'n key = 'n t

Module for maps from index sets to values.