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 | |
---|