|
0
|
1 package fj.data;
|
|
|
2
|
|
|
3 import fj.F;
|
|
|
4 import fj.F2;
|
|
|
5 import static fj.Function.*;
|
|
|
6 import static fj.data.Option.none;
|
|
|
7 import static fj.data.Option.some;
|
|
|
8
|
|
|
9 import fj.Function;
|
|
|
10 import fj.Ord;
|
|
|
11
|
|
|
12 import static fj.Ord.*;
|
|
|
13 import fj.Ordering;
|
|
|
14 import static fj.Ordering.*;
|
|
|
15
|
|
|
16 import java.math.BigDecimal;
|
|
|
17 import java.math.BigInteger;
|
|
|
18
|
|
|
19 /**
|
|
|
20 * Abstracts over a type that may have a successor and/or predecessor value. This implies ordering for that type. A user
|
|
|
21 * may construct an enumerator with an optimised version for <code>plus</code>, otherwise a default is implemented using
|
|
|
22 * the given successor/predecessor implementations.
|
|
|
23 * <p/>
|
|
|
24 * For any enumerator e, the following laws must satisfy:
|
|
|
25 * <ul>
|
|
|
26 * <li>forall a. e.successor(a).forall(\t -> e.predecessor(t).forall(\z -> z == a))</li>
|
|
|
27 * <li>forall a. e.predecessor(a).forall(\t -> e.successor(t).forall(\z -> z == a))</li>
|
|
|
28 * <li>e.max().forall(\t -> e.successor(t).isNone)</li>
|
|
|
29 * <li>e.min().forall(\t -> e.predecessor(t).isNone)</li>
|
|
|
30 * <li>forall a n. e.plus(a, 0) == Some(a)</li>
|
|
|
31 * <li>forall a n | n > 0. e.plus(a, n) == e.plus(a, n - 1)</li>
|
|
|
32 * <li>forall a n | n < 0. e.plus(a, n) == e.plus(a, n + 1)</li>
|
|
|
33 * </ul>
|
|
|
34 *
|
|
|
35 * @version %build.number%
|
|
|
36 */
|
|
|
37 public final class Enumerator<A> {
|
|
|
38 private final F<A, Option<A>> successor;
|
|
|
39 private final F<A, Option<A>> predecessor;
|
|
|
40 private final Option<A> max;
|
|
|
41 private final Option<A> min;
|
|
|
42 private final Ord<A> order;
|
|
|
43 private final F<A, F<Long, Option<A>>> plus;
|
|
|
44
|
|
|
45 private Enumerator(final F<A, Option<A>> successor, final F<A, Option<A>> predecessor, final Option<A> max,
|
|
|
46 final Option<A> min, final Ord<A> order, final F<A, F<Long, Option<A>>> plus) {
|
|
|
47 this.successor = successor;
|
|
|
48 this.predecessor = predecessor;
|
|
|
49 this.max = max;
|
|
|
50 this.min = min;
|
|
|
51 this.order = order;
|
|
|
52 this.plus = plus;
|
|
|
53 }
|
|
|
54
|
|
|
55 /**
|
|
|
56 * Returns the potential successor of a value for this enumerator in curried form.
|
|
|
57 *
|
|
|
58 * @return The potential successor of a value for this enumerator in curried form.
|
|
|
59 */
|
|
|
60 public F<A, Option<A>> successor() {
|
|
|
61 return successor;
|
|
|
62 }
|
|
|
63
|
|
|
64 /**
|
|
|
65 * Returns the potential successor of a value for this enumerator.
|
|
|
66 *
|
|
|
67 * @param a The value to return the successor of.
|
|
|
68 * @return The potential successor of a value for this enumerator.
|
|
|
69 */
|
|
|
70 public Option<A> successor(final A a) {
|
|
|
71 return successor.f(a);
|
|
|
72 }
|
|
|
73
|
|
|
74 /**
|
|
|
75 * Returns the potential predecessor of a value for this enumerator in curried form.
|
|
|
76 *
|
|
|
77 * @return The potential predecessor of a value for this enumerator in curried form.
|
|
|
78 */
|
|
|
79 public F<A, Option<A>> predecessor() {
|
|
|
80 return predecessor;
|
|
|
81 }
|
|
|
82
|
|
|
83 /**
|
|
|
84 * Returns the potential predecessor of a value for this enumerator.
|
|
|
85 *
|
|
|
86 * @param a The value to return the predecessor of.
|
|
|
87 * @return The potential predecessor of a value for this enumerator.
|
|
|
88 */
|
|
|
89 public Option<A> predecessor(final A a) {
|
|
|
90 return predecessor.f(a);
|
|
|
91 }
|
|
|
92
|
|
|
93 /**
|
|
|
94 * Returns the maximum value for this enumerator if there is one.
|
|
|
95 *
|
|
|
96 * @return The maximum value for this enumerator if there is one.
|
|
|
97 */
|
|
|
98 public Option<A> max() {
|
|
|
99 return max;
|
|
|
100 }
|
|
|
101
|
|
|
102 /**
|
|
|
103 * Returns the minimum value for this enumerator if there is one.
|
|
|
104 *
|
|
|
105 * @return The minimum value for this enumerator if there is one.
|
|
|
106 */
|
|
|
107 public Option<A> min() {
|
|
|
108 return min;
|
|
|
109 }
|
|
|
110
|
|
|
111 /**
|
|
|
112 * Returns a function that moves a value along the enumerator a given number of times.
|
|
|
113 *
|
|
|
114 * @return A function that moves a value along the enumerator a given number of times.
|
|
|
115 */
|
|
|
116 public F<A, F<Long, Option<A>>> plus() {
|
|
|
117 return plus;
|
|
|
118 }
|
|
|
119
|
|
|
120 /**
|
|
|
121 * Returns a function that moves a value along the enumerator a given number of times.
|
|
|
122 *
|
|
|
123 * @param a The value to begin moving along from.
|
|
|
124 * @return A function that moves a value along the enumerator a given number of times.
|
|
|
125 */
|
|
|
126 public F<Long, Option<A>> plus(final A a) {
|
|
|
127 return plus.f(a);
|
|
|
128 }
|
|
|
129
|
|
|
130 /**
|
|
|
131 * Returns a function that moves a value along the enumerator a given number of times.
|
|
|
132 *
|
|
|
133 * @param l The number of times to move along the enumerator.
|
|
|
134 * @return A function that moves a value along the enumerator a given number of times.
|
|
|
135 */
|
|
|
136 public F<A, Option<A>> plus(final long l) {
|
|
|
137 return flip(plus).f(l);
|
|
|
138 }
|
|
|
139
|
|
|
140 /**
|
|
|
141 * Moves a value along the enumerator a given number of times.
|
|
|
142 *
|
|
|
143 * @param a The value to begin moving along from.
|
|
|
144 * @param l The number of times to move along the enumerator.
|
|
|
145 * @return A potential value after having moved the given number of times.
|
|
|
146 */
|
|
|
147 public Option<A> plus(final A a, final long l) {
|
|
|
148 return plus.f(a).f(l);
|
|
|
149 }
|
|
|
150
|
|
|
151 /**
|
|
|
152 * Returns the ordering for the enumerator.
|
|
|
153 *
|
|
|
154 * @return The ordering for the enumerator.
|
|
|
155 */
|
|
|
156 public Ord<A> order() {
|
|
|
157 return order;
|
|
|
158 }
|
|
|
159
|
|
|
160 /**
|
|
|
161 * Invariant functor map over this enumerator.
|
|
|
162 *
|
|
|
163 * @param f The covariant map.
|
|
|
164 * @param g The contra-variant map.
|
|
|
165 * @return An enumerator after the given functions are applied.
|
|
|
166 */
|
|
|
167 public <B> Enumerator<B> xmap(final F<A, B> f, final F<B, A> g) {
|
|
|
168 final F<Option<A>, Option<B>> of = new F<Option<A>, Option<B>>() {
|
|
|
169 public Option<B> f(final Option<A> o) {
|
|
|
170 return o.map(f);
|
|
|
171 }
|
|
|
172 };
|
|
|
173 return enumerator(compose(compose(of, successor), g),
|
|
|
174 compose(compose(of, predecessor), g),
|
|
|
175 max.map(f),
|
|
|
176 min.map(f),
|
|
|
177 order.comap(g),
|
|
|
178 compose(compose(Function.<Long, Option<A>, Option<B>>compose().f(of), plus), g));
|
|
|
179 }
|
|
|
180
|
|
|
181 /**
|
|
|
182 * Returns a stream of the values from this enumerator, starting at the given value, counting up.
|
|
|
183 *
|
|
|
184 * @param a A value at which to begin the stream.
|
|
|
185 * @return a stream of the values from this enumerator, starting at the given value, counting up.
|
|
|
186 */
|
|
|
187 public Stream<A> toStream(final A a) {
|
|
|
188 final F<A, A> id = identity();
|
|
|
189 return Stream.fromFunction(this, id, a);
|
|
|
190 }
|
|
|
191
|
|
|
192 /**
|
|
|
193 * Create a new enumerator with the given minimum value.
|
|
|
194 *
|
|
|
195 * @param min A minimum value.
|
|
|
196 * @return A new enumerator identical to this one, but with the given minimum value.
|
|
|
197 */
|
|
|
198 public Enumerator<A> setMin(final Option<A> min) {
|
|
|
199 return enumerator(successor, predecessor, max, min, order, plus);
|
|
|
200 }
|
|
|
201
|
|
|
202 /**
|
|
|
203 * Create a new enumerator with the given maximum value.
|
|
|
204 *
|
|
|
205 * @param max A maximum value.
|
|
|
206 * @return A new enumerator identical to this one, but with the given maximum value.
|
|
|
207 */
|
|
|
208 public Enumerator<A> setMax(final Option<A> max) {
|
|
|
209 return enumerator(successor, predecessor, max, min, order, plus);
|
|
|
210 }
|
|
|
211
|
|
|
212 /**
|
|
|
213 * Construct an enumerator. `
|
|
|
214 *
|
|
|
215 * @param successor The successor function.
|
|
|
216 * @param predecessor The predecessor function.
|
|
|
217 * @param max The potential maximum value.
|
|
|
218 * @param min The potential minimum value.
|
|
|
219 * @param order The ordering for the type.
|
|
|
220 * @param plus The function to move the enumeration a given number of times. This may be supplied for a performance
|
|
|
221 * enhancement for certain types.
|
|
|
222 * @return An enumerator with the given values.
|
|
|
223 */
|
|
|
224 public static <A> Enumerator<A> enumerator(final F<A, Option<A>> successor, final F<A, Option<A>> predecessor,
|
|
|
225 final Option<A> max, final Option<A> min, final Ord<A> order,
|
|
|
226 final F<A, F<Long, Option<A>>> plus) {
|
|
|
227 return new Enumerator<A>(successor, predecessor, max, min, order, plus);
|
|
|
228 }
|
|
|
229
|
|
|
230 /**
|
|
|
231 * Construct an enumerator. The <code>plus</code> function is derived from the <code>successor</code> and
|
|
|
232 * <code>predecessor</code>.
|
|
|
233 *
|
|
|
234 * @param successor The successor function.
|
|
|
235 * @param predecessor The predecessor function.
|
|
|
236 * @param max The potential maximum value.
|
|
|
237 * @param min The potential minimum value.
|
|
|
238 * @param order The ordering for the type.
|
|
|
239 * @return An enumerator with the given values.
|
|
|
240 */
|
|
|
241 public static <A> Enumerator<A> enumerator(final F<A, Option<A>> successor, final F<A, Option<A>> predecessor,
|
|
|
242 final Option<A> max, final Option<A> min, final Ord<A> order) {
|
|
|
243 return new Enumerator<A>(successor, predecessor, max, min, order, curry(new F2<A, Long, Option<A>>() {
|
|
|
244 public Option<A> f(final A a, final Long l) {
|
|
|
245 if (l == 0L)
|
|
|
246 return some(a);
|
|
|
247 else if (l < 0L) {
|
|
|
248 A aa = a;
|
|
|
249 for (long x = l; x < 0; x++) {
|
|
|
250 final Option<A> s = predecessor.f(aa);
|
|
|
251 if (s.isNone())
|
|
|
252 return none();
|
|
|
253 else
|
|
|
254 aa = s.some();
|
|
|
255 }
|
|
|
256 return some(aa);
|
|
|
257 } else {
|
|
|
258 A aa = a;
|
|
|
259 for (long x = l; x > 0; x--) {
|
|
|
260 final Option<A> s = successor.f(aa);
|
|
|
261 if (s.isNone())
|
|
|
262 return none();
|
|
|
263 else
|
|
|
264 aa = s.some();
|
|
|
265 }
|
|
|
266 return some(aa);
|
|
|
267 }
|
|
|
268 }
|
|
|
269 }));
|
|
|
270 }
|
|
|
271
|
|
|
272 /**
|
|
|
273 * An enumerator for <code>boolean</code>.
|
|
|
274 */
|
|
|
275 public static final Enumerator<Boolean> booleanEnumerator = enumerator(new F<Boolean, Option<Boolean>>() {
|
|
|
276 public Option<Boolean> f(final Boolean b) {
|
|
|
277 return b ? Option.<Boolean>none() : some(true);
|
|
|
278 }
|
|
|
279 }, new F<Boolean, Option<Boolean>>() {
|
|
|
280 public Option<Boolean> f(final Boolean b) {
|
|
|
281 return b ? some(false) : Option.<Boolean>none();
|
|
|
282 }
|
|
|
283 }, some(true), some(false), booleanOrd);
|
|
|
284
|
|
|
285 /**
|
|
|
286 * An enumerator for <code>byte</code>.
|
|
|
287 */
|
|
|
288 public static final Enumerator<Byte> byteEnumerator = enumerator(new F<Byte, Option<Byte>>() {
|
|
|
289 public Option<Byte> f(final Byte b) {
|
|
|
290 return b == Byte.MAX_VALUE ? Option.<Byte>none() : some((byte) (b + 1));
|
|
|
291 }
|
|
|
292 }, new F<Byte, Option<Byte>>() {
|
|
|
293 public Option<Byte> f(final Byte b) {
|
|
|
294 return b == Byte.MIN_VALUE ? Option.<Byte>none() : some((byte) (b - 1));
|
|
|
295 }
|
|
|
296 }, some(Byte.MAX_VALUE), some(Byte.MIN_VALUE), byteOrd);
|
|
|
297
|
|
|
298 /**
|
|
|
299 * An enumerator for <code>char</code>.
|
|
|
300 */
|
|
|
301 public static final Enumerator<Character> charEnumerator = enumerator(new F<Character, Option<Character>>() {
|
|
|
302 public Option<Character> f(final Character c) {
|
|
|
303 return c == Character.MAX_VALUE ? Option.<Character>none() : some((char) (c + 1));
|
|
|
304 }
|
|
|
305 }, new F<Character, Option<Character>>() {
|
|
|
306 public Option<Character> f(final Character c) {
|
|
|
307 return c == Character.MIN_VALUE ? Option.<Character>none() : some((char) (c - 1));
|
|
|
308 }
|
|
|
309 }, some(Character.MAX_VALUE), some(Character.MIN_VALUE), charOrd);
|
|
|
310
|
|
|
311 /**
|
|
|
312 * An enumerator for <code>double</code>.
|
|
|
313 */
|
|
|
314 public static final Enumerator<Double> doubleEnumerator = enumerator(new F<Double, Option<Double>>() {
|
|
|
315 public Option<Double> f(final Double d) {
|
|
|
316 return d == Double.MAX_VALUE ? Option.<Double>none() : some(d + 1D);
|
|
|
317 }
|
|
|
318 }, new F<Double, Option<Double>>() {
|
|
|
319 public Option<Double> f(final Double d) {
|
|
|
320 return d == Double.MIN_VALUE ? Option.<Double>none() : some(d - 1D);
|
|
|
321 }
|
|
|
322 }, some(Double.MAX_VALUE), some(Double.MIN_VALUE), doubleOrd);
|
|
|
323
|
|
|
324 /**
|
|
|
325 * An enumerator for <code>float</code>.
|
|
|
326 */
|
|
|
327 public static final Enumerator<Float> floatEnumerator = enumerator(new F<Float, Option<Float>>() {
|
|
|
328 public Option<Float> f(final Float f) {
|
|
|
329 return f == Float.MAX_VALUE ? Option.<Float>none() : some(f + 1F);
|
|
|
330 }
|
|
|
331 }, new F<Float, Option<Float>>() {
|
|
|
332 public Option<Float> f(final Float f) {
|
|
|
333 return f == Float.MIN_VALUE ? Option.<Float>none() : some(f - 1F);
|
|
|
334 }
|
|
|
335 }, some(Float.MAX_VALUE), some(Float.MIN_VALUE), floatOrd);
|
|
|
336
|
|
|
337 /**
|
|
|
338 * An enumerator for <code>int</code>.
|
|
|
339 */
|
|
|
340 public static final Enumerator<Integer> intEnumerator = enumerator(new F<Integer, Option<Integer>>() {
|
|
|
341 public Option<Integer> f(final Integer i) {
|
|
|
342 return i == Integer.MAX_VALUE ? Option.<Integer>none() : some(i + 1);
|
|
|
343 }
|
|
|
344 }, new F<Integer, Option<Integer>>() {
|
|
|
345 public Option<Integer> f(final Integer i) {
|
|
|
346 return i == Integer.MIN_VALUE ? Option.<Integer>none() : some(i - 1);
|
|
|
347 }
|
|
|
348 }, some(Integer.MAX_VALUE), some(Integer.MIN_VALUE), intOrd);
|
|
|
349
|
|
|
350 /**
|
|
|
351 * An enumerator for <code>BigInteger</code>.
|
|
|
352 */
|
|
|
353 public static final Enumerator<BigInteger> bigintEnumerator = enumerator(new F<BigInteger, Option<BigInteger>>() {
|
|
|
354 public Option<BigInteger> f(final BigInteger i) {
|
|
|
355 return some(i.add(BigInteger.ONE));
|
|
|
356 }
|
|
|
357 }, new F<BigInteger, Option<BigInteger>>() {
|
|
|
358 public Option<BigInteger> f(final BigInteger i) {
|
|
|
359 return some(i.subtract(BigInteger.ONE));
|
|
|
360 }
|
|
|
361 }, Option.<BigInteger>none(), Option.<BigInteger>none(), bigintOrd, curry(
|
|
|
362 new F2<BigInteger, Long, Option<BigInteger>>() {
|
|
|
363 public Option<BigInteger> f(final BigInteger i, final Long l) {
|
|
|
364 return some(i.add(BigInteger.valueOf(l)));
|
|
|
365 }
|
|
|
366 }));
|
|
|
367
|
|
|
368 /**
|
|
|
369 * An enumerator for <code>BigDecimal</code>.
|
|
|
370 */
|
|
|
371 public static final Enumerator<BigDecimal> bigdecimalEnumerator = enumerator(new F<BigDecimal, Option<BigDecimal>>() {
|
|
|
372 public Option<BigDecimal> f(final BigDecimal i) {
|
|
|
373 return some(i.add(BigDecimal.ONE));
|
|
|
374 }
|
|
|
375 }, new F<BigDecimal, Option<BigDecimal>>() {
|
|
|
376 public Option<BigDecimal> f(final BigDecimal i) {
|
|
|
377 return some(i.subtract(BigDecimal.ONE));
|
|
|
378 }
|
|
|
379 }, Option.<BigDecimal>none(), Option.<BigDecimal>none(), bigdecimalOrd, curry(
|
|
|
380 new F2<BigDecimal, Long, Option<BigDecimal>>() {
|
|
|
381 public Option<BigDecimal> f(final BigDecimal d, final Long l) {
|
|
|
382 return some(d.add(BigDecimal.valueOf(l)));
|
|
|
383 }
|
|
|
384 }));
|
|
|
385
|
|
|
386 /**
|
|
|
387 * An enumerator for <code>long</code>.
|
|
|
388 */
|
|
|
389 public static final Enumerator<Long> longEnumerator = enumerator(new F<Long, Option<Long>>() {
|
|
|
390 public Option<Long> f(final Long i) {
|
|
|
391 return i == Long.MAX_VALUE ? Option.<Long>none() : some(i + 1L);
|
|
|
392 }
|
|
|
393 }, new F<Long, Option<Long>>() {
|
|
|
394 public Option<Long> f(final Long i) {
|
|
|
395 return i == Long.MIN_VALUE ? Option.<Long>none() : some(i - 1L);
|
|
|
396 }
|
|
|
397 }, some(Long.MAX_VALUE), some(Long.MIN_VALUE), longOrd);
|
|
|
398
|
|
|
399 /**
|
|
|
400 * An enumerator for <code>short</code>.
|
|
|
401 */
|
|
|
402 public static final Enumerator<Short> shortEnumerator = enumerator(new F<Short, Option<Short>>() {
|
|
|
403 public Option<Short> f(final Short i) {
|
|
|
404 return i == Short.MAX_VALUE ? Option.<Short>none() : some((short) (i + 1));
|
|
|
405 }
|
|
|
406 }, new F<Short, Option<Short>>() {
|
|
|
407 public Option<Short> f(final Short i) {
|
|
|
408 return i == Short.MIN_VALUE ? Option.<Short>none() : some((short) (i - 1));
|
|
|
409 }
|
|
|
410 }, some(Short.MAX_VALUE), some(Short.MIN_VALUE), shortOrd);
|
|
|
411
|
|
|
412 /**
|
|
|
413 * An enumerator for <code>Ordering</code>.
|
|
|
414 */
|
|
|
415 public static final Enumerator<Ordering> orderingEnumerator = enumerator(new F<Ordering, Option<Ordering>>() {
|
|
|
416 public Option<Ordering> f(final Ordering o) {
|
|
|
417 return o == LT ? some(EQ) : o == EQ ? some(GT) : Option.<Ordering>none();
|
|
|
418 }
|
|
|
419 }, new F<Ordering, Option<Ordering>>() {
|
|
|
420 public Option<Ordering> f(final Ordering o) {
|
|
|
421 return o == GT ? some(EQ) : o == EQ ? some(LT) : Option.<Ordering>none();
|
|
|
422 }
|
|
|
423 }, some(GT), some(LT), orderingOrd);
|
|
|
424
|
|
|
425 /**
|
|
|
426 * An enumerator for <code>Natural</code>
|
|
|
427 */
|
|
|
428 public static final Enumerator<Natural> naturalEnumerator = enumerator(new F<Natural, Option<Natural>>() {
|
|
|
429 public Option<Natural> f(final Natural n) {
|
|
|
430 return Option.some(n.succ());
|
|
|
431 }
|
|
|
432 }, new F<Natural, Option<Natural>>() {
|
|
|
433 public Option<Natural> f(final Natural n) {
|
|
|
434 return n.pred();
|
|
|
435 }
|
|
|
436 }, Option.<Natural>none(), some(Natural.ZERO), naturalOrd, curry(new F2<Natural, Long, Option<Natural>>() {
|
|
|
437 public Option<Natural> f(final Natural n, final Long l) {
|
|
|
438 return some(n).apply(Natural.natural(l).map(Function.curry(new F2<Natural, Natural, Natural>() {
|
|
|
439 public Natural f(final Natural n1, final Natural n2) {
|
|
|
440 return n1.add(n2);
|
|
|
441 }
|
|
|
442 })));
|
|
|
443 }
|
|
|
444 }));
|
|
|
445
|
|
|
446 }
|
