1 (******************************************************************************)
2 (* SXSI : XPath evaluator *)
3 (* Kim Nguyen (Kim.Nguyen@nicta.com.au) *)
4 (* Copyright NICTA 2008 *)
5 (* Distributed under the terms of the LGPL (see LICENCE) *)
6 (******************************************************************************)
17 val is_empty : t -> bool
18 val is_any : t -> bool
19 val is_finite : t -> bool
20 val kind : t -> [ `Finite | `Cofinite ]
21 val singleton : elt -> t
22 val mem : elt -> t -> bool
23 val add : elt -> t -> t
24 val remove : elt -> t -> t
27 val diff : t -> t -> t
29 val compare : t -> t -> int
30 val subset : t -> t -> bool
31 val kind_split : t list -> t * t
32 val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
33 val for_all : (elt -> bool) -> t -> bool
34 val exists : (elt -> bool) -> t -> bool
35 val filter : (elt -> bool) -> t -> t
36 val partition : (elt -> bool) -> t -> t * t
37 val cardinal : t -> int
38 val elements : t -> elt list
39 val from_list : elt list -> t
42 val equal : t -> t -> bool
44 val positive : t -> set
45 val negative : t -> set
46 val inj_positive : set -> t
47 val inj_negative : set -> t
50 module Make (E : Ptset.S) : S with type elt = E.elt and type set = E.t =
54 type node = Finite of E.t | CoFinite of E.t
56 module Node = Hcons.Make(struct
60 (Finite(s1),Finite(s2))
61 | (CoFinite(s1),CoFinite(s2)) -> E.equal s1 s2
64 Finite (s) -> HASHINT2(PRIME2,E.hash s)
65 | CoFinite(s) -> HASHINT2(PRIME7,E.hash s)
68 let empty = Node.make (Finite E.empty)
69 let any = Node.make (CoFinite E.empty)
70 let finite x = Node.make (Finite x)
71 let cofinite x = Node.make (CoFinite x)
73 let is_empty = function
74 { Node.node = Finite s } when E.is_empty s -> true
78 { Node.node = CoFinite s } when E.is_empty s -> true
81 let is_finite t = match t.Node.node with
82 | Finite _ -> true | _ -> false
84 let kind t = match t.Node.node with
88 let mem x t = match t.Node.node with
89 | Finite s -> E.mem x s
90 | CoFinite s -> not (E.mem x s)
92 let singleton x = finite (E.singleton x)
93 let add e t = match t.Node.node with
94 | Finite s -> finite (E.add e s)
95 | CoFinite s -> cofinite (E.remove e s)
96 let remove e t = match t.Node.node with
97 | Finite s -> finite (E.remove e s)
98 | CoFinite s -> cofinite (E.add e s)
100 let cup s t = match (s.Node.node,t.Node.node) with
101 | Finite s, Finite t -> finite (E.union s t)
102 | CoFinite s, CoFinite t -> cofinite ( E.inter s t)
103 | Finite s, CoFinite t -> cofinite (E.diff t s)
104 | CoFinite s, Finite t-> cofinite (E.diff s t)
106 let cap s t = match (s.Node.node,t.Node.node) with
107 | Finite s, Finite t -> finite (E.inter s t)
108 | CoFinite s, CoFinite t -> cofinite (E.union s t)
109 | Finite s, CoFinite t -> finite (E.diff s t)
110 | CoFinite s, Finite t-> finite (E.diff t s)
112 let diff s t = match (s.Node.node,t.Node.node) with
113 | Finite s, Finite t -> finite (E.diff s t)
114 | Finite s, CoFinite t -> finite(E.inter s t)
115 | CoFinite s, Finite t -> cofinite(E.union t s)
116 | CoFinite s, CoFinite t -> finite (E.diff t s)
118 let neg t = match t.Node.node with
119 | Finite s -> cofinite s
120 | CoFinite s -> finite s
122 let compare s t = match (s.Node.node,t.Node.node) with
123 | Finite s , Finite t -> E.compare s t
124 | CoFinite s , CoFinite t -> E.compare t s
125 | Finite _, CoFinite _ -> -1
126 | CoFinite _, Finite _ -> 1
128 let subset s t = match (s.Node.node,t.Node.node) with
129 | Finite s , Finite t -> E.subset s t
130 | CoFinite s , CoFinite t -> E.subset t s
131 | Finite s, CoFinite t -> E.is_empty (E.inter s t)
132 | CoFinite _, Finite _ -> false
134 (* given a list l of type t list,
135 returns two sets (f,c) where :
136 - f is the union of all the finite sets of l
137 - c is the union of all the cofinite sets of l
138 - f and c are disjoint
139 Invariant : cup f c = List.fold_left cup empty l
141 We treat the CoFinite part explicitely :
146 let rec next_finite_cofinite facc cacc = function
147 | [] -> finite facc, cofinite (E.diff cacc facc)
148 | { Node.node = Finite s } ::r -> next_finite_cofinite (E.union s facc) cacc r
149 | { Node.node = CoFinite _ } ::r when E.is_empty cacc -> next_finite_cofinite facc cacc r
150 | { Node.node = CoFinite s } ::r -> next_finite_cofinite facc (E.inter cacc s) r
152 let rec first_cofinite facc = function
154 | { Node.node = Finite s } :: r-> first_cofinite (E.union s facc) r
155 | { Node.node = CoFinite s } :: r -> next_finite_cofinite facc s r
157 first_cofinite E.empty l
159 let fold f t a = match t.Node.node with
160 | Finite s -> E.fold f s a
161 | CoFinite _ -> raise InfiniteSet
163 let for_all f t = match t.Node.node with
164 | Finite s -> E.for_all f s
165 | CoFinite _ -> raise InfiniteSet
167 let exists f t = match t.Node.node with
168 | Finite s -> E.exists f s
169 | CoFinite _ -> raise InfiniteSet
171 let filter f t = match t.Node.node with
172 | Finite s -> finite (E.filter f s)
173 | CoFinite _ -> raise InfiniteSet
175 let partition f t = match t.Node.node with
176 | Finite s -> let a,b = E.partition f s in finite a,finite b
177 | CoFinite _ -> raise InfiniteSet
179 let cardinal t = match t.Node.node with
180 | Finite s -> E.cardinal s
181 | CoFinite _ -> raise InfiniteSet
183 let elements t = match t.Node.node with
184 | Finite s -> E.elements s
185 | CoFinite _ -> raise InfiniteSet
188 finite (List.fold_left (fun x a -> E.add a x ) E.empty l)
190 let choose t = match t.Node.node with
191 Finite s -> E.choose s
192 | _ -> raise InfiniteSet
196 let hash t = t.Node.key
198 let uid t = t.Node.id
202 match t.Node.node with
207 match t.Node.node with
211 let inj_positive t = finite t
212 let inj_negative t = cofinite t