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 }