Commit | Line | Data |
---|---|---|
34e49164 C |
1 | (*pad: taken from set.ml from stdlib ocaml, functor sux: module Make(Ord: OrderedType) = *) |
2 | (* with some addons such as from list *) | |
3 | (***********************************************************************) | |
4 | (* *) | |
5 | (* Objective Caml *) | |
6 | (* *) | |
7 | (* Xavier Leroy, projet Cristal, INRIA Rocquencourt *) | |
8 | (* *) | |
9 | (* Copyright 1996 Institut National de Recherche en Informatique et *) | |
10 | (* en Automatique. All rights reserved. This file is distributed *) | |
11 | (* under the terms of the GNU Library General Public License, with *) | |
12 | (* the special exception on linking described in file ../LICENSE. *) | |
13 | (* *) | |
14 | (***********************************************************************) | |
15 | ||
16 | (* set.mli 1.32 2004/04/23 10:01:54 xleroy Exp $ *) | |
17 | ||
18 | (** Sets over ordered types. | |
19 | ||
20 | This module implements the set data structure, given a total ordering | |
21 | function over the set elements. All operations over sets | |
22 | are purely applicative (no side-effects). | |
23 | The implementation uses balanced binary trees, and is therefore | |
24 | reasonably efficient: insertion and membership take time | |
ae4735db | 25 | logarithmic in the size of the set, for instance. |
34e49164 C |
26 | *) |
27 | (* pad: | |
ae4735db | 28 | module type OrderedType = |
34e49164 C |
29 | sig |
30 | type t | |
31 | (** The type of the set elements. *) | |
32 | val compare : t -> t -> int | |
33 | (** A total ordering function over the set elements. | |
34 | This is a two-argument function [f] such that | |
35 | [f e1 e2] is zero if the elements [e1] and [e2] are equal, | |
36 | [f e1 e2] is strictly negative if [e1] is smaller than [e2], | |
37 | and [f e1 e2] is strictly positive if [e1] is greater than [e2]. | |
38 | Example: a suitable ordering function is the generic structural | |
39 | comparison function {!Pervasives.compare}. *) | |
40 | end | |
41 | (** Input signature of the functor {!Set.Make}. *) | |
42 | *) | |
43 | (* | |
44 | module type S = | |
45 | sig | |
46 | *) | |
47 | (* type elt *) | |
48 | (** The type of the set elements. *) | |
49 | ||
50 | type 'elt t | |
51 | (** The type of sets. *) | |
52 | ||
53 | val empty: 'elt t | |
54 | (** The empty set. *) | |
55 | ||
56 | val is_empty: 'elt t -> bool | |
57 | (** Test whether a set is empty or not. *) | |
58 | ||
59 | val mem: 'elt -> 'elt t -> bool | |
60 | (** [mem x s] tests whether [x] belongs to the set [s]. *) | |
61 | ||
62 | val add: 'elt -> 'elt t -> 'elt t | |
63 | (** [add x s] returns a set containing all elements of [s], | |
64 | plus [x]. If [x] was already in [s], [s] is returned unchanged. *) | |
65 | ||
66 | val singleton: 'elt -> 'elt t | |
67 | (** [singleton x] returns the one-element set containing only [x]. *) | |
68 | ||
69 | val remove: 'elt -> 'elt t -> 'elt t | |
70 | (** [remove x s] returns a set containing all elements of [s], | |
71 | except [x]. If [x] was not in [s], [s] is returned unchanged. *) | |
72 | ||
73 | val union: 'elt t -> 'elt t -> 'elt t | |
74 | (** Set union. *) | |
75 | ||
76 | val inter: 'elt t -> 'elt t -> 'elt t | |
77 | (** Set intersection. *) | |
78 | ||
79 | (** Set difference. *) | |
80 | val diff: 'elt t -> 'elt t -> 'elt t | |
81 | ||
82 | val compare: 'elt t -> 'elt t -> int | |
83 | (** Total ordering between sets. Can be used as the ordering function | |
84 | for doing sets of sets. *) | |
85 | ||
86 | val equal: 'elt t -> 'elt t -> bool | |
87 | (** [equal s1 s2] tests whether the sets [s1] and [s2] are | |
88 | equal, that is, contain equal elements. *) | |
89 | ||
90 | val subset: 'elt t -> 'elt t -> bool | |
91 | (** [subset s1 s2] tests whether the set [s1] is a subset of | |
92 | the set [s2]. *) | |
93 | ||
94 | val iter: ('elt -> unit) -> 'elt t -> unit | |
95 | (** [iter f s] applies [f] in turn to all elements of [s]. | |
96 | The elements of [s] are presented to [f] in increasing order | |
97 | with respect to the ordering over the type of the elements. *) | |
98 | ||
99 | val fold: ('elt -> 'a -> 'a) -> 'elt t -> 'a -> 'a | |
100 | (** [fold f s a] computes [(f xN ... (f x2 (f x1 a))...)], | |
101 | where [x1 ... xN] are the elements of [s], in increasing order. *) | |
102 | ||
103 | val for_all: ('elt -> bool) -> 'elt t -> bool | |
104 | (** [for_all p s] checks if all elements of the set | |
105 | satisfy the predicate [p]. *) | |
106 | ||
107 | val exists: ('elt -> bool) -> 'elt t -> bool | |
108 | (** [exists p s] checks if at least one element of | |
109 | the set satisfies the predicate [p]. *) | |
ae4735db | 110 | |
34e49164 C |
111 | val filter: ('elt -> bool) -> 'elt t -> 'elt t |
112 | (** [filter p s] returns the set of all elements in [s] | |
113 | that satisfy predicate [p]. *) | |
114 | ||
115 | val partition: ('elt -> bool) -> 'elt t -> 'elt t * 'elt t | |
116 | (** [partition p s] returns a pair of sets [(s1, s2)], where | |
117 | [s1] is the set of all the elements of [s] that satisfy the | |
118 | predicate [p], and [s2] is the set of all the elements of | |
119 | [s] that do not satisfy [p]. *) | |
120 | ||
121 | val cardinal: 'elt t -> int | |
122 | (** Return the number of elements of a set. *) | |
123 | ||
124 | val elements: 'elt t -> 'elt list | |
125 | (** Return the list of all elements of the given set. | |
126 | The returned list is sorted in increasing order with respect | |
127 | to the ordering [Ord.compare], where [Ord] is the argument | |
128 | given to {!Set.Make}. *) | |
129 | ||
130 | val min_elt: 'elt t -> 'elt | |
131 | (** Return the smallest element of the given set | |
132 | (with respect to the [Ord.compare] ordering), or raise | |
133 | [Not_found] if the set is empty. *) | |
134 | ||
135 | val max_elt: 'elt t -> 'elt | |
136 | (** Same as {!Set.S.min_elt}, but returns the largest element of the | |
137 | given set. *) | |
138 | ||
139 | val choose: 'elt t -> 'elt | |
140 | (** Return one element of the given set, or raise [Not_found] if | |
141 | the set is empty. Which element is chosen is unspecified, | |
142 | but equal elements will be chosen for equal sets. *) | |
143 | ||
144 | val split: 'elt -> 'elt t -> 'elt t * bool * 'elt t | |
145 | (** [split x s] returns a triple [(l, present, r)], where | |
146 | [l] is the set of elements of [s] that are | |
147 | strictly less than [x]; | |
148 | [r] is the set of elements of [s] that are | |
149 | strictly greater than [x]; | |
150 | [present] is [false] if [s] contains no element equal to [x], | |
151 | or [true] if [s] contains an element equal to [x]. *) | |
152 | (* | |
153 | end | |
154 | (** Output signature of the functor {!Set.Make}. *) | |
155 | ||
156 | module Make (Ord : OrderedType) : S with type elt = Ord.t | |
157 | (** Functor building an implementation of the set structure | |
158 | given a totally ordered type. *) | |
159 | *) |