ptset.mli

   1 (**************************************************************************)
   2 (*                                                                        *)
   3 (*  Copyright (C) Jean-Christophe Filliatre                               *)
   4 (*                                                                        *)
   5 (*  This software is free software; you can redistribute it and/or        *)
   6 (*  modify it under the terms of the GNU Library General Public           *)
   7 (*  License version 2.1, with the special exception on linking            *)
   8 (*  described in file LICENSE.                                            *)
   9 (*                                                                        *)
  10 (*  This software is distributed in the hope that it will be useful,      *)
  11 (*  but WITHOUT ANY WARRANTY; without even the implied warranty of        *)
  12 (*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                  *)
  13 (*                                                                        *)
  14 (**************************************************************************)
  15
  16 (*i $Id: ptset.mli,v 1.10 2008-07-21 14:53:06 filliatr Exp $ i*)
  17
  18 (*s Sets of integers implemented as Patricia trees.  The following
  19     signature is exactly [Set.S with type elt = int], with the same
  20     specifications. This is a purely functional data-structure. The
  21     performances are similar to those of the standard library's module
  22     [Set]. The representation is unique and thus structural comparison
  23     can be performed on Patricia trees. *)
  24
  25 type t
  26
  27 type elt = int
  28
  29 val empty : t
  30
  31 val is_empty : t -> bool
  32
  33 val mem : int -> t -> bool
  34
  35 val add : int -> t -> t
  36
  37 val singleton : int -> t
  38
  39 val remove : int -> t -> t
  40
  41 val union : t -> t -> t
  42
  43 val subset : t -> t -> bool
  44
  45 val inter : t -> t -> t
  46
  47 val diff : t -> t -> t
  48
  49 val equal : t -> t -> bool
  50
  51 val compare : t -> t -> int
  52
  53 val elements : t -> int list
  54
  55 val choose : t -> int
  56
  57 val cardinal : t -> int
  58
  59 val iter : (int -> unit) -> t -> unit
  60
  61 val fold : (int -> 'a -> 'a) -> t -> 'a -> 'a
  62
  63 val for_all : (int -> bool) -> t -> bool
  64
  65 val exists : (int -> bool) -> t -> bool
  66
  67 val filter : (int -> bool) -> t -> t
  68
  69 val partition : (int -> bool) -> t -> t * t
  70
  71 val split : int -> t -> t * bool * t
  72
  73 (*s Warning: [min_elt] and [max_elt] are linear w.r.t. the size of the
  74     set. In other words, [min_elt t] is barely more efficient than [fold
  75     min t (choose t)]. *)
  76
  77 val min_elt : t -> int
  78 val max_elt : t -> int
  79
  80 (*s Additional functions not appearing in the signature [Set.S] from ocaml
  81     standard library. *)
  82
  83 (* [intersect u v] determines if sets [u] and [v] have a non-empty
  84    intersection. *)
  85
  86 val intersect : t -> t -> bool
  87 val is_singleton : t -> bool
  88
  89 val hash : t -> int
  90
  91 val from_list : int list -> t
  92
  93 type int_vector
  94 val to_int_vector : t -> int_vector
  95