001 package fj.data.fingertrees; 002 003 import fj.data.vector.V2; 004 import fj.data.vector.V3; 005 006 /** 007 * A builder of trees and tree components, supplied with a particular monoid and measuring function. 008 */ 009 public final class MakeTree<V, A> { 010 private final Measured<V, A> m; 011 012 MakeTree(final Measured<V, A> m) { 013 this.m = m; 014 } 015 016 // Tree constructors 017 018 /** 019 * Constructs an empty tree. 020 * 021 * @return The empty tree. 022 */ 023 public FingerTree<V, A> empty() { 024 return new Empty<V, A>(m); 025 } 026 027 /** 028 * Constructs a singleton tree. 029 * 030 * @param a A single element for the tree. 031 * @return A tree with the given value as the single element. 032 */ 033 public FingerTree<V, A> single(final A a) { 034 return new Single<V, A>(m, a); 035 } 036 037 /** 038 * Constructs a deep tree. This structure consists of two digits, of 1 to 4 elements each, on the left and right, 039 * with the rest of the tree in the middle. 040 * 041 * @param prefix The leftmost elements of the tree. 042 * @param middle The subtree, which is a Finger Tree of 2-3 nodes. 043 * @param suffix The rightmost elements of the tree. 044 * @return A new finger tree with the given prefix, suffix, and middle. 045 */ 046 public FingerTree<V, A> deep(final Digit<V, A> prefix, final FingerTree<V, Node<V, A>> middle, 047 final Digit<V, A> suffix) { 048 return deep(m.sum(prefix.measure(), m.sum(middle.measure(), suffix.measure())), prefix, middle, suffix); 049 } 050 051 /** 052 * Constructs a deep tree with the given annotation value. 053 * 054 * @param v The value with which to annotate this tree. 055 * @param prefix The leftmost elements of the tree. 056 * @param middle The subtree, which is a Finger Tree of 2-3 nodes. 057 * @param suffix The rightmost elements of the tree. 058 * @return A new finger tree with the given prefix, suffix, and middle, and annotated with the given value. 059 */ 060 public FingerTree<V, A> deep(final V v, final Digit<V, A> prefix, final FingerTree<V, Node<V, A>> middle, 061 final Digit<V, A> suffix) { 062 return new Deep<V, A>(m, v, prefix, middle, suffix); 063 } 064 065 // Digit constructors 066 067 /** 068 * A digit of one element. 069 * 070 * @param a The element of the digit. 071 * @return A digit of the given element. 072 */ 073 public One<V, A> one(final A a) { 074 return new One<V, A>(m, a); 075 } 076 077 /** 078 * A digit of two elements. 079 * 080 * @param a The first element of the digit. 081 * @param b The second element of the digit. 082 * @return A digit of the given elements. 083 */ 084 public Two<V, A> two(final A a, final A b) { 085 return new Two<V, A>(m, fj.data.vector.V.v(a, b)); 086 } 087 088 /** 089 * A digit of three elements. 090 * 091 * @param a The first element of the digit. 092 * @param b The second element of the digit. 093 * @param c The third element of the digit. 094 * @return A digit of the given elements. 095 */ 096 public Three<V, A> three(final A a, final A b, final A c) { 097 return new Three<V, A>(m, fj.data.vector.V.v(a, b, c)); 098 } 099 100 /** 101 * A digit of four elements. 102 * 103 * @param a The first element of the digit. 104 * @param b The second element of the digit. 105 * @param c The third element of the digit. 106 * @param d The fifth element of the digit. 107 * @return A digit of the given elements. 108 */ 109 public Four<V, A> four(final A a, final A b, final A c, final A d) { 110 return new Four<V, A>(m, fj.data.vector.V.v(a, b, c, d)); 111 } 112 113 // Node constructors 114 115 /** 116 * A binary tree node. 117 * 118 * @param a The left child of the node. 119 * @param b The right child of the node. 120 * @return A new binary tree node. 121 */ 122 public Node2<V, A> node2(final A a, final A b) { 123 return new Node2<V, A>(m, fj.data.vector.V.v(a, b)); 124 } 125 126 /** 127 * A trinary tree node. 128 * 129 * @param a The left child of the node. 130 * @param b The middle child of the node. 131 * @param c The right child of the node. 132 * @return A new trinary tree node. 133 */ 134 public Node3<V, A> node3(final A a, final A b, final A c) { 135 return new Node3<V, A>(m, fj.data.vector.V.v(a, b, c)); 136 } 137 138 /** 139 * A binary tree node 140 * 141 * @param v A vector of the node's elements. 142 * @return A new binary tree node. 143 */ 144 public Node2<V, A> node2(final V2<A> v) { 145 return new Node2<V, A>(m, v); 146 } 147 148 /** 149 * A trinary tree node 150 * 151 * @param v A vector of the node's elements. 152 * @return A new trinary tree node. 153 */ 154 public Node3<V, A> node3(final V3<A> v) { 155 return new Node3<V, A>(m, v); 156 } 157 158 }