Commit | Line | Data |
---|---|---|
182a2654 AC |
1 | (* ord-map-sig.sml |
2 | * | |
3 | * COPYRIGHT (c) 1996 by AT&T Research. See COPYRIGHT file for details. | |
4 | * | |
5 | * Abstract signature of an applicative-style finite maps (dictionaries) | |
6 | * structure over ordered monomorphic keys. | |
7 | *) | |
8 | ||
9 | signature ORD_MAP = | |
10 | sig | |
11 | ||
12 | structure Key : ORD_KEY | |
13 | ||
14 | type 'a map | |
15 | ||
16 | val empty : 'a map | |
17 | (* The empty map *) | |
18 | ||
19 | val isEmpty : 'a map -> bool | |
20 | (* Return true if and only if the map is empty *) | |
21 | ||
22 | val singleton : (Key.ord_key * 'a) -> 'a map | |
23 | (* return the specified singleton map *) | |
24 | ||
25 | val insert : 'a map * Key.ord_key * 'a -> 'a map | |
26 | val insert' : ((Key.ord_key * 'a) * 'a map) -> 'a map | |
27 | (* Insert an item. *) | |
28 | ||
29 | val find : 'a map * Key.ord_key -> 'a option | |
30 | (* Look for an item, return NONE if the item doesn't exist *) | |
31 | ||
32 | val inDomain : ('a map * Key.ord_key) -> bool | |
33 | (* return true, if the key is in the domain of the map *) | |
34 | ||
35 | val remove : 'a map * Key.ord_key -> 'a map * 'a | |
36 | (* Remove an item, returning new map and value removed. | |
37 | * Raises LibBase.NotFound if not found. | |
38 | *) | |
39 | ||
40 | val first : 'a map -> 'a option | |
41 | val firsti : 'a map -> (Key.ord_key * 'a) option | |
42 | (* return the first item in the map (or NONE if it is empty) *) | |
43 | ||
44 | val numItems : 'a map -> int | |
45 | (* Return the number of items in the map *) | |
46 | ||
47 | val listItems : 'a map -> 'a list | |
48 | val listItemsi : 'a map -> (Key.ord_key * 'a) list | |
49 | (* Return an ordered list of the items (and their keys) in the map. *) | |
50 | ||
51 | val listKeys : 'a map -> Key.ord_key list | |
52 | (* return an ordered list of the keys in the map. *) | |
53 | ||
54 | val collate : ('a * 'a -> order) -> ('a map * 'a map) -> order | |
55 | (* given an ordering on the map's range, return an ordering | |
56 | * on the map. | |
57 | *) | |
58 | ||
59 | val unionWith : ('a * 'a -> 'a) -> ('a map * 'a map) -> 'a map | |
60 | val unionWithi : (Key.ord_key * 'a * 'a -> 'a) -> ('a map * 'a map) -> 'a map | |
61 | (* return a map whose domain is the union of the domains of the two input | |
62 | * maps, using the supplied function to define the map on elements that | |
63 | * are in both domains. | |
64 | *) | |
65 | ||
66 | val intersectWith : ('a * 'b -> 'c) -> ('a map * 'b map) -> 'c map | |
67 | val intersectWithi : (Key.ord_key * 'a * 'b -> 'c) -> ('a map * 'b map) -> 'c map | |
68 | (* return a map whose domain is the intersection of the domains of the | |
69 | * two input maps, using the supplied function to define the range. | |
70 | *) | |
71 | ||
72 | val mergeWith : ('a option * 'b option -> 'c option) | |
73 | -> ('a map * 'b map) -> 'c map | |
74 | val mergeWithi : (Key.ord_key * 'a option * 'b option -> 'c option) | |
75 | -> ('a map * 'b map) -> 'c map | |
76 | (* merge two maps using the given function to control the merge. For | |
77 | * each key k in the union of the two maps domains, the function | |
78 | * is applied to the image of the key under the map. If the function | |
79 | * returns SOME y, then (k, y) is added to the resulting map. | |
80 | *) | |
81 | ||
82 | val app : ('a -> unit) -> 'a map -> unit | |
83 | val appi : ((Key.ord_key * 'a) -> unit) -> 'a map -> unit | |
84 | (* Apply a function to the entries of the map in map order. *) | |
85 | ||
86 | val map : ('a -> 'b) -> 'a map -> 'b map | |
87 | val mapi : (Key.ord_key * 'a -> 'b) -> 'a map -> 'b map | |
88 | (* Create a new map by applying a map function to the | |
89 | * name/value pairs in the map. | |
90 | *) | |
91 | ||
92 | val foldl : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b | |
93 | val foldli : (Key.ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b | |
94 | (* Apply a folding function to the entries of the map | |
95 | * in increasing map order. | |
96 | *) | |
97 | ||
98 | val foldr : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b | |
99 | val foldri : (Key.ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b | |
100 | (* Apply a folding function to the entries of the map | |
101 | * in decreasing map order. | |
102 | *) | |
103 | ||
104 | val filter : ('a -> bool) -> 'a map -> 'a map | |
105 | val filteri : (Key.ord_key * 'a -> bool) -> 'a map -> 'a map | |
106 | (* Filter out those elements of the map that do not satisfy the | |
107 | * predicate. The filtering is done in increasing map order. | |
108 | *) | |
109 | ||
110 | val mapPartial : ('a -> 'b option) -> 'a map -> 'b map | |
111 | val mapPartiali : (Key.ord_key * 'a -> 'b option) -> 'a map -> 'b map | |
112 | (* map a partial function over the elements of a map in increasing | |
113 | * map order. | |
114 | *) | |
115 | ||
116 | end (* ORD_MAP *) |