|
0
|
1 package fj.data;
|
|
|
2
|
|
|
3 import fj.F;
|
|
|
4 import fj.F2;
|
|
|
5 import fj.Function;
|
|
|
6 import static fj.Bottom.error;
|
|
|
7 import static fj.Monoid.intAdditionMonoid;
|
|
|
8 import static fj.data.fingertrees.FingerTree.measured;
|
|
|
9
|
|
|
10 import fj.data.fingertrees.FingerTree;
|
|
|
11 import fj.data.fingertrees.MakeTree;
|
|
|
12 import fj.data.fingertrees.Measured;
|
|
|
13
|
|
|
14 /**
|
|
|
15 * Provides an immutable finite sequence, implemented as a finger tree. This structure gives O(1) access to
|
|
|
16 * the head and tail, as well as O(log n) random access and concatenation of sequences.
|
|
|
17 */
|
|
|
18 public final class Seq<A> {
|
|
|
19 private static final Measured<Integer, Object> ELEM_MEASURED = measured(intAdditionMonoid, Function.constant(1));
|
|
|
20 private static final MakeTree<Integer, Object> MK_TREE = FingerTree.mkTree(ELEM_MEASURED);
|
|
|
21 private static final Seq<Object> EMPTY = new Seq<Object>(MK_TREE.empty());
|
|
|
22
|
|
|
23 @SuppressWarnings("unchecked")
|
|
|
24 private static <A> MakeTree<Integer, A> mkTree() {
|
|
|
25 return (MakeTree<Integer, A>) MK_TREE;
|
|
|
26 }
|
|
|
27
|
|
|
28 private final FingerTree<Integer, A> ftree;
|
|
|
29
|
|
|
30 private Seq(final FingerTree<Integer, A> ftree) {
|
|
|
31 this.ftree = ftree;
|
|
|
32 }
|
|
|
33
|
|
|
34 @SuppressWarnings("unchecked")
|
|
|
35 private static <A> Measured<Integer, A> elemMeasured() {
|
|
|
36 return (Measured<Integer, A>) ELEM_MEASURED;
|
|
|
37 }
|
|
|
38
|
|
|
39 /**
|
|
|
40 * The empty sequence.
|
|
|
41 *
|
|
|
42 * @return A sequence with no elements.
|
|
|
43 */
|
|
|
44 @SuppressWarnings("unchecked")
|
|
|
45 public static <A> Seq<A> empty() {
|
|
|
46 return (Seq<A>) EMPTY;
|
|
|
47 }
|
|
|
48
|
|
|
49 /**
|
|
|
50 * A singleton sequence.
|
|
|
51 *
|
|
|
52 * @param a The single element in the sequence.
|
|
|
53 * @return A new sequence with the given element in it.
|
|
|
54 */
|
|
|
55 public static <A> Seq<A> single(final A a) {
|
|
|
56 return new Seq<A>(Seq.<A>mkTree().single(a));
|
|
|
57 }
|
|
|
58
|
|
|
59 /**
|
|
|
60 * Inserts the given element at the front of this sequence.
|
|
|
61 *
|
|
|
62 * @param a An element to insert at the front of this sequence.
|
|
|
63 * @return A new sequence with the given element at the front.
|
|
|
64 */
|
|
|
65 public Seq<A> cons(final A a) {
|
|
|
66 return new Seq<A>(ftree.cons(a));
|
|
|
67 }
|
|
|
68
|
|
|
69 /**
|
|
|
70 * Inserts the given element at the end of this sequence.
|
|
|
71 *
|
|
|
72 * @param a An element to insert at the end of this sequence.
|
|
|
73 * @return A new sequence with the given element at the end.
|
|
|
74 */
|
|
|
75 public Seq<A> snoc(final A a) {
|
|
|
76 return new Seq<A>(ftree.snoc(a));
|
|
|
77 }
|
|
|
78
|
|
|
79 /**
|
|
|
80 * Appends the given sequence to this sequence.
|
|
|
81 *
|
|
|
82 * @param as A sequence to append to this one.
|
|
|
83 * @return A new sequence with the given sequence appended to this one.
|
|
|
84 */
|
|
|
85 public Seq<A> append(final Seq<A> as) {
|
|
|
86 return new Seq<A>(ftree.append(as.ftree));
|
|
|
87 }
|
|
|
88
|
|
|
89 /**
|
|
|
90 * Checks if this is the empty sequence.
|
|
|
91 *
|
|
|
92 * @return True if this sequence is empty, otherwise false.
|
|
|
93 */
|
|
|
94 public boolean isEmpty() {
|
|
|
95 return ftree.isEmpty();
|
|
|
96 }
|
|
|
97
|
|
|
98 /**
|
|
|
99 * Returns the number of elements in this sequence.
|
|
|
100 *
|
|
|
101 * @return the number of elements in this sequence.
|
|
|
102 */
|
|
|
103 public int length() {
|
|
|
104 return ftree.measure();
|
|
|
105 }
|
|
|
106
|
|
|
107 /**
|
|
|
108 * Returns the element at the given index.
|
|
|
109 *
|
|
|
110 * @param i The index of the element to return.
|
|
|
111 * @return The element at the given index, or throws an error if the index is out of bounds.
|
|
|
112 */
|
|
|
113 public A index(final int i) {
|
|
|
114 if (i < 0 || i >= length())
|
|
|
115 throw error("Index " + i + "out of bounds.");
|
|
|
116 return ftree.lookup(Function.<Integer>identity(), i)._2();
|
|
|
117 }
|
|
|
118
|
|
|
119 public <B> B foldLeft(final F2<B, A, B> f, final B z) {
|
|
|
120 return ftree.foldLeft(f, z);
|
|
|
121 }
|
|
|
122
|
|
|
123 public <B> B foldRight(final F2<A, B, B> f, final B z) {
|
|
|
124 return ftree.foldRight(f, z);
|
|
|
125 }
|
|
|
126
|
|
|
127 public <B> Seq<B> map(F<A, B> f) {
|
|
|
128 return new Seq<B>(ftree.map(f, Seq.<B>elemMeasured()));
|
|
|
129 }
|
|
|
130
|
|
|
131 }
|
