1(* ========================================================================= *) 2(* FINITE MAPS WITH A FIXED KEY TYPE *) 3(* Copyright (c) 2004 Joe Hurd, distributed under the BSD License *) 4(* ========================================================================= *) 5 6signature KeyMap = 7sig 8 9(* ------------------------------------------------------------------------- *) 10(* A type of map keys. *) 11(* ------------------------------------------------------------------------- *) 12 13type key 14 15val compareKey : key * key -> order 16 17val equalKey : key -> key -> bool 18 19(* ------------------------------------------------------------------------- *) 20(* A type of finite maps. *) 21(* ------------------------------------------------------------------------- *) 22 23type 'a map 24 25(* ------------------------------------------------------------------------- *) 26(* Constructors. *) 27(* ------------------------------------------------------------------------- *) 28 29val new : unit -> 'a map 30 31val singleton : key * 'a -> 'a map 32 33(* ------------------------------------------------------------------------- *) 34(* Map size. *) 35(* ------------------------------------------------------------------------- *) 36 37val null : 'a map -> bool 38 39val size : 'a map -> int 40 41(* ------------------------------------------------------------------------- *) 42(* Querying. *) 43(* ------------------------------------------------------------------------- *) 44 45val peekKey : 'a map -> key -> (key * 'a) option 46 47val peek : 'a map -> key -> 'a option 48 49val get : 'a map -> key -> 'a (* raises Error *) 50 51val pick : 'a map -> key * 'a (* an arbitrary key/value pair *) 52 53val nth : 'a map -> int -> key * 'a (* in the range [0,size-1] *) 54 55val random : 'a map -> key * 'a 56 57(* ------------------------------------------------------------------------- *) 58(* Adding. *) 59(* ------------------------------------------------------------------------- *) 60 61val insert : 'a map -> key * 'a -> 'a map 62 63val insertList : 'a map -> (key * 'a) list -> 'a map 64 65(* ------------------------------------------------------------------------- *) 66(* Removing. *) 67(* ------------------------------------------------------------------------- *) 68 69val delete : 'a map -> key -> 'a map (* must be present *) 70 71val remove : 'a map -> key -> 'a map 72 73val deletePick : 'a map -> (key * 'a) * 'a map 74 75val deleteNth : 'a map -> int -> (key * 'a) * 'a map 76 77val deleteRandom : 'a map -> (key * 'a) * 'a map 78 79(* ------------------------------------------------------------------------- *) 80(* Joining (all join operations prefer keys in the second map). *) 81(* ------------------------------------------------------------------------- *) 82 83val merge : 84 {first : key * 'a -> 'c option, 85 second : key * 'b -> 'c option, 86 both : (key * 'a) * (key * 'b) -> 'c option} -> 87 'a map -> 'b map -> 'c map 88 89val union : 90 ((key * 'a) * (key * 'a) -> 'a option) -> 91 'a map -> 'a map -> 'a map 92 93val intersect : 94 ((key * 'a) * (key * 'b) -> 'c option) -> 95 'a map -> 'b map -> 'c map 96 97(* ------------------------------------------------------------------------- *) 98(* Set operations on the domain. *) 99(* ------------------------------------------------------------------------- *) 100 101val inDomain : key -> 'a map -> bool 102 103val unionDomain : 'a map -> 'a map -> 'a map 104 105val unionListDomain : 'a map list -> 'a map 106 107val intersectDomain : 'a map -> 'a map -> 'a map 108 109val intersectListDomain : 'a map list -> 'a map 110 111val differenceDomain : 'a map -> 'a map -> 'a map 112 113val symmetricDifferenceDomain : 'a map -> 'a map -> 'a map 114 115val equalDomain : 'a map -> 'a map -> bool 116 117val subsetDomain : 'a map -> 'a map -> bool 118 119val disjointDomain : 'a map -> 'a map -> bool 120 121(* ------------------------------------------------------------------------- *) 122(* Mapping and folding. *) 123(* ------------------------------------------------------------------------- *) 124 125val mapPartial : (key * 'a -> 'b option) -> 'a map -> 'b map 126 127val map : (key * 'a -> 'b) -> 'a map -> 'b map 128 129val app : (key * 'a -> unit) -> 'a map -> unit 130 131val transform : ('a -> 'b) -> 'a map -> 'b map 132 133val filter : (key * 'a -> bool) -> 'a map -> 'a map 134 135val partition : 136 (key * 'a -> bool) -> 'a map -> 'a map * 'a map 137 138val foldl : (key * 'a * 's -> 's) -> 's -> 'a map -> 's 139 140val foldr : (key * 'a * 's -> 's) -> 's -> 'a map -> 's 141 142(* ------------------------------------------------------------------------- *) 143(* Searching. *) 144(* ------------------------------------------------------------------------- *) 145 146val findl : (key * 'a -> bool) -> 'a map -> (key * 'a) option 147 148val findr : (key * 'a -> bool) -> 'a map -> (key * 'a) option 149 150val firstl : (key * 'a -> 'b option) -> 'a map -> 'b option 151 152val firstr : (key * 'a -> 'b option) -> 'a map -> 'b option 153 154val exists : (key * 'a -> bool) -> 'a map -> bool 155 156val all : (key * 'a -> bool) -> 'a map -> bool 157 158val count : (key * 'a -> bool) -> 'a map -> int 159 160(* ------------------------------------------------------------------------- *) 161(* Comparing. *) 162(* ------------------------------------------------------------------------- *) 163 164val compare : ('a * 'a -> order) -> 'a map * 'a map -> order 165 166val equal : ('a -> 'a -> bool) -> 'a map -> 'a map -> bool 167 168(* ------------------------------------------------------------------------- *) 169(* Converting to and from lists. *) 170(* ------------------------------------------------------------------------- *) 171 172val keys : 'a map -> key list 173 174val values : 'a map -> 'a list 175 176val toList : 'a map -> (key * 'a) list 177 178val fromList : (key * 'a) list -> 'a map 179 180(* ------------------------------------------------------------------------- *) 181(* Pretty-printing. *) 182(* ------------------------------------------------------------------------- *) 183 184val toString : 'a map -> string 185 186(* ------------------------------------------------------------------------- *) 187(* Iterators over maps. *) 188(* ------------------------------------------------------------------------- *) 189 190type 'a iterator 191 192val mkIterator : 'a map -> 'a iterator option 193 194val mkRevIterator : 'a map -> 'a iterator option 195 196val readIterator : 'a iterator -> key * 'a 197 198val advanceIterator : 'a iterator -> 'a iterator option 199 200end 201