package ptset

  1. Overview
  2. Docs
package ptset
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module PtsetSource

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.

Sourcetype t

sets implemented with little-endian Patricia trees

Sourcetype elt = int
Sourceval empty : t
Sourceval is_empty : t -> bool
Sourceval mem : elt -> t -> bool
Sourceval add : elt -> t -> t
Sourceval singleton : elt -> t
Sourceval remove : elt -> t -> t
Sourceval union : t -> t -> t
Sourceval inter : t -> t -> t
Sourceval diff : t -> t -> t
Sourceval compare : t -> t -> int
Sourceval equal : t -> t -> bool
Sourceval subset : t -> t -> bool
Sourceval iter : (elt -> unit) -> t -> unit
Sourceval fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
Sourceval for_all : (elt -> bool) -> t -> bool
Sourceval exists : (elt -> bool) -> t -> bool
Sourceval filter : (elt -> bool) -> t -> t
Sourceval cardinal : t -> int
Sourceval choose : t -> elt
Sourceval choose_opt : t -> elt option
Sourceval find : elt -> t -> elt
Sourceval find_opt : elt -> t -> elt option
Sourceval of_list : elt list -> t
Sourceval map : (elt -> elt) -> t -> t
Sourceval partition : (elt -> bool) -> t -> t * t
Sourceval 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.

Sourceval intersect : t -> t -> bool

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

Big-endian Patricia trees

Sourcemodule 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
Sourcemodule BigPos : sig ... end