root/trunk/Library/PrefixSet.fss

Revision 4130, 19.9 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
18(******************************************************************************
19
20  Prefix trees, aka Tries: implementing Sets; purely functional
21
22  PrefixSet[\E,F\] is the type of sets where F is a zero-indexed data type storing elements of type E, supporting an operator addLeft. Indexing gives lexicographic ordering.
23
24  At present F must be a subtype of List[\E\] (where List is defined as in List.fss).
25
26  Future improvements:
27
28   - When the standard collection trait hierarchy is done, we can make this code work more pleasantly and in more generality:
29       - we want F to be any type modelling List[\E\]
30       - we could demand that PrefixSet[\E,F\] model Set[\F\].
31       - we could vary the indexing data structure for each node. For some prefix trees, it would be best to implement their children as an array. If we are indexing by lists of booleans, we would want an ad-hoc indexing structure whose lookup algorithm is an "if".
32
33   - It would be nice to implement efficient indexing for PrefixSet. This is apparently impossible, if we are to base it on the existing Map.fss. We would need a variant of Map.fss, which disambiguates references to the number of nodes of a binary tree (which is an internal notion) and the number of elements stored (which is an external notion). Each node of a map, since it represents a whole prefix tree, can contribute many indices, not just one.
34
35  *****************************************************************************)
36
37component PrefixSet
38import Containment.{...}
39import CovariantCollection.{...}
40import List.{...}
41import Map.{...} except { opr BIG UNION, opr BIG INTERSECTION, opr BIG SYMDIFF }
42export PrefixSet
43
44
45
46
47
48trait PrefixSet[\E extends StandardTotalOrder[\E\], F extends List[\E\]\]
49        extends ContainmentGenerator[\F,PrefixSet[\E,F\]\]
50
51    getter indexValuePairs():ZeroIndexed[\(ZZ32,F)\] =
52        IndexValuePrefixSetGenerator[\E,F\](self)
53
54    getter asString():String = "{/" || (", ".join[\F\](self)) || "/}"
55
56    getter size():ZZ32
57
58    getter isEmpty():Boolean = (NOT isMember()) AND children().isEmpty
59
60    isMember():Boolean
61    children():Map[\E,PrefixSet[\E,F\]\]
62
63    prefixGenerate[\R\](prefix:F, r:Reduction[\R\], body: F->R):R = do
64        t:R = children().generate[\R\](r, fn (k,v) => v.prefixGenerate[\R\](prefix.addRight(k),r,body))
65        if isMember() then
66            r.join(body(prefix), t)
67        else
68            t
69        end
70    end
71    generate[\R\](r: Reduction[\R\], body:F->R):R = prefixGenerate[\R\](<|[\E\] |>, r, body)
72
73    prefixSeqgen[\R\](prefix:F, r: Reduction[\R\], body: F->R):R = do
74        t:R = children().seqgen[\R\](r, fn (k,v) => v.prefixSeqgen[\R\](prefix.addRight(k),r,body))
75        if isMember() then
76            r.join(body(prefix),t)
77        else
78            t
79        end
80    end
81    seqgen[\R\](r: Reduction[\R\], body: F->R):R = prefixSeqgen[\R\](<|[\E\] |>, r, body)
82
83    seq(self): SequentialGenerator[\F\] = SeqPrefixSetGenerator[\E,F\](self)
84
85    opr IN(x:F, self):Boolean = do
86        if (h,t) <- x.extractLeft() then
87            if z <- (children().member(h)) then
88                t IN z
89            else
90                false
91            end
92        else
93            isMember()
94        end
95    end
96
97
98    add(x:F): PrefixSet[\E,F\] = do
99        if (h,t) <- x.extractLeft() then
100            f(z:Maybe[\PrefixSet[\E,F\]\]):Maybe[\PrefixSet[\E,F\]\] = do
101                if a <- z then
102                    Just[\PrefixSet[\E,F\]\](a.add(t))
103                else
104                    Just[\PrefixSet[\E,F\]\](emptyPrefixSet[\E,F\]().add(t))
105                end
106            end
107            fastPrefixSet[\E,F\](isMember(),children().updateWith(f, h))
108        else
109            fastPrefixSet[\E,F\](true,children())
110        end
111    end
112
113
114    delete(x:F): PrefixSet[\E,F\] = do
115        if (h,t) <- x.extractLeft() then
116            z = children().member(h)
117            if a <- z then
118                prefixSet[\E,F\](isMember(), children().update(h,a.delete(t)))
119            else
120                self
121            end
122        else
123            prefixSet[\E,F\](false,children())
124        end
125    end
126
127
128    opr =(self, s2:PrefixSet[\E,F\]):Boolean = (isMember() = s2.isMember()) AND (children() = s2.children())
129
130
131    (* Expensive indexing code begins here *)
132
133    opr[i:ZZ32]:F = do
134        if isMember() AND (i = 0) then
135            <|[\E\] |>
136        else
137            var c:ZZ32
138            c := (if isMember() then 1 else 0 end)
139            label Search
140                for (k,v) <- seq(children()) do
141                    s = v.size
142                    if c + s > i then
143                        exit Search with v[i-c].addLeft(k)
144                    else
145                        c += s
146                    end
147                end
148                throw NotFound
149            end Search
150        end
151    end
152
153    indexOf(x:F):Maybe[\ZZ32\] = do
154        if (x IN self) then
155            Just[\ZZ32\](self.indexOfMember(x))
156        else
157            Nothing[\ZZ32\]
158        end
159    end
160
161    indexOfMember(x:F):ZZ32 = do
162        if (h,t) <- x.extractLeft() then
163            label Search
164                var c:ZZ32 = (if isMember() then 1 else 0 end)
165                for (k,v) <- seq(children()) do
166                    if (k=h) then
167                        exit Search with c+v.indexOfMember(t)
168                    else
169                        c += v.size
170                    end
171                end
172            end Search
173        else
174            0
175        end
176    end
177
178    (** Split at index x, meaning left result has size = x or
179        left result has size < x and right result is empty. **)
180    splitIndex(x:ZZ32):(PrefixSet[\E,F\],PrefixSet[\E,F\]) = do
181        (a,_,b) = splitAt(self[x])
182        (a,b.add(x))
183    end
184
185    prefixivgen[\R\](prefix:F, i0:ZZ32, r: Reduction[\R\], body: (ZZ32,F)->R): R = do
186        var i:ZZ32
187        var a:R
188        if isMember() then
189            a := body(i0,prefix)
190            i := i0 + 1
191        else
192            a := r.empty()
193            i := i0
194        end
195        for (l,x) <- seq(children()) do
196            a := r.join(a, x.prefixivgen[\R\](prefix.addRight(l), i, r, body))
197            i := i + |x|
198        end
199        a
200    end
201
202    ivgen[\R\](i0:ZZ32, r: Reduction[\R\], body: (ZZ32,F)->R): R = prefixivgen[\R\](<|[\E\] |>, i0, r, body)
203    (* Expensive indexing code ends here *)
204
205    minimum():Maybe[\F\] = if self.isEmpty then Nothing[\F\] else Just[\F\] getMinimum() end
206    getMinimum():F throws NotFound = do
207        if isMember() then
208            <|[\E\] |>
209        elif (k,v) <- children().minimum() then
210            v.getMinimum().addLeft(k)
211        else
212             throw NotFound
213        end
214    end
215
216    maximum():Maybe[\F\] = if self.isEmpty then Nothing[\F\] else Just[\F\] getMaximum() end
217    getMaximum():F throws NotFound = do
218        if (k,v) <- children().maximum() then
219            v.getMaximum().addLeft(k)
220        else
221            <|[\E\] |>
222        end
223    end
224
225    deleteMinimum():PrefixSet[\E,F\] =
226        if (_, res) <- extractMinimum() then res else self end
227    deleteMaximum():PrefixSet[\E,F\] =
228        if (_, res) <- extractMaximum() then res else self end
229
230    extractMinimum():Maybe[\(F, PrefixSet[\E,F\])\] = do
231        if isMember() then
232            Just[\(F, PrefixSet[\E,F\])\](<|[\E\] |>, fastPrefixSet[\E,F\](false, children()))
233        elif (k,v,r) <- children().extractMinimum() then
234            (m,s) = v.extractMinimum().get
235            Just[\(F, PrefixSet[\E,F\])\](m.addLeft(k), prefixSet[\E,F\](false, r.add(k,s)))
236        else
237            Nothing[\(F, PrefixSet[\E,F\])\]
238        end
239    end
240
241    extractMaximum():Maybe[\(F, PrefixSet[\E,F\])\] = do
242        if (k,v,r) <- children().extractMaximum() then
243            (m,s) = v.extractMaximum().get
244            Just[\(F, PrefixSet[\E,F\])\](m.addLeft(k), prefixSet[\E,F\](isMember(), r.add(k,s)))
245        elif isMember() then
246            Just[\(F, PrefixSet[\E,F\])\](<|[\E\] |>, emptyPrefixSet[\E,F\]())
247        else
248            Nothing[\(F, PrefixSet[\E,F\])\]
249        end
250    end
251
252
253
254    (* Concatenation: assumes that all the values on the right are greater than all those on the left. *)
255    concat(s2:PrefixSet[\E,F\]):PrefixSet[\E,F\] = do
256        leftm = children().extractMaximum()
257        rightm = s2.children().extractMinimum()
258        if (leftmaxkey,leftmaxval,left) <- leftm then
259            if (rightminkey,rightminval,right) <- rightm then
260                if leftmaxkey<rightminkey then
261                    fastPrefixSet[\E,F\](isMember() OR s2.isMember(), children().concat(s2.children()))
262                else
263                    fastPrefixSet[\E,F\](isMember() OR s2.isMember(), left.concat3(leftmaxkey, leftmaxval.concat(rightminval), right))
264                end
265            else
266                self
267            end
268        else
269            s2
270        end
271    end
272
273    concat3(v:F, s2:PrefixSet[\E,F\]):PrefixSet[\E,F\] = do
274        leftm = children().extractMaximum()
275        rightm = s2.children().extractMinimum()
276        if NOT leftm.holds then
277            s2
278        elif NOT rightm.holds then
279            self
280        else
281            (leftmaxkey,leftmaxval,left) = leftm.get
282            (rightminkey,rightminval,right) = rightm.get
283
284            if (|v| = 0) then
285                if leftmaxkey<rightminkey then
286                    fastPrefixSet[\E,F\](true, children().concat(s2.children()))
287                else
288                    fastPrefixSet[\E,F\](isMember() OR s2.isMember(), left.concat3(leftmaxkey, leftmaxval.concat(rightminval), right))
289                end
290            else
291                (midh, midt) = v.extractLeft()
292                if   leftmaxkey<midh<rightminkey then
293                    fastPrefixSet[\E,F\](isMember() OR s2.isMember(), children().concat3(midh,singletonPrefixSet(midt),s2.children()))
294                elif leftmaxkey=midh<rightminkey then
295                    fastPrefixSet[\E,F\](isMember() OR s2.isMember(), left.concat3(leftmaxkey,leftmaxval.concat(singletonPrefixSet(midt)),s2.children()))
296                elif leftmaxkey<midh=rightminkey then
297                    fastPrefixSet[\E,F\](isMember() OR s2.isMember(),children().concat3(rightminkey,singletonPrefixSet(midt).concat(rightminval),right))
298                else (*) leftmaxkey=midh=rightminkey
299                    fastPrefixSet[\E,F\](isMember() OR s2.isMember(),left.concat3(leftmaxkey,leftmaxval.concat3(midt,rightminval),right))
300                end
301            end
302        end
303    end
304
305    (* Could we replace some of the prefixSet calls with fastPrefixSet? *)
306    splitAt(x:F):(PrefixSet[\E,F\],Boolean,PrefixSet[\E,F\]) = do
307        if (h,t) <- x.extractLeft() then
308            (l,m,r) = children().splitAt(h)
309            if a <- m then
310                (lb,b,rb) = a.splitAt(t)
311                (prefixSet(isMember(), l.add(a,lb)), b, prefixSet(false, r.add(a,rb)))
312            else
313                (prefixSet(isMember(), l), false, prefixSet(isMember(), r))
314            end
315        else
316            (emptyPrefixSet[\E,F\](), isMember(), fastPrefixSet(false, children()))
317        end
318    end
319
320
321    opr SUBSETEQ(self, other:PrefixSet[\E,F\]): Boolean = (other.isMember() OR NOT isMember()) AND (BIG AND[(k,v) <- children()] (k IN other.children()) AND (children()[k] SUBSETEQ (other.children())[k]))
322    opr SUBSET(self, other:PrefixSet[\E,F\]): Boolean = (NOT (self = other)) AND (self SUBSETEQ other)
323
324    opr SUPSETEQ(self, other:PrefixSet[\E,F\]): Boolean = other SUBSETEQ self
325    opr SUPSET(self, other:PrefixSet[\E,F\]): Boolean = other SUBSET self
326
327    opr SETCMP(self, other:PrefixSet[\E,F\]): Comparison = do
328        if (self = other) then
329            EqualTo
330        elif (self SUBSETEQ other) then
331            LessThan
332        elif (other SUBSETEQ self) then
333            GreaterThan
334        else
335            Unordered
336        end
337    end
338
339
340    opr |self|:ZZ32 = self.size
341
342    opr UNION(self,s2:PrefixSet[\E,F\]):PrefixSet[\E,F\] = do
343        ifOne(k:E, v:PrefixSet[\E,F\]):Maybe[\PrefixSet[\E,F\]\] = Just[\PrefixSet[\E,F\]\](v)
344        mapOne(a:Map[\E,PrefixSet[\E,F\]\]):Map[\E,PrefixSet[\E,F\]\] = a
345        ifBoth(k:E, u:PrefixSet[\E,F\], v:PrefixSet[\E,F\]):Maybe[\PrefixSet[\E,F\]\] = Just[\PrefixSet[\E,F\]\](u UNION v)
346        fastPrefixSet[\E,F\](isMember() OR s2.isMember(), children().combine[\PrefixSet[\E,F\],PrefixSet[\E,F\]\](ifBoth,ifOne,ifOne,mapOne,mapOne,s2.children()))
347    end
348
349    opr INTERSECTION(self,s2:PrefixSet[\E,F\]):PrefixSet[\E,F\] = do
350        ifOne(k:E, v:PrefixSet[\E,F\]):Maybe[\PrefixSet[\E,F\]\] = Nothing[\PrefixSet[\E,F\]\]
351        mapOne(a:Map[\E,PrefixSet[\E,F\]\]):Map[\E,PrefixSet[\E,F\]\] = mapping[\E,PrefixSet[\E,F\]\]()
352        ifBoth(k:E, u:PrefixSet[\E,F\], v:PrefixSet[\E,F\]):Maybe[\PrefixSet[\E,F\]\] = Just[\PrefixSet[\E,F\]\](u INTERSECTION v)
353        prefixSet[\E,F\](isMember() AND s2.isMember(), children().combine[\PrefixSet[\E,F\],PrefixSet[\E,F\]\](ifBoth,ifOne,ifOne,mapOne,mapOne,s2.children()))
354    end
355
356    opr SYMDIFF(self,s2:PrefixSet[\E,F\]):PrefixSet[\E,F\] = do
357        ifOne(k:E, v:PrefixSet[\E,F\]):Maybe[\PrefixSet[\E,F\]\] = Just[\PrefixSet[\E,F\]\](v)
358        mapOne(a:Map[\E,PrefixSet[\E,F\]\]):Map[\E,PrefixSet[\E,F\]\] = a
359        ifBoth(k:E, u:PrefixSet[\E,F\], v:PrefixSet[\E,F\]):Maybe[\PrefixSet[\E,F\]\] = Just[\PrefixSet[\E,F\]\](u SYMDIFF v)
360        prefixSet[\E,F\](isMember() XOR s2.isMember(), children().combine[\PrefixSet[\E,F\],PrefixSet[\E,F\]\](ifBoth,ifOne,ifOne,mapOne,mapOne,s2.children()))
361    end
362
363    opr DIFFERENCE(self,s2:PrefixSet[\E,F\]):PrefixSet[\E,F\] = do
364        ifThis(k:E, v:PrefixSet[\E,F\]):Maybe[\PrefixSet[\E,F\]\] = Just[\PrefixSet[\E,F\]\](v)
365        mapThis(a:Map[\E,PrefixSet[\E,F\]\]):Map[\E,PrefixSet[\E,F\]\] = a
366        ifThat(k:E, v:PrefixSet[\E,F\]):Maybe[\PrefixSet[\E,F\]\] = Nothing[\PrefixSet[\E,F\]\]
367        mapThat(a:Map[\E,PrefixSet[\E,F\]\]):Map[\E,PrefixSet[\E,F\]\] = mapping[\E,PrefixSet[\E,F\]\]()
368        ifBoth(k:E, u:PrefixSet[\E,F\], v:PrefixSet[\E,F\]):Maybe[\PrefixSet[\E,F\]\] = Just[\PrefixSet[\E,F\]\](u DIFFERENCE v)
369        prefixSet[\E,F\](isMember() AND NOT s2.isMember(), children().combine[\PrefixSet[\E,F\],PrefixSet[\E,F\]\](ifBoth,ifThis,ifThat,mapThis,mapThat,s2.children()))
370    end
371
372
373end
374
375
376
377(* A PrefixSet with given children: 'unsafe' as it assumes it is not given any useless tree structure *)
378object fastPrefixSet[\E extends StandardTotalOrder[\E\], F extends List[\E\]\](v:Boolean,c:Map[\E,PrefixSet[\E,F\]\]) extends PrefixSet[\E,F\]
379    getter size():ZZ32 = fixedsize
380    fixedsize:ZZ32 = (if v then 1 else 0 end) + (SUM[(k,a) <- c] a.size)
381    isMember():Boolean = v
382    children():Map[\E,PrefixSet[\E,F\]\] = c
383end
384
385
386(* A PrefixSet with given children: 'safe' as it will remove any useless tree structure *)
387prefixSet[\E extends StandardTotalOrder[\E\], F extends List[\E\]\](v:Boolean, c:Map[\E,PrefixSet[\E,F\]\]):PrefixSet[\E,F\] = fastPrefixSet[\E,F\](v, {[\E,PrefixSet[\E,F\]\] k |-> l | (k,l)<-c, l.size =/= 0 })
388
389
390emptyPrefixSet[\E extends StandardTotalOrder[\E\], F extends List[\E\]\]():PrefixSet[\E,F\] = fastPrefixSet[\E,F\](false,mapping[\E,PrefixSet[\E,F\]\]())
391
392
393singletonPrefixSet[\E extends StandardTotalOrder[\E\], F extends List[\E\]\](x:F):PrefixSet[\E,F\] = do
394    if (h,t) <- x.extractLeft() then
395        prefixSet[\E,F\](false, singleton[\E,PrefixSet[\E,F\]\](h,singletonPrefixSet[\E,F\](t)))
396    else
397        fastPrefixSet[\E,F\](true, mapping[\E,PrefixSet[\E,F\]\]())
398    end
399end
400
401
402
403
404
405
406
407
408(* Standard generator code *)
409
410
411prefixSet[\E extends StandardTotalOrder[\E\], F extends List[\E\]\](g:Generator[\F\]):PrefixSet[\E,F\] = g.generate[\PrefixSet[\E,F\]\](Union[\E,F\], singletonPrefixSet[\E,F\])
412
413opr {/[\E extends StandardTotalOrder[\E\], F extends List[\E\]\] fs:F... /}: PrefixSet[\E,F\] = prefixSet[\E,F\](fs)
414
415opr BIG {/[\E extends StandardTotalOrder[\E\], F extends List[\E\]\]/} : Comprehension[\F,PrefixSet[\E,F\],AnyCovColl,AnyCovColl\] =
416    covariantCompr[\F,PrefixSet[\E,F\]\](fn cc => prefixSet(cc.toImmutableArray()))
417
418opr BIG {/[\E extends StandardTotalOrder[\E\], F extends List[\E\]\] g:Generator[\F\]/}:PrefixSet[\E,F\] =
419    __bigOperatorSugar[\F,PrefixSet[\E,F\],AnyCovColl,AnyCovColl\](BIG {/[\E,F\]/}(), g)
420
421
422
423(* Standard union & intersection code *)
424
425object Union[\E extends StandardTotalOrder[\E\], F extends List[\E\]\] extends CommutativeMonoidReduction[\PrefixSet[\E,F\]\]
426    getter asString(): String = "Union reduction"
427    empty():PrefixSet[\E,F\] = emptyPrefixSet[\E,F\]()
428    join(a:PrefixSet[\E,F\], b:PrefixSet[\E,F\]): PrefixSet[\E,F\] = a UNION b
429end
430
431opr BIG UNION[\E extends StandardTotalOrder[\E\], F extends List[\E\]\](): BigReduction[\PrefixSet[\E,F\],PrefixSet[\E,F\]\] =
432    BigReduction[\PrefixSet[\E,F\],PrefixSet[\E,F\]\](Union[\E,F\])
433
434opr BIG UNION[\E extends StandardTotalOrder[\E\], F extends List[\E\]\](g: Generator[\PrefixSet[\E,F\]\]):PrefixSet[\E,F\] =
435    __bigOperatorSugar[\PrefixSet[\E,F\],PrefixSet[\E,F\],PrefixSet[\E,F\],PrefixSet[\E,F\]\](BIG UNION[\PrefixSet[\E,F\]\](), g)
436
437
438
439
440object Intersection[\E extends StandardTotalOrder[\E\], F extends List[\E\]\] extends CommutativeMonoidReduction[\PrefixSet[\E,F\]\]
441    getter asString(): String = "Intersection reduction"
442    empty():PrefixSet[\E,F\] = emptyPrefixSet[\E,F\]()
443    join(a:PrefixSet[\E,F\], b:PrefixSet[\E,F\]): PrefixSet[\E,F\] = a INTERSECTION b
444end
445
446opr BIG INTERSECTION[\E extends StandardTotalOrder[\E\], F extends List[\E\]\](): BigReduction[\PrefixSet[\E,F\],PrefixSet[\E,F\]\] =
447    BigReduction[\PrefixSet[\E,F\],PrefixSet[\E,F\]\](Intersection[\E,F\])
448
449opr BIG INTERSECTION[\E extends StandardTotalOrder[\E\], F extends List[\E\]\](g: Generator[\PrefixSet[\E,F\]\]):PrefixSet[\E,F\] =
450    __bigOperatorSugar[\PrefixSet[\E,F\],PrefixSet[\E,F\],PrefixSet[\E,F\],PrefixSet[\E,F\]\](BIG INTERSECTION[\PrefixSet[\E,F\]\](), g)
451
452
453
454
455object SymmetricDifference[\E extends StandardTotalOrder[\E\], F extends List[\E\]\] extends CommutativeMonoidReduction[\PrefixSet[\E,F\]\]
456    getter asString(): String = "Symmetric difference reduction"
457    empty():PrefixSet[\E,F\] = emptyPrefixSet[\E,F\]()
458    join(a:PrefixSet[\E,F\], b:PrefixSet[\E,F\]): PrefixSet[\E,F\] = a SYMDIFF b
459end
460
461opr BIG SYMDIFF[\E extends StandardTotalOrder[\E\], F extends List[\E\]\](): BigReduction[\PrefixSet[\E,F\],PrefixSet[\E,F\]\] =
462    BigReduction[\PrefixSet[\E,F\],PrefixSet[\E,F\]\](SymmetricDifference[\E,F\])
463
464opr BIG SYMDIFF[\E extends StandardTotalOrder[\E\], F extends List[\E\]\](g: Generator[\PrefixSet[\E,F\]\]):PrefixSet[\E,F\] =
465    __bigOperatorSugar[\PrefixSet[\E,F\],PrefixSet[\E,F\],PrefixSet[\E,F\],PrefixSet[\E,F\]\](BIG SYMDIFF[\PrefixSet[\E,F\]\](), g)
466
467
468
469
470
471
472value object SeqPrefixSetGenerator[\E extends StandardTotalOrder[\E\],F extends List[\E\]\](s: PrefixSet[\E,F\])
473        extends SequentialGenerator[\F\]
474    getter size():ZZ32 = |s|
475    getter isEmpty():Boolean = s.isEmpty
476    opr |self|: ZZ32 = |s|
477    generate[\R\](r: Reduction[\R\], body: F->R): R =
478        s.seqgen[\R\](r,body)
479end
480
481value object IndexValuePrefixSetGenerator[\E extends StandardTotalOrder[\E\],F extends List[\E\]\](s: PrefixSet[\E,F\])
482        extends ZeroIndexed[\(ZZ32,F)\]
483    getter size():ZZ32 = |s|
484    getter indices(): Generator[\ZZ32\] = s.indices()
485    getter isEmpty(): Boolean = s.isEmpty
486    opr |self|:ZZ32 = |s|
487    generate[\R\](r: Reduction[\R\], body: (ZZ32,F)->R): R = s.ivgen[\R\](0,r,body)
488    opr[ x:ZZ32 ]:(ZZ32,E) = (x,s[x])
489    opr[ r:Range[\ZZ32\] ]:ZeroIndexed[\(ZZ32,F)\] = s[r].indexValuePairs
490    indexOf(i:ZZ32,v:F):Maybe[\ZZ32\] = if s[i]=v then Just[\ZZ32\](i) else Nothing[\ZZ32\] end
491end
492
493
494end
Note: See TracBrowser for help on using the browser.