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    }