001    package fj.data.fingertrees;
002    
003    import fj.F;
004    import fj.Function;
005    import fj.P2;
006    import fj.pre.Ord;
007    import fj.data.vector.V2;
008    import fj.data.vector.V3;
009    import fj.data.vector.V4;
010    import static fj.data.List.list;
011    import static fj.Function.flip;
012    
013    /**
014     * A finger tree with 1-4-digits on the left and right, and a finger tree of 2-3-nodes in the middle.
015     */
016    public final class Deep<V, A> extends FingerTree<V, A> {
017      private final V v;
018      private final Digit<V, A> prefix;
019      private final FingerTree<V, Node<V, A>> middle;
020      private final Digit<V, A> suffix;
021    
022      Deep(final Measured<V, A> m, final V v, final Digit<V, A> prefix,
023           final FingerTree<V, Node<V, A>> middle,
024           final Digit<V, A> suffix) {
025        super(m);
026        this.v = v;
027        this.prefix = prefix;
028        this.middle = middle;
029        this.suffix = suffix;
030      }
031    
032      /**
033       * Returns the first few elements of this tree.
034       *
035       * @return the first few elements of this tree.
036       */
037      public Digit<V, A> prefix() {
038        return prefix;
039      }
040    
041      /**
042       * Returns a finger tree of the inner nodes of this tree.
043       *
044       * @return a finger tree of the inner nodes of this tree.
045       */
046      public FingerTree<V, Node<V, A>> middle() {
047        return middle;
048      }
049    
050      /**
051       * Returns the last few elements of this tree.
052       *
053       * @return the last few elements of this tree.
054       */
055      public Digit<V, A> suffix() {
056        return suffix;
057      }
058    
059      /**
060       * @see fj.data.fingertrees.FingerTree#foldRight(fj.F, Object)
061       */
062      @Override public <B> B foldRight(final F<A, F<B, B>> aff, final B z) {
063        return prefix.foldRight(aff, middle.foldRight(flip(Node.<V, A, B>foldRight_(aff)), suffix.foldRight(aff, z)));
064      }
065    
066      /**
067       * @see fj.data.fingertrees.FingerTree#reduceRight(fj.F)
068       */
069      @Override public A reduceRight(final F<A, F<A, A>> aff) {
070        return prefix.foldRight(aff, middle.foldRight(flip(Node.<V, A, A>foldRight_(aff)), suffix.reduceRight(aff)));
071      }
072    
073      @Override public <B> B foldLeft(final F<B, F<A, B>> bff, final B z) {
074        return suffix.foldLeft(bff, middle.foldLeft(Node.<V, A, B>foldLeft_(bff), prefix.foldLeft(bff, z)));
075      }
076    
077      @Override public A reduceLeft(final F<A, F<A, A>> aff) {
078        return suffix.foldLeft(aff, middle.foldLeft(Node.<V, A, A>foldLeft_(aff), prefix.reduceLeft(aff)));
079      }
080    
081      @Override public <B> FingerTree<V, B> map(final F<A, B> abf, final Measured<V, B> m) {
082        return new Deep<V, B>(m, v, prefix.map(abf, m), middle.map(Node.<V, A, B>liftM(abf, m), m.nodeMeasured()),
083                              suffix.map(abf, m));
084      }
085    
086      /**
087       * Returns the sum of the measurements of this tree's elements, according to the monoid.
088       *
089       * @return the sum of the measurements of this tree's elements, according to the monoid.
090       */
091      public V measure() {
092        return v;
093      }
094    
095      /**
096       * Pattern matching on the tree. Matches the function on the Deep tree.
097       */
098      @Override public <B> B match(final F<Empty<V, A>, B> empty, final F<Single<V, A>, B> single,
099                                   final F<fj.data.fingertrees.Deep<V, A>, B> deep) {
100        return deep.f(this);
101      }
102    
103      @Override public FingerTree<V, A> cons(final A a) {
104        final Measured<V, A> m = measured();
105        final V measure = m.sum(m.measure(a), v);
106        final MakeTree<V, A> mk = mkTree(m);
107        return prefix.match(new F<One<V, A>, FingerTree<V, A>>() {
108          public FingerTree<V, A> f(final One<V, A> one) {
109            return new Deep<V, A>(m, measure, mk.two(a, one.value()), middle, suffix);
110          }
111        }, new F<Two<V, A>, FingerTree<V, A>>() {
112          public FingerTree<V, A> f(final Two<V, A> two) {
113            return new Deep<V, A>(m, measure, mk.three(a, two.values()._1(), two.values()._2()), middle, suffix);
114          }
115        }, new F<Three<V, A>, FingerTree<V, A>>() {
116          public FingerTree<V, A> f(final Three<V, A> three) {
117            return new Deep<V, A>(m, measure, mk.four(a, three.values()._1(), three.values()._2(),
118                                                      three.values()._3()), middle, suffix);
119          }
120        }, new F<Four<V, A>, FingerTree<V, A>>() {
121          public FingerTree<V, A> f(final Four<V, A> four) {
122            return new Deep<V, A>(m, measure, mk.two(a, four.values()._1()),
123                                  middle.cons(mk.node3(four.values()._2(), four.values()._3(), four.values()._4())),
124                                  suffix);
125          }
126        });
127      }
128    
129      public FingerTree<V, A> snoc(final A a) {
130        final Measured<V, A> m = measured();
131        final V measure = m.sum(m.measure(a), v);
132        final MakeTree<V, A> mk = mkTree(m);
133        return suffix.match(new F<One<V, A>, FingerTree<V, A>>() {
134          public FingerTree<V, A> f(final One<V, A> one) {
135            return new Deep<V, A>(m, measure, prefix, middle, mk.two(one.value(), a));
136          }
137        }, new F<Two<V, A>, FingerTree<V, A>>() {
138          public FingerTree<V, A> f(final Two<V, A> two) {
139            return new Deep<V, A>(m, measure, prefix, middle, mk.three(two.values()._1(), two.values()._2(), a));
140          }
141        }, new F<Three<V, A>, FingerTree<V, A>>() {
142          public FingerTree<V, A> f(final Three<V, A> three) {
143            return new Deep<V, A>(m, measure, prefix, middle, mk.four(three.values()._1(), three.values()._2(),
144                                                                      three.values()._3(), a));
145          }
146        }, new F<Four<V, A>, FingerTree<V, A>>() {
147          public FingerTree<V, A> f(final Four<V, A> four) {
148            return new Deep<V, A>(m, measure, prefix,
149                                  middle.snoc(mk.node3(four.values()._1(), four.values()._2(), four.values()._3())),
150                                  mk.two(four.values()._4(), a));
151          }
152        });
153      }
154    
155      @Override public FingerTree<V, A> append(final FingerTree<V, A> t) {
156        final Measured<V, A> m = measured();
157        return t.match(Function.<Empty<V, A>, FingerTree<V, A>>constant(t), new F<Single<V, A>, FingerTree<V, A>>() {
158          public FingerTree<V, A> f(final Single<V, A> single) {
159            return t.snoc(single.value());
160          }
161        }, new F<Deep<V, A>, FingerTree<V, A>>() {
162          public FingerTree<V, A> f(final Deep<V, A> deep) {
163            return new Deep<V, A>(m, m.sum(measure(), deep.measure()), prefix,
164                                  addDigits0(m, middle, suffix, deep.prefix, deep.middle), deep.suffix);
165          }
166        });
167      }
168    
169      @Override public P2<Integer, A> lookup(final F<V, Integer> o, final int i) {
170        final int spr = o.f(prefix.measure());
171        final int spm = o.f(middle.measure());
172        if (i < spr)
173            return null; // TODO
174          //return prefix.lookup(o, i);
175        if (i < spm) {
176          return null; // TODO
177          /* final P2<Integer, Node<V, A>> p = middle.lookup(o, i - spr);
178          return p._2().lookup(o, p._1()); */
179        }
180        return null; // TODO suffix.lookup(i - spm);
181      }
182    
183      private static <V, A> FingerTree<V, Node<V, A>> addDigits0(final Measured<V, A> m, final FingerTree<V, Node<V, A>> m1,
184                                                                 final Digit<V, A> s1, final Digit<V, A> p2,
185                                                                 final FingerTree<V, Node<V, A>> m2) {
186        final MakeTree<V, A> mk = mkTree(m);
187        return s1.match(new F<One<V, A>, FingerTree<V, Node<V, A>>>() {
188          public FingerTree<V, Node<V, A>> f(final One<V, A> one1) {
189            return p2.match(new F<One<V, A>, FingerTree<V, Node<V, A>>>() {
190              public FingerTree<V, Node<V, A>> f(final One<V, A> one2) {
191                return append1(m, m1, mk.node2(one1.value(), one2.value()), m2);
192              }
193            }, new F<Two<V, A>, FingerTree<V, Node<V, A>>>() {
194              public FingerTree<V, Node<V, A>> f(final Two<V, A> two2) {
195                final V2<A> vs = two2.values();
196                return append1(m, m1, mk.node3(one1.value(), vs._1(), vs._2()), m2);
197              }
198            }, new F<Three<V, A>, FingerTree<V, Node<V, A>>>() {
199              public FingerTree<V, Node<V, A>> f(final Three<V, A> three) {
200                final V3<A> vs = three.values();
201                return append2(m, m1, mk.node2(one1.value(), vs._1()), mk.node2(vs._2(), vs._3()), m2);
202              }
203            }, new F<Four<V, A>, FingerTree<V, Node<V, A>>>() {
204              public FingerTree<V, Node<V, A>> f(final Four<V, A> four) {
205                final V4<A> vs = four.values();
206                return append2(m, m1, mk.node3(one1.value(), vs._1(), vs._2()), mk.node2(vs._3(), vs._4()), m2);
207              }
208            });
209          }
210        }, new F<Two<V, A>, FingerTree<V, Node<V, A>>>() {
211          public FingerTree<V, Node<V, A>> f(final Two<V, A> two1) {
212            final V2<A> v1 = two1.values();
213            return p2.match(new F<One<V, A>, FingerTree<V, Node<V, A>>>() {
214              public FingerTree<V, Node<V, A>> f(final One<V, A> one) {
215                return append1(m, m1, mk.node3(v1._1(), v1._2(), one.value()), m2);
216              }
217            }, new F<Two<V, A>, FingerTree<V, Node<V, A>>>() {
218              public FingerTree<V, Node<V, A>> f(final Two<V, A> two2) {
219                final V2<A> v2 = two2.values();
220                return append2(m, m1, mk.node2(v1._1(), v1._2()), mk.node2(v2._1(), v2._2()), m2);
221              }
222            }, new F<Three<V, A>, FingerTree<V, Node<V, A>>>() {
223              public FingerTree<V, Node<V, A>> f(final Three<V, A> three) {
224                final V3<A> v2 = three.values();
225                return append2(m, m1, mk.node3(v1._1(), v1._2(), v2._1()), mk.node2(v2._2(), v2._3()), m2);
226              }
227            }, new F<Four<V, A>, FingerTree<V, Node<V, A>>>() {
228              public FingerTree<V, Node<V, A>> f(final Four<V, A> four) {
229                final V4<A> v2 = four.values();
230                return append2(m, m1, mk.node3(v1._1(), v1._2(), v2._1()), mk.node3(v2._2(), v2._3(), v2._4()), m2);
231              }
232            });
233          }
234        }, new F<Three<V, A>, FingerTree<V, Node<V, A>>>() {
235          public FingerTree<V, Node<V, A>> f(final Three<V, A> three1) {
236            final V3<A> v1 = three1.values();
237            return p2.match(new F<One<V, A>, FingerTree<V, Node<V, A>>>() {
238              public FingerTree<V, Node<V, A>> f(final One<V, A> one) {
239                return append2(m, m1, mk.node2(v1._1(), v1._2()), mk.node2(v1._3(), one.value()), m2);
240              }
241            }, new F<Two<V, A>, FingerTree<V, Node<V, A>>>() {
242              public FingerTree<V, Node<V, A>> f(final Two<V, A> two) {
243                V2<A> v2 = two.values();
244                return append2(m, m1, mk.node3(v1), mk.node2(v2), m2);
245              }
246            }, new F<Three<V, A>, FingerTree<V, Node<V, A>>>() {
247              public FingerTree<V, Node<V, A>> f(final Three<V, A> three2) {
248                return append2(m, m1, mk.node3(v1), mk.node3(three2.values()), m2);
249              }
250            }, new F<Four<V, A>, FingerTree<V, Node<V, A>>>() {
251              public FingerTree<V, Node<V, A>> f(final Four<V, A> four) {
252                return append3(m, m1, mk.node3(v1), mk.node2(four.values()._1(), four.values()._2()),
253                               mk.node2(four.values()._3(), four.values()._4()), m2);
254              }
255            });
256          }
257        }, new F<Four<V, A>, FingerTree<V, Node<V, A>>>() {
258          public FingerTree<V, Node<V, A>> f(final Four<V, A> four1) {
259            final V4<A> v1 = four1.values();
260            return p2.match(new F<One<V, A>, FingerTree<V, Node<V, A>>>() {
261              public FingerTree<V, Node<V, A>> f(final One<V, A> one) {
262                return append2(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node2(v1._4(), one.value()), m2);
263              }
264            }, new F<Two<V, A>, FingerTree<V, Node<V, A>>>() {
265              public FingerTree<V, Node<V, A>> f(final Two<V, A> two) {
266                final V2<A> v2 = two.values();
267                return append2(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), v2._1(), v2._2()), m2);
268              }
269            }, new F<Three<V, A>, FingerTree<V, Node<V, A>>>() {
270              public FingerTree<V, Node<V, A>> f(final Three<V, A> three) {
271                final V3<A> v2 = three.values();
272                return append3(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node2(v1._4(), v2._1()),
273                               mk.node2(v2._2(), v2._3()), m2);
274              }
275            }, new F<Four<V, A>, FingerTree<V, Node<V, A>>>() {
276              public FingerTree<V, Node<V, A>> f(final Four<V, A> four2) {
277                final V4<A> v2 = four2.values();
278                return append3(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), v2._1(), v2._2()),
279                               mk.node2(v2._3(), v2._4()), m2);
280              }
281            });
282          }
283        });
284      }
285    
286      private static <V, A> FingerTree<V, Node<V, A>> append1(final Measured<V, A> m, final FingerTree<V, Node<V, A>> xs,
287                                                              final Node<V, A> a, final FingerTree<V, Node<V, A>> ys) {
288        return xs.match(new F<Empty<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
289          public FingerTree<V, Node<V, A>> f(final Empty<V, Node<V, A>> empty) {
290            return ys.cons(a);
291          }
292        }, new F<Single<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
293          public FingerTree<V, Node<V, A>> f(final Single<V, Node<V, A>> single) {
294            return ys.cons(a).cons(single.value());
295          }
296        }, new F<Deep<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
297          public FingerTree<V, Node<V, A>> f(final Deep<V, Node<V, A>> deep1) {
298            return ys.match(new F<Empty<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
299              public FingerTree<V, Node<V, A>> f(final Empty<V, Node<V, A>> empty) {
300                return xs.snoc(a);
301              }
302            }, new F<Single<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
303              public FingerTree<V, Node<V, A>> f(final Single<V, Node<V, A>> single) {
304                return xs.snoc(a).snoc(single.value());
305              }
306            }, new F<Deep<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
307              public FingerTree<V, Node<V, A>> f(final Deep<V, Node<V, A>> deep2) {
308                Measured<V, Node<V, A>> nm = m.nodeMeasured();
309                return new Deep<V, Node<V, A>>(nm, m.sum(m.sum(deep1.v, nm.measure(a)), deep2.v), deep1.prefix,
310                                               addDigits1(nm, deep1.middle, deep1.suffix, a, deep2.prefix, deep2.middle),
311                                               deep2.suffix);
312              }
313            });
314          }
315        });
316      }
317    
318      private static <V, A> FingerTree<V, Node<V, Node<V, A>>> addDigits1(final Measured<V, Node<V, A>> m,
319                                                                          final FingerTree<V, Node<V, Node<V, A>>> m1,
320                                                                          final Digit<V, Node<V, A>> x, final Node<V, A> n,
321                                                                          final Digit<V, Node<V, A>> y,
322                                                                          final FingerTree<V, Node<V, Node<V, A>>> m2) {
323        final MakeTree<V, Node<V, A>> mk = mkTree(m);
324        return x.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
325          public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one1) {
326            return y.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
327              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one2) {
328                return append1(m, m1, mk.node3(one1.value(), n, one2.value()), m2);
329              }
330            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
331              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
332                return append2(m, m1, mk.node2(one1.value(), n), mk.node2(two.values()), m2);
333              }
334            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
335              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
336                final V3<Node<V, A>> v2 = three.values();
337                return append2(m, m1, mk.node3(one1.value(), n, v2._1()), mk.node2(v2._2(), v2._3()), m2);
338              }
339            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
340              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
341                final V4<Node<V, A>> v2 = four.values();
342                return append2(m, m1, mk.node3(one1.value(), n, v2._1()), mk.node3(v2._2(), v2._3(), v2._4()), m2);
343              }
344            });
345          }
346        }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
347          public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two1) {
348            final V2<Node<V, A>> v1 = two1.values();
349            return y.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
350              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
351                return append2(m, m1, mk.node2(v1), mk.node2(n, one.value()), m2);
352              }
353            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
354              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
355                return append2(m, m1, mk.node3(v1._1(), v1._2(), n), mk.node2(two.values()), m2);
356              }
357            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
358              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
359                return append2(m, m1, mk.node3(v1._1(), v1._2(), n), mk.node3(three.values()), m2);
360              }
361            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
362              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
363                final V4<Node<V, A>> v2 = four.values();
364                return append3(m, m1, mk.node3(v1._1(), v1._2(), n), mk.node2(v2._1(), v2._2()), mk.node2(v2._3(), v2._4()),
365                               m2);
366              }
367            });
368          }
369        }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
370          public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
371            final V3<Node<V, A>> v1 = three.values();
372            return y.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
373              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
374                return append2(m, m1, mk.node3(v1), mk.node2(n, one.value()), m2);
375              }
376            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
377              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
378                final V2<Node<V, A>> v2 = two.values();
379                return append2(m, m1, mk.node3(v1), mk.node3(n, v2._1(), v2._2()), m2);
380              }
381            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
382              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
383                final V3<Node<V, A>> v2 = three.values();
384                return append3(m, m1, mk.node3(v1), mk.node2(n, v2._1()), mk.node2(v2._2(), v2._3()), m2);
385              }
386            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
387              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
388                final V4<Node<V, A>> v2 = four.values();
389                return append3(m, m1, mk.node3(v1), mk.node3(n, v2._1(), v2._2()), mk.node2(v2._3(), v2._4()), m2);
390              }
391            });
392          }
393        }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
394          public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
395            final V4<Node<V, A>> v1 = four.values();
396            return y.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
397              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
398                return append2(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n, one.value()), m2);
399              }
400            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
401              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
402                return append3(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node2(v1._4(), n), mk.node2(two.values()),
403                               m2);
404              }
405            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
406              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
407                final V3<Node<V, A>> v2 = three.values();
408                return append3(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n, v2._1()),
409                               mk.node2(v2._2(), v2._3()), m2);
410              }
411            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
412              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
413                final V4<Node<V, A>> v2 = four.values();
414                return append3(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n, v2._1()),
415                               mk.node3(v2._2(), v2._3(), v2._4()), m2);
416              }
417            });
418          }
419        });
420      }
421    
422      private static <V, A> FingerTree<V, Node<V, A>> append2(final Measured<V, A> m, final FingerTree<V, Node<V, A>> t1,
423                                                              final Node<V, A> n1, final Node<V, A> n2,
424                                                              final FingerTree<V, Node<V, A>> t2) {
425        return t1.match(new F<Empty<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
426          public FingerTree<V, Node<V, A>> f(final Empty<V, Node<V, A>> empty) {
427            return t2.cons(n2).cons(n1);
428          }
429        }, new F<Single<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
430          public FingerTree<V, Node<V, A>> f(final Single<V, Node<V, A>> single) {
431            return t2.cons(n2).cons(n1).cons(single.value());
432          }
433        }, new F<Deep<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
434          public FingerTree<V, Node<V, A>> f(final Deep<V, Node<V, A>> deep) {
435            return t2.match(new F<Empty<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
436              public FingerTree<V, Node<V, A>> f(final Empty<V, Node<V, A>> empty) {
437                return deep.snoc(n1).snoc(n2);
438              }
439            }, new F<Single<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
440              public FingerTree<V, Node<V, A>> f(final Single<V, Node<V, A>> single) {
441                return deep.snoc(n1).snoc(n2).snoc(single.value());
442              }
443            }, new F<Deep<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
444              public FingerTree<V, Node<V, A>> f(final Deep<V, Node<V, A>> deep2) {
445                return new Deep<V, Node<V, A>>(m.nodeMeasured(),
446                                               m.sum(m.sum(m.sum(deep.measure(), n1.measure()), n2.measure()),
447                                                     deep2.measure()), deep.prefix,
448                                               addDigits2(m.nodeMeasured(), deep.middle, deep.suffix, n1, n2, deep2.prefix,
449                                                          deep2.middle), deep2.suffix);
450              }
451            });
452          }
453        });
454      }
455    
456      private static <V, A> FingerTree<V, Node<V, Node<V, A>>> addDigits2(final Measured<V, Node<V, A>> m,
457                                                                          final FingerTree<V, Node<V, Node<V, A>>> m1,
458                                                                          final Digit<V, Node<V, A>> suffix,
459                                                                          final Node<V, A> n1, final Node<V, A> n2,
460                                                                          final Digit<V, Node<V, A>> prefix,
461                                                                          final FingerTree<V, Node<V, Node<V, A>>> m2) {
462        final MakeTree<V, Node<V, A>> mk = mkTree(m);
463        return suffix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
464          public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
465            return prefix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
466              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one2) {
467                return append2(m, m1, mk.node2(one.value(), n1), mk.node2(n2, one2.value()), m2);
468              }
469            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
470              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
471                return append2(m, m1, mk.node3(one.value(), n1, n2), mk.node2(two.values()), m2);
472              }
473            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
474              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
475                return append2(m, m1, mk.node3(one.value(), n1, n2), mk.node3(three.values()), m2);
476              }
477            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
478              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
479                final V4<Node<V, A>> v2 = four.values();
480                return append3(m, m1, mk.node3(one.value(), n1, n2), mk.node2(v2._1(), v2._2()), mk.node2(v2._3(), v2._4()),
481                               m2);
482              }
483            });
484          }
485        }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
486          public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
487            final V2<Node<V, A>> v1 = two.values();
488            return prefix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
489              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
490                return append2(m, m1, mk.node3(v1._1(), v1._2(), n1), mk.node2(n2, one.value()), m2);
491              }
492            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
493              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two2) {
494                final V2<Node<V, A>> v2 = two2.values();
495                return append2(m, m1, mk.node3(v1._1(), v1._2(), n1), mk.node3(n2, v2._1(), v2._2()), m2);
496              }
497            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
498              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
499                final V3<Node<V, A>> v2 = three.values();
500                return append3(m, m1, mk.node3(v1._1(), v1._2(), n1), mk.node2(n2, v2._1()), mk.node2(v2._2(), v2._3()),
501                               m2);
502              }
503            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
504              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
505                final V4<Node<V, A>> v2 = four.values();
506                return append3(m, m1, mk.node3(v1._1(), v1._2(), n1), mk.node3(n2, v2._1(), v2._2()),
507                               mk.node2(v2._3(), v2._4()), m2);
508              }
509            });
510          }
511        }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
512          public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
513            final V3<Node<V, A>> v1 = three.values();
514            return prefix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
515              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
516                return append2(m, m1, mk.node3(v1), mk.node3(n1, n2, one.value()), m2);
517              }
518            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
519              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
520                return append3(m, m1, mk.node3(v1), mk.node2(n1, n2), mk.node2(two.values()), m2);
521              }
522            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
523              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three2) {
524                final V3<Node<V, A>> v2 = three2.values();
525                return append3(m, m1, mk.node3(v1), mk.node3(n1, n2, v2._1()), mk.node2(v2._2(), v2._3()), m2);
526              }
527            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
528              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
529                final V4<Node<V, A>> v2 = four.values();
530                return append3(m, m1, mk.node3(v1), mk.node3(n1, n2, v2._1()), mk.node3(v2._2(), v2._3(), v2._4()), m2);
531              }
532            });
533          }
534        }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
535          public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
536            final V4<Node<V, A>> v1 = four.values();
537            return prefix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
538              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
539                return append3(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node2(v1._4(), n1), mk.node2(n2, one.value()),
540                               m2);
541              }
542            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
543              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
544                return append3(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n1, n2),
545                               mk.node2(two.values()), m2);
546              }
547            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
548              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
549                return append3(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n1, n2),
550                               mk.node3(three.values()), m2);
551              }
552            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
553              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four2) {
554                V4<Node<V, A>> v2 = four2.values();
555                return append4(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n1, n2),
556                               mk.node2(v2._1(), v2._2()), mk.node2(v2._3(), v2._4()), m2);
557              }
558            });
559          }
560        });
561      }
562    
563      @SuppressWarnings("unchecked")
564      private static <V, A> FingerTree<V, Node<V, A>> append3(final Measured<V, A> m, final FingerTree<V, Node<V, A>> t1,
565                                                              final Node<V, A> n1, final Node<V, A> n2, final Node<V, A> n3,
566                                                              final FingerTree<V, Node<V, A>> t2) {
567        final Measured<V, Node<V, A>> nm = m.nodeMeasured();
568        return t1.match(new F<Empty<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
569          public FingerTree<V, Node<V, A>> f(final Empty<V, Node<V, A>> empty) {
570            return t2.cons(n3).cons(n2).cons(n1);
571          }
572        }, new F<Single<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
573          public FingerTree<V, Node<V, A>> f(final Single<V, Node<V, A>> single) {
574            return t2.cons(n3).cons(n2).cons(n1).cons(single.value());
575          }
576        }, new F<Deep<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
577          public FingerTree<V, Node<V, A>> f(final Deep<V, Node<V, A>> deep) {
578            return t2.match(new F<Empty<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
579              public FingerTree<V, Node<V, A>> f(final Empty<V, Node<V, A>> empty) {
580                return deep.snoc(n1).snoc(n2).snoc(n3);
581              }
582            }, new F<Single<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
583              public FingerTree<V, Node<V, A>> f(final Single<V, Node<V, A>> single) {
584                return deep.snoc(n1).snoc(n2).snoc(n3).snoc(single.value());
585              }
586            }, new F<Deep<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
587              public FingerTree<V, Node<V, A>> f(final Deep<V, Node<V, A>> deep2) {
588                return new Deep<V, Node<V, A>>(nm, nm.monoid().sumLeft(
589                    list(deep.v, n1.measure(), n2.measure(), n3.measure(), deep2.v)), deep.prefix,
590                                               addDigits3(nm, deep.middle, deep.suffix, n1, n2, n3, deep2.prefix,
591                                                          deep2.middle), deep2.suffix);
592              }
593            });
594          }
595        });
596      }
597    
598      private static <V, A> FingerTree<V, Node<V, Node<V, A>>> addDigits3(final Measured<V, Node<V, A>> m,
599                                                                          final FingerTree<V, Node<V, Node<V, A>>> m1,
600                                                                          final Digit<V, Node<V, A>> suffix,
601                                                                          final Node<V, A> n1, final Node<V, A> n2,
602                                                                          final Node<V, A> n3,
603                                                                          final Digit<V, Node<V, A>> prefix,
604                                                                          final FingerTree<V, Node<V, Node<V, A>>> m2) {
605        final MakeTree<V, Node<V, A>> mk = mkTree(m);
606        return suffix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
607          public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
608            return prefix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
609              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one2) {
610                return append2(m, m1, mk.node3(one.value(), n1, n2), mk.node2(n3, one2.value()), m2);
611              }
612            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
613              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
614                final V2<Node<V, A>> v2 = two.values();
615                return append2(m, m1, mk.node3(one.value(), n1, n2), mk.node3(n3, v2._1(), v2._2()), m2);
616              }
617            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
618              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
619                final V3<Node<V, A>> v2 = three.values();
620                return append3(m, m1, mk.node3(one.value(), n1, n2), mk.node2(n3, v2._1()), mk.node2(v2._2(), v2._3()), m2);
621              }
622            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
623              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
624                final V4<Node<V, A>> v2 = four.values();
625                return append3(m, m1, mk.node3(one.value(), n1, n2), mk.node3(n3, v2._1(), v2._2()),
626                               mk.node2(v2._3(), v2._4()), m2);
627              }
628            });
629          }
630        }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
631          public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
632            final V2<Node<V, A>> v1 = two.values();
633            return prefix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
634              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
635                return append2(m, m1, mk.node3(v1._1(), v1._2(), n1), mk.node3(n2, n3, one.value()), m2);
636              }
637            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
638              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
639                return append3(m, m1, mk.node3(v1._1(), v1._2(), n1), mk.node2(n2, n3), mk.node2(two.values()), m2);
640              }
641            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
642              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
643                final V3<Node<V, A>> v2 = three.values();
644                return append3(m, m1, mk.node3(v1._1(), v1._2(), n1), mk.node3(n2, n3, v2._1()), mk.node2(v2._2(), v2._3()),
645                               m2);
646              }
647            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
648              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
649                final V4<Node<V, A>> v2 = four.values();
650                return append3(m, m1, mk.node3(v1._1(), v1._2(), n1), mk.node3(n2, n3, v2._1()),
651                               mk.node3(v2._2(), v2._3(), v2._4()), m2);
652              }
653            });
654          }
655        }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
656          public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
657            return prefix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
658              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
659                return append3(m, m1, mk.node3(three.values()), mk.node2(n1, n2), mk.node2(n3, one.value()), m2);
660              }
661            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
662              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
663                return append3(m, m1, mk.node3(three.values()), mk.node3(n1, n2, n3), mk.node2(two.values()), m2);
664              }
665            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
666              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three2) {
667                return append3(m, m1, mk.node3(three.values()), mk.node3(n1, n2, n3), mk.node3(three2.values()), m2);
668              }
669            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
670              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
671                final V4<Node<V, A>> v2 = four.values();
672                return append4(m, m1, mk.node3(three.values()), mk.node3(n1, n2, n3), mk.node2(v2._1(), v2._2()),
673                               mk.node2(v2._3(), v2._4()), m2);
674              }
675            });
676          }
677        }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
678          public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
679            final V4<Node<V, A>> v1 = four.values();
680            return prefix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
681              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
682                return append3(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n1, n2),
683                               mk.node2(n3, one.value()), m2);
684              }
685            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
686              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
687                final V2<Node<V, A>> v2 = two.values();
688                return append3(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n1, n2),
689                               mk.node3(n3, v2._1(), v2._2()), m2);
690              }
691            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
692              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
693                final V3<Node<V, A>> v2 = three.values();
694                return append4(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n1, n2), mk.node2(n3, v2._1()),
695                               mk.node2(v2._2(), v2._3()), m2);
696              }
697            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
698              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four2) {
699                final V4<Node<V, A>> v2 = four2.values();
700                return append4(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n1, n2),
701                               mk.node3(n3, v2._1(), v2._2()), mk.node2(v2._3(), v2._4()), m2);
702              }
703            });
704          }
705        });
706      }
707    
708      @SuppressWarnings("unchecked")  
709      private static <V, A> FingerTree<V, Node<V, A>> append4(final Measured<V, A> m,
710                                                              final FingerTree<V, Node<V, A>> t1,
711                                                              final Node<V, A> n1,
712                                                              final Node<V, A> n2,
713                                                              final Node<V, A> n3,
714                                                              final Node<V, A> n4,
715                                                              final FingerTree<V, Node<V, A>> t2) {
716        final Measured<V, Node<V, A>> nm = m.nodeMeasured();
717        return t1.match(new F<Empty<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
718          public FingerTree<V, Node<V, A>> f(final Empty<V, Node<V, A>> empty) {
719            return t2.cons(n4).cons(n3).cons(n2).cons(n1);
720          }
721        }, new F<Single<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
722          public FingerTree<V, Node<V, A>> f(final Single<V, Node<V, A>> single) {
723            return t2.cons(n4).cons(n3).cons(n2).cons(n1).cons(single.value());
724          }
725        }, new F<Deep<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
726          public FingerTree<V, Node<V, A>> f(final Deep<V, Node<V, A>> deep) {
727            return t2.match(new F<Empty<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
728              public FingerTree<V, Node<V, A>> f(final Empty<V, Node<V, A>> empty) {
729                return t1.snoc(n1).snoc(n2).snoc(n3).snoc(n4);
730              }
731            }, new F<Single<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
732              public FingerTree<V, Node<V, A>> f(final Single<V, Node<V, A>> single) {
733                return t1.snoc(n1).snoc(n2).snoc(n3).snoc(n4).snoc(single.value());
734              }
735            }, new F<Deep<V, Node<V, A>>, FingerTree<V, Node<V, A>>>() {
736              public FingerTree<V, Node<V, A>> f(final Deep<V, Node<V, A>> deep2) {
737                return new Deep<V, Node<V, A>>(nm, m.monoid().sumLeft(
738                    list(deep.v, n1.measure(), n2.measure(), n3.measure(), n4.measure(), deep2.v)), deep.prefix,
739                                               addDigits4(nm, deep.middle, deep.suffix, n1, n2, n3, n4, deep2.prefix,
740                                                          deep2.middle), deep2.suffix);
741              }
742            });
743          }
744        });
745      }
746    
747      private static <V, A> FingerTree<V, Node<V, Node<V, A>>> addDigits4(final Measured<V, Node<V, A>> m,
748                                                                          final FingerTree<V, Node<V, Node<V, A>>> m1,
749                                                                          final Digit<V, Node<V, A>> suffix,
750                                                                          final Node<V, A> n1, final Node<V, A> n2,
751                                                                          final Node<V, A> n3, final Node<V, A> n4,
752                                                                          final Digit<V, Node<V, A>> prefix,
753                                                                          final FingerTree<V, Node<V, Node<V, A>>> m2) {
754        final MakeTree<V, Node<V, A>> mk = mkTree(m);
755        return suffix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
756          public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
757            return prefix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
758              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one2) {
759                return append2(m, m1, mk.node3(one.value(), n1, n2), mk.node3(n3, n4, one2.value()), m2);
760              }
761            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
762              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
763                return append3(m, m1, mk.node3(one.value(), n1, n2), mk.node2(n3, n4), mk.node2(two.values()), m2);
764              }
765            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
766              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
767                final V3<Node<V, A>> v2 = three.values();
768                return append3(m, m1, mk.node3(one.value(), n1, n2), mk.node3(n3, n4, v2._1()), mk.node2(v2._2(), v2._3()),
769                               m2);
770              }
771            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
772              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
773                final V4<Node<V, A>> v2 = four.values();
774                return append3(m, m1, mk.node3(one.value(), n1, n2), mk.node3(n3, n4, v2._1()),
775                               mk.node3(v2._2(), v2._3(), v2._4()), m2);
776              }
777            });
778          }
779        }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
780          public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
781            final V2<Node<V, A>> v1 = two.values();
782            return prefix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
783              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
784                return append3(m, m1, mk.node3(v1._1(), v1._2(), n1), mk.node2(n2, n3), mk.node2(n4, one.value()), m2);
785              }
786            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
787              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two2) {
788                return append3(m, m1, mk.node3(v1._1(), v1._2(), n1), mk.node3(n2, n3, n4), mk.node2(two2.values()), m2);
789              }
790            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
791              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
792                return append3(m, m1, mk.node3(v1._1(), v1._2(), n1), mk.node3(n2, n3, n4), mk.node3(three.values()), m2);
793              }
794            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
795              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
796                final V4<Node<V, A>> v2 = four.values();
797                return append4(m, m1, mk.node3(v1._1(), v1._2(), n1), mk.node3(n2, n3, n4), mk.node2(v2._1(), v2._2()),
798                               mk.node2(v2._3(), v2._4()), m2);
799              }
800            });
801          }
802        }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
803          public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
804            final V3<Node<V, A>> v1 = three.values();
805            return prefix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
806              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
807                return append3(m, m1, mk.node3(v1), mk.node3(n1, n2, n3), mk.node2(n4, one.value()), m2);
808              }
809            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
810              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
811                final V2<Node<V, A>> v2 = two.values();
812                return append3(m, m1, mk.node3(v1), mk.node3(n1, n2, n3), mk.node3(n4, v2._1(), v2._2()), m2);
813              }
814            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
815              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
816                final V3<Node<V, A>> v2 = three.values();
817                return append4(m, m1, mk.node3(v1), mk.node3(n1, n2, n3), mk.node2(n4, v2._1()), mk.node2(v2._2(), v2._3()),
818                               m2);
819              }
820            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
821              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
822                final V4<Node<V, A>> v2 = four.values();
823                return append4(m, m1, mk.node3(v1), mk.node3(n1, n2, n3), mk.node3(n4, v2._1(), v2._2()),
824                               mk.node2(v2._3(), v2._4()), m2);
825              }
826            });
827          }
828        }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
829          public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
830            final V4<Node<V, A>> v1 = four.values();
831            return prefix.match(new F<One<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
832              public FingerTree<V, Node<V, Node<V, A>>> f(final One<V, Node<V, A>> one) {
833                return append3(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n1, n2),
834                               mk.node3(n3, n4, one.value()), m2);
835              }
836            }, new F<Two<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
837              public FingerTree<V, Node<V, Node<V, A>>> f(final Two<V, Node<V, A>> two) {
838                return append4(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n1, n2),
839                               mk.node2(n3, n4), mk.node2(two.values()), m2);
840              }
841            }, new F<Three<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
842              public FingerTree<V, Node<V, Node<V, A>>> f(final Three<V, Node<V, A>> three) {
843                final V3<Node<V, A>> v2 = three.values();
844                return append4(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n1, n2),
845                               mk.node3(n3, n4, v2._1()), mk.node2(v2._2(), v2._3()), m2);
846              }
847            }, new F<Four<V, Node<V, A>>, FingerTree<V, Node<V, Node<V, A>>>>() {
848              public FingerTree<V, Node<V, Node<V, A>>> f(final Four<V, Node<V, A>> four) {
849                final V4<Node<V, A>> v2 = four.values();
850                return append4(m, m1, mk.node3(v1._1(), v1._2(), v1._3()), mk.node3(v1._4(), n1, n2),
851                               mk.node3(n3, n4, v2._1()), mk.node3(v2._2(), v2._3(), v2._4()), m2);
852              }
853            });
854          }
855        });
856      }
857    }