001    package fj.data.fingertrees;
002    
003    import fj.F;
004    import fj.F2;
005    import fj.data.vector.V2;
006    import fj.data.vector.V3;
007    import fj.data.vector.V4;
008    import static fj.data.fingertrees.FingerTree.mkTree;
009    
010    /**
011     * A digit is a vector of 1-4 elements. Serves as a pointer to the prefix or suffix of a finger tree.
012     */
013    public abstract class Digit<V, A> {
014      /**
015       * Folds this digit to the right using the given function and the given initial value.
016       *
017       * @param f A function with which to fold this digit.
018       * @param z An initial value to apply at the rightmost end of the fold.
019       * @return The right reduction of this digit with the given function and the given initial value.
020       */
021      public abstract <B> B foldRight(final F<A, F<B, B>> f, final B z);
022    
023      /**
024       * Folds this digit to the left using the given function and the given initial value.
025       *
026       * @param f A function with which to fold this digit.
027       * @param z An initial value to apply at the leftmost end of the fold.
028       * @return The left reduction of this digit with the given function and the given initial value.
029       */
030      public abstract <B> B foldLeft(final F<B, F<A, B>> f, final B z);
031    
032      /**
033       * Folds this digit to the right using the given function.
034       *
035       * @param f A function with which to fold this digit.
036       * @return The right reduction of this digit with the given function.
037       */
038      public final A reduceRight(final F<A, F<A, A>> f) {
039        return match(new F<One<V, A>, A>() {
040          public A f(final One<V, A> one) {
041            return one.value();
042          }
043        }, new F<Two<V, A>, A>() {
044          public A f(final Two<V, A> two) {
045            final V2<A> v = two.values();
046            return f.f(v._1()).f(v._2());
047          }
048        }, new F<Three<V, A>, A>() {
049          public A f(final Three<V, A> three) {
050            final V3<A> v = three.values();
051            return f.f(v._1()).f(f.f(v._2()).f(v._3()));
052          }
053        }, new F<Four<V, A>, A>() {
054          public A f(final Four<V, A> four) {
055            final V4<A> v = four.values();
056            return f.f(v._1()).f(f.f(v._2()).f(f.f(v._3()).f(v._4())));
057          }
058        });
059      }
060    
061      /**
062       * Folds this digit to the right using the given function.
063       *
064       * @param f A function with which to fold this digit.
065       * @return The right reduction of this digit with the given function.
066       */
067      public final A reduceLeft(final F<A, F<A, A>> f) {
068        return match(new F<One<V, A>, A>() {
069          public A f(final One<V, A> one) {
070            return one.value();
071          }
072        }, new F<Two<V, A>, A>() {
073          public A f(final Two<V, A> two) {
074            final V2<A> v = two.values();
075            return f.f(v._1()).f(v._2());
076          }
077        }, new F<Three<V, A>, A>() {
078          public A f(final Three<V, A> three) {
079            final V3<A> v = three.values();
080            return f.f(f.f(v._1()).f(v._2())).f(v._3());
081          }
082        }, new F<Four<V, A>, A>() {
083          public A f(final Four<V, A> four) {
084            final V4<A> v = four.values();
085            return f.f(f.f(f.f(v._1()).f(v._2())).f(v._3())).f(v._4());
086          }
087        });
088      }
089    
090      /**
091       * Maps a function across the elements of this digit, measuring with the given measurement.
092       *
093       * @param f A function to map across the elements of this digit.
094       * @param m A measuring for the function's domain (destination type).
095       * @return A new digit with the same structure as this digit, but with all elements transformed
096       *         with the given function and measured with the given measuring.
097       */
098      public <B> Digit<V, B> map(final F<A, B> f, final Measured<V, B> m) {
099        return match(new F<One<V, A>, Digit<V, B>>() {
100          public Digit<V, B> f(final One<V, A> one) {
101            return new One<V, B>(m, f.f(one.value()));
102          }
103        }, new F<Two<V, A>, Digit<V, B>>() {
104          public Digit<V, B> f(final Two<V, A> two) {
105            return new Two<V, B>(m, two.values().map(f));
106          }
107        }, new F<Three<V, A>, Digit<V, B>>() {
108          public Digit<V, B> f(final Three<V, A> three) {
109            return new Three<V, B>(m, three.values().map(f));
110          }
111        }, new F<Four<V, A>, Digit<V, B>>() {
112          public Digit<V, B> f(final Four<V, A> four) {
113            return new Four<V, B>(m, four.values().map(f));
114          }
115        });
116      }
117    
118      /**
119       * Structural pattern matching on digits. Applies the function that matches the structure of this digit.
120       *
121       * @param one   A function to apply to this digit if it's One.
122       * @param two   A function to apply to this digit if it's Two.
123       * @param three A function to apply to this digit if it's Three.
124       * @param four  A function to apply to this digit if it's Four.
125       * @return The result of applying the function matching this Digit.
126       */
127      public abstract <B> B match(final F<One<V, A>, B> one, final F<Two<V, A>, B> two, final F<Three<V, A>, B> three,
128                                  final F<Four<V, A>, B> four);
129    
130      private final Measured<V, A> m;
131    
132      Digit(final Measured<V, A> m) {
133        this.m = m;
134      }
135    
136      /**
137       * Returns the sum of the measurements of this digit according to the monoid.
138       *
139       * @return the sum of the measurements of this digit according to the monoid.
140       */
141      public V measure() {
142        return foldLeft(fj.Function.curry(new F2<V, A, V>() {
143          public V f(final V v, final A a) {
144            return m.sum(v, m.measure(a));
145          }
146        }), m.zero());
147      }
148    
149      /**
150       * Returns the tree representation of this digit.
151       * @return the tree representation of this digit. 
152       */
153      public FingerTree<V, A> toTree() {
154        final MakeTree<V, A> mk = mkTree(m);
155        return match(new F<One<V, A>, FingerTree<V, A>>() {
156          public FingerTree<V, A> f(final One<V, A> one) {
157            return mk.single(one.value());
158          }
159        }, new F<Two<V, A>, FingerTree<V, A>>() {
160          public FingerTree<V, A> f(final Two<V, A> two) {
161            return mk.deep(mk.one(two.values()._1()), new Empty<V, Node<V, A>>(m.nodeMeasured()), mk.one(two.values()._2()));
162          }
163        }, new F<Three<V, A>, FingerTree<V, A>>() {
164          public FingerTree<V, A> f(final Three<V, A> three) {
165            return mk.deep(mk.two(three.values()._1(), three.values()._2()), new Empty<V, Node<V, A>>(m.nodeMeasured()),
166                           mk.one(three.values()._3()));
167          }
168        }, new F<Four<V, A>, FingerTree<V, A>>() {
169          public FingerTree<V, A> f(final Four<V, A> four) {
170            return mk.deep(mk.two(four.values()._1(), four.values()._2()), new Empty<V, Node<V, A>>(m.nodeMeasured()),
171                           mk.two(four.values()._3(), four.values()._4()));
172          }
173        });
174      }
175    }