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