package ptset

You can search for identifiers within the package.

in-package search v0.2.0

ptset
- CHANGES
- README
- Library ptset
  - Ptset
    
    Big
    
    BigPos
- Sources
  - ptset
    
    ptset.ml

Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module `Ptset`Source

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

package ptset

Module PtsetSource

Module `Ptset`Source