001 package fj.data.fingertrees;
002
003 import fj.F;
004 import fj.P2;
005 import fj.pre.Monoid;
006
007 /**
008 * Provides 2-3 finger trees, a functional representation of persistent sequences supporting access to the ends in
009 * amortized O(1) time. Concatenation and splitting time is O(log n) in the size of the smaller piece.
010 * A general purpose data structure that can serve as a sequence, priority queue, search tree, priority search queue
011 * and more.
012 * <p/>
013 * This class serves as a datastructure construction kit, rather than a datastructure in its own right. By supplying
014 * a monoid, a measurement function, insertion, deletion, and so forth, any purely functional datastructure can be
015 * emulated. See {@link fj.data.Seq} for an example.
016 * <p/>
017 * Based on "Finger trees: a simple general-purpose data structure", by Ralf Hinze and Ross Paterson.
018 *
019 * @param <V> The monoidal type with which to annotate nodes.
020 * @param <A> The type of the tree's elements.
021 */
022 public abstract class FingerTree<V, A> {
023 private final Measured<V, A> m;
024
025 /**
026 * Folds the tree to the right with the given function and the given initial element.
027 *
028 * @param f A function with which to fold the tree.
029 * @param z An initial element to apply to the fold.
030 * @return A reduction of this tree by applying the given function, associating to the right.
031 */
032 public abstract <B> B foldRight(final F<A, F<B, B>> f, final B z);
033
034 /**
035 * Folds the tree to the right with the given function.
036 *
037 * @param f A function with which to fold the tree.
038 * @return A reduction of this tree by applying the given function, associating to the right.
039 */
040 public abstract A reduceRight(final F<A, F<A, A>> f);
041
042 /**
043 * Folds the tree to the left with the given function and the given initial element.
044 *
045 * @param f A function with which to fold the tree.
046 * @param z An initial element to apply to the fold.
047 * @return A reduction of this tree by applying the given function, associating to the left.
048 */
049 public abstract <B> B foldLeft(final F<B, F<A, B>> f, final B z);
050
051 /**
052 * Folds the tree to the left with the given function.
053 *
054 * @param f A function with which to fold the tree.
055 * @return A reduction of this tree by applying the given function, associating to the right.
056 */
057 public abstract A reduceLeft(final F<A, F<A, A>> f);
058
059 /**
060 * Maps the given function across this tree, measuring with the given Measured instance.
061 *
062 * @param f A function to map across the values of this tree.
063 * @param m A measuring with which to annotate the tree.
064 * @return A new tree with the same structure as this tree, with each element transformed by the given function,
065 * and nodes annotated according to the given measuring.
066 */
067 public abstract <B> FingerTree<V, B> map(final F<A, B> f, final Measured<V, B> m);
068
069 /**
070 * Returns the sum of this tree's annotations.
071 *
072 * @return the sum of this tree's annotations.
073 */
074 public abstract V measure();
075
076 /**
077 * Indicates whether this tree is empty.
078 *
079 * @return true if this tree is the empty tree, otherwise false.
080 */
081 public boolean isEmpty() {
082 return this instanceof Empty;
083 }
084
085 protected Measured<V, A> measured() {
086 return m;
087 }
088
089 /**
090 * Provides pattern matching on trees. This is the Church encoding of the FingerTree datatype.
091 *
092 * @param empty The function to apply to this empty tree.
093 * @param single A function to apply if this tree contains a single element.
094 * @param deep A function to apply if this tree contains more than one element.
095 * @return The result of the function that matches this tree structurally, applied to this tree.
096 */
097 public abstract <B> B match(final F<Empty<V, A>, B> empty, final F<Single<V, A>, B> single,
098 final F<Deep<V, A>, B> deep);
099
100 FingerTree(final Measured<V, A> m) {
101 this.m = m;
102 }
103
104 /**
105 * Constructs a Measured instance for the element type, given a monoid and a measuring function.
106 *
107 * @param monoid A monoid for the measures.
108 * @param measure A function with which to measure element values.
109 * @return A Measured instance for the given element type, that uses the given monoid and measuring function.
110 */
111 public static <V, A> Measured<V, A> measured(final Monoid<V> monoid, final F<A, V> measure) {
112 return Measured.measured(monoid, measure);
113 }
114
115 /**
116 * Returns a builder of trees and tree components that annotates them using the given Measured instance.
117 *
118 * @param m A Measured instance with which to annotate trees, digits, and nodes.
119 * @return A builder of trees and tree components that annotates them using the given Measured instance.
120 */
121 public static <V, A> MakeTree<V, A> mkTree(final Measured<V, A> m) {
122 return new MakeTree<V, A>(m);
123 }
124
125 /**
126 * Adds the given element to this tree as the first element.
127 *
128 * @param a The element to add to the front of this tree.
129 * @return A new tree with the given element at the front.
130 */
131 public abstract FingerTree<V, A> cons(final A a);
132
133 /**
134 * Adds the given element to this tree as the last element.
135 *
136 * @param a The element to add to the end of this tree.
137 * @return A new tree with the given element at the end.
138 */
139 public abstract FingerTree<V, A> snoc(final A a);
140
141 /**
142 * Appends one finger tree to another.
143 *
144 * @param t A finger tree to append to this one.
145 * @return A new finger tree which is a concatenation of this tree and the given tree.
146 */
147 public abstract FingerTree<V, A> append(final FingerTree<V, A> t);
148
149 public abstract P2<Integer, A> lookup(final F<V, Integer> o, final int i);
150 }