(**************************************************************************) (* *) (* Copyright (C) Jean-Christophe Filliatre *) (* *) (* This software is free software; you can redistribute it and/or *) (* modify it under the terms of the GNU Library General Public *) (* License version 2.1, with the special exception on linking *) (* described in file LICENSE. *) (* *) (* This software is distributed in the hope that it will be useful, *) (* but WITHOUT ANY WARRANTY; without even the implied warranty of *) (* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *) (* *) (**************************************************************************) (*i $Id$ i*) (*s Sets of integers implemented as Patricia trees. The following signature is exactly [Set.S with type elt = int], with the same specifications. This is a purely functional data-structure. The performances are similar to those of the standard library's module [Set]. The representation is unique and thus structural comparison can be performed on Patricia trees. *) include Set.S with type elt = int (*s Warning: [min_elt] and [max_elt] are linear w.r.t. the size of the set. In other words, [min_elt t] is barely more efficient than [fold min t (choose t)]. *) (*s Additional functions not appearing in the signature [Set.S] from ocaml standard library. *) (* [intersect u v] determines if sets [u] and [v] have a non-empty intersection. *) val intersect : t -> t -> bool (*s Big-endian Patricia trees *) module Big : sig include Set.S with type elt = int val intersect : t -> t -> bool end (*s Big-endian Patricia trees with non-negative elements. 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 now O(log(N)) - [elements] returns a list with elements in ascending order *) module BigPos : sig include Set.S with type elt = int val intersect : t -> t -> bool end
This document was generated using caml2html