DIET : Discrete Interval Encoding Trees
Sets of integers represented as ranges
This data structure is efficient for large sets of integers where many adjacent integers are all part of the set. This will have higher overhead for sets with lots of point elements, but will be much more efficient for sets containing mostly ranges.
val empty : tThe empty set
val is_empty : t -> boolTest whether a set is empty, returns true if the set is empty.
val mem : t -> int -> booltest whether a given int is a member of the set
add_range t lo hi adds the range of integers lo, hi (including both endpoints) to the given set, returning a new set
val intersects_range : t -> int -> int -> boolval singleton : int -> tReturn the singleton set containing only the given element
remove_range lo hi t removes a range of elements from the given set, returning a new set
Compute the union of two sets. This is the set whose elements are those elements in either input set.
Compute the intersection of two sets. This is the set whose elements are those in *both* of the input sets.
Compute the difference between two sets. This is the set of elements that are in the first but not in the second. Unlike union and inter, order matters here.
Create the complement of the given set - i.e. the set of all values not in the input set.
Compare two sets. It is not safe to use the polymorphic (<) and related functions to compare these sets, as the tree representation used can balance in multiple ways.
Test whether two sets are equal. It is not safe to use the polymorphic (=) on these sets, as the same set can have multiple representations depending on how it was built.
val iter : t -> f:(int -> unit) -> unititer f t calls f once for each element of t
val iter_range : t -> f:(int -> int -> unit) -> unititer_range ~f t calls f once for each contiguous range of t. The contiguous ranges of a set are sequences of adjacent integers all part of the set.
val fold : t -> init:'a -> f:(int -> 'a -> 'a) -> 'afold f t x0 returns the final result of merging each element of t into x0 using merge function f
val fold_range : t -> init:'a -> f:(int -> int -> 'a -> 'a) -> 'aAs fold, but operates on contiguous ranges
val for_all : t -> f:(int -> bool) -> boolTests whether a predicate applies to all elements of the set
val exists : t -> f:(int -> bool) -> boolTest whether some element of a set satisfies a predicate
Builds the subset of those elements that satisfy the predicate
partitions the input set into two sets with elements that satisfy the predicate and those that don't
val cardinal : t -> intReturns the number of elements in the set
val elements : t -> int listReturns a list of all elements in the set
val ranges : t -> (int * int) listReturns a list of all contiguous ranges in the set
val min_elt : t -> intReturns the minimum element in the set
val max_elt : t -> intReturns the maximum element in the set
val choose : t -> intReturns some element in the set
val to_stream : t -> (int * int) Stream.tEnumerates all contiguous ranges in the set
val of_stream : (int * int) Stream.t -> tval of_list : (int * int) list -> tBuild a ISet.t out of a list or enum of ranges