1 (* Copyright (C) 2009 Matthew Fluet.
2 * Copyright (C) 1999-2005 Henry Cejtin, Matthew Fluet, Suresh
3 * Jagannathan, and Stephen Weeks.
5 * MLton is released under a BSD-style license.
6 * See the file MLton-LICENSE for details.
9 functor BitVectorSet (Element : sig
16 structure Element = Element
21 val difference : t * t -> t
23 val equals : t * t -> bool
24 val fold : t * 'a * (int * 'a -> 'a) -> 'a
25 val intersect : t * t -> t
26 val singleton : int -> t
27 val union : t * t -> t
31 val binSize = wordSize
33 val equals : t * t -> bool = op =
35 fun singleton i = <<(0wx1, Word.fromInt i)
36 val difference = fn (b1, b2) => andb (b1, notb b2)
37 val intersect = fn (b1, b2) => andb (b1, b2)
38 val union = fn (b1, b2) => orb (b1, b2)
42 = if Int.< (i, wordSize)
44 val a = if andb (w, 0wx1) <> 0wx0
48 loop (>>(w, 0wx1), a, Int.+ (i, 1))
57 type index = int (* position in t *)
58 type slot = int (* position in bin *)
59 type pos = index * slot
61 val ltPos : pos * pos -> bool
62 = fn ((index1, slot1), (index2, slot2)) =>
63 index1 < index2 orelse
64 (index1 = index2 andalso slot1 < slot2)
66 val intToPos : int -> pos
67 = fn pos => (Int.quot (pos, Bin.binSize), Int.rem (pos, Bin.binSize))
68 val posToInt : pos -> int
69 = fn (index, slot) => index * Bin.binSize + slot
70 val slotToBin : slot -> bin = fn slot => Bin.singleton slot
72 val eltToPos = intToPos o Element.toInt
73 fun eltToPosBin x = let val pos as (index, slot) = eltToPos x
74 in (pos, slotToBin slot)
76 val posToElt = Element.fromInt o posToInt
78 val maxPos as (maxIndex,maxSlot) = intToPos (Element.size - 1)
80 val empty : t = Vector.new (maxIndex + 1, Bin.empty)
81 fun isEmpty (v : t) = Vector.forall (v, fn b => b = Bin.empty)
82 fun singleton x = let val ((index,_), bin) = eltToPosBin x
83 in Vector.tabulate (maxIndex + 1, fn i =>
88 fun contains (v, x) = let val ((index,_), bin) = eltToPosBin x
89 in Bin.intersect (bin, Vector.sub (v, index)) <> Bin.empty
91 fun add (v, x) = let val ((index, _), bin) = eltToPosBin x
92 in Vector.mapi (v, fn (i, b) =>
94 then Bin.union (bin, b)
97 fun remove (v, x) = let val ((index, _), bin) = eltToPosBin x
98 in Vector.mapi (v, fn (i, b) =>
100 then Bin.difference (b, bin)
103 fun difference (v1, v2)
104 = Vector.map2 (v1, v2, fn (b1, b2) => Bin.difference (b1, b2))
105 fun intersect (v1, v2)
106 = Vector.map2 (v1, v2, fn (b1, b2) => Bin.intersect (b1, b2))
108 = Vector.map2 (v1, v2, fn (b1, b2) => Bin.union (b1, b2))
109 fun unions ss = List.fold (ss, empty, union)
110 fun equals (v1, v2) = Vector.equals (v1, v2, Bin.equals)
111 fun isSubsetEq (v1, v2)
115 (v1, v2, true, fn (b1, b2, a) =>
116 if Bin.difference (b1, b2) = Bin.empty
119 fun isSubset (s1, s2) = isSubsetEq (s1, s2) andalso not (equals (s1, s2))
120 fun isSupersetEq (s1, s2) = isSubsetEq (s2, s1)
121 fun isSuperset (s1, s2) = isSubset (s2, s1)
123 fun areDisjoint (v1, v2)
127 (v1, v2, true, fn (b1, b2, a) =>
128 if Bin.intersect(b1, b2) = Bin.empty
135 (v, a, fn (i, b, a) =>
137 val check = if i < maxIndex
139 else fn s => s < maxSlot
141 Bin.fold (b, a, fn (s, a) => if check s
142 then f (posToElt (i, s), a)
145 fun foreach (s, f) = fold (s, (), fn (x, ()) => f x)
146 fun peekGen (s, no, f)
152 | SOME yes => escape yes)
154 fun exists (s, p) = peekGen (s,
156 fn x => if p x then SOME true else NONE)
157 fun forall (s, p) = not (exists (s, not o p))
159 fun subsetSize (s, p)
160 = fold (s, 0 : int, fn (x, a) => if p x then a + 1 else a)
161 fun size s = subsetSize (s, fn _ => true)
163 fun replace (s, f) = fold(s, empty, fn (x, s) =>
166 | SOME x' => add (s, x'))
167 fun map (s, f) = replace (s, fn x => SOME (f x))
168 fun subset (s, p) = replace (s, fn x => if p x then SOME x else NONE)
169 fun partition (s, p) = let val yes = subset (s, p)
170 in {yes = yes, no = difference (s, yes)}
173 fun fromList l = List.fold (l, empty, fn (x, s) => add (s, x))
174 fun toList s = fold (s, nil, op ::)
175 fun layout s = List.layout Element.layout (toList s)
178 val op - = difference
180 val op <= = isSubsetEq
181 val op > = isSuperset
182 val op >= = isSupersetEq
184 fun power _ = Error.unimplemented "BitVectorSet.power"
185 fun subsets _ = Error.unimplemented "BitVectorSet.subsets"