Skip to content

Commit a2e9b5c

Browse files
orionllorionll
committed
Added missing functionality for FingerTree and Seq. Seq implements Iterable.
1 parent e23bddd commit a2e9b5c

File tree

13 files changed

+460
-70
lines changed

13 files changed

+460
-70
lines changed

‎core/src/main/java/fj/data/Seq.java‎

Lines changed: 81 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -10,11 +10,15 @@
1010
import fj.data.fingertrees.MakeTree;
1111
import fj.data.fingertrees.Measured;
1212

13+
import java.util.AbstractList;
14+
import java.util.Iterator;
15+
import java.util.NoSuchElementException;
16+
1317
/**
1418
* Provides an immutable finite sequence, implemented as a finger tree. This structure gives O(1) access to
1519
* the head and tail, as well as O(log n) random access and concatenation of sequences.
1620
*/
17-
public final class Seq<A> {
21+
public final class Seq<A> implements Iterable<A> {
1822
private static final Measured<Integer, Object> ELEM_MEASURED = measured(intAdditionMonoid, Function.constant(1));
1923
private static final MakeTree<Integer, Object> MK_TREE = FingerTree.mkTree(ELEM_MEASURED);
2024
private static final Seq<Object> EMPTY = new Seq<Object>(MK_TREE.empty());
@@ -89,10 +93,79 @@ public Seq<A> snoc(final A a) {
8993
return new Seq<A>(ftree.snoc(a));
9094
}
9195

96+
/**
97+
* The first element of this sequence. This is an O(1) operation.
98+
*
99+
* @return The first element if this sequence is nonempty, otherwise throws an error.
100+
*/
101+
public A head() { return ftree.head(); }
102+
103+
/**
104+
* The last element of this sequence. This is an O(1) operation.
105+
*
106+
* @return The last element if this sequence is nonempty, otherwise throws an error.
107+
*/
108+
public A last() { return ftree.last(); }
109+
110+
/**
111+
* The sequence without the first element. This is an O(1) operation.
112+
*
113+
* @return The sequence without the first element if this sequence is nonempty, otherwise throws an error.
114+
*/
115+
public Seq<A> tail() {
116+
return (length() == 1) ? empty() : new Seq<>(ftree.tail());
117+
}
118+
119+
/**
120+
* The sequence without the last element. This is an O(1) operation.
121+
*
122+
* @return The sequence without the last element if this sequence is nonempty, otherwise throws an error.
123+
*/
124+
public Seq<A> init() {
125+
return (length() == 1) ? empty() : new Seq<>(ftree.init());
126+
}
127+
92128
public Stream<A> toStream() {
93129
return ftree.foldLeft((b, a) -> b.cons(a), Stream.<A>nil()).reverse();
94130
}
95131

132+
public final java.util.List<A> toJavaList() {
133+
return new AbstractList<A>() {
134+
@Override public A get(int i) { return index(i); }
135+
@Override public Iterator<A> iterator() { return Seq.this.iterator(); }
136+
@Override public int size() { return length(); }
137+
};
138+
}
139+
140+
/**
141+
* Returns an iterator for this seq. This method exists to permit the use in a <code>for</code>-each loop.
142+
*
143+
* @return A iterator for this seq.
144+
*/
145+
public final Iterator<A> iterator() {
146+
return new Iterator<A>() {
147+
private FingerTree<Integer, A> ftree = Seq.this.ftree;
148+
149+
public boolean hasNext() {
150+
return !ftree.isEmpty();
151+
}
152+
153+
public A next() {
154+
if (ftree.isEmpty())
155+
throw new NoSuchElementException();
156+
else {
157+
final A a = ftree.head();
158+
ftree = ftree.tail();
159+
return a;
160+
}
161+
}
162+
163+
public void remove() {
164+
throw new UnsupportedOperationException();
165+
}
166+
};
167+
}
168+
96169
@Override
97170
public String toString() {
98171
return Show.seqShow(Show.<A>anyShow()).showS(this);
@@ -126,15 +199,20 @@ public int length() {
126199
return ftree.measure();
127200
}
128201

202+
public P2<Seq<A>, Seq<A>> split(final int i) {
203+
final P2<FingerTree<Integer, A>, FingerTree<Integer, A>> lr = ftree.split(index -> index > i);
204+
return P.p(new Seq<>(lr._1()), new Seq<>(lr._2()));
205+
}
206+
129207
/**
130-
* Returns the element at the given index.
208+
* Returns the element at the given index. This is an O(log(n)) operation.
131209
*
132210
* @param i The index of the element to return.
133211
* @return The element at the given index, or throws an error if the index is out of bounds.
134212
*/
135213
public A index(final int i) {
136214
if (i < 0 || i >= length())
137-
throw error("Index " + i + "out of bounds.");
215+
throw error("Index " + i + " is out of bounds.");
138216
return ftree.lookup(Function.<Integer>identity(), i)._2();
139217
}
140218

‎core/src/main/java/fj/data/fingertrees/Deep.java‎

Lines changed: 77 additions & 53 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,7 @@
11
package fj.data.fingertrees;
22

3-
import fj.F;
4-
import fj.Function;
5-
import fj.P2;
3+
import fj.*;
4+
import fj.data.Option;
65
import fj.data.vector.V2;
76
import fj.data.vector.V3;
87
import fj.data.vector.V4;
@@ -97,54 +96,60 @@ public V measure() {
9796
final Measured<V, A> m = measured();
9897
final V measure = m.sum(m.measure(a), v);
9998
final MakeTree<V, A> mk = mkTree(m);
100-
return prefix.match(new F<One<V, A>, FingerTree<V, A>>() {
101-
public FingerTree<V, A> f(final One<V, A> one) {
102-
return new Deep<V, A>(m, measure, mk.two(a, one.value()), middle, suffix);
103-
}
104-
}, new F<Two<V, A>, FingerTree<V, A>>() {
105-
public FingerTree<V, A> f(final Two<V, A> two) {
106-
return new Deep<V, A>(m, measure, mk.three(a, two.values()._1(), two.values()._2()), middle, suffix);
107-
}
108-
}, new F<Three<V, A>, FingerTree<V, A>>() {
109-
public FingerTree<V, A> f(final Three<V, A> three) {
110-
return new Deep<V, A>(m, measure, mk.four(a, three.values()._1(), three.values()._2(),
111-
three.values()._3()), middle, suffix);
112-
}
113-
}, new F<Four<V, A>, FingerTree<V, A>>() {
114-
public FingerTree<V, A> f(final Four<V, A> four) {
115-
return new Deep<V, A>(m, measure, mk.two(a, four.values()._1()),
116-
middle.cons(mk.node3(four.values()._2(), four.values()._3(), four.values()._4())),
117-
suffix);
118-
}
119-
});
99+
100+
return prefix.match(
101+
one -> new Deep<>(m, measure, mk.two(a, one.value()), middle, suffix),
102+
two -> new Deep<>(m, measure, mk.three(a, two.values()._1(), two.values()._2()), middle, suffix),
103+
three -> new Deep<>(m, measure, mk.four(a, three.values()._1(), three.values()._2(), three.values()._3()), middle, suffix),
104+
four -> new Deep<>(m, measure, mk.two(a, four.values()._1()), middle.cons(mk.node3(four.values()._2(), four.values()._3(), four.values()._4())), suffix));
120105
}
121106

122107
public FingerTree<V, A> snoc(final A a) {
123108
final Measured<V, A> m = measured();
124109
final V measure = m.sum(m.measure(a), v);
125110
final MakeTree<V, A> mk = mkTree(m);
126-
return suffix.match(new F<One<V, A>, FingerTree<V, A>>() {
127-
public FingerTree<V, A> f(final One<V, A> one) {
128-
return new Deep<V, A>(m, measure, prefix, middle, mk.two(one.value(), a));
129-
}
130-
}, new F<Two<V, A>, FingerTree<V, A>>() {
131-
public FingerTree<V, A> f(final Two<V, A> two) {
132-
return new Deep<V, A>(m, measure, prefix, middle, mk.three(two.values()._1(), two.values()._2(), a));
133-
}
134-
}, new F<Three<V, A>, FingerTree<V, A>>() {
135-
public FingerTree<V, A> f(final Three<V, A> three) {
136-
return new Deep<V, A>(m, measure, prefix, middle, mk.four(three.values()._1(), three.values()._2(),
137-
three.values()._3(), a));
138-
}
139-
}, new F<Four<V, A>, FingerTree<V, A>>() {
140-
public FingerTree<V, A> f(final Four<V, A> four) {
141-
return new Deep<V, A>(m, measure, prefix,
142-
middle.snoc(mk.node3(four.values()._1(), four.values()._2(), four.values()._3())),
143-
mk.two(four.values()._4(), a));
144-
}
145-
});
111+
112+
return suffix.match(
113+
one -> new Deep<>(m, measure, prefix, middle, mk.two(one.value(), a)),
114+
two -> new Deep<>(m, measure, prefix, middle, mk.three(two.values()._1(), two.values()._2(), a)),
115+
three -> new Deep<>(m, measure, prefix, middle, mk.four(three.values()._1(), three.values()._2(), three.values()._3(), a)),
116+
four -> new Deep<>(m, measure, prefix, middle.snoc(mk.node3(four.values()._1(), four.values()._2(), four.values()._3())), mk.two(four.values()._4(), a)));
117+
}
118+
119+
@Override public A head() {
120+
return prefix.match(
121+
One::value,
122+
two -> two.values()._1(),
123+
three -> three.values()._1(),
124+
four -> four.values()._1());
146125
}
147126

127+
@Override public A last() {
128+
return suffix.match(
129+
One::value,
130+
two -> two.values()._2(),
131+
three -> three.values()._3(),
132+
four -> four.values()._4());
133+
}
134+
135+
private static final <V, A> FingerTree<V, A> deepL(final Measured<V, A> measured, final Option<Digit<V, A>> lOpt, final FingerTree<V, Node<V, A>> m, final Digit<V, A> r) {
136+
return lOpt.option(
137+
P.lazy(() -> m.isEmpty() ? r.toTree() : mkTree(measured).deep(m.head().toDigit(), m.tail(), r)),
138+
(F<Digit<V, A>, FingerTree<V, A>>) l -> mkTree(measured).deep(l, m, r)
139+
);
140+
}
141+
142+
private static final <V, A> FingerTree<V, A> deepR(final Measured<V, A> measured, final Option<Digit<V, A>> rOpt, final FingerTree<V, Node<V, A>> m, final Digit<V, A> l) {
143+
return rOpt.option(
144+
P.lazy(() -> m.isEmpty() ? l.toTree() : mkTree(measured).deep(l, m.init(), m.last().toDigit())),
145+
(F<Digit<V, A>, FingerTree<V, A>>) r -> mkTree(measured).deep(l, m, r)
146+
);
147+
}
148+
149+
@Override public FingerTree<V, A> tail() { return deepL(measured(), prefix.tail(), middle, suffix); }
150+
151+
@Override public FingerTree<V, A> init() { return deepR(measured(), suffix.init(), middle, prefix); }
152+
148153
@Override public FingerTree<V, A> append(final FingerTree<V, A> t) {
149154
final Measured<V, A> m = measured();
150155
return t.match(Function.<Empty<V, A>, FingerTree<V, A>>constant(t), new F<Single<V, A>, FingerTree<V, A>>() {
@@ -159,19 +164,38 @@ public FingerTree<V, A> f(final Deep<V, A> deep) {
159164
});
160165
}
161166

162-
@SuppressWarnings({"ReturnOfNull", "IfStatementWithIdenticalBranches"})
167+
@Override P3<FingerTree<V, A>, A, FingerTree<V, A>> split1(final F<V, Boolean> predicate, final V acc) {
168+
final Measured<V, A> m = measured();
169+
final V accL = m.sum(acc, prefix.measure());
170+
if (predicate.f(accL)) {
171+
final P3<Option<Digit<V, A>>, A, Option<Digit<V, A>>> lxr = prefix.split1(predicate, accL);
172+
return P.p(lxr._1().option(new Empty<>(m), Digit::toTree), lxr._2(), deepL(m, lxr._3(), middle, suffix));
173+
} else {
174+
final V accM = m.sum(accL, middle.measure());
175+
if (predicate.f(accM)) {
176+
final P3<FingerTree<V, Node<V, A>>, Node<V, A>, FingerTree<V, Node<V, A>>> mlXsMr = middle.split1(predicate, accL);
177+
final P3<Option<Digit<V, A>>, A, Option<Digit<V, A>>> lxr = mlXsMr._2().split1(predicate, m.sum(accL, mlXsMr._1().measure()));
178+
return P.p(deepR(m, lxr._1(), mlXsMr._1(), prefix), lxr._2(), deepL(m, lxr._3(), mlXsMr._3(), suffix));
179+
} else {
180+
final P3<Option<Digit<V, A>>, A, Option<Digit<V, A>>> lxr = suffix.split1(predicate, accM);
181+
return P.p(deepR(m, lxr._1(), middle, prefix), lxr._2(), lxr._3().option(new Empty<>(m), Digit::toTree));
182+
}
183+
}
184+
}
185+
163186
@Override public P2<Integer, A> lookup(final F<V, Integer> o, final int i) {
164187
final int spr = o.f(prefix.measure());
165-
final int spm = o.f(middle.measure());
166-
if (i < spr)
167-
return null; // TODO
168-
//return prefix.lookup(o, i);
169-
if (i < spm) {
170-
return null; // TODO
171-
/* final P2<Integer, Node<V, A>> p = middle.lookup(o, i - spr);
172-
return p._2().lookup(o, p._1()); */
188+
if (i < spr) {
189+
return prefix.lookup(o, i);
190+
} else {
191+
final int spm = spr + o.f(middle.measure());
192+
if (i < spm) {
193+
final P2<Integer, Node<V, A>> p = middle.lookup(o, i - spr);
194+
return p._2().lookup(o, p._1());
195+
} else {
196+
return suffix.lookup(o, i - spm);
197+
}
173198
}
174-
return null; // TODO suffix.lookup(i - spm);
175199
}
176200

177201
private static <V, A> FingerTree<V, Node<V, A>> addDigits0(final Measured<V, A> m, final FingerTree<V, Node<V, A>> m1,

‎core/src/main/java/fj/data/fingertrees/Digit.java‎

Lines changed: 27 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,11 @@
11
package fj.data.fingertrees;
22

3-
import fj.F;
4-
import fj.F2;
5-
import fj.Function;
3+
import fj.*;
4+
import fj.data.Option;
65
import fj.data.vector.V2;
76
import fj.data.vector.V3;
87
import fj.data.vector.V4;
8+
99
import static fj.data.fingertrees.FingerTree.mkTree;
1010

1111
/**
@@ -134,6 +134,8 @@ public abstract <B> B match(final F<One<V, A>, B> one, final F<Two<V, A>, B> two
134134
this.m = m;
135135
}
136136

137+
final Measured<V, A> measured() { return m; }
138+
137139
/**
138140
* Returns the sum of the measurements of this digit according to the monoid.
139141
*
@@ -173,4 +175,26 @@ public FingerTree<V, A> f(final Four<V, A> four) {
173175
}
174176
});
175177
}
178+
179+
Option<Digit<V, A>> tail() {
180+
return match(
181+
one -> Option.<Digit<V, A>> none(),
182+
two -> Option.<Digit<V, A>> some(mkTree(m).one(two.values()._2())),
183+
three -> Option.<Digit<V, A>> some(mkTree(m).two(three.values()._2(), three.values()._3())),
184+
four -> Option.<Digit<V, A>> some(mkTree(m).three(four.values()._2(), four.values()._3(), four.values()._4()))
185+
);
186+
}
187+
188+
Option<Digit<V, A>> init() {
189+
return match(
190+
one -> Option.<Digit<V, A>> none(),
191+
two -> Option.<Digit<V, A>> some(mkTree(m).one(two.values()._1())),
192+
three -> Option.<Digit<V, A>> some(mkTree(m).two(three.values()._1(), three.values()._2())),
193+
four -> Option.<Digit<V, A>> some(mkTree(m).three(four.values()._1(), four.values()._2(), four.values()._3()))
194+
);
195+
}
196+
197+
abstract P3<Option<Digit<V, A>>, A, Option<Digit<V, A>>> split1(final F<V, Boolean> predicate, final V acc);
198+
199+
public abstract P2<Integer, A> lookup(final F<V, Integer> o, final int i);
176200
}

‎core/src/main/java/fj/data/fingertrees/Empty.java‎

Lines changed: 15 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,10 @@
11
package fj.data.fingertrees;
22

33
import fj.F;
4+
import fj.P;
45
import fj.P2;
6+
import fj.P3;
7+
58
import static fj.Bottom.error;
69

710
/**
@@ -20,13 +23,19 @@ public final class Empty<V, A> extends FingerTree<V, A> {
2023
return cons(a);
2124
}
2225

26+
@Override public A head() { throw error("Selection of head in empty tree"); }
27+
28+
@Override public A last() { throw error("Selection of last in empty tree"); }
29+
30+
@Override public FingerTree<V, A> tail() { throw error("Selection of tail in empty tree"); }
31+
32+
@Override public FingerTree<V, A> init() { throw error("Selection of init in empty tree"); }
33+
2334
@Override public FingerTree<V, A> append(final FingerTree<V, A> t) {
2435
return t;
2536
}
2637

27-
@Override public P2<Integer, A> lookup(final F<V, Integer> o, final int i) {
28-
throw error("Lookup of empty tree.");
29-
}
38+
@Override public P2<Integer, A> lookup(final F<V, Integer> o, final int i) { throw error("Lookup of empty tree."); }
3039

3140
@Override public <B> B foldRight(final F<A, F<B, B>> aff, final B z) {
3241
return z;
@@ -65,5 +74,7 @@ public V measure() {
6574
return empty.f(this);
6675
}
6776

68-
77+
@Override P3<FingerTree<V, A>, A, FingerTree<V, A>> split1(final F<V, Boolean> predicate, final V acc) {
78+
throw error("Splitting an empty tree");
79+
}
6980
}

0 commit comments

Comments
 (0)