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