package ptset

You can search for identifiers within the package.

in-package search v0.2.0

ptset
- Ptset
  - Big
  - BigPos

Legend:
Library
Module
Module type
Parameter
Class
Class type

Sets of integers implemented as Patricia trees.

Following Chris Okasaki and Andrew Gill's paper "Fast Mergeable Integer Maps".

This is a purely applicative data structure implementing a large fragment of Set.S with type elt = int, with identical specifications and similar performances.

One advantage of Patricia trees is unicity of representation. Thus OCaml's structural comparison can be used on sets.

type t

sets implemented with little-endian Patricia trees

type elt = int

val empty : t

val is_empty : t -> bool

val mem : elt -> t -> bool

val add : elt -> t -> t

val singleton : elt -> t

val remove : elt -> t -> t

val union : t -> t -> t

val inter : t -> t -> t

val diff : t -> t -> t

val compare : t -> t -> int

val equal : t -> t -> bool

val subset : t -> t -> bool

val iter : (elt -> unit) -> t -> unit

val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a

val for_all : (elt -> bool) -> t -> bool

val exists : (elt -> bool) -> t -> bool

val filter : (elt -> bool) -> t -> t

val cardinal : t -> int

val choose : t -> elt

val choose_opt : t -> elt option

val find : elt -> t -> elt

val find_opt : elt -> t -> elt option

val of_list : elt list -> t

val map : (elt -> elt) -> t -> t

val partition : (elt -> bool) -> t -> t * t

val split : elt -> t -> t * bool * t

Notes:

Functions min_elt, max_elt, and elements are purposely not provided, as there is no efficient way to implement them. If needed, you can implement min_elt s with fold min s (choose s), and similarly for max_elt, but this has linear complexity.

Functions map and split are merely implemented using fold and add.

Additional functions not appearing in the signature Set.S from ocaml standard library.

val intersect : t -> t -> bool

intersect u v determines whether sets u and v have a non-empty intersection.

Big-endian Patricia trees

module Big : sig ... end

Big-endian Patricia trees with nonnegative elements only.

Changes:

add and singleton raise Invalid_arg if a negative element is given
mem is slightly faster (the Patricia tree is now a search tree)
min_elt and max_elt are provided (and efficient)
elements returns a list with elements in ascending order

module BigPos : sig ... end