001    package fj.data;
002    
003    import static fj.data.Option.some;
004    import static fj.data.Stream.iterableStream;
005    import fj.F;
006    import fj.F2;
007    import fj.F3;
008    import fj.P1;
009    import fj.P2;
010    import fj.pre.Equal;
011    import static fj.Function.curry;
012    import static fj.Function.identity;
013    
014    import java.util.Collection;
015    import java.util.Iterator;
016    import java.util.ListIterator;
017    import java.util.NoSuchElementException;
018    
019    /**
020     * A wrapper for Iterable that equips it with some useful functions.
021     */
022    public final class IterableW<A> implements Iterable<A> {
023    
024      private final Iterable<A> i;
025    
026      private IterableW(final Iterable<A> i) {
027        this.i = i;
028      }
029    
030      /**
031       * Wraps the given iterable.
032       *
033       * @param a The iterable to wrap.
034       * @return An iterable equipped with some useful functions.
035       */
036      public static <A> IterableW<A> wrap(final Iterable<A> a) {
037        return new IterableW<A>(a);
038      }
039    
040      /**
041       * Provides a function that wraps the given iterable.
042       *
043       * @return A function that returns the given iterable, wrapped.
044       */
045      public static <A, T extends Iterable<A>> F<T, IterableW<A>> wrap() {
046        return new F<T, IterableW<A>>() {
047          public IterableW<A> f(final T a) {
048            return wrap(a);
049          }
050        };
051      }
052    
053      /**
054       * Returns an Iterable that completely preserves the argument. The unit function for Iterables.
055       *
056       * @param a A value to preserve in an Iterable.
057       * @return An Iterable that yields the argument when iterated over.
058       */
059      public static <A> IterableW<A> iterable(final A a) {
060        return wrap(some(a));
061      }
062    
063      /**
064       * Wraps a given function's return value in a Iterable.
065       * The Kleisli arrow for Iterables.
066       *
067       * @param f The function whose return value to wrap in a Iterable.
068       * @return The equivalent function whose return value is iterable.
069       */
070      public static <A, B> F<A, IterableW<B>> iterable(final F<A, B> f) {
071        return new F<A, IterableW<B>>() {
072          public IterableW<B> f(final A a) {
073            return iterable(f.f(a));
074          }
075        };
076      }
077    
078      /**
079       * Provides a transformation from a function to a Iterable-valued function that is equivalent to it.
080       * The first-class Kleisli arrow for Iterables.
081       *
082       * @return A transformation from a function to the equivalent Iterable-valued function.
083       */
084      public static <A, B> F<F<A, B>, F<A, IterableW<B>>> arrow() {
085        return new F<F<A, B>, F<A, IterableW<B>>>() {
086          public F<A, IterableW<B>> f(final F<A, B> f) {
087            return iterable(f);
088          }
089        };
090      }
091    
092      /**
093       * Binds the given function across the wrapped Iterable with a final join.
094       *
095       * @param f A function to bind across the Iterable.
096       * @return an iterable result of binding the given function over the wrapped Iterable.
097       */
098      public <B, T extends Iterable<B>> IterableW<B> bind(final F<A, T> f) {
099        return wrap(iterableStream(this).bind(new F<A, Stream<B>>() {
100          public Stream<B> f(final A a) {
101            return iterableStream(f.f(a));
102          }
103        }));
104      }
105    
106      /**
107       * Performs function application within an iterable (applicative functor pattern).
108       *
109       * @param f The iterable function to apply.
110       * @return A new iterable after applying the given iterable function to the wrapped iterable.
111       */
112      public <B> IterableW<B> apply(final Iterable<F<A, B>> f) {
113        return wrap(f).bind(new F<F<A, B>, Iterable<B>>() {
114          public Iterable<B> f(final F<A, B> f) {
115            return map(f);
116          }
117        });
118      }
119    
120      /**
121       * Binds the given function to the values in the given iterables with a final join.
122       *
123       * @param a A given iterable to bind the given function with.
124       * @param b A given iterable to bind the given function with.
125       * @param f The function to apply to the values in the given iterables.
126       * @return A new iterable after performing the map, then final join.
127       */
128      public static <A, B, C> IterableW<C> bind(final Iterable<A> a, final Iterable<B> b, final F<A, F<B, C>> f) {
129        return wrap(b).apply(wrap(a).map(f));
130      }
131    
132      /**
133       * Promotes a function of arity-2 to a function on iterables.
134       *
135       * @param f The function to promote.
136       * @return A function of arity-2 promoted to map over iterables.
137       */
138      public static <A, B, C> F<Iterable<A>, F<Iterable<B>, IterableW<C>>> liftM2(final F<A, F<B, C>> f) {
139        return curry(new F2<Iterable<A>, Iterable<B>, IterableW<C>>() {
140          public IterableW<C> f(final Iterable<A> ca, final Iterable<B> cb) {
141            return bind(ca, cb, f);
142          }
143        });
144      }
145    
146      /**
147       * Performs a bind across each element of all iterables of an iterable, collecting the values in an iterable.
148       * This implementation is strict and requires O(n) stack space.
149       *
150       * @param as The iterable of iterables to transform.
151       * @return A iterable of iterables containing the results of the bind operations across all given iterables.
152       */
153      public static <A, T extends Iterable<A>> IterableW<IterableW<A>> sequence(final Iterable<T> as) {
154        final Stream<T> ts = iterableStream(as);
155        return ts.isEmpty() ? iterable(wrap(Option.<A>none())) : wrap(ts.head()).bind(new F<A, Iterable<IterableW<A>>>() {
156          public Iterable<IterableW<A>> f(final A a) {
157            return sequence(ts.tail().map(IterableW.<T, Stream<T>>wrap())._1())
158                .bind(new F<IterableW<A>, Iterable<IterableW<A>>>() {
159                  public Iterable<IterableW<A>> f(final IterableW<A> as) {
160                    return iterable(wrap(Stream.cons(a, new P1<Stream<A>>() {
161                      public Stream<A> _1() {
162                        return iterableStream(as);
163                      }
164                    })));
165                  }
166                });
167          }
168        });
169      }
170    
171      /**
172       * The first-class bind function over Iterable.
173       * Returns a function that binds a given function across a given iterable.
174       *
175       * @return a function that binds a given function across a given iterable.
176       */
177      public static <A, B, T extends Iterable<B>> F<IterableW<A>, F<F<A, T>, IterableW<B>>> bind() {
178        return new F<IterableW<A>, F<F<A, T>, IterableW<B>>>() {
179          public F<F<A, T>, IterableW<B>> f(final IterableW<A> a) {
180            return new F<F<A, T>, IterableW<B>>() {
181              public IterableW<B> f(final F<A, T> f) {
182                return a.bind(f);
183              }
184            };
185          }
186        };
187      }
188    
189      /**
190       * Joins an Iterable of Iterables into a single Iterable.
191       *
192       * @param as An Iterable of Iterables to join.
193       * @return the joined Iterable.
194       */
195      public static <A, T extends Iterable<A>> IterableW<A> join(final Iterable<T> as) {
196        final F<T, T> id = identity();
197        return wrap(as).bind(id);
198      }
199    
200      /**
201       * Returns a function that joins an Iterable of Iterables into a single Iterable.
202       *
203       * @return a function that joins an Iterable of Iterables into a single Iterable.
204       */
205      public static <A, T extends Iterable<A>> F<Iterable<T>, IterableW<A>> join() {
206        return new F<Iterable<T>, IterableW<A>>() {
207          public IterableW<A> f(final Iterable<T> a) {
208            return join(a);
209          }
210        };
211      }
212    
213      /**
214       * Maps a given function across the wrapped Iterable.
215       *
216       * @param f A function to map across the wrapped Iterable.
217       * @return An Iterable of the results of mapping the given function across the wrapped Iterable.
218       */
219      public <B> IterableW<B> map(final F<A, B> f) {
220        return bind(iterable(f));
221      }
222    
223      /**
224       * Returns a function that promotes any function so that it operates on Iterables.
225       *
226       * @return a function that promotes any function so that it operates on Iterables.
227       */
228      public static <A, B> F<F<A, B>, F<IterableW<A>, IterableW<B>>> map() {
229        return new F<F<A, B>, F<IterableW<A>, IterableW<B>>>() {
230          public F<IterableW<A>, IterableW<B>> f(final F<A, B> f) {
231            return new F<IterableW<A>, IterableW<B>>() {
232              public IterableW<B> f(final IterableW<A> a) {
233                return a.map(f);
234              }
235            };
236          }
237        };
238      }
239    
240      /**
241       * The catamorphism for Iterables, implemented as a left fold.
242       *
243       * @param f The function with which to fold the wrapped iterable.
244       * @param z The base case value of the destination type, applied first (leftmost) to the fold.
245       * @return The result of the catamorphism.
246       */
247      public <B> B foldLeft(final F<B, F<A, B>> f, final B z) {
248        B p = z;
249        for (final A x : this) {
250          p = f.f(p).f(x);
251        }
252        return p;
253      }
254    
255      /**
256       * Takes the first 2 elements of the iterable and applies the function to them,
257       * then applies the function to the result and the third element and so on.
258       *
259       * @param f The function to apply on each element of the iterable.
260       * @return The final result after the left-fold reduction.
261       */
262      public A foldLeft1(final F2<A, A, A> f) {
263        return foldLeft1(curry(f));
264      }
265    
266      /**
267       * Takes the first 2 elements of the iterable and applies the function to them,
268       * then applies the function to the result and the third element and so on.
269       *
270       * @param f The function to apply on each element of the iterable.
271       * @return The final result after the left-fold reduction.
272       */
273      public A foldLeft1(final F<A, F<A, A>> f) {
274        return iterableStream(this).foldLeft1(f);
275      }
276    
277      /**
278       * The catamorphism for Iterables, implemented as a right fold.
279       *
280       * @param f The function with which to fold the wrapped iterable.
281       * @param z The base case value of the destination type, applied last (rightmost) to the fold.
282       * @return The result of the catamorphism.
283       */
284      public <B> B foldRight(final F2<A, B, B> f, final B z) {
285        final F<B, B> id = identity();
286        return foldLeft(curry(new F3<F<B, B>, A, B, B>() {
287          public B f(final F<B, B> k, final A a, final B b) {
288            return k.f(f.f(a, b));
289          }
290        }), id).f(z);
291      }
292    
293      /**
294       * Returns an iterator for this iterable.
295       *
296       * @return an iterator for this iterable.
297       */
298      public Iterator<A> iterator() {
299        return i.iterator();
300      }
301    
302      /**
303       * Zips this iterable with the given iterable of functions, applying each function in turn to the
304       * corresponding element in this iterable to produce a new iterable. The iteration is normalised
305       * so that it ends when one of the iterators is exhausted.
306       *
307       * @param fs The iterable of functions to apply to this iterable.
308       * @return A new iterable with the results of applying the functions to this iterable.
309       */
310      public <B> IterableW<B> zapp(final Iterable<F<A, B>> fs) {
311        return wrap(iterableStream(this).zapp(iterableStream(fs)));
312      }
313    
314      /**
315       * Zips this iterable with the given iterable using the given function to produce a new iterable. If
316       * this iterable and the given iterable have different lengths, then the longer iterable is normalised
317       * so this function never fails.
318       *
319       * @param bs The iterable to zip this iterable with.
320       * @param f  The function to zip this iterable and the given iterable with.
321       * @return A new iterable with a length the same as the shortest of this iterable and the given
322       *         iterable.
323       */
324      public <B, C> Iterable<C> zipWith(final Iterable<B> bs, final F<A, F<B, C>> f) {
325        return wrap(iterableStream(this).zipWith(iterableStream(bs), f));
326      }
327    
328      /**
329       * Zips this iterable with the given iterable using the given function to produce a new iterable. If
330       * this iterable and the given iterable have different lengths, then the longer iterable is normalised
331       * so this function never fails.
332       *
333       * @param bs The iterable to zip this iterable with.
334       * @param f  The function to zip this iterable and the given iterable with.
335       * @return A new iterable with a length the same as the shortest of this iterable and the given
336       *         iterable.
337       */
338      public <B, C> Iterable<C> zipWith(final Iterable<B> bs, final F2<A, B, C> f) {
339        return zipWith(bs, curry(f));
340      }
341    
342      /**
343       * Zips this iterable with the given iterable to produce a iterable of pairs. If this iterable and the
344       * given iterable have different lengths, then the longer iterable is normalised so this function
345       * never fails.
346       *
347       * @param bs The iterable to zip this iterable with.
348       * @return A new iterable with a length the same as the shortest of this iterable and the given
349       *         iterable.
350       */
351      public <B> Iterable<P2<A, B>> zip(final Iterable<B> bs) {
352        return wrap(iterableStream(this).zip(iterableStream(bs)));
353      }
354    
355      /**
356       * Zips this iterable with the index of its element as a pair.
357       *
358       * @return A new iterable with the same length as this iterable.
359       */
360      public Iterable<P2<A, Integer>> zipIndex() {
361        return wrap(iterableStream(this).zipIndex());
362      }
363    
364      /**
365       * Returns a java.util.List implementation for this iterable.
366       * The returned list cannot be modified.
367       *
368       * @return An immutable implementation of java.util.List for this iterable.
369       */
370      public java.util.List<A> toStandardList() {
371        return new java.util.List<A>() {
372    
373          public int size() {
374            return iterableStream(IterableW.this).length();
375          }
376    
377          public boolean isEmpty() {
378            return iterableStream(IterableW.this).isEmpty();
379          }
380    
381          @SuppressWarnings({"unchecked"})
382          public boolean contains(final Object o) {
383            return iterableStream(IterableW.this).exists(Equal.<A>anyEqual().eq((A) o));
384          }
385    
386          public Iterator<A> iterator() {
387            return IterableW.this.iterator();
388          }
389    
390          public Object[] toArray() {
391            return Array.iterableArray(iterableStream(IterableW.this)).array();
392          }
393    
394          @SuppressWarnings({"SuspiciousToArrayCall"})
395          public <T> T[] toArray(final T[] a) {
396            return iterableStream(IterableW.this).toCollection().toArray(a);
397          }
398    
399          public boolean add(final A a) {
400            return false;
401          }
402    
403          public boolean remove(final Object o) {
404            return false;
405          }
406    
407          public boolean containsAll(final Collection<?> c) {
408            return iterableStream(IterableW.this).toCollection().containsAll(c);
409          }
410    
411          public boolean addAll(final Collection<? extends A> c) {
412            return false;
413          }
414    
415          public boolean addAll(final int index, final Collection<? extends A> c) {
416            return false;
417          }
418    
419          public boolean removeAll(final Collection<?> c) {
420            return false;
421          }
422    
423          public boolean retainAll(final Collection<?> c) {
424            return false;
425          }
426    
427          public void clear() {
428            throw new UnsupportedOperationException("Modifying an immutable List.");
429          }
430    
431          public A get(final int index) {
432            return iterableStream(IterableW.this).index(index);
433          }
434    
435          public A set(final int index, final A element) {
436            throw new UnsupportedOperationException("Modifying an immutable List.");
437          }
438    
439          public void add(final int index, final A element) {
440            throw new UnsupportedOperationException("Modifying an immutable List.");
441          }
442    
443          public A remove(final int index) {
444            throw new UnsupportedOperationException("Modifying an immutable List.");
445          }
446    
447          public int indexOf(final Object o) {
448            int i = -1;
449            for (final A a : IterableW.this) {
450              i++;
451              if (a.equals(o))
452                return i;
453            }
454            return i;
455          }
456    
457          public int lastIndexOf(final Object o) {
458            int i = -1;
459            int last = -1;
460            for (final A a : IterableW.this) {
461              i++;
462              if (a.equals(o))
463                last = i;
464            }
465            return last;
466          }
467    
468          public ListIterator<A> listIterator() {
469            return toListIterator(toZipper());
470          }
471    
472          public ListIterator<A> listIterator(final int index) {
473            return toListIterator(toZipper().bind(Zipper.<A>move().f(index)));
474          }
475    
476          public java.util.List<A> subList(final int fromIndex, final int toIndex) {
477            return wrap(Stream.iterableStream(IterableW.this).drop(fromIndex).take(toIndex - fromIndex)).toStandardList();
478          }
479    
480          private ListIterator<A> toListIterator(final Option<Zipper<A>> z) {
481            return new ListIterator<A>() {
482    
483              private Option<Zipper<A>> pz = z;
484    
485              public boolean hasNext() {
486                return pz.isSome() && !pz.some().atEnd();
487              }
488    
489              public A next() {
490                if (pz.isSome())
491                  pz = pz.some().next();
492                else throw new NoSuchElementException();
493                if (pz.isSome())
494                  return pz.some().focus();
495                else throw new NoSuchElementException();
496              }
497    
498              public boolean hasPrevious() {
499                return pz.isSome() && !pz.some().atStart();
500              }
501    
502              public A previous() {
503                pz = pz.some().previous();
504                return pz.some().focus();
505              }
506    
507              public int nextIndex() {
508                return pz.some().index() + (pz.some().atEnd() ? 0 : 1);
509              }
510    
511              public int previousIndex() {
512                return pz.some().index() - (pz.some().atStart() ? 0 : 1);
513              }
514    
515              public void remove() {
516                throw new UnsupportedOperationException("Remove on immutable ListIterator");
517              }
518    
519              public void set(final A a) {
520                throw new UnsupportedOperationException("Set on immutable ListIterator");
521              }
522    
523              public void add(final A a) {
524                throw new UnsupportedOperationException("Add on immutable ListIterator");
525              }
526            };
527          }
528    
529        };
530      }
531    
532      public Option<Zipper<A>> toZipper() {
533        return Zipper.fromStream(iterableStream(this));
534      }
535    }