001    package fj.data;
002    
003    import static fj.Bottom.error;
004    import fj.Effect;
005    import fj.F;
006    import static fj.Function.identity;
007    import static fj.P.p;
008    import fj.P1;
009    import fj.Unit;
010    import static fj.Unit.unit;
011    import static fj.data.Array.mkArray;
012    import static fj.data.List.single;
013    import static fj.data.List.cons_;
014    import static fj.data.Option.some;
015    
016    import java.util.Collection;
017    import java.util.Iterator;
018    
019    /**
020     * The <code>Either</code> type represents a value of one of two possible types (a disjoint union).
021     * The data constructors; <code>Left</code> and <code>Right</code> represent the two possible
022     * values. The <code>Either</code> type is often used as an alternative to
023     * <code>scala.Option</code> where <code>Left</code> represents failure (by convention) and
024     * <code>Right</code> is akin to <code>Some</code>.
025     *
026     * @version %build.number%<br>
027     *          <ul>
028     *          <li>$LastChangedRevision: 161 $</li>
029     *          <li>$LastChangedDate: 2009-06-01 17:14:38 +1000 (Mon, 01 Jun 2009) $</li>
030     *          </ul>
031     */
032    public abstract class Either<A, B> {
033      private Either() {
034    
035      }
036    
037      /**
038       * Projects this either as a left.
039       *
040       * @return A left projection of this either.
041       */
042      public LeftProjection<A, B> left() {
043        return new LeftProjection<A, B>(this);
044      }
045    
046      /**
047       * Projects this either as a right.
048       *
049       * @return A right projection of this either.
050       */
051      public RightProjection<A, B> right() {
052        return new RightProjection<A, B>(this);
053      }
054    
055      /**
056       * Returns <code>true</code> if this either is a left, <code>false</code> otherwise.
057       *
058       * @return <code>true</code> if this either is a left, <code>false</code> otherwise.
059       */
060      public abstract boolean isLeft();
061    
062      /**
063       * Returns <code>true</code> if this either is a right, <code>false</code> otherwise.
064       *
065       * @return <code>true</code> if this either is a right, <code>false</code> otherwise.
066       */
067      public abstract boolean isRight();
068    
069      /**
070       * The catamorphism for either. Folds over this either breaking into left or right.
071       *
072       * @param left  The function to call if this is left.
073       * @param right The function to call if this is right.
074       * @return The reduced value.
075       */
076      public <X> X either(final F<A, X> left, final F<B, X> right) {
077        return isLeft() ?
078               left.f(left().value()) :
079               right.f(right().value());
080      }
081    
082      /**
083       * If this is a left, then return the left value in right, or vice versa.
084       *
085       * @return The value of this either swapped to the opposing side.
086       */
087      public Either<B, A> swap() {
088        return isLeft() ? new Right<B, A>(((Left<A, B>) this).a) : new Left<B, A>(((Right<A, B>) this).b);
089      }
090    
091      private static final class Left<A, B> extends Either<A, B> {
092        private final A a;
093    
094        Left(final A a) {
095          this.a = a;
096        }
097    
098        public boolean isLeft() {
099          return true;
100        }
101    
102        public boolean isRight() {
103          return false;
104        }
105      }
106    
107      private static final class Right<A, B> extends Either<A, B> {
108        private final B b;
109    
110        Right(final B b) {
111          this.b = b;
112        }
113    
114        public boolean isLeft() {
115          return false;
116        }
117    
118        public boolean isRight() {
119          return true;
120        }
121      }
122    
123      /**
124       * A left projection of an either value.
125       */
126      public final class LeftProjection<A, B> implements Iterable<A> {
127        private final Either<A, B> e;
128    
129        private LeftProjection(final Either<A, B> e) {
130          this.e = e;
131        }
132    
133        /**
134         * Returns an iterator for this projection. This method exists to permit the use in a <code>for</code>-each loop.
135         *
136         * @return A iterator for this projection.
137         */
138        public Iterator<A> iterator() {
139          return toCollection().iterator();
140        }
141    
142        /**
143         * The either value underlying this projection.
144         *
145         * @return The either value underlying this projection.
146         */
147        public Either<A, B> either() {
148          return e;
149        }
150    
151        /**
152         * Returns the value of this projection or fails with the given error message.
153         *
154         * @param err The error message to fail with.
155         * @return The value of this projection
156         */
157        public A valueE(final P1<String> err) {
158          if (e.isLeft())
159            //noinspection CastToConcreteClass
160            return ((Left<A, B>) e).a;
161          else
162            throw error(err._1());
163        }
164    
165        /**
166         * Returns the value of this projection or fails with the given error message.
167         *
168         * @param err The error message to fail with.
169         * @return The value of this projection
170         */
171        public A valueE(final String err) {
172          return valueE(p(err));
173        }
174    
175        /**
176         * The value of this projection or fails with a specialised error message.
177         *
178         * @return The value of this projection.
179         */
180        public A value() {
181          return valueE(p("left.value on Right"));
182        }
183    
184        /**
185         * The value of this projection or the given argument.
186         *
187         * @param a The value to return if this projection has no value.
188         * @return The value of this projection or the given argument.
189         */
190        public A orValue(final P1<A> a) {
191          return isLeft() ? value() : a._1();
192        }
193    
194        /**
195         * The value of this projection or the given argument.
196         *
197         * @param a The value to return if this projection has no value.
198         * @return The value of this projection or the given argument.
199         */
200        public A orValue(final A a) {
201          return isLeft() ? value() : a;
202        }
203    
204        /**
205         * The value of this projection or the result of the given function on the opposing projection's
206         * value.
207         *
208         * @param f The function to execute if this projection has no value.
209         * @return The value of this projection or the result of the given function on the opposing projection's
210         *         value.
211         */
212        public A on(final F<B, A> f) {
213          return isLeft() ? value() : f.f(e.right().value());
214        }
215    
216        /**
217         * Execute a side-effect on this projection's value if it has one.
218         *
219         * @param f The side-effect to execute.
220         * @return The unit value.
221         */
222        public Unit foreach(final F<A, Unit> f) {
223          if (isLeft())
224            f.f(value());
225    
226          return unit();
227        }
228    
229        /**
230         * Execute a side-effect on this projection's value if it has one.
231         *
232         * @param f The side-effect to execute.
233         */
234        public void foreach(final Effect<A> f) {
235          if (isLeft())
236            f.e(value());
237        }
238    
239        /**
240         * Map the given function across this projection's value if it has one.
241         *
242         * @param f The function to map across this projection.
243         * @return A new either value after mapping.
244         */
245        public <X> Either<X, B> map(final F<A, X> f) {
246          return isLeft() ? new Left<X, B>(f.f(value())) : new Right<X, B>(e.right().value());
247        }
248    
249        /**
250         * Binds the given function across this projection's value if it has one.
251         *
252         * @param f The function to bind across this projection.
253         * @return A new either value after binding.
254         */
255        public <X> Either<X, B> bind(final F<A, Either<X, B>> f) {
256          return isLeft() ? f.f(value()) : new Right<X, B>(e.right().value());
257        }
258    
259        /**
260         * Anonymous bind through this projection.
261         *
262         * @param e The value to bind with.
263         * @return An either after binding through this projection.
264         */
265        public <X> Either<X, B> sequence(final Either<X, B> e) {
266          return bind(fj.Function.<A, Either<X, B>>constant(e));
267        }
268    
269        /**
270         * Returns <code>None</code> if this projection has no value or if the given predicate
271         * <code>p</code> does not hold for the value, otherwise, returns a right in <code>Some</code>.
272         *
273         * @param f The predicate function to test on this projection's value.
274         * @return <code>None</code> if this projection has no value or if the given predicate
275         *         <code>p</code> does not hold for the value, otherwise, returns a right in <code>Some</code>.
276         */
277        public <X> Option<Either<A, X>> filter(final F<A, Boolean> f) {
278          return isLeft() ?
279                 f.f(value()) ?
280                 Option.<Either<A, X>>some(new Left<A, X>(value())) :
281                 Option.<Either<A, X>>none() :
282                 Option.<Either<A, X>>none();
283        }
284    
285        /**
286         * Function application on this projection's value.
287         *
288         * @param e The either of the function to apply on this projection's value.
289         * @return The result of function application within either.
290         */
291        public <X> Either<X, B> apply(final Either<F<A, X>, B> e) {
292          return e.left().bind(new F<F<A, X>, Either<X, B>>() {
293            public Either<X, B> f(final F<A, X> f) {
294              return map(f);
295            }
296          });
297        }
298    
299        /**
300         * Returns <code>true</code> if no value or returns the result of the application of the given
301         * function to the value.
302         *
303         * @param f The predicate function to test on this projection's value.
304         * @return <code>true</code> if no value or returns the result of the application of the given
305         *         function to the value.
306         */
307        public boolean forall(final F<A, Boolean> f) {
308          return isRight() || f.f(value());
309        }
310    
311        /**
312         * Returns <code>false</code> if no value or returns the result of the application of the given
313         * function to the value.
314         *
315         * @param f The predicate function to test on this projection's value.
316         * @return <code>false</code> if no value or returns the result of the application of the given
317         *         function to the value.
318         */
319        public boolean exists(final F<A, Boolean> f) {
320          return isLeft() && f.f(value());
321        }
322    
323        /**
324         * Returns a single element list if this projection has a value, otherwise an empty list.
325         *
326         * @return A single element list if this projection has a value, otherwise an empty list.
327         */
328        public List<A> toList() {
329          return isLeft() ? single(value()) : List.<A>nil();
330        }
331    
332        /**
333         * Returns this projection's value in <code>Some</code> if it exists, otherwise
334         * <code>None</code>.
335         *
336         * @return This projection's value in <code>Some</code> if it exists, otherwise
337         *         <code>None</code>.
338         */
339        public Option<A> toOption() {
340          return isLeft() ? some(value()) : Option.<A>none();
341        }
342    
343        /**
344         * Returns a single element array if this projection has a value, otherwise an empty array.
345         *
346         * @return A single element array if this projection has a value, otherwise an empty array.
347         */
348        public Array<A> toArray() {
349          if (isLeft()) {
350            final Object[] a = new Object[1];
351            a[0] = value();
352            return mkArray(a);
353          } else
354            return mkArray(new Object[0]);
355        }
356    
357        /**
358         * Returns a single element stream if this projection has a value, otherwise an empty stream.
359         *
360         * @return A single element stream if this projection has a value, otherwise an empty stream.
361         */
362        public Stream<A> toStream() {
363          return isLeft() ? Stream.single(value()) : Stream.<A>nil();
364        }
365    
366        /**
367         * Projects an immutable collection of this projection.
368         *
369         * @return An immutable collection of this projection.
370         */
371        public Collection<A> toCollection() {
372          return toList().toCollection();
373        }
374      }
375    
376      /**
377       * A right projection of an either value.
378       */
379      public final class RightProjection<A, B> implements Iterable<B> {
380        private final Either<A, B> e;
381    
382        private RightProjection(final Either<A, B> e) {
383          this.e = e;
384        }
385    
386        /**
387         * Returns an iterator for this projection. This method exists to permit the use in a <code>for</code>-each loop.
388         *
389         * @return A iterator for this projection.
390         */
391        public Iterator<B> iterator() {
392          return toCollection().iterator();
393        }
394    
395        /**
396         * The either value underlying this projection.
397         *
398         * @return The either value underlying this projection.
399         */
400        public Either<A, B> either() {
401          return e;
402        }
403    
404        /**
405         * Returns the value of this projection or fails with the given error message.
406         *
407         * @param err The error message to fail with.
408         * @return The value of this projection
409         */
410        public B valueE(final P1<String> err) {
411          if (e.isRight())
412            //noinspection CastToConcreteClass
413            return ((Right<A, B>) e).b;
414          else
415            throw error(err._1());
416        }
417    
418        /**
419         * The value of this projection or fails with a specialised error message.
420         *
421         * @return The value of this projection.
422         */
423        public B value() {
424          return valueE(p("right.value on Left"));
425        }
426    
427        /**
428         * The value of this projection or the given argument.
429         *
430         * @param b The value to return if this projection has no value.
431         * @return The value of this projection or the given argument.
432         */
433        public B orValue(final P1<B> b) {
434          return isRight() ? value() : b._1();
435        }
436    
437        /**
438         * The value of this projection or the result of the given function on the opposing projection's
439         * value.
440         *
441         * @param f The function to execute if this projection has no value.
442         * @return The value of this projection or the result of the given function on the opposing projection's
443         *         value.
444         */
445        public B on(final F<A, B> f) {
446          return isRight() ? value() : f.f(e.left().value());
447        }
448    
449        /**
450         * Execute a side-effect on this projection's value if it has one.
451         *
452         * @param f The side-effect to execute.
453         * @return The unit value.
454         */
455        public Unit foreach(final F<B, Unit> f) {
456          if (isRight())
457            f.f(value());
458    
459          return unit();
460        }
461    
462        /**
463         * Execute a side-effect on this projection's value if it has one.
464         *
465         * @param f The side-effect to execute.
466         */
467        public void foreach(final Effect<B> f) {
468          if (isRight())
469            f.e(value());
470        }
471    
472        /**
473         * Map the given function across this projection's value if it has one.
474         *
475         * @param f The function to map across this projection.
476         * @return A new either value after mapping.
477         */
478        public <X> Either<A, X> map(final F<B, X> f) {
479          return isRight() ? new Right<A, X>(f.f(value())) : new Left<A, X>(e.left().value());
480        }
481    
482        /**
483         * Binds the given function across this projection's value if it has one.
484         *
485         * @param f The function to bind across this projection.
486         * @return A new either value after binding.
487         */
488        public <X> Either<A, X> bind(final F<B, Either<A, X>> f) {
489          return isRight() ? f.f(value()) : new Left<A, X>(e.left().value());
490        }
491    
492    
493        /**
494         * Anonymous bind through this projection.
495         *
496         * @param e The value to bind with.
497         * @return An either after binding through this projection.
498         */
499        public <X> Either<A, X> sequence(final Either<A, X> e) {
500          return bind(fj.Function.<B, Either<A, X>>constant(e));
501        }
502    
503        /**
504         * Returns <code>None</code> if this projection has no value or if the given predicate
505         * <code>p</code> does not hold for the value, otherwise, returns a left in <code>Some</code>.
506         *
507         * @param f The predicate function to test on this projection's value.
508         * @return <code>None</code> if this projection has no value or if the given predicate
509         *         <code>p</code> does not hold for the value, otherwise, returns a left in <code>Some</code>.
510         */
511        public <X> Option<Either<X, B>> filter(final F<B, Boolean> f) {
512          return isRight() ?
513                 f.f(value()) ?
514                 Option.<Either<X, B>>some(new Right<X, B>(value())) :
515                 Option.<Either<X, B>>none() :
516                 Option.<Either<X, B>>none();
517        }
518    
519        /**
520         * Function application on this projection's value.
521         *
522         * @param e The either of the function to apply on this projection's value.
523         * @return The result of function application within either.
524         */
525        public <X> Either<A, X> apply(final Either<A, F<B, X>> e) {
526          return e.right().bind(new F<F<B, X>, Either<A, X>>() {
527            public Either<A, X> f(final F<B, X> f) {
528              return map(f);
529            }
530          });
531        }
532    
533        /**
534         * Returns <code>true</code> if no value or returns the result of the application of the given
535         * function to the value.
536         *
537         * @param f The predicate function to test on this projection's value.
538         * @return <code>true</code> if no value or returns the result of the application of the given
539         *         function to the value.
540         */
541        public boolean forall(final F<B, Boolean> f) {
542          return isLeft() || f.f(value());
543        }
544    
545        /**
546         * Returns <code>false</code> if no value or returns the result of the application of the given
547         * function to the value.
548         *
549         * @param f The predicate function to test on this projection's value.
550         * @return <code>false</code> if no value or returns the result of the application of the given
551         *         function to the value.
552         */
553        public boolean exists(final F<B, Boolean> f) {
554          return isRight() && f.f(value());
555        }
556    
557        /**
558         * Returns a single element list if this projection has a value, otherwise an empty list.
559         *
560         * @return A single element list if this projection has a value, otherwise an empty list.
561         */
562        public List<B> toList() {
563          return isRight() ? single(value()) : List.<B>nil();
564        }
565    
566        /**
567         * Returns this projection's value in <code>Some</code> if it exists, otherwise
568         * <code>None</code>.
569         *
570         * @return This projection's value in <code>Some</code> if it exists, otherwise
571         *         <code>None</code>.
572         */
573        public Option<B> toOption() {
574          return isRight() ? some(value()) : Option.<B>none();
575        }
576    
577        /**
578         * Returns a single element array if this projection has a value, otherwise an empty array.
579         *
580         * @return A single element array if this projection has a value, otherwise an empty array.
581         */
582        public Array<B> toArray() {
583          if (isRight()) {
584            final Object[] a = new Object[1];
585            a[0] = value();
586            return mkArray(a);
587          } else
588            return Array.empty();
589        }
590    
591        /**
592         * Returns a single element stream if this projection has a value, otherwise an empty stream.
593         *
594         * @return A single element stream if this projection has a value, otherwise an empty stream.
595         */
596        public Stream<B> toStream() {
597          return isRight() ? Stream.single(value()) : Stream.<B>nil();
598        }
599    
600        /**
601         * Projects an immutable collection of this projection.
602         *
603         * @return An immutable collection of this projection.
604         */
605        public Collection<B> toCollection() {
606          return toList().toCollection();
607        }
608      }
609    
610      /**
611       * Construct a left value of either.
612       *
613       * @param a The value underlying the either.
614       * @return A left value of either.
615       */
616      public static <A, B> Either<A, B> left(final A a) {
617        return new Left<A, B>(a);
618      }
619    
620      /**
621       * A function that constructs a left value of either.
622       *
623       * @return A function that constructs a left value of either.
624       */
625      public static <A, B> F<A, Either<A, B>> left_() {
626        return new F<A, Either<A, B>>() {
627          public Either<A, B> f(final A a) {
628            return left(a);
629          }
630        };
631      }
632    
633      /**
634       * A function that constructs a right value of either.
635       *
636       * @return A function that constructs a right value of either.
637       */
638      public static <A, B> F<B, Either<A, B>> right_() {
639        return new F<B, Either<A, B>>() {
640          public Either<A, B> f(final B b) {
641            return right(b);
642          }
643        };
644      }
645    
646      /**
647       * Construct a right value of either.
648       *
649       * @param b The value underlying the either.
650       * @return A right value of either.
651       */
652      public static <A, B> Either<A, B> right(final B b) {
653        return new Right<A, B>(b);
654      }
655    
656      /**
657       * @return A function that maps another function across an either's left projection.
658       */
659      public static <A, B, X> F<F<A, X>, F<Either<A, B>, Either<X, B>>> leftMap_() {
660        return new F<F<A, X>, F<Either<A, B>, Either<X, B>>>() {
661          public F<Either<A, B>, Either<X, B>> f(final F<A, X> axf) {
662            return new F<Either<A, B>, Either<X, B>>() {
663              public Either<X, B> f(final Either<A, B> e) {
664                return e.left().map(axf);
665              }
666            };
667          }
668        };
669      }
670    
671      /**
672       * @return A function that maps another function across an either's right projection.
673       */
674      public static <A, B, X> F<F<B, X>, F<Either<A, B>, Either<A, X>>> rightMap_() {
675        return new F<F<B, X>, F<Either<A, B>, Either<A, X>>>() {
676          public F<Either<A, B>, Either<A, X>> f(final F<B, X> axf) {
677            return new F<Either<A, B>, Either<A, X>>() {
678              public Either<A, X> f(final Either<A, B> e) {
679                return e.right().map(axf);
680              }
681            };
682          }
683        };
684      }
685    
686      /**
687       * Joins an either through left.
688       *
689       * @param e The either of either to join.
690       * @return An either after joining.
691       */
692      public static <A, B> Either<A, B> joinLeft(final Either<Either<A, B>, B> e) {
693        final F<Either<A, B>, Either<A, B>> id = identity();
694        return e.left().bind(id);
695      }
696    
697      /**
698       * Joins an either through right.
699       *
700       * @param e The either of either to join.
701       * @return An either after joining.
702       */
703      public static <A, B> Either<A, B> joinRight(final Either<A, Either<A, B>> e) {
704        final F<Either<A, B>, Either<A, B>> id = identity();
705        return e.right().bind(id);
706      }
707    
708      /**
709       * Sequences through the left side of the either monad with a list of values.
710       *
711       * @param a The list of values to sequence with the either monad.
712       * @return A sequenced value.
713       */
714      public static <A, X> Either<List<A>, X> sequenceLeft(final List<Either<A, X>> a) {
715        return a.isEmpty() ?
716               Either.<List<A>, X>left(List.<A>nil()) :
717               a.head().left().bind(new F<A, Either<List<A>, X>>() {
718                 public Either<List<A>, X> f(final A aa) {
719                   return sequenceLeft(a.tail()).left().map(cons_(aa));
720                 }
721               });
722      }
723    
724      /**
725       * Sequences through the right side of the either monad with a list of values.
726       *
727       * @param a The list of values to sequence with the either monad.
728       * @return A sequenced value.
729       */
730      public static <B, X> Either<X, List<B>> sequenceRight(final List<Either<X, B>> a) {
731        return a.isEmpty() ?
732               Either.<X, List<B>>right(List.<B>nil()) :
733               a.head().right().bind(new F<B, Either<X, List<B>>>() {
734                 public Either<X, List<B>> f(final B bb) {
735                   return sequenceRight(a.tail()).right().map(cons_(bb));
736                 }
737               });
738      }
739    
740      /**
741       * Takes an <code>Either</code> to its contained value within left or right.
742       *
743       * @param e The either to reduce.
744       * @return An <code>Either</code> to its contained value within left or right.
745       */
746      public static <A> A reduce(final Either<A, A> e) {
747        return e.isLeft() ? e.left().value() : e.right().value();
748      }
749    
750      /**
751       * If the condition satisfies, return the given A in left, otherwise, return the given B in right.
752       *
753       * @param c     The condition to test.
754       * @param right The right value to use if the condition satisfies.
755       * @param left  The left value to use if the condition does not satisfy.
756       * @return A constructed either based on the given condition.
757       */
758      public static <A, B> Either<A, B> iif(final boolean c, final P1<B> right, final P1<A> left) {
759        return c ? new Right<A, B>(right._1()) : new Left<A, B>(left._1());
760      }
761    
762      /**
763       * Returns all the left values in the given list.
764       *
765       * @param es The list of possible left values.
766       * @return All the left values in the given list.
767       */
768      public static <A, B> List<A> lefts(final List<Either<A, B>> es) {
769        return es.foldRight(new F<Either<A, B>, F<List<A>, List<A>>>() {
770          public F<List<A>, List<A>> f(final Either<A, B> e) {
771            return new F<List<A>, List<A>>() {
772              public List<A> f(final List<A> as) {
773                return e.isLeft() ? as.cons(e.left().value()) : as;
774              }
775            };
776          }
777        }, List.<A>nil());
778      }
779    
780      /**
781       * Returns all the right values in the given list.
782       *
783       * @param es The list of possible right values.
784       * @return All the right values in the given list.
785       */
786      public static <A, B> List<B> rights(final List<Either<A, B>> es) {
787        return es.foldRight(new F<Either<A, B>, F<List<B>, List<B>>>() {
788          public F<List<B>, List<B>> f(final Either<A, B> e) {
789            return new F<List<B>, List<B>>() {
790              public List<B> f(final List<B> bs) {
791                return e.isRight() ? bs.cons(e.right().value()) : bs;
792              }
793            };
794          }
795        }, List.<B>nil());
796      }
797    }
798