1 | (* Pasted from Pottier's PP compiler *) |
---|
2 | |
---|
3 | (** This module offers sets of elements where each element carries an |
---|
4 | integer priority. All operations execute in logarithmic time with |
---|
5 | respect to the number of elements in the set. *) |
---|
6 | |
---|
7 | module Make (X : Set.OrderedType) : sig |
---|
8 | |
---|
9 | (* This is the type of priority sets. *) |
---|
10 | |
---|
11 | type t |
---|
12 | |
---|
13 | (* [empty] is the empty set. *) |
---|
14 | |
---|
15 | val empty: t |
---|
16 | |
---|
17 | (* [add x p s] inserts element [x] with priority [p]. *) |
---|
18 | |
---|
19 | val add: X.t -> int -> t -> t |
---|
20 | |
---|
21 | (* [remove x s] removes element [x]. *) |
---|
22 | |
---|
23 | val remove: X.t -> t -> t |
---|
24 | |
---|
25 | (* [change x p s] changes the priority of element [x] to [p]. *) |
---|
26 | |
---|
27 | val change: X.t -> int -> t -> t |
---|
28 | |
---|
29 | (* [increment x d s] increases the priority of element [x] by [d]. *) |
---|
30 | |
---|
31 | val increment: X.t -> int -> t -> t |
---|
32 | |
---|
33 | (* [incrementifx x p s] increases the priority of element [x] by [d] |
---|
34 | if [x] is a member of the priority set. *) |
---|
35 | |
---|
36 | val incrementifx: X.t -> int -> t -> t |
---|
37 | |
---|
38 | (* [priority x s] looks up the priority of element [x]. *) |
---|
39 | |
---|
40 | val priority: X.t -> t -> int |
---|
41 | |
---|
42 | (* [lowest s] returns [Some (x, p)], where element [x] has minimum |
---|
43 | priority [p] among all elements of [s]. It returns [None] if [s] |
---|
44 | is empty. *) |
---|
45 | |
---|
46 | val lowest: t -> (X.t * int) option |
---|
47 | |
---|
48 | (* [fold f s accu] fold over the set [s]. Elements are presented |
---|
49 | to [f] in increasing order of priority. *) |
---|
50 | |
---|
51 | val fold: (X.t -> int -> 'a -> 'a) -> t -> 'a -> 'a |
---|
52 | |
---|
53 | end |
---|
54 | |
---|