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