001    package fj.data;
002    
003    import fj.F;
004    import fj.F2;
005    import static fj.Function.*;
006    import static fj.data.Option.none;
007    import static fj.data.Option.some;
008    import fj.pre.Ord;
009    import static fj.pre.Ord.*;
010    import fj.pre.Ordering;
011    import static fj.pre.Ordering.*;
012    
013    import java.math.BigDecimal;
014    import java.math.BigInteger;
015    
016    /**
017     * Abstracts over a type that may have a successor and/or predecessor value. This implies ordering for that type. A user
018     * may construct an enumerator with an optimised version for <code>plus</code>, otherwise a default is implemented using
019     * the given successor/predecessor implementations.
020     * <p/>
021     * For any enumerator e, the following laws must satisfy:
022     * <ul>
023     * <li>forall a. e.successor(a).forall(\t -> e.predecessor(t).forall(\z -> z == a))</li>
024     * <li>forall a. e.predecessor(a).forall(\t -> e.successor(t).forall(\z -> z == a))</li>
025     * <li>e.max().forall(\t -> e.successor(t).isNone)</li>
026     * <li>e.min().forall(\t -> e.predecessor(t).isNone)</li>
027     * <li>forall a n. e.plus(a, 0) == Some(a)</li>
028     * <li>forall a n | n > 0. e.plus(a, n) == e.plus(a, n - 1)</li>
029     * <li>forall a n | n < 0. e.plus(a, n) == e.plus(a, n + 1)</li>
030     * </ul>
031     *
032     * @version %build.number%<br>
033     *          <ul>
034     *          <li>$LastChangedRevision: 161 $</li>
035     *          <li>$LastChangedDate: 2009-06-01 17:14:38 +1000 (Mon, 01 Jun 2009) $</li>
036     *          </ul>
037     */
038    public final class Enumerator<A> {
039      private final F<A, Option<A>> successor;
040      private final F<A, Option<A>> predecessor;
041      private final Option<A> max;
042      private final Option<A> min;
043      private final Ord<A> order;
044      private final F<A, F<Long, Option<A>>> plus;
045    
046      private Enumerator(final F<A, Option<A>> successor, final F<A, Option<A>> predecessor, final Option<A> max,
047                         final Option<A> min, final Ord<A> order, final F<A, F<Long, Option<A>>> plus) {
048        this.successor = successor;
049        this.predecessor = predecessor;
050        this.max = max;
051        this.min = min;
052        this.order = order;
053        this.plus = plus;
054      }
055    
056      /**
057       * Returns the potential successor of a value for this enumerator in curried form.
058       *
059       * @return The potential successor of a value for this enumerator in curried form.
060       */
061      public F<A, Option<A>> successor() {
062        return successor;
063      }
064    
065      /**
066       * Returns the potential successor of a value for this enumerator.
067       *
068       * @param a The value to return the successor of.
069       * @return The potential successor of a value for this enumerator.
070       */
071      public Option<A> successor(final A a) {
072        return successor.f(a);
073      }
074    
075      /**
076       * Returns the potential predecessor of a value for this enumerator in curried form.
077       *
078       * @return The potential predecessor of a value for this enumerator in curried form.
079       */
080      public F<A, Option<A>> predecessor() {
081        return predecessor;
082      }
083    
084      /**
085       * Returns the potential predecessor of a value for this enumerator.
086       *
087       * @param a The value to return the predecessor of.
088       * @return The potential predecessor of a value for this enumerator.
089       */
090      public Option<A> predecessor(final A a) {
091        return predecessor.f(a);
092      }
093    
094      /**
095       * Returns the maximum value for this enumerator if there is one.
096       *
097       * @return The maximum value for this enumerator if there is one.
098       */
099      public Option<A> max() {
100        return max;
101      }
102    
103      /**
104       * Returns the minimum value for this enumerator if there is one.
105       *
106       * @return The minimum value for this enumerator if there is one.
107       */
108      public Option<A> min() {
109        return min;
110      }
111    
112      /**
113       * Returns a function that moves a value along the enumerator a given number of times.
114       *
115       * @return A function that moves a value along the enumerator a given number of times.
116       */
117      public F<A, F<Long, Option<A>>> plus() {
118        return plus;
119      }
120    
121      /**
122       * Returns a function that moves a value along the enumerator a given number of times.
123       *
124       * @param a The value to begin moving along from.
125       * @return A function that moves a value along the enumerator a given number of times.
126       */
127      public F<Long, Option<A>> plus(final A a) {
128        return plus.f(a);
129      }
130    
131      /**
132       * Returns a function that moves a value along the enumerator a given number of times.
133       *
134       * @param l The number of times to move along the enumerator.
135       * @return A function that moves a value along the enumerator a given number of times.
136       */
137      public F<A, Option<A>> plus(final long l) {
138        return flip(plus).f(l);
139      }
140    
141      /**
142       * Moves a value along the enumerator a given number of times.
143       *
144       * @param a The value to begin moving along from.
145       * @param l The number of times to move along the enumerator.
146       * @return A potential value after having moved the given number of times.
147       */
148      public Option<A> plus(final A a, final long l) {
149        return plus.f(a).f(l);
150      }
151    
152      /**
153       * Returns the ordering for the enumerator.
154       *
155       * @return The ordering for the enumerator.
156       */
157      public Ord<A> order() {
158        return order;
159      }
160    
161      /**
162       * Invariant functor map over this enumerator.
163       *
164       * @param f The covariant map.
165       * @param g The contra-variant map.
166       * @return An enumerator after the given functions are applied.
167       */
168      public <B> Enumerator<B> xmap(final F<A, B> f, final F<B, A> g) {
169        final F<Option<A>, Option<B>> of = new F<Option<A>, Option<B>>() {
170          public Option<B> f(final Option<A> o) {
171            return o.map(f);
172          }
173        };
174        return enumerator(compose(compose(of, successor), g),
175                          compose(compose(of, predecessor), g),
176                          max.map(f),
177                          min.map(f),
178                          order.comap(g),
179                          compose(compose(fj.Function.<Long, Option<A>, Option<B>>compose().f(of), plus), g));
180      }
181    
182      /**
183       * Returns a stream of the values from this enumerator, starting at the given value, counting up.
184       *
185       * @param a A value at which to begin the stream.
186       * @return a stream of the values from this enumerator, starting at the given value, counting up.
187       */
188      public Stream<A> toStream(final A a) {
189        final F<A, A> id = identity();
190        return Stream.fromFunction(this, id, a);
191      }
192    
193      /**
194       * Create a new enumerator with the given minimum value.
195       *
196       * @param min A minimum value.
197       * @return A new enumerator identical to this one, but with the given minimum value.
198       */
199      public Enumerator<A> setMin(final Option<A> min) {
200        return enumerator(successor, predecessor, max, min, order, plus);
201      }
202    
203      /**
204       * Create a new enumerator with the given maximum value.
205       *
206       * @param max A maximum value.
207       * @return A new enumerator identical to this one, but with the given maximum value.
208       */
209      public Enumerator<A> setMax(final Option<A> max) {
210        return enumerator(successor, predecessor, max, min, order, plus);
211      }
212    
213      /**
214       * Construct an enumerator.    `
215       *
216       * @param successor   The successor function.
217       * @param predecessor The predecessor function.
218       * @param max         The potential maximum value.
219       * @param min         The potential minimum value.
220       * @param order       The ordering for the type.
221       * @param plus        The function to move the enumeration a given number of times. This may be supplied for a performance
222       *                    enhancement for certain types.
223       * @return An enumerator with the given values.
224       */
225      public static <A> Enumerator<A> enumerator(final F<A, Option<A>> successor, final F<A, Option<A>> predecessor,
226                                                 final Option<A> max, final Option<A> min, final Ord<A> order,
227                                                 final F<A, F<Long, Option<A>>> plus) {
228        return new Enumerator<A>(successor, predecessor, max, min, order, plus);
229      }
230    
231      /**
232       * Construct an enumerator. The <code>plus</code> function is derived from the <code>successor</code> and
233       * <code>predecessor</code>.
234       *
235       * @param successor   The successor function.
236       * @param predecessor The predecessor function.
237       * @param max         The potential maximum value.
238       * @param min         The potential minimum value.
239       * @param order       The ordering for the type.
240       * @return An enumerator with the given values.
241       */
242      public static <A> Enumerator<A> enumerator(final F<A, Option<A>> successor, final F<A, Option<A>> predecessor,
243                                                 final Option<A> max, final Option<A> min, final Ord<A> order) {
244        return new Enumerator<A>(successor, predecessor, max, min, order, curry(new F2<A, Long, Option<A>>() {
245          public Option<A> f(final A a, final Long l) {
246            if (l == 0L)
247              return some(a);
248            else if (l < 0L) {
249              A aa = a;
250              for (long x = l; x < 0; x++) {
251                final Option<A> s = predecessor.f(aa);
252                if (s.isNone())
253                  return none();
254                else
255                  aa = s.some();
256              }
257              return some(aa);
258            } else {
259              A aa = a;
260              for (long x = l; x > 0; x--) {
261                final Option<A> s = successor.f(aa);
262                if (s.isNone())
263                  return none();
264                else
265                  aa = s.some();
266              }
267              return some(aa);
268            }
269          }
270        }));
271      }
272    
273      /**
274       * An enumerator for <code>boolean</code>.
275       */
276      public static final Enumerator<Boolean> booleanEnumerator = enumerator(new F<Boolean, Option<Boolean>>() {
277        public Option<Boolean> f(final Boolean b) {
278          return b ? Option.<Boolean>none() : some(true);
279        }
280      }, new F<Boolean, Option<Boolean>>() {
281        public Option<Boolean> f(final Boolean b) {
282          return b ? some(false) : Option.<Boolean>none();
283        }
284      }, some(true), some(false), booleanOrd);
285    
286      /**
287       * An enumerator for <code>byte</code>.
288       */
289      public static final Enumerator<Byte> byteEnumerator = enumerator(new F<Byte, Option<Byte>>() {
290        public Option<Byte> f(final Byte b) {
291          return b == Byte.MAX_VALUE ? Option.<Byte>none() : some((byte) (b + 1));
292        }
293      }, new F<Byte, Option<Byte>>() {
294        public Option<Byte> f(final Byte b) {
295          return b == Byte.MIN_VALUE ? Option.<Byte>none() : some((byte) (b - 1));
296        }
297      }, some(Byte.MAX_VALUE), some(Byte.MIN_VALUE), byteOrd);
298    
299      /**
300       * An enumerator for <code>char</code>.
301       */
302      public static final Enumerator<Character> charEnumerator = enumerator(new F<Character, Option<Character>>() {
303        public Option<Character> f(final Character c) {
304          return c == Character.MAX_VALUE ? Option.<Character>none() : some((char) (c + 1));
305        }
306      }, new F<Character, Option<Character>>() {
307        public Option<Character> f(final Character c) {
308          return c == Character.MIN_VALUE ? Option.<Character>none() : some((char) (c - 1));
309        }
310      }, some(Character.MAX_VALUE), some(Character.MIN_VALUE), charOrd);
311    
312      /**
313       * An enumerator for <code>double</code>.
314       */
315      public static final Enumerator<Double> doubleEnumerator = enumerator(new F<Double, Option<Double>>() {
316        public Option<Double> f(final Double d) {
317          return d == Double.MAX_VALUE ? Option.<Double>none() : some(d + 1D);
318        }
319      }, new F<Double, Option<Double>>() {
320        public Option<Double> f(final Double d) {
321          return d == Double.MIN_VALUE ? Option.<Double>none() : some(d - 1D);
322        }
323      }, some(Double.MAX_VALUE), some(Double.MIN_VALUE), doubleOrd);
324    
325      /**
326       * An enumerator for <code>float</code>.
327       */
328      public static final Enumerator<Float> floatEnumerator = enumerator(new F<Float, Option<Float>>() {
329        public Option<Float> f(final Float f) {
330          return f == Float.MAX_VALUE ? Option.<Float>none() : some(f + 1F);
331        }
332      }, new F<Float, Option<Float>>() {
333        public Option<Float> f(final Float f) {
334          return f == Float.MIN_VALUE ? Option.<Float>none() : some(f - 1F);
335        }
336      }, some(Float.MAX_VALUE), some(Float.MIN_VALUE), floatOrd);
337    
338      /**
339       * An enumerator for <code>int</code>.
340       */
341      public static final Enumerator<Integer> intEnumerator = enumerator(new F<Integer, Option<Integer>>() {
342        public Option<Integer> f(final Integer i) {
343          return i == Integer.MAX_VALUE ? Option.<Integer>none() : some(i + 1);
344        }
345      }, new F<Integer, Option<Integer>>() {
346        public Option<Integer> f(final Integer i) {
347          return i == Integer.MIN_VALUE ? Option.<Integer>none() : some(i - 1);
348        }
349      }, some(Integer.MAX_VALUE), some(Integer.MIN_VALUE), intOrd);
350    
351      /**
352       * An enumerator for <code>BigInteger</code>.
353       */
354      public static final Enumerator<BigInteger> bigintEnumerator = enumerator(new F<BigInteger, Option<BigInteger>>() {
355        public Option<BigInteger> f(final BigInteger i) {
356          return some(i.add(BigInteger.ONE));
357        }
358      }, new F<BigInteger, Option<BigInteger>>() {
359        public Option<BigInteger> f(final BigInteger i) {
360          return some(i.subtract(BigInteger.ONE));
361        }
362      }, Option.<BigInteger>none(), Option.<BigInteger>none(), bigintOrd, curry(
363          new F2<BigInteger, Long, Option<BigInteger>>() {
364            public Option<BigInteger> f(final BigInteger i, final Long l) {
365              return some(i.add(BigInteger.valueOf(l)));
366            }
367          }));
368    
369      /**
370       * An enumerator for <code>BigDecimal</code>.
371       */
372      public static final Enumerator<BigDecimal> bigdecimalEnumerator = enumerator(new F<BigDecimal, Option<BigDecimal>>() {
373        public Option<BigDecimal> f(final BigDecimal i) {
374          return some(i.add(BigDecimal.ONE));
375        }
376      }, new F<BigDecimal, Option<BigDecimal>>() {
377        public Option<BigDecimal> f(final BigDecimal i) {
378          return some(i.subtract(BigDecimal.ONE));
379        }
380      }, Option.<BigDecimal>none(), Option.<BigDecimal>none(), bigdecimalOrd, curry(
381          new F2<BigDecimal, Long, Option<BigDecimal>>() {
382            public Option<BigDecimal> f(final BigDecimal d, final Long l) {
383              return some(d.add(BigDecimal.valueOf(l)));
384            }
385          }));
386    
387      /**
388       * An enumerator for <code>long</code>.
389       */
390      public static final Enumerator<Long> longEnumerator = enumerator(new F<Long, Option<Long>>() {
391        public Option<Long> f(final Long i) {
392          return i == Long.MAX_VALUE ? Option.<Long>none() : some(i + 1L);
393        }
394      }, new F<Long, Option<Long>>() {
395        public Option<Long> f(final Long i) {
396          return i == Long.MIN_VALUE ? Option.<Long>none() : some(i - 1L);
397        }
398      }, some(Long.MAX_VALUE), some(Long.MIN_VALUE), longOrd);
399    
400      /**
401       * An enumerator for <code>short</code>.
402       */
403      public static final Enumerator<Short> shortEnumerator = enumerator(new F<Short, Option<Short>>() {
404        public Option<Short> f(final Short i) {
405          return i == Short.MAX_VALUE ? Option.<Short>none() : some((short) (i + 1));
406        }
407      }, new F<Short, Option<Short>>() {
408        public Option<Short> f(final Short i) {
409          return i == Short.MIN_VALUE ? Option.<Short>none() : some((short) (i - 1));
410        }
411      }, some(Short.MAX_VALUE), some(Short.MIN_VALUE), shortOrd);
412    
413      /**
414       * An enumerator for <code>Ordering</code>.
415       */
416      public static final Enumerator<Ordering> orderingEnumerator = enumerator(new F<Ordering, Option<Ordering>>() {
417        public Option<Ordering> f(final Ordering o) {
418          return o == LT ? some(EQ) : o == EQ ? some(GT) : Option.<Ordering>none();
419        }
420      }, new F<Ordering, Option<Ordering>>() {
421        public Option<Ordering> f(final Ordering o) {
422          return o == GT ? some(EQ) : o == EQ ? some(LT) : Option.<Ordering>none();
423        }
424      }, some(GT), some(LT), orderingOrd);
425    
426      /**
427       * An enumerator for <code>Natural</code>
428       */
429      public static final Enumerator<Natural> naturalEnumerator = enumerator(new F<Natural, Option<Natural>>() {
430        public Option<Natural> f(final Natural n) {
431          return Option.some(n.succ());
432        }
433      }, new F<Natural, Option<Natural>>() {
434        public Option<Natural> f(final Natural n) {
435          return n.pred();
436        }
437      }, Option.<Natural>none(), some(Natural.ZERO), naturalOrd, curry(new F2<Natural, Long, Option<Natural>>() {
438        public Option<Natural> f(final Natural n, final Long l) {
439          return some(n).apply(Natural.natural(l).map(curry(new F2<Natural, Natural, Natural>() {
440            public Natural f(final Natural n1, final Natural n2) {
441              return n1.add(n2);
442            }
443          })));
444        }
445      }));
446    
447    }