1(* Redblackmap -- applicative maps as Red-black trees *)
2signature Redblackmap =
3sig
4type ('key, 'a) dict
5
6exception NotFound
7
8val mkDict    : ('key * 'key -> order) -> ('key, 'a) dict
9val insert    : ('key, 'a) dict * 'key * 'a -> ('key, 'a) dict
10val find      : ('key, 'a) dict * 'key -> 'a
11val peek      : ('key, 'a) dict * 'key -> 'a option
12val remove    : ('key, 'a) dict * 'key -> ('key, 'a) dict * 'a
13val numItems  : ('key, 'a) dict -> int
14val listItems : ('key, 'a) dict -> ('key * 'a) list
15val app       : ('key * 'a -> unit) -> ('key,'a) dict -> unit
16val revapp    : ('key * 'a -> unit) -> ('key,'a) dict -> unit
17val foldr     : ('key * 'a * 'b -> 'b)-> 'b -> ('key,'a) dict -> 'b
18val foldl     : ('key * 'a * 'b -> 'b) -> 'b -> ('key,'a) dict -> 'b
19val map       : ('key * 'a -> 'b) -> ('key,'a) dict -> ('key, 'b) dict
20val transform : ('a -> 'b) -> ('key,'a) dict -> ('key, 'b) dict
21end
22
23(*
24   [('key, 'a) dict] is the type of applicative maps from domain type
25   'key to range type 'a, or equivalently, applicative dictionaries
26   with keys of type 'key and values of type 'a.  They are implemented
27   as Okasaki-style red-black trees.
28
29   [mkDict ordr] returns a new, empty map whose keys have ordering
30   ordr.
31
32   [insert(m, i, v)] extends (or modifies) map m to map i to v.
33
34   [find (m, k)] returns v if m maps k to v; otherwise raises NotFound.
35
36   [peek(m, k)] returns SOME v if m maps k to v; otherwise returns NONE.
37
38   [remove(m, k)] removes k from the domain of m and returns the
39   modified map and the element v corresponding to k.  Raises NotFound
40   if k is not in the domain of m.
41
42   [numItems m] returns the number of entries in m (that is, the size
43   of the domain of m).
44
45   [listItems m] returns a list of the entries (k, v) of keys k and
46   the corresponding values v in m, in order of increasing key values.
47
48   [app f m] applies function f to the entries (k, v) in m, in
49   increasing order of k (according to the ordering ordr used to
50   create the map or dictionary).
51
52   [revapp f m] applies function f to the entries (k, v) in m, in
53   decreasing order of k.
54
55   [foldl f e m] applies the folding function f to the entries (k, v)
56   in m, in increasing order of k.
57
58   [foldr f e m] applies the folding function f to the entries (k, v)
59   in m, in decreasing order of k.
60
61   [map f m] returns a new map whose entries have form (k, f(k,v)),
62   where (k, v) is an entry in m.
63
64   [transform f m] returns a new map whose entries have form (k, f v),
65   where (k, v) is an entry in m.
66*)
67