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 }