root/trunk/Library/PureList.fss

Revision 4130, 34.6 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 PureList
19import CovariantCollection.{...}
20export PureList
21
22(** Finger trees, based on Ralf Hinze and Ross Paterson's article, JFP
23    16:2 2006.
24
25    Why finger trees?  They're balanced and support nearly any
26    operation we care to think of in optimal asymptotic time and
27    space.  The code is niggly due to lots of cases, but fast in
28    practice.
29
30    It's also a trial for encoding type-based invariants in Fortress.
31    Can we represent "array of size at most n"?  Not yet, but we ought
32    to be able to do so.  This involves questions about the encoding
33    of existentials, especially constrained existentials.
34
35 **)
36
37(* Tests can be found in
38   tests/PureListQuick.fss
39   demos/PureListLong.fss
40*)
41
42(** Generic list trait.
43    We return a Generator for non-List-specific operations for which
44    reuse of the Generator won't increase asymptotic complexity, but
45    return a List in cases (such as map and filter) where it will.
46*)
47trait List[\E\] extends { LexicographicOrder[\List[\E\],E\] }
48        excludes { Number, HasRank, String }
49    (** %left% and %extractLeft% return the leftmost element in the list
50        (and in the latter case, the remainder of the list without its
51        leftmost element).  They return %Nothing% if the list is empty.
52        %right% and %extractRight% do the same with the rightmost
53        element. *)
54    getter left():Maybe[\E\] = self.extractLeft.map[\E\](fn (v:E,_):E => v)
55    getter right():Maybe[\E\] = self.extractRight.map[\E\](fn (_,v:E):E => v)
56    getter extractLeft(): Maybe[\(E,List[\E\])\]
57    getter extractRight(): Maybe[\(List[\E\],E)\]
58    getter asString(): String = "<|" || ", ".join[\E\](self) || "|>"
59    getter reverse(): List[\E\] =
60        generate[\List[\E\]\](RevConcat[\E\],singleton[\E\])
61    opr ||(self, other:List[\E\]): List[\E\]
62    (** %addLeft% and %addRight% add an element to the left or right of
63        the list, respectively *)
64    addLeft(e:E):List[\E\]
65    addRight(e:E):List[\E\]
66    (** %take% returns the leftmost %n% elements of the list; if the
67        list is shorter than this, the entire list is returned. *)
68    take(n:ZZ32): List[\E\]
69    (** %drop% drops the leftmost %n% elements of the list; if the list
70        is shorter than this, an empty list is returned. *)
71    drop(n:ZZ32): List[\E\]
72    opr [n:ZZ32]: E
73    opr [n:Range[\ZZ32\]]: List[\E\] = do
74        r = (0 # |self|).narrowToRange(n)
75        if r.stride = 1 then
76            drop(r.left.get).take(|r|)
77        else
78            <| self[i] | i <- r |>
79        end
80      end
81    (** %l.split(n)% is equivalent to %(l.take(n),l.drop(n))%.  Note in
82        particular that appending its results yields the original
83        list. *)
84    split(n:ZZ32): (List[\E\], List[\E\])
85    (** %split% splits the list into two smaller lists.  If %|l| > 1%
86        both lists will be non-empty. *)
87    split(): (List[\E\], List[\E\])
88    filter(p: E -> Boolean): List[\E\] =
89        concatMap[\E\](fn (x:E):List[\E\] => if p(x) then singleton[\E\](x)
90                                             else emptyList[\E\]() end)
91    (** %concatMap% is an in-place version of the %nest% method from
92        %Generator%; it flattens the result into an actual list, rather than
93        returning an abstract %Generator%. *)
94    concatMap[\G\](f: E->List[\G\]): List[\G\] =
95        generate[\List[\G\]\](Concat[\G\],f)
96    map[\G\](f: E->G): List[\G\] =
97        concatMap[\G\](fn (e:E):List[\G\] => singleton[\G\](f(e)))
98    ivmap[\G\](f: (ZZ32,E)->G): List[\G\] =
99        self.indexValuePairs.generate[\List[\G\]\](Concat[\G\],
100                  fn (t:(ZZ32,E)):List[\G\] => singleton[\G\](f(t)))
101end
102
103(** Vararg factory for lists; provides aggregate list constants **)
104opr <|[\E\] xs: E... |>: List[\E\] = list(xs)
105opr BIG <|[\T\]|>: Comprehension[\T,List[\T\],AnyCovColl,AnyCovColl\] =
106    covariantCompr[\T,List[\T\]\](fn cc => list(cc.toImmutableArray()))
107opr BIG <|[\T\] g:Generator[\T\]|>:List[\T\] =
108    __bigOperatorSugar[\T,List[\T\],AnyCovColl,AnyCovColl\](BIG <|[\T\]|>(), g)
109
110(** Convert generator into list; can be used to desugar list
111    comprehensions *)
112list[\E\](g:Generator[\E\]):List[\E\] =
113    g.generate[\List[\E\]\](Concat[\E\], singleton[\E\])
114list[\E\](g:ReadableArray[\E,ZZ32\]): List[\E\] =
115    PureList[\E\](arrayToFingerTree[\E\](g))
116
117arrayToFingerTree[\E\](g:ReadableArray[\E,ZZ32\]): FingerTree[\E\] = do
118    l = g.bounds.lower
119    case |g| of
120        0 => D0[\E\]
121        1 => D1[\E\](g[l])
122        2 => Deep[\E\](D1[\E\](g[l]),D0[\D23[\E\]\],D1[\E\](g[l+1]))
123        3 => Deep[\E\](D1[\E\](g[l]),D0[\D23[\E\]\],D2[\E\](g[l+1],g[l+2]))
124        else =>
125            u = g.bounds.upper
126            n = (|g| + 2) DIV 3 - 2
127            (start, left, right) =
128                case |g| MOD 3 of
129                    0 => (3, D3[\E\](g[l],g[l+1],g[l+2]), D3[\E\](g[u-2],g[u-1],g[u]))
130                    1 => (2, D2[\E\](g[l],g[l+1]),        D2[\E\](       g[u-1],g[u]))
131                    2 => (3, D3[\E\](g[l],g[l+1],g[l+2]), D2[\E\](       g[u-1],g[u]))
132                end
133            arr = immutableArray[\D23[\E\]\](n)
134            for i <- arr.indices do
135                offset = start + 3 i
136                arr.init(i, D3[\E\](g[offset],g[offset+1],g[offset+2]))
137            end
138            Deep[\E\](left,arrayToFingerTree[\D23[\E\]\](arr),right)
139    end
140  end
141
142(** Flatten a list of lists *)
143concat[\E\](x:List[\List[\E\]\]):List[\E\] = x.concatMap[\E\](identity[\E\])
144
145(** A reduction object for concatenating lists. *)
146private object Concat[\E\] extends MonoidReduction[\ List[\E\] \]
147  getter asString(): String = "List concatenation reduction"
148  empty(): List[\E\] = emptyList[\E\]()
149  join(a:List[\E\], b:List[\E\]): List[\E\] = a || b
150end
151
152(** The same for reverse concatenation *)
153private object RevConcat[\E\] extends MonoidReduction[\ List[\E\] \]
154  getter asString(): String = "List reversal reduction"
155  empty(): List[\E\] = emptyList[\E\]()
156  join(a:List[\E\], b:List[\E\]): List[\E\] = b || a
157end
158
159(** A reduction object for concatenating specifically PureLists. *)
160private object PLConcat[\E\] extends MonoidReduction[\ PureList[\E\] \]
161  getter asString(): String = "PureList concatenation reduction"
162  empty(): PureList[\E\] = D0[\E\]
163  join(a:PureList[\E\], b:PureList[\E\]): PureList[\E\] = a || b
164end
165
166(* We must wrap the FingerTree, since we need to also wrap the elements
167   in order to compute the nested monoidal computation (here the size of
168   each sublist) systematically. *)
169value object PureList[\E\]( it: FingerTree[\E\] )
170      extends { List[\E\] }
171  getter size(): ZZ32 = |self|
172  getter isEmpty(): Boolean = it.isEmpty
173  getter left():Maybe[\E\] = left1(it)
174  getter right():Maybe[\E\] = right1(it)
175  getter extractLeft(): Maybe[\(E,PureList[\E\])\] = extractLeft1(it)
176  getter extractRight(): Maybe[\(PureList[\E\],E)\] = extractRight1(it)
177  getter indexValuePairs(): Generator[\(ZZ32,E)\] =
178      IndexValuePairs[\E\](it)
179  getter reverse(): PureList[\E\] = PureList[\E\](it.revMap(identity[\E\]))
180  opr |self| : ZZ32 = leafSize(it)
181  generate[\R\](r: Reduction[\R\], body: E->R): R =
182      it.generate[\R\](r,body)
183  seq(self): SequentialGenerator[\E\] = SeqListGenerator[\E\](it)
184  opr ||(self, f:List[\E\]): List[\E\] =
185      self || f.generate[\PureList[\E\]\](PLConcat[\E\],singleton[\E\])
186  opr ||(self, f:PureList[\E\]): PureList[\E\] =
187      PureList[\E\](it.append(f.contents()))
188  addLeft(e:E):PureList[\E\] =
189      PureList[\E\](it.addLeft(e))
190  addRight(e:E):PureList[\E\] =
191      PureList[\E\](it.addRight(e))
192  take(n:ZZ32): PureList[\E\] =
193      if n <= 0 then
194          emptyList[\E\]()
195      else
196          PureList[\E\](it.take(n))
197      end
198  drop(n:ZZ32): PureList[\E\] =
199      if n >= |self| then
200          emptyList[\E\]()
201      else
202          PureList[\E\](it.drop(n))
203      end
204  opr [n:ZZ32]: E =
205      if n < 0 then
206          fail("PureList[" n "] index negative")
207      elif n >= |self| then
208          fail("PureList[" n "] of size " |self| " index too large")
209      else
210          (_,res) = it.index(n)
211          res
212      end
213  split(n:ZZ32): (PureList[\E\], PureList[\E\]) =
214      if n <= 0 then
215          (emptyList[\E\](),self)
216      elif n >= |self| then
217          (self,emptyList[\E\]())
218      else
219        (l,r) = it.split(n)
220        (PureList[\E\](l),PureList[\E\](r))
221      end
222  split(): (PureList[\E\], PureList[\E\]) = do
223      (l,r) = it.split()
224      (PureList[\E\](l),PureList[\E\](r))
225    end
226  private contents():FingerTree[\E\] = it
227  private left1(itt: D0[\E\]): Nothing[\E\] = Nothing[\E\]
228  private left1(itt: NonEmptyFingerTree[\E\]): Just[\E\] =
229      Just[\E\](itt.left)
230  private right1(itt: D0[\E\]): Nothing[\E\] = Nothing[\E\]
231  private right1(itt: NonEmptyFingerTree[\E\]): Just[\E\] =
232      Just[\E\](itt.right)
233  private extractLeft1(itt: D0[\E\]): Nothing[\(E,PureList[\E\])\] =
234      Nothing[\(E,PureList[\E\])\]
235  private extractLeft1(itt: NonEmptyFingerTree[\E\]):
236          Just[\(E,PureList[\E\])\] = do
237      (h,t) = it.extractLeft
238      Just[\(E,PureList[\E\])\](h,PureList[\E\](t))
239    end
240  private extractRight1(itt: D0[\E\]): Nothing[\(E,PureList[\E\])\] =
241      Nothing[\(E,PureList[\E\])\]
242  private extractRight1(itt: NonEmptyFingerTree[\E\]):
243          Just[\(E,PureList[\E\])\] = do
244      (i,l) = it.extractRight
245      Just[\(PureList[\E\],E)\](PureList[\E\](i),l)
246    end
247end
248
249private value object SeqListGenerator[\E\]( it: FingerTree[\E\] )
250        extends { SequentialGenerator[\E\] }
251    getter size(): ZZ32 = |self|
252    opr |self| : ZZ32 = leafSize(it)
253    generate[\R\](r: Reduction[\R\], body: E->R): R =
254        it.seqgen[\R\](r,fn (x: E): R => body(x))
255end
256
257emptyList[\E\](): List[\E\] = PureList[\E\](D0[\E\])
258singleton[\E\](e:E): List[\E\] =
259    PureList[\E\](D1[\E\](e))
260
261(* Everything except tree innards must be a datum, and thus has size
262   1.  This works because the tree innards can never be part of a
263   nested tree unless there is an intervening PureList.  Data
264   abstraction has its advantages! *)
265private leafSize(a:Any):ZZ32 = 1
266
267private trait Sized
268    leafSize(self):ZZ32
269end
270
271private trait FTStructure[\E\] extends Sized
272    comprises { FingerTree[\E\], D04[\E\] }
273  generate[\R\](r: Reduction[\R\], body: E->R): R
274  seqgen[\R\](r: Reduction[\R\], body: E->R): R
275  ivgen[\R\](leftIndex: ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R
276  sivgen[\R\](leftIndex: ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R
277  split():(FTStructure[\E\],FTStructure[\E\])
278  revMap(f:E -> E):FTStructure[\E\]
279end
280
281private object IndexValuePairs[\E\](it: FingerTree[\E\]) extends Generator[\(ZZ32,E)\]
282    getter size(): ZZ32 = |it|
283    opr |self| : ZZ32 = |it|
284    generate[\R\](r: Reduction[\R\], body: (ZZ32,E)->R): R =
285        it.ivgen[\R\](0,r,body)
286    seq(self): SequentialGenerator[\E\] = SequentialIndexValuePairs[\E\](it)
287end
288
289private object SequentialIndexValuePairs[\E\](it: FingerTree[\E\])
290        extends SequentialGenerator[\(ZZ32,E)\]
291    getter size(): ZZ32 = |it|
292    opr |self| : ZZ32 = |it|
293    generate[\R\](r: Reduction[\R\], body: E->R): R = it.sivgen[\R\](0,r,body)
294end
295
296private trait FingerTree[\E\] extends FTStructure[\E\]
297    comprises { D01[\E\], NonEmptyFingerTree[\E\] }
298  append(f:D01[\E\]) : FingerTree[\E\] = addRightD(f)
299  append(f:Deep[\E\]) : FingerTree[\E\]
300  addLeftD(e:D0[\E\]) : FingerTree[\E\] = self
301  addLeftD(e:D14[\E\]) : FingerTree[\E\]
302  addLeft(e:E):FingerTree[\E\]
303  addRightD(e:D0[\E\]) : FingerTree[\E\] = self
304  addRightD(e:D14[\E\]) : FingerTree[\E\]
305  addRight(e:E):FingerTree[\E\]
306  append3(e:D04[\E\], f:D01[\E\]):FingerTree[\E\] = addRightD(e).addRightD(f)
307  append3(e:D04[\E\], f:Deep[\E\]):FingerTree[\E\]
308  take(n:ZZ32): FingerTree[\E\]
309  drop(n:ZZ32): FingerTree[\E\]
310  index(n:ZZ32): (ZZ32, E)
311  split(n:ZZ32): (FingerTree[\E\], FingerTree[\E\])
312  split(): (FingerTree[\E\], FingerTree[\E\])
313end
314
315private trait NonEmptyFingerTree[\E\] extends FingerTree[\E\]
316    comprises { D1[\E\], Deep[\E\] }
317  getter isEmpty(): Boolean = false
318  getter left():E
319  getter right():E
320  getter extractLeft():(E,FingerTree[\E\])
321  getter extractRight():(FingerTree[\E\],E)
322  split(): (NonEmptyFingerTree[\E\], FingerTree[\E\])
323  split3(n:ZZ32): (FingerTree[\E\], E, FingerTree[\E\])
324end
325
326(* The type of all digits, from 0 to 4.
327   We populate the sets of digits of particular sizes.  The ones which
328   matter most are D14 (fringes of a Deep), D01 (shallow FingerTree), and
329   D23 (nodes of the middle of a Deep).  *)
330private trait D04[\E\] extends FTStructure[\E\]
331    comprises { D03[\E\], D14[\E\] }
332  toFinger():FingerTree[\E\]
333  split(): (D02[\E\], D02[\E\])
334  index(n:ZZ32): (ZZ32, E)
335end
336
337private trait D03[\E\] extends D04[\E\]
338    comprises { D02[\E\], D13[\E\] }
339  cons(e:E) : D14[\E\]
340  snoc(e:E) : D14[\E\]
341end
342
343private trait D14[\E\] extends D04[\E\]
344    comprises { D13[\E\], D24[\E\] }
345  getter isEmpty(): Boolean = false
346  getter uncons() : (E,D03[\E\])
347  getter unsnoc() : (D03[\E\],E)
348  getter car() : E
349  getter rac() : E
350  nodes3(x:D04[\E\],y:D14[\E\]):D14[\D23[\E\]\]
351  nodes2(x:D14[\E\]):D13[\D23[\E\]\]
352  take(n:ZZ32): D14[\E\]
353  drop(n:ZZ32): D14[\E\]
354  split3(n:ZZ32): (D03[\E\], E, D03[\E\])
355end
356
357private trait D02[\E\] extends D03[\E\]
358    comprises { D01[\E\],D12[\E\] }
359  cons(e:E) : D13[\E\]
360  snoc(e:E) : D13[\E\]
361end
362
363private trait D13[\E\] extends { D03[\E\], D14[\E\] }
364    comprises { D12[\E\], D23[\E\] }
365  getter uncons() : (E,D02[\E\])
366  getter unsnoc() : (D02[\E\],E)
367  cons(e:E) : D24[\E\]
368  snoc(e:E) : D24[\E\]
369  nodes3(x:D04[\E\],y:D14[\E\]):D14[\D23[\E\]\]
370  nodes2(x:D14[\E\]):D13[\D23[\E\]\]
371end
372
373private trait D24[\E\] extends D14[\E\]
374  getter uncons() : (E,D13[\E\])
375  getter unsnoc() : (D13[\E\],E)
376  nodes3(x:D04[\E\],y:D14[\E\]):D14[\D23[\E\]\]
377  nodes2(x:D14[\E\]):D13[\D23[\E\]\]
378  nodes1():D12[\D23[\E\]\]
379end
380
381private trait D01[\E\]
382    extends { D02[\E\], FingerTree[\E\]  }
383    comprises { D0[\E\], D1[\E\] }
384  cons(e:E) : D12[\E\]
385  snoc(e:E) : D12[\E\]
386  append(f:Deep[\E\]) : FingerTree[\E\] = f.addLeftD(self)
387  toFinger():FingerTree[\E\] = self
388end
389
390private trait D12[\E\] extends { D02[\E\], D13[\E\] }
391    comprises { D1[\E\], D2[\E\] }
392  getter uncons() : (E,D01[\E\])
393  getter unsnoc() : (D01[\E\],E)
394  cons(e:E) : D34[\E\]
395  snoc(e:E) : D34[\E\]
396  nodes3(x:D04[\E\],y:D14[\E\]):D14[\D23[\E\]\]
397  nodes2(x:D14[\E\]):D12[\D23[\E\]\]
398end
399
400private trait D23[\E\] extends { D13[\E\], D24[\E\] }
401    comprises { D2[\E\], D3[\E\] }
402  getter uncons() : (E,D12[\E\])
403  getter unsnoc() : (D12[\E\],E)
404  cons(e:E) : D34[\E\]
405  snoc(e:E) : D34[\E\]
406  nodes3(x:D04[\E\],y:D14[\E\]):D14[\D23[\E\]\]
407  nodes2(x:D14[\E\]):D13[\D23[\E\]\]
408end
409
410private trait D34[\E\] extends D24[\E\]
411    comprises { D3[\E\], D4[\E\] }
412  getter uncons() : (E,D23[\E\])
413  getter unsnoc() : (D23[\E\],E)
414  nodes3(x:D04[\E\],y:D14[\E\]):D24[\D23[\E\]\]
415  nodes2(x:D14[\E\]):D23[\D23[\E\]\]
416end
417
418private object D0[\E\] extends { D01[\E\] }
419  getter isEmpty():Boolean = true
420  getter asString() = "#"
421  generate[\R\](r: Reduction[\R\], body: E->R): R = r.empty()
422  seqgen[\R\](r: Reduction[\R\], body: E->R): R = r.empty()
423  ivgen[\R\](_: ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R = r.empty()
424  sivgen[\R\](_: ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R = r.empty()
425  cons(e:E):D1[\E\] = D1[\E\](e)
426  snoc(e:E):D1[\E\] = D1[\E\](e)
427  append(f:Deep[\E\]):Deep[\E\] = f
428  addLeft(e:E):FingerTree[\E\] = cons(e)
429  addLeftD(e:D14[\E\]) : FingerTree[\E\] = e.toFinger()
430  addRight(e:E):FingerTree[\E\] = snoc(e)
431  addRightD(e:D14[\E\]): FingerTree[\E\] = e.toFinger()
432  append3(e:D04[\E\], f:Deep[\E\]):FingerTree[\E\] = f.addLeftD(e)
433  leafSize(self):ZZ32 = 0
434  take(_:ZZ32): D0[\E\] = self
435  drop(_:ZZ32): D0[\E\] = self
436  index(_:ZZ32): (ZZ32, E) = fail("D0[] should never be called.")
437  split(_:ZZ32): (D0[\E\],D0[\E\]) = split()
438  split(): (D0[\E\],D0[\E\]) = (self,self)
439  revMap(f:E->E): D0[\E\] = self
440end
441
442private object D1[\E\](a:E)
443    extends { D01[\E\], D12[\E\], NonEmptyFingerTree[\E\] }
444  getter left():Just[\E\] = a
445  getter right():Just[\E\] = a
446  getter extractLeft():(E,FingerTree[\E\]) = self.uncons
447  getter extractRight():Just[\(E,FingerTree[\E\])\] = self.unsnoc
448  getter uncons():(E,D0[\E\]) = (a,D0[\E\])
449  getter unsnoc():(D0[\E\],E) = (D0[\E\],a)
450  getter car() = a
451  getter rac() = a
452  getter asString()= "{" || a || "}"
453  leafSize(self):ZZ32 = leafSize(a)
454  generate[\R\](r: Reduction[\R\], body: E->R): R = body(a)
455  seqgen[\R\](r: Reduction[\R\], body: E->R): R = body(a)
456  ivgen[\R\](leftIndex: ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R =
457      body(leftIndex, a)
458  sivgen[\R\](leftIndex: ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R =
459      body(leftIndex, a)
460  cons(e:E):D2[\E\] = D2[\E\](e,a)
461  snoc(e:E):D2[\E\] = D2[\E\](a,e)
462  append(f:FingerTree[\E\]) = f.addLeftD(self)
463  addLeft(e:E):FingerTree[\E\] = addLeftD(D1[\E\](e))
464  addLeftD(e:D14[\E\]) = Deep[\E\](e,D0[\D23[\E\]\],self)
465  addRight(e:E):FingerTree[\E\] = addRightD(D1[\E\](e))
466  addRightD(e:D14[\E\]) = Deep[\E\](self,D0[\D23[\E\]\],e)
467  append3(e:D04[\E\],f:Deep[\E\]):FingerTree[\E\] = f.addLeftD(e).addLeftD(self)
468  nodes3(x:D04[\E\],y:D14[\E\]):D14[\D23[\E\]\] =
469    fail("Should never be called, shortcoming of comprises handling.")
470  nodes3(x:D4[\E\],y:D14[\E\]):D23[\D23[\E\]\] =
471    D2[\E\](x.c,x.d).nodes2(y).cons(D3[\E\](a,x.a,x.b))
472  nodes3(x:D03[\E\],y:D14[\E\]):D12[\D23[\E\]\] =
473    x.cons(a).nodes2(y)
474  nodes2(x:D14[\E\]):D12[\D23[\E\]\] =
475    fail("Should never be called, shortcoming of comprises handling.")
476  nodes2(x:D4[\E\]):D2[\D23[\E\]\] =
477    D2[\D23[\E\]\](D3[\E\](a,x.a,x.b),D2[\E\](x.c,x.d))
478  nodes2(x:D13[\E\]):D12[\D23[\E\]\] = x.cons(a).nodes1()
479  take(n:ZZ32): D1[\E\] = if n<=0 then fail("D1.take <= 0") else self end
480  drop(n:ZZ32): D1[\E\] =
481      if n < leafSize(a) then
482          self
483      else
484          fail("D1.drop(" n ") >= leafSize()")
485      end
486  split(): (D1[\E\],D0[\E\]) = (self,D0[\E\])
487  split(n:ZZ32): (D1[\E\],D0[\E\]) = if n<=0 then fail("D1.split <= 0")
488                                             else split() end
489  index(n:ZZ32): (ZZ32, E) = (n,a)
490  split3(n:ZZ32): (D0[\E\], E, D0[\E\]) = split3()
491  split3(): (D0[\E\], E, D0[\E\]) = do
492      e = D0[\E\]
493      (e,a,e)
494    end
495  revMap(f:E->E): D1[\E\] = D1[\E\](f(a))
496end
497
498private object D2[\E\](a:E, b:E) extends { D12[\E\], D23[\E\] }
499  ls = leafSize(a) + leafSize(b)
500  getter car() = a
501  getter rac() = b
502  getter uncons():(E,D1[\E\]) = (a,D1[\E\](b))
503  getter unsnoc():(D1[\E\],E) = (D1[\E\](a),b)
504  getter asString()= "(" || a || ", " || b || ")"
505  leafSize(self):ZZ32 = ls
506  generate[\R\](r: Reduction[\R\], body: E->R): R = r.join(body(a),body(b))
507  seqgen[\R\](r: Reduction[\R\], body: E->R): R = do
508      ab = body(a)
509      bb = body(b)
510      r.join(ab,bb)
511    end
512  ivgen[\R\](leftIndex: ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R =
513      r.join(body(leftIndex, a), body(leftIndex+leafSize(a), b))
514  sivgen[\R\](leftIndex: ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R = do
515      ab = body(leftIndex,a)
516      bb = body(leftIndex + leafSize(a), b)
517      r.join(ab,bb)
518    end
519  cons(e:E):D3[\E\] = D3[\E\](e,a,b)
520  snoc(e:E):D3[\E\] = D3[\E\](a,b,e)
521  nodes3(x:D04[\E\],y:D14[\E\]):D14[\D23[\E\]\] =
522    fail("Should never be called, shortcoming of comprises handling.")
523  nodes3(x:D0[\E\],y:D14[\E\]):D14[\D23[\E\]\] =
524    nodes2(y)
525  nodes3(x:D1[\E\],y:D14[\E\]):D14[\D23[\E\]\] =
526    snoc(x.car).nodes2(y)
527  nodes3(x:D24[\E\],y:D14[\E\]):D14[\D23[\E\]\] = do
528      (xh, xt) = x.uncons
529      xt.nodes2(y).cons(D3[\E\](a,b,xh))
530    end
531  nodes2(x:D14[\E\]):D12[\D23[\E\]\] =
532    fail("Should never be called, shortcoming of comprises handling.")
533  nodes2(x:D1[\E\]):D1[\D23[\E\]\] =
534    D1[\D23[\E\]\](self.snoc(x.car))
535  nodes2(x:D2[\E\]):D2[\D23[\E\]\] =
536    D2[\D23[\E\]\](self,x)
537  nodes2(x:D34[\E\]):D12[\D23[\E\]\] = do
538      (xh, xt) = x.uncons
539      xt.nodes1().cons(D3[\E\](a,b,xh))
540    end
541  nodes1():D1[\D23[\E\]\] = D1[\D23[\E\]\](self)
542  toFinger()=Deep[\E\](D1[\E\](a),D0[\D23[\E\]\],D1[\E\](b))
543  take(n:ZZ32): D12[\E\] =
544      if n <= 0 then
545          fail("D2.take <= 0")
546      elif n <= leafSize(a) then
547          D1[\E\](a)
548      else
549          self
550      end
551  drop(n:ZZ32): D12[\E\] =
552      if n < leafSize(a) then
553          self
554      else
555          na = n - leafSize(a)
556          if na < leafSize(b) then
557              D1[\E\](b)
558          else
559              fail("D2.drop(" n ") >= leafSize()")
560          end
561      end
562  index(n:ZZ32): (ZZ32,E) =
563      if n < 0 then
564          fail("D2[" n "] subscript < 0")
565      elif n < leafSize(a) then
566          (n,a)
567      else
568          (n-leafSize(a),b)
569      end
570  split3(n:ZZ32): (D01[\E\], E, D01[\E\]) =
571      if n <= 0 then
572          fail("D2.split3 <= 0")
573      elif n <= leafSize(a) then
574          (D0[\E\], a, D1[\E\](b))
575      else
576          (D1[\E\](a), b, D0[\E\])
577      end
578  split():(D1[\E\],D1[\E\]) = (D1[\E\](a),D1[\E\](b))
579  revMap(f:E->E): D2[\E\] = D2[\E\](f(b),f(a))
580end
581
582private object D3[\E\](a:E, b:E, c:E) extends { D23[\E\], D34[\E\] }
583  ls = leafSize(a) + leafSize(b) + leafSize(c)
584  getter car() = a
585  getter rac() = c
586  getter uncons():(E,D2[\E\]) = (a,D2[\E\](b,c))
587  getter unsnoc():(D2[\E\],E) = (D2[\E\](a,b),c)
588  getter asString() = "(" || a || ", " ||  b || ", " || c || ")"
589  leafSize(self):ZZ32 = ls
590  generate[\R\](r: Reduction[\R\], body: E->R): R =
591    r.join(body(a),r.join(body(b),body(c)))
592  seqgen[\R\](r: Reduction[\R\], body: E->R): R = do
593      ab = body(a)
594      bb = body(b)
595      abb = r.join(ab,bb)
596      cb = body(c)
597      r.join(abb,cb)
598    end
599  ivgen[\R\](leftIndex: ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R = do
600      lib = leftIndex + leafSize(a)
601      lic = lib + leafSize(b)
602      r.join(r.join(body(leftIndex,a),body(lib,b)),body(lic,c))
603    end
604  sivgen[\R\](leftIndex: ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R = do
605      ab = body(leftIndex,a)
606      lib = leftIndex + leafSize(a)
607      bb = body(lib,b)
608      abb = r.join(ab,bb)
609      lic = lib + leafSize(b)
610      cb = body(lic,c)
611      r.join(abb,cb)
612    end
613  cons(e:E):D4[\E\] = D4[\E\](e,a,b,c)
614  snoc(e:E):D4[\E\] = D4[\E\](a,b,c,e)
615  nodes3(x:D04[\E\],y:D14[\E\]):D24[\D23[\E\]\] =
616    x.nodes2(y).cons(self)
617  nodes2(x:D14[\E\]):D13[\D23[\E\]\] =
618    fail("Should never be called, shortcoming of comprises handling.")
619  nodes2(x:D1[\E\]):D23[\D23[\E\]\] =
620    D2[\D23[\E\]\](D2[\E\](a,b),D2[\E\](c,x.car))
621  nodes2(x:D24[\E\]):D23[\D23[\E\]\] =
622    x.nodes1().cons(self)
623  nodes1():D1[\D23[\E\]\] = D1[\D23[\E\]\](self)
624  toFinger()=Deep[\E\](D2[\E\](a,b),D0[\D23[\E\]\],D1[\E\](c))
625  take(n:ZZ32): D13[\E\] =
626      if n <= 0 then
627          fail("D3.take <= 0")
628      elif n <= leafSize(a) then
629          D1[\E\](a)
630      else
631          na = n - leafSize(a)
632          if na <= leafSize(b) then
633              D2[\E\](a,b)
634          else
635              self
636          end
637      end
638  drop(n:ZZ32): D13[\E\] =
639      if n < leafSize(a) then
640          self
641      else
642          na = n - leafSize(a)
643          if na < leafSize(b) then
644              D2[\E\](b,c)
645          else
646              nb = na - leafSize(b)
647              if nb < leafSize(c) then
648                  D1[\E\](c)
649              else
650                  fail("D2.drop(" n ") >= leafSize()")
651              end
652          end
653      end
654  index(n:ZZ32): (ZZ32,E) =
655      if n < 0 then
656          fail("D3[" n "] subscript < 0")
657      elif n < leafSize(a) then
658          (n,a)
659      else
660          na = n - leafSize(a)
661          if na < leafSize(b) then
662              (na,b)
663          else
664              (na-leafSize(b), c)
665          end
666      end
667  split3(n:ZZ32): (D02[\E\], E, D02[\E\]) =
668      if n <= 0 then
669          fail("D3.split3 <= 0")
670      elif n <= leafSize(a) then
671          (D0[\E\], a, D2[\E\](b,c))
672      else
673          na = n - leafSize(a)
674          if na <= leafSize(b) then
675              (D1[\E\](a), b, D1[\E\](c))
676          else
677              (D2[\E\](a,b), c, D0[\E\])
678          end
679      end
680  split():(D2[\E\],D1[\E\]) = (D2[\E\](a,b),D1[\E\](c))
681  revMap(f:E->E): D3[\E\] = D3[\E\](f(c),f(b),f(a))
682end
683
684private object D4[\E\](a:E, b:E, c:E, d:E) extends { D34[\E\] }
685  ls = leafSize(a) + leafSize(b) + leafSize(c) + leafSize(d)
686  getter car() = a
687  getter rac() = d
688  getter uncons():(E,D3[\E\]) = (a,D3[\E\](b,c,d))
689  getter unsnoc():(D3[\E\],E) = (D3[\E\](a,b,c),d)
690  getter asString() = "{" || a || ", " || b || ", " || c || ", " || d || "}"
691  leafSize(self):ZZ32 = ls
692  generate[\R\](r: Reduction[\R\], body: E->R): R =
693    r.join(r.join(body(a),body(b)),r.join(body(c),body(d)))
694  seqgen[\R\](r: Reduction[\R\], body: E->R): R = do
695      ab = body(a)
696      bb = body(b)
697      abb = r.join(ab,bb)
698      cb = body(c)
699      abc = r.join(abb,cb)
700      db = body(d)
701      r.join(abc,db)
702    end
703  ivgen[\R\](leftIndex: ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R = do
704      lib = leftIndex + leafSize(a)
705      lic = lib + leafSize(b)
706      lid = lic + leafSize(c)
707      r.join(r.join(body(leftIndex,a),body(lib,b)),
708             r.join(body(lic,c),body(lid,d)))
709    end
710  sivgen[\R\](leftIndex: ZZ32, r: Reduction[\R\], body: (ZZ32,E)->R): R = do
711      ab = body(leftIndex,a)
712      lib = leftIndex + leafSize(a)
713      bb = body(lib,b)
714      abb = r.join(ab,bb)
715      lic = lib + leafSize(b)
716      cb = body(lic,c)
717      abc = r.join(abb,cb)
718      lid = lic + leafSize(c)
719      db = body(lid,d)
720      r.join(abc,db)
721    end
722  nodes3(x:D04[\E\],y:D14[\E\]):D24[\D23[\E\]\] =
723    D1[\E\](d).nodes3(x,y).cons(D3[\E\](a,b,c))
724  nodes2(x:D14[\E\]):D23[\D23[\E\]\] =
725    D1[\E\](d).nodes2(x).cons(D3[\E\](a,b,c))
726  nodes1():D2[\D23[\E\]\] = D2[\D23[\E\]\](D2[\E\](a,b),D2[\E\](c,d))
727  toFinger()=Deep[\E\](D2[\E\](a,b),D0[\D23[\E\]\],D2[\E\](c,d))
728  take(n:ZZ32): D14[\E\] =
729      if n <= 0 then
730          fail("D4.take <= 0")
731      elif n <= leafSize(a) then
732          D1[\E\](a)
733      else
734          na = n - leafSize(a)
735          if na <= leafSize(b) then
736              D2[\E\](a,b)
737          else
738              nb = na - leafSize(b)
739              if nb <= leafSize(c) then
740                  D3[\E\](a,b,c)
741              else
742                  self
743              end
744          end
745      end
746  drop(n:ZZ32): D14[\E\] =
747      if n < leafSize(a) then
748          self
749      else
750          na = n - leafSize(a)
751          if na < leafSize(b) then
752              D3[\E\](b,c,d)
753          else
754              nb = na - leafSize(b)
755              if nb < leafSize(c) then
756                  D2[\E\](c,d)
757              else
758                  nc = nb - leafSize(c)
759                  if nc < leafSize(d) then
760                      D1[\E\](d)
761                  else
762                      fail("D2.drop(" n ") >= leafSize()")
763                  end
764              end
765          end
766      end
767  index(n:ZZ32): (ZZ32,E) =
768      if n < 0 then
769          fail("D3[" n "] subscript < 0")
770      elif n < leafSize(a) then
771          (n,a)
772      else
773          na = n - leafSize(a)
774          if na < leafSize(b) then
775              (na,b)
776          else
777              nb = na - leafSize(b)
778              if nb < leafSize(c) then
779                  (nb,c)
780              else
781                  (nb-leafSize(c), d)
782              end
783          end
784      end
785  split3(n:ZZ32): (D03[\E\], E, D03[\E\]) =
786      if n <= 0 then
787          fail("D4.split3 <= 0")
788      elif n <= leafSize(a) then
789          (D0[\E\], a, D3[\E\](b,c,d))
790      else
791          na = n - leafSize(a)
792          if na <= leafSize(b) then
793              (D1[\E\](a), b, D2[\E\](c,d))
794          else
795              nb = na - leafSize(b)
796              if nb <= leafSize(c) then
797                  (D2[\E\](a,b), c, D1[\E\](d))
798              else
799                  (D3[\E\](a,b,c), d, D0[\E\])
800              end
801          end
802      end
803  split():(D2[\E\],D2[\E\]) = (D2[\E\](a,b),D2[\E\](c,d))
804  revMap(f:E->E): D4[\E\] = D4[\E\](f(d),f(c),f(b),f(a))
805end
806
807private object Deep[\E\]
808           (l:D14[\E\], m:FingerTree[\ D23[\E\] \], r:D14[\E\])
809    extends { NonEmptyFingerTree[\E\] }
810  ls = leafSize(l)+leafSize(m)+leafSize(r)
811  getter left():Just[\E\] = l.car
812  getter right():Just[\E\] = r.rac
813  getter extractLeft():(E,FingerTree[\E\]) = extractLeft1(l,m)
814  getter extractRight():(FingerTree[\E\],E) = extractRight1(r,m)
815  getter asString() = "[" l.asString ";" m.asString ";" r.asString "]"
816
817  leafSize(self):ZZ32 = ls
818  generate[\R\](j: Reduction[\R\], body: E->R): R = do
819      j.join(
820       j.join(l.generate[\R\](j,body),
821              m.generate[\R\](j,fn (n23:D23[\E\]):R =>
822                                    n23.generate[\R\](j,body))),
823       r.generate[\R\](j,body))
824    end
825  seqgen[\R\](j: Reduction[\R\], body: E->R): R = do
826      gl = l.seqgen[\R\](j,body)
827      ml = m.seqgen[\R\](j,fn (n23:D23[\E\]):R =>
828                               n23.seqgen[\R\](j,body))
829      ll = j.join(gl,ml)
830      rl = r.seqgen[\R\](j,body)
831      j.join(ll,rl)
832    end
833  ivgen[\R\](li: ZZ32, j: Reduction[\R\], body: (ZZ32,E)->R): R = do
834      mi = li + leafSize(l)
835      ri = mi + leafSize(m)
836      j.join(
837       j.join(l.ivgen[\R\](li,j,body),
838              m.ivgen[\R\](mi,j,fn (li':ZZ32, n23:D23[\E\]):R =>
839                                    n23.ivgen[\R\](li',j,body))),
840       r.ivgen[\R\](ri,j,body))
841    end
842  sivgen[\R\](li: ZZ32, j: Reduction[\R\], body: (ZZ32,E)->R): R = do
843      gl = l.sivgen[\R\](li,j,body)
844      mi = li + leafSize(l)
845      ml = m.sivgen[\R\](mi,j,fn (li':ZZ32, n23:D23[\E\]):R =>
846                                  n23.sivgen[\R\](li',j,body))
847      ll = j.join(gl,ml)
848      ri = mi + leafSize(m)
849      rl = r.sivgen[\R\](ri,j,body)
850      j.join(ll,rl)
851    end
852
853  addLeft(e:E):FingerTree[\E\] = addLeft1(e,l)
854  addLeft1(e:E,l0:D4[\E\]) =
855        Deep[\E\](D2[\E\](e,l0.a),m.addLeft(D3[\E\](l0.b,l0.c,l0.d)),r)
856  addLeft1(e:E,l0:D03[\E\]) = Deep[\E\](l0.cons(e),m,r)
857  addLeftD(e:D14[\E\]) : FingerTree[\E\] = do
858      (ef,er) = e.unsnoc
859      addLeft(er).addLeftD(ef)
860    end
861  addRight(e:E):FingerTree[\E\] = addRight1(e,r)
862  addRight1(e:E,r0:D4[\E\]) =
863      Deep[\E\](l,m.addRight(D3[\E\](r0.a,r0.b,r0.c)),D2[\E\](r0.d,e))
864  addRight1(e:E,r0:D03[\E\]) = Deep[\E\](l,m,r.snoc(e))
865  addRightD(e:D14[\E\]) : FingerTree[\E\] = do
866      (ef,er) = e.uncons
867      addRight(ef).addRightD(er)
868    end
869
870  (* Helper methods for extractLeft and extractRight *)
871  extractLeft1(l0:D1[\E\], m0:D0[\D23[\E\]\]) = (l0.car,r.toFinger())
872  extractLeft1(l0:D1[\E\], m0:NonEmptyFingerTree[\D23[\E\]\]) = do
873      (l1,m1) = m0.extractLeft
874      (l0.car,Deep[\E\](l1,m1,r))
875    end
876  extractLeft1(l0:D24[\E\], m0:FingerTree[\D23[\E\]\]) = do
877      (f,l1) = l0.uncons
878      (f,Deep[\E\](l1,m0,r))
879    end
880  extractRight1(r0:D1[\E\], m0:D0[\D23[\E\]\]) = (l.toFinger(),r0.rac)
881  extractRight1(r0:D1[\E\], m0:NonEmptyFingerTree[\D23[\E\]\]) = do
882      (m1,r1) = m0.extractRight
883      (Deep[\E\](l,m1,r1),r0.rac)
884    end
885  extractRight1(r0:D24[\E\], m0:FingerTree[\D23[\E\]\]) = do
886      (r1,b) = r0.unsnoc
887      (Deep[\E\](l,m0,r1),b)
888    end
889
890  append(f:Deep[\E\]) : FingerTree[\E\] =
891      Deep[\E\](l,m.append3(r.nodes2(f.l),f.m),f.r)
892  append3(e:D04[\E\], f:Deep[\E\]):FingerTree[\E\] =
893      Deep[\E\](l,m.append3(r.nodes3(e,f.l),f.m),f.r)
894
895  take(n:ZZ32): FingerTree[\E\] =
896      if n <= 0 then
897          fail("Deep.take " n " <= 0")
898      elif n <= leafSize(l) then
899          l.take(n).toFinger()
900      else
901          takeM(n - leafSize(l), m)
902      end
903  takeM(n:ZZ32, m0:D0[\D23[\E\]\]): FingerTree[\E\] = takeR(n)
904  takeM(n:ZZ32, m0:NonEmptyFingerTree[\D23[\E\]\]): FingerTree[\E\] =
905      if n <= leafSize(m0) then
906          (mm,mr) = m0.take(n).extractRight
907          deepR[\E\](l,mm,mr.take(n - leafSize(mm)))
908      else
909          takeR(n - leafSize(m0))
910      end
911  takeR(n:ZZ32): FingerTree[\E\] = Deep[\E\](l,m,r.take(n))
912  drop(n:ZZ32): NonEmptyFingerTree[\E\] =
913      if n <= 0 then
914          self
915      elif n < leafSize(l) then
916          Deep[\E\](l.drop(n),m,r)
917      else
918          dropM(n - leafSize(l), m)
919      end
920  dropM(n:ZZ32,_:D0[\D23[\E\]\]): NonEmptyFingerTree[\E\] = dropR(n)
921  dropM(n:ZZ32,m0:NonEmptyFingerTree[\D23[\E\]\]): NonEmptyFingerTree[\E\] =
922      if n < leafSize(m0) then
923          md = m0.drop(n)
924          (ml,mm) = md.extractLeft
925          deepL[\E\](ml.drop(n-(leafSize(m0)-leafSize(md))),mm,r)
926      else
927          dropR(n - leafSize(m0))
928      end
929  dropR(n:ZZ32) =
930      if n < leafSize(r) then
931          r.drop(n).toFinger()
932      else
933          fail("Deep.drop(" n ") too large")
934      end
935  split(n:ZZ32): (FingerTree[\E\], FingerTree[\E\]) = do
936      (ll,mm,rr) = split3(n)
937      (ll.addRight(mm),rr)
938    end
939  split(): (FingerTree[\E\], FingerTree[\E\]) = do
940      (ll, rr) = m.split()
941      (deepR[\E\](l,ll,D0[\E\]), deepL[\E\](D0[\E\],rr,r))
942    end
943  index(n:ZZ32): (ZZ32,E) =
944      if n < 0 then
945          fail("Deep[" n "]: negative index")
946      elif n < leafSize(l) then
947          l.index(n)
948      else
949          nm = n - leafSize(l)
950          if nm < leafSize(m) then
951              (nm0,mm) = m.index(nm)
952              mm.index(nm0)
953          else
954              nr = nm - leafSize(m)
955              r.index(nr)
956          end
957      end
958  split3(n:ZZ32): (FingerTree[\E\], E, FingerTree[\E\]) =
959      if n <= 0 then
960          fail("Deep.split3 n<=0 should not happen.")
961      elif n <= leafSize(l) then
962          (ll,lm,lr) = l.split3(n)
963          (ll.toFinger(), lm, deepL[\E\](lr,m,r))
964      else
965          nm = n - leafSize(l)
966          if nm <= leafSize(m) then
967              (ml,mm,mr) = m.split3(nm)
968              ne = nm - leafSize(ml)
969              (ll,e,rr) = mm.split3(ne)
970              (deepR[\E\](l,ml,ll), e, deepL[\E\](rr,mr,r))
971          else
972              nr = nm - leafSize(m)
973              (rl,rm,rr) = r.split3(nr)
974              (deepR[\E\](l,m,rl), rm, rr.toFinger())
975          end
976      end
977  revMap(f: E->E): Deep[\E\] =
978      Deep[\E\](r.revMap(f),
979                m.revMap(fn (x:D23[\E\]):D23[\E\] => x.revMap(f)),
980                l.revMap(f))
981end
982
983deepL[\E\](l:D14[\E\],m:FingerTree[\D23[\E\]\],r:D14[\E\]):NonEmptyFingerTree[\E\] =
984    Deep[\E\](l,m,r)
985deepL[\E\](_:D0[\E\],_:D0[\D23[\E\]\],r:D14[\E\]):FingerTree[\E\] = r.toFinger()
986deepL[\E\](_:D0[\E\],m:NonEmptyFingerTree[\D23[\E\]\],r:D14[\E\]):NonEmptyFingerTree[\E\] = do
987    (ll,mm) = m.extractLeft
988    Deep[\E\](ll,mm,r)
989  end
990
991deepR[\E\](l:D14[\E\],m:FingerTree[\D23[\E\]\],r:D14[\E\]):NonEmptyFingerTree[\E\] =
992    Deep[\E\](l,m,r)
993deepR[\E\](l:D14[\E\],_:D0[\D23[\E\]\],_:D0[\E\]):FingerTree[\E\] = l.toFinger()
994deepR[\E\](l:D14[\E\],m:NonEmptyFingerTree[\D23[\E\]\],_:D0[\E\]):NonEmptyFingerTree[\E\] = do
995    (mm,rr) = m.extractRight
996    Deep[\E\](l,mm,rr)
997  end
998
999end
Note: See TracBrowser for help on using the browser.