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 }