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 *  Extended by two functions "update" and "findSome" - Martin Erwig
9 *)
10
11signature ORD_MAP_UPD =
12  sig
13
14    type 'a map
15
16    val empty : 'a map
17        (* The empty map *)
18
19    val insert : 'a map * int * 'a -> 'a map
20        (* Insert an item.  *)
21
22    val update : 'a map * int * ('a -> 'a) -> 'a map
23        (* Update an item by applying a function to the item already stored.
24     * Raises LibBase.NotFound if not found.
25     *)
26
27    val find : 'a map * int -> 'a option
28        (* Look for an item, return NONE if the item doesn't exist *)
29
30    val findSome : 'a map -> (int * 'a) option
31        (* Get an arbitrary item, return NONE if the map is empty *)
32
33    val remove : 'a map * int -> 'a map * 'a
34        (* Remove an item, returning new map and value removed.
35     * Raises LibBase.NotFound if not found.
36         *)
37
38    val numItems : 'a map ->  int
39        (* Return the number of items in the map *)
40
41    val listItems  : 'a map -> 'a list
42    val listItemsi : 'a map -> (int * 'a) list
43        (* Return an ordered list of the items (and their keys) in the map.
44     *)
45
46    val collate : ('a * 'a -> order) -> ('a map * 'a map) -> order
47        (* given an ordering on the map's range, return an ordering
48         * on the map.
49         *)
50
51    val unionWith  : ('a * 'a -> 'a) -> ('a map * 'a map) -> 'a map
52    val unionWithi : (int * 'a * 'a -> 'a) -> ('a map * 'a map) -> 'a map
53        (* return a map whose domain is the union of the domains of the two input
54         * maps, using the supplied function to define the map on elements that
55         * are in both domains.
56         *)
57
58    val intersectWith  : ('a * 'a -> 'b) -> ('a map * 'a map) -> 'b map
59    val intersectWithi : (int * 'a * 'a -> 'b) -> ('a map * 'a map) -> 'b map
60        (* return a map whose domain is the intersection of the domains of the
61         * two input maps, using the supplied function to define the range.
62         *)
63
64    val app  : ('a -> unit) -> 'a map -> unit
65    val appi : ((int * 'a) -> unit) -> 'a map -> unit
66        (* Apply a function to the entries of the map in map order. *)
67
68    val map  : ('a -> 'b) -> 'a map -> 'b map
69    val mapi : (int * 'a -> 'b) -> 'a map -> 'b map
70        (* Create a new map by applying a map function to the
71         * name/value pairs in the map.
72         *)
73
74    val foldl  : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
75    val foldli : (int * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b
76        (* Apply a folding function to the entries of the map
77         * in increasing map order.
78         *)
79
80    val foldr  : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
81    val foldri : (int * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b
82        (* Apply a folding function to the entries of the map
83         * in decreasing map order.
84         *)
85
86    val filter  : ('a -> bool) -> 'a map -> 'a map
87    val filteri : (int * 'a -> bool) -> 'a map -> 'a map
88        (* Filter out those elements of the map that do not satisfy the
89         * predicate.  The filtering is done in increasing map order.
90         *)
91
92    val mapPartial  : ('a -> 'b option) -> 'a map -> 'b map
93    val mapPartiali : (int * 'a -> 'b option) -> 'a map -> 'b map
94        (* map a partial function over the elements of a map in increasing
95         * map order.
96         *)
97
98  end (* ORD_MAP *)
99