1(* Redblackmap -- applicative maps as Red-black trees *)
2signature Redblackmap =
3sig
4  type ('key, 'a) dict
5
6  exception NotFound
7
8  val mkDict     : ('key * 'key -> order) -> ('key, 'a) dict
9  val fromList   : ('key * 'key -> order) -> ('key * 'a) list -> ('key, 'a) dict
10  val update     : ('key, 'a) dict * 'key * ('a option -> 'a) -> ('key, 'a) dict
11  val insert     : ('key, 'a) dict * 'key * 'a -> ('key, 'a) dict
12  val insertList : ('key, 'a) dict * ('key * 'a) list -> ('key, 'a) dict
13  val findKey    : ('key, 'a) dict * 'key -> 'key * 'a
14  val find       : ('key, 'a) dict * 'key -> 'a
15  val peek       : ('key, 'a) dict * 'key -> 'a option
16  val remove     : ('key, 'a) dict * 'key -> ('key, 'a) dict * 'a
17  val numItems   : ('key, 'a) dict -> int
18  val listItems  : ('key, 'a) dict -> ('key * 'a) list
19  val isEmpty    : ('key, 'a) dict -> bool
20  val app        : ('key * 'a -> unit) -> ('key,'a) dict -> unit
21  val revapp     : ('key * 'a -> unit) -> ('key,'a) dict -> unit
22  val foldr      : ('key * 'a * 'b -> 'b)-> 'b -> ('key,'a) dict -> 'b
23  val foldl      : ('key * 'a * 'b -> 'b) -> 'b -> ('key,'a) dict -> 'b
24  val map        : ('key * 'a -> 'b) -> ('key,'a) dict -> ('key, 'b) dict
25  val transform  : ('a -> 'b) -> ('key,'a) dict -> ('key, 'b) dict
26end
27
28(*
29   [('key, 'a) dict] is the type of applicative maps from domain type
30   'key to range type 'a, or equivalently, applicative dictionaries
31   with keys of type 'key and values of type 'a.  They are implemented
32   as Okasaki-style red-black trees.
33
34   [mkDict ordr] returns a new, empty map whose keys have ordering
35   ordr.
36
37   [fromList ordr xs] returns a map that contains the (index, value)
38   pairs in xs, whose keys have ordering ordr.  It is equivalent to
39   insertList (mkDict ordr, xs).
40
41   [update(m, i, f)] extends m to map i to (f NONE) if i is not
42   already mapped, or to (f (SOME v)) if i is already mapped to v.
43
44   [insert(m, i, v)] extends (or modifies) map m to map i to v.
45
46   [insertList(m, xs)] extends (or modifies) map m with the (index,
47   value) pairs in xs.  (It is equivalent to foldl (fn ((i, v), m) =>
48   insert (m, i, v)) m xs.)  Note that later list entries will
49   overwrite earlier entries for the same index.
50
51   [findKey (m, k)] returns (k, v) if m maps k to v;
52   otherwise, raises NotFound. The returned key is the last one EQUAL in
53   the order to k that was used to extend or modify the map.
54
55   [find (m, k)] returns v if m maps k to v; otherwise raises NotFound.
56
57   [peek(m, k)] returns SOME v if m maps k to v; otherwise returns NONE.
58
59   [remove(m, k)] removes k from the domain of m and returns the
60   modified map and the element v corresponding to k.  Raises NotFound
61   if k is not in the domain of m.
62
63   [numItems m] returns the number of entries in m (that is, the size
64   of the domain of m).
65
66   [listItems m] returns a list of the entries (k, v) of keys k and
67   the corresponding values v in m, in order of increasing key values.
68
69   [isEmpty m] returns true if the map m is empty, and false otherwise.
70
71   [app f m] applies function f to the entries (k, v) in m, in
72   increasing order of k (according to the ordering ordr used to
73   create the map or dictionary).
74
75   [revapp f m] applies function f to the entries (k, v) in m, in
76   decreasing order of k.
77
78   [foldl f e m] applies the folding function f to the entries (k, v)
79   in m, in increasing order of k.
80
81   [foldr f e m] applies the folding function f to the entries (k, v)
82   in m, in decreasing order of k.
83
84   [map f m] returns a new map whose entries have form (k, f(k,v)),
85   where (k, v) is an entry in m.
86
87   [transform f m] returns a new map whose entries have form (k, f v),
88   where (k, v) is an entry in m.
89*)
90