1(* Intmap -- Applicative maps with integer keys                  *)
2(* From SML/NJ lib 0.2, copyright 1993 by AT&T Bell Laboratories *)
3(* Original implementation due to Stephen Adams, Southampton, UK *)
4
5signature Intmap =
6sig
7
8type 'a intmap
9
10exception NotFound
11
12val empty     : unit -> 'a intmap
13val insert    : 'a intmap * int * 'a -> 'a intmap
14val retrieve  : 'a intmap * int -> 'a
15val peek      : 'a intmap * int -> 'a option
16val remove    : 'a intmap * int -> 'a intmap * 'a
17val numItems  : 'a intmap ->  int
18val listItems : 'a intmap -> (int * 'a) list
19val app       : (int * 'a -> unit) -> 'a intmap -> unit
20val revapp    : (int * 'a -> unit) -> 'a intmap -> unit
21val foldr     : (int * 'a * 'b -> 'b) -> 'b -> 'a intmap -> 'b
22val foldl     : (int * 'a * 'b -> 'b) -> 'b -> 'a intmap -> 'b
23val map       : (int * 'a -> 'b) -> 'a intmap -> 'b intmap
24val transform : ('a -> 'b) -> 'a intmap -> 'b intmap
25
26end
27
28(*
29   ['a intmap] is the type of applicative maps from int to 'a.
30
31   [empty] creates a new empty map.
32
33   [insert(m, i, v)] extends (or modifies) map m to map i to v.
34
35   [retrieve(m, i)] returns v if m maps i to v; otherwise raises
36   NotFound.
37
38   [peek(m, i)] returns SOME v if m maps i to v; otherwise NONE.
39
40   [remove(m, i)] removes i from the domain of m and returns the
41   modified map and the element v corresponding to i.  Raises NotFound
42   if i is not in the domain of m.
43
44   [numItems m] returns the number of entries in m (that is, the size
45   of the domain of m).
46
47   [listItems m] returns a list of the entries (i, v) of integers i and
48   the corresponding values v in m, in increasing order of i.
49
50   [app f m] applies function f to the entries (i, v) in m, in
51   increasing order of i.
52
53   [revapp f m] applies function f to the entries (i, v) in m, in
54   decreasing order of i.
55
56   [foldl f e m] applies the folding function f to the entries (i, v)
57   in m, in increasing order of i.
58
59   [foldr f e m] applies the folding function f to the entries (i, v)
60   in m, in decreasing order of i.
61
62   [map f m] returns a new map whose entries have form (i, f(i,v)),
63   where (i, v) is an entry in m.
64
65   [transform f m] returns a new map whose entries have form (i, f(i,v)),
66   where (i, v) is an entry in m.
67*)
68