root/trunk/Library/Set.fss

Revision 4130, 18.3 KB (checked in by sukyoungryu, 3 months ago)

[disambiguator] Fixed handling getters and setters in ExprDisambiguator?. Fixed libraries and tests using getters.
Line 
1(*******************************************************************************
2    Copyright 2009 Sun Microsystems, Inc.,
3    4150 Network Circle, Santa Clara, California 95054, U.S.A.
4    All rights reserved.
5
6    U.S. Government Rights - Commercial software.
7    Government users are subject to the Sun Microsystems, Inc. standard
8    license agreement and applicable provisions of the FAR and its supplements.
9
10    Use is subject to license terms.
11
12    This distribution may include materials developed by third parties.
13
14    Sun, Sun Microsystems, the Sun logo and Java are trademarks or registered
15    trademarks of Sun Microsystems, Inc. in the U.S. and other countries.
16 ******************************************************************************)
17
18component Set
19import Containment.{...}
20import CovariantCollection.{...}
21import QuickSort.{...}
22export Set
23
24(** Thrown when taking big intersection of no sets. **)
25object EmptyIntersection extends UncheckedException end
26
27weight:ZZ32 = 4
28
29(** The natural order of the set, and indexing on the set, yields set
30    elements in ascending order. **)
31trait Set[\E extends StandardTotalOrder[\E\]\]
32        extends { ZeroIndexed[\E\], ContainmentGenerator[\E,Set[\E\]\] }
33        comprises {NodeSet[\E\], EmptySet[\E\]}
34    getter indexValuePairs():ZeroIndexed[\(ZZ32,E)\] =
35        IndexValueSetGenerator[\E\](self)
36    getter asDebugString():String = "Set: " || self.showTree()
37    seqgen[\R\](r: Reduction[\R\], body: E->R): R
38    ivgen[\R\](i0:ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R
39    seq(self): SequentialGenerator[\E\] = SeqSetGenerator[\E\](self)
40    getVal():E
41    getLeftChild():Set[\E\]
42    getRightChild():Set[\E\]
43    showTree():String
44    opr IN(x:E, self):Boolean
45    indexOf(x:E): Maybe[\ZZ32\] = self.indexOfI(0,x)
46    indexOfI(i:ZZ32, x:E): Maybe[\ZZ32\]
47    minimum():Maybe[\E\]
48    maximum():Maybe[\E\]
49    deleteMinimum():Set[\E\] =
50        if (_, res) <- extractMinimum() then res else self end
51    deleteMaximum():Set[\E\] =
52        if (_, res) <- extractMaximum() then res else self end
53    extractMinimum():Maybe[\(E, Set[\E\])\]
54    extractMaximum():Maybe[\(E, Set[\E\])\]
55    add(z:E):Set[\E\]
56    delete(z:E):Set[\E\]
57    balancedDelete(r:Set[\E\]):Set[\E\]
58    opr | self | : ZZ32
59    opr UNION(self,t2:Set[\E\]):Set[\E\]
60    opr INTERSECTION(self,t2:Set[\E\]):Set[\E\]
61    opr DIFFERENCE(self,t2:Set[\E\]):Set[\E\]
62    opr SYMDIFF(self,t2:Set[\E\]):Set[\E\]
63    concat(t2:Set[\E\]):Set[\E\]
64    (** Split at index x, meaning left result has size = x or
65        left result has size < x and right result is empty. **)
66    splitIndex(x:ZZ32):(Set[\E\],Set[\E\])
67    splitAt(x:E):(Set[\E\],Boolean,Set[\E\])
68    concat3(v:E, t2:Set[\E\]):Set[\E\]
69    opr SUBSET(self, other:Set[\E\]): Boolean = (self SETCMP other) = LessThan
70    opr SUBSETEQ(self, other:Set[\E\]): Boolean
71    opr SUPSET(self, other:Set[\E\]): Boolean = other SUBSET self
72    opr SUPSETEQ(self, other:Set[\E\]): Boolean = other SUBSETEQ self
73    opr =(self, other:Set[\E\]): Boolean
74    opr SETCMP(self, other:Set[\E\]): Comparison
75end
76
77singleton[\E\](x:E): Set[\E\] = do
78    e = EmptySet[\E\]
79    NodeSet[\E\](x,e,e)
80end
81
82set[\E extends StandardTotalOrder[\E\]\](): Set[\E\] = EmptySet[\E\]
83set[\E extends StandardTotalOrder[\E\], T extends E\](g: Generator[\T\]): Set[\E\] =
84    g.generate[\Set[\E\]\](Union[\E\], singleton[\E\])
85set[\E extends StandardTotalOrder[\E\], T extends E\](g: ReadableArray[\T,ZZ32\]): Set[\E\] = do
86    a = array[\E\](|g|)
87    a.init0(i,g.get(i)), i <- a.indices
88    fromCopiedArray(a)
89  end
90
91fromCopiedArray[\E extends StandardTotalOrder[\E\], T extends E\](a: Array[\T,ZZ32\]): Set[\E\] = do
92    quicksort[\T\](a)
93    j : ZZ32 := 1
94    for i <- seq(a.indices), i > 0, a[i-1]=/=a[i] do
95        a[j] := a[i]
96        j += 1
97    end
98    fromSortedArrayFragment[\E,T\](a,0,(j MIN |a|) - 1)
99  end
100
101fromSortedArrayFragment[\E extends StandardTotalOrder[\E\], T extends E\]
102                       (a: Array[\T,ZZ32\], lo:ZZ32, hi:ZZ32): Set[\E\] =
103    if hi < lo then
104        EmptySet[\E\]
105    else
106        mid = (hi+lo) DIV 2
107        (l,r) = (fromSortedArrayFragment[\E,T\](a,lo,mid-1),
108                 fromSortedArrayFragment[\E,T\](a,mid+1,hi))
109        NodeSet[\E\](a[mid],l,r)
110    end
111
112opr {[\E extends StandardTotalOrder[\E\]\] es: E... }: Set[\E\] =
113    es.generate[\Set[\E\]\](Union[\E\], fn (e:E): Set[\E\] => singleton[\E\](e))
114
115opr BIG {[\T extends StandardTotalOrder[\T\]\]} : Comprehension[\T,Set[\T\],AnyCovColl,AnyCovColl\] =
116    covariantCompr[\T,Set[\T\]\](fn cc => fromCopiedArray(cc.toArray()))
117
118opr BIG {[\T extends StandardTotalOrder[\T\]\] g:Generator[\T\]}:Set[\T\] =
119    __bigOperatorSugar[\T,Set[\T\],AnyCovColl,AnyCovColl\](BIG {[\T\]}(), g)
120
121opr BIG UNION[\R extends StandardTotalOrder[\R\]\](): BigReduction[\Set[\R\],Set[\R\]\] =
122    BigReduction[\Set[\R\],Set[\R\]\](Union[\R\])
123
124opr BIG UNION[\R extends StandardTotalOrder[\R\]\](g: Generator[\Set[\R\]\]):Set[\R\] =
125    __bigOperatorSugar[\Set[\R\],Set[\R\],Set[\R\],Set[\R\]\](BIG UNION[\R\](), g)
126
127object Union[\E extends StandardTotalOrder[\E\]\] extends CommutativeMonoidReduction[\Set[\E\]\]
128    getter asString(): String = "Union reduction"
129    empty():Set[\E\] = EmptySet[\E\]
130    join(a:Set[\E\], b:Set[\E\]): Set[\E\] = a UNION b
131end
132
133opr BIG INTERSECTION[\R extends StandardTotalOrder[\R\]\]():
134        BigReduction[\Set[\R\],AnyMaybe\] =
135    BigReduction[\Set[\R\],AnyMaybe\](Intersection[\R\])
136
137opr BIG INTERSECTION[\R extends StandardTotalOrder[\R\]\](g: Generator[\Set[\R\]\]):Set[\R\] =
138    __bigOperatorSugar[\Set[\R\],Set[\R\],Set[\R\],AnyMaybe\](BIG INTERSECTION[\R\](), g)
139
140object Intersection[\E extends StandardTotalOrder[\E\]\]
141        extends { CommutativeReduction[\Set[\E\]\],
142                  ReductionWithZeroes[\Set[\E\],Maybe[\Set[\E\]\]\] }
143    getter asString(): String = "Intersection reduction"
144    simpleJoin(a:Set[\E\], b:Set[\E\]):Set[\E\] = a INTERSECTION b
145    isZero(s:Set[\E\]): Boolean = s.isEmpty
146end
147
148value object SeqSetGenerator[\E extends StandardTotalOrder[\E\]\](s: Set[\E\])
149       extends SequentialGenerator[\E\]
150    getter size(): ZZ32 = |s|
151    getter isEmpty(): Boolean = s.isEmpty
152    opr |self| : ZZ32 = |s|
153    generate[\R\](r: Reduction[\R\], body: E->R): R =
154        s.seqgen[\R\](r,body)
155end
156
157value object IndexValueSetGenerator[\E extends StandardTotalOrder[\E\]\](s: Set[\E\])
158        extends ZeroIndexed[\(ZZ32,E)\]
159    getter size(): ZZ32 = |s|
160    getter indices(): Generator[\ZZ32\] = s.indices()
161    getter isEmpty(): Boolean = s.isEmpty
162    opr |self| : ZZ32 = |s|
163    generate[\R\](r: Reduction[\R\], body: (ZZ32,E)->R): R =
164       s.ivgen[\R\](0,r,body)
165    opr[ x: ZZ32 ]: (ZZ32,E) = (x,s[x])
166    opr[ r: Range[\ZZ32\] ]: ZeroIndexed[\(ZZ32,E)\] = s[r].indexValuePairs
167    indexOf(i:ZZ32,v:E): Maybe[\ZZ32\] = if s[i]=v then Just[\ZZ32\](i) else Nothing[\ZZ32\] end
168end
169
170object EmptySet[\E extends StandardTotalOrder[\E\]\] extends Set[\E\]
171    getter size():ZZ32 = 0
172    getter bounds():CompactFullRange[\ZZ32\] = 0#0
173    getter isEmpty():Boolean = true
174    getter asString(): String = "{}"
175    opr |self| : ZZ32 = 0
176    opr[i:ZZ32]:E = fail("Empty set: cannot use subscript operator.")
177    opr[r:Range[\ZZ32\]] : Set[\E\] = do
178        rr = self.bounds.narrowToRange(r)
179        self
180    end
181    indexOfI(_:ZZ32, e:E):Maybe[\ZZ32\] = Nothing[\ZZ32\]
182    generate[\R\](r: Reduction[\R\], body: E->R): R = r.empty()
183    ivgen[\R\](i0: ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R = r.empty()
184    seqgen[\R\](r: Reduction[\R\], body: E->R): R = r.empty()
185    getVal():E = fail("Empty set: cannot getVal()")
186    getLeftChild():Set[\E\] = self
187    getRightChild():Set[\E\] = self
188    showTree():String = "ε"
189    opr IN(x:E, self):Boolean = false
190    minimum():Nothing[\E\] = Nothing[\E\]
191    extractMinimum():Nothing[\(E, Set[\E\])\] = Nothing[\(E, Set[\E\])\]
192    maximum():Nothing[\E\] = Nothing[\E\]
193    extractMaximum():Nothing[\(E, Set[\E\])\] = Nothing[\(E, Set[\E\])\]
194    add(z:E):Set[\E\] = NodeSet[\E\](z,self,self)
195    delete(z:E):Set[\E\] = self
196    balancedAdd(val:E,  left:Set[\E\], right:Set[\E\]):NodeSet[\E\] = NodeSet[\E\](val,self,self)
197    balancedDelete(r:Set[\E\]):Set[\E\] = r
198    opr UNION(self, t2:Set[\E\]):Set[\E\] = t2
199    opr INTERSECTION(self,t2:Set[\E\]):Set[\E\] = self
200    opr DIFFERENCE(self,t2:Set[\E\]):Set[\E\] = self
201    opr SYMDIFF(self,t2:Set[\E\]):Set[\E\] = t2
202    concat(t2:Set[\E\]):Set[\E\] = t2
203    splitAt(x:E):(Set[\E\],Boolean,Set[\E\]) = (self, false, self)
204    splitIndex(x:ZZ32):(Set[\E\],Set[\E\]) = (self,self)
205    concat3(v:E, t2:Set[\E\]):Set[\E\] = t2.add(v)
206    opr =(self, other:Set[\E\]): Boolean = other.isEmpty
207    opr SUBSETEQ(self, other:Set[\E\]): Boolean = true
208    opr SUBSET(self, other:Set[\E\]): Boolean = NOT (other.isEmpty)
209    opr SETCMP(self, other:Set[\E\]): Comparison =
210        if other.isEmpty then EqualTo else LessThan end
211end
212
213object NodeSet[\E extends StandardTotalOrder[\E\]\](val:E,  left:Set[\E\], right:Set[\E\])
214        extends Set[\E\]
215    sz:ZZ32 = 1 + |left| + |right|
216    getter size():ZZ32 = sz
217    getter isEmpty():Boolean = false
218    getter asString():String = "{" || ",".join[\E\](self) || "}"
219    opr |self| : ZZ32 = sz
220    subscript(i:ZZ32):E = if i < |left| then left.subscript(i)
221       elif i = |left| then val
222       else right.subscript(i - |left| - 1) end
223    opr[i:ZZ32]:E = if 0 <= i < sz then subscript(i)
224                    else fail(self "[" i "] is out of bounds.") end
225    opr[r:Range[\ZZ32\]] : Set[\E\] = do
226        r' = self.bounds.narrowToRange(r)
227        (lside,rside) = splitIndex( r'.lower )
228        (lside',rside') = rside.splitIndex( |r'| )
229        lside'
230      end
231    indexOfI(i:ZZ32, e:E): Maybe[\ZZ32\] =
232        typecase _ = e CMP val of
233            LessThan => left.indexOfI(i,e)
234            EqualTo => Just[\ZZ32\](i + |left|)
235            GreaterThan => right.indexOfI(i + |left| + 1,e)
236        end
237    generate[\R\](r: Reduction[\R\], body: E->R): R =
238       r.join(r.join(left.generate[\R\](r,body),body(val)),
239              right.generate[\R\](r,body))
240    ivgen[\R\](i0:ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R = do
241        mi = |left| + i0
242        r.join(r.join(left.ivgen[\R\](i0,r,body),body(mi,val)),
243               right.ivgen[\R\](mi+1,r,body))
244      end
245    seqgen[\R\](r: Reduction[\R\], body: E->R): R = do
246        lg = left.seqgen[\R\](r,body)
247        vg = body(val)
248        mg = r.join(lg,vg)
249        rg = right.seqgen[\R\](r,body)
250        r.join(mg,rg)
251      end
252    getVal():E = val
253    getLeftChild():Set[\E\] = left
254    getRightChild():Set[\E\] = right
255
256    showTree():String =
257       "(" left.showTree() " " val " " right.showTree() ")"
258
259    opr IN(z:E, self):Boolean =
260        typecase _ = z CMP val of
261            LessThan => z IN left
262            EqualTo => true
263            GreaterThan => z IN right
264        end
265
266    add(z:()): Set[\E\] = self
267    add(z:E):Set[\E\] =
268        if   (z = val) then self
269        elif (z < val) then balancedAdd(val,left.add(z),right)
270        else balancedAdd(val,left,right.add(z))
271        end
272
273    delete(x:E):Set[\E\] =
274        if   x < val then balancedAdd(val,left.delete(x),right)
275        elif val < x then balancedAdd(val,left,right.delete(x))
276        else              left.balancedDelete(right)
277        end
278
279    balancedDelete(r:Set[\E\]):Set[\E\] =
280        if (min_elt, del_min) <- r.extractMinimum() then
281            balancedAdd(min_elt, self, del_min)
282        else
283            self
284        end
285
286    minimum():Just[\E\] = do
287        notDone : Boolean := true
288        t : NodeSet[\E\] := self
289        while notDone do
290            typecase l = t.getLeftChild() of
291                NodeSet[\E\] => t := l
292                else => notDone := false
293            end
294        end
295        Just[\E\](t.getVal())
296      end
297
298    maximum():Just[\E\] = do
299        notDone : Boolean := true
300        t : NodeSet[\E\] := self
301        while notDone do
302            typecase l = t.getRightChild() of
303                NodeSet[\E\] => t := l
304                else => notDone := false
305            end
306        end
307        Just[\E\](t.getVal())
308      end
309
310    extractMinimum(): Just[\(E,Set[\E\])\] =
311        if (min, delmin) <- left.extractMinimum() then
312            Just[\(E,Set[\E\])\](min, balancedAdd(val,delmin,right))
313        else
314            Just[\(E,Set[\E\])\](val,right)
315        end
316
317    extractMaximum(): Just[\(E,Set[\E\])\] =
318        if (max, delmax) <- right.extractMaximum() then
319            Just[\(E,Set[\E\])\](max, balancedAdd(val,left,delmax))
320        else
321            Just[\(E,Set[\E\])\](val,left)
322        end
323
324    (* TODO: union, intersection, and difference should use hedge
325       algorithms, which avoid splitting and the allocation it entails
326       but require a pile of code instead. *)
327    opr UNION(self, t2:NodeSet[\E\]):Set[\E\] = do
328        (newl, _, newr) = t2.splitAt(val)
329        r = (left UNION newl).concat3(val, right UNION newr)
330        (* println(self "∪" t2 " = " r) *)
331        r
332      end
333    opr UNION(self, t2:Set[\E\]):Set[\E\] = self
334
335    opr INTERSECTION(self,t2:NodeSet[\E\]):Set[\E\] = do
336        (newl, m, newr) = t2.splitAt(val)
337        (li, ri) = (left INTERSECTION newl, right INTERSECTION newr)
338        if m then li.concat3(val,ri) else li.concat(ri)
339        end
340      end
341    opr INTERSECTION(self,t2:Set[\E\]):Set[\E\] = t2
342
343    opr DIFFERENCE(self,t2:NodeSet[\E\]):Set[\E\] = do
344        (newl, m, newr) = t2.splitAt(val)
345        (li,ri) = (left DIFFERENCE newl, right DIFFERENCE newr)
346        if m then li.concat(ri) else li.concat3(val,ri) end
347      end
348    opr DIFFERENCE(self,t2:Set[\E\]):Set[\E\] = self
349
350    opr SYMDIFF(self,t2:NodeSet[\E\]):Set[\E\] = do
351        (newl, m, newr) = t2.splitAt(val)
352        (li,ri) = (left SYMDIFF newl, right SYMDIFF newr)
353        if m then li.concat(ri) else li.concat3(val,ri) end
354      end
355    opr SYMDIFF(self,t2:Set[\E\]):Set[\E\] = self
356
357    opr =(self, other:Set[\E\]): Boolean =
358        if self SEQV other then true
359        elif other.isEmpty then false
360        else
361            (l,m,r) = other.splitAt(val)
362            m AND: left=l AND: right=r
363        end
364    opr SUBSETEQ(self, other:Set[\E\]): Boolean =
365        if self SEQV other then true
366        elif other.isEmpty then false
367        else
368            (l,m,r) = other.splitAt(val)
369            m AND: left SUBSETEQ l AND right SUBSETEQ r
370        end
371    opr SETCMP(self, other:Set[\E\]): Comparison =
372        if self SEQV other then EqualTo
373        elif other.isEmpty then GreaterThan
374        else
375            (l,m,r) = other.splitAt(val)
376            typecase _ = left SETCMP l of
377                Unordered => Unordered
378                LessThan =>
379                    if m AND: right SUBSETEQ r then
380                        LessThan
381                    else Unordered end
382                EqualTo =>
383                    if m then right SETCMP r
384                    elif r SUBSETEQ right then
385                        GreaterThan
386                    else Unordered end
387                GreaterThan =>
388                    if r SUBSETEQ right then
389                        GreaterThan
390                    else Unordered end
391            end
392        end
393
394    concat(t2:Set[\E\]):Set[\E\] =
395        if (min, delmin) <- t2.extractMinimum() then
396            concat3(min, delmin)
397        else
398            self
399        end
400
401    splitIndex(x:ZZ32):(Set[\E\],Set[\E\]) =
402        if x < |left| then
403            (ll,rl) = left.splitIndex(x)
404            (ll,rl.concat3(val,right))
405        elif |left| < x then
406            (lr,rr) = right.splitIndex(x - |left| - 1)
407            (left.concat3(val,lr),rr)
408        else
409            (left,right.add(val))
410        end
411
412    splitAt(x:E):(Set[\E\],Boolean,Set[\E\]) =
413        if x < val then
414            (ll,m,rl) = left.splitAt(x)
415            (ll,m,rl.concat3(val,right))
416        elif val < x then
417            (lr,m,rr) = right.splitAt(x)
418            (left.concat3(val,lr),m,rr)
419        else (left,true,right)
420        end
421
422    concat3(v:E, t2:NodeSet[\E\]):NodeSet[\E\] = do
423        v1 = val
424        n1 = sz
425        l1 = left
426        r1 = right
427        v2 = t2.getVal()
428        n2 = |t2|
429        l2 = t2.getLeftChild()
430        r2 = t2.getRightChild()
431        if   weight n1 < n2 then balancedAdd(v2,concat3(v,l2),r2)
432        elif weight n2 < n1 then balancedAdd(v1,l1,r1.concat3(v,t2))
433        else NodeSet[\E\](v,self,t2) end
434      end
435    concat3(v:E, t2:Set[\E\]):NodeSet[\E\] = add(v)
436
437    balancedAdd(val':E,  left':Set[\E\], right':Set[\E\]):NodeSet[\E\] = do
438        ln = |left'|
439        rn = |right'|
440        if ln + rn < weight then NodeSet[\E\](val', left', right')
441        elif rn > weight ln then
442            rl = right'.getLeftChild()
443            rr = right'.getRightChild()
444            rln = |rl|
445            rrn = |rr|
446            if rln < rrn
447            then single_L(val', left', right')
448            else double_L(val', left', right') end
449        elif ln > weight rn then
450            ll = left'.getLeftChild()
451            lr = left'.getRightChild()
452            lln = |ll|
453            lrn = |lr|
454            if lrn < lln
455            then single_R(val', left', right')
456            else double_R(val',left',right') end
457        else NodeSet[\E\](val',left',right') end
458      end
459
460    single_L(val':E,  left':Set[\E\], right':Set[\E\]):NodeSet[\E\] = do
461        a = val'
462        x = left'
463        b = right'.getVal()
464        y = right'.getLeftChild()
465        z = right'.getRightChild()
466        NodeSet[\E\](b, NodeSet[\E\](a, x, y), z)
467      end
468
469    single_R(val':E,  left':Set[\E\], right':Set[\E\]):NodeSet[\E\] = do
470        b = val'
471        a = left'.getVal()
472        x = left'.getLeftChild()
473        y = left'.getRightChild()
474        z = right'
475        NodeSet[\E\](a,x,NodeSet[\E\](b,y,z))
476      end
477
478    double_L(val':E,  left':Set[\E\], right':Set[\E\]):NodeSet[\E\] = do
479        a = val'
480        x = left'
481        c = right'.getVal()
482        b = right'.getLeftChild().getVal()
483        y1 = right'.getLeftChild().getLeftChild()
484        y2 = right'.getLeftChild().getRightChild()
485        z = right'.getRightChild()
486        (* println("double_L " a " " b) *)
487        NodeSet[\E\](b, NodeSet[\E\](a,x,y1),NodeSet[\E\](c,y2,z))
488      end
489
490    double_R(val':E,  left':Set[\E\], right':Set[\E\]):NodeSet[\E\] = do
491        c = val'
492        a = left'.getVal()
493        x = left'.getLeftChild()
494        b = left'.getRightChild().getVal()
495        y1 = left'.getRightChild().getLeftChild()
496        y2 = left'.getRightChild().getRightChild()
497        z = right'
498        (* println("double_R " a " " b " " c) *)
499        NodeSet[\E\](b, NodeSet[\E\](a, x,y1), NodeSet[\E\](c,y2,z))
500      end
501end
502
503end
Note: See TracBrowser for help on using the browser.