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