001    package fj.data;
002    
003    import static fj.data.Stream.nil;
004    import static fj.data.Stream.repeat;
005    import static fj.data.Option.some;
006    import static fj.data.Option.none;
007    import fj.pre.Ord;
008    import fj.pre.Equal;
009    import fj.pre.Show;
010    import fj.*;
011    import static fj.F2W.$$;
012    import static fj.Function.*;
013    import fj.function.Integers;
014    
015    import java.util.Iterator;
016    
017    /**
018     * Provides a pointed stream, which is a non-empty zipper-like stream structure that tracks an index (focus)
019     * position in a stream. Focus can be moved forward and backwards through the stream, elements can be inserted
020     * before or after the focused position, and the focused item can be deleted.
021     * <p/>
022     * Based on the pointedlist library by Jeff Wheeler.
023     */
024    public class Zipper<A> implements Iterable<Zipper<A>> {
025      private final Stream<A> left;
026      private final A focus;
027      private final Stream<A> right;
028    
029      private Zipper(final Stream<A> left, final A focus, final Stream<A> right) {
030        this.left = left;
031        this.focus = focus;
032        this.right = right;
033      }
034    
035    
036      /**
037       * Creates a new Zipper with the given streams before and after the focus, and the given focused item.
038       *
039       * @param left  The stream of elements before the focus.
040       * @param focus The element under focus.
041       * @param right The stream of elements after the focus.
042       * @return a new Zipper with the given streams before and after the focus, and the given focused item.
043       */
044      public static <A> Zipper<A> zipper(final Stream<A> left, final A focus, final Stream<A> right) {
045        return new Zipper<A>(left, focus, right);
046      }
047    
048      /**
049       * Creates a new Zipper from the given triple.
050       *
051       * @param p A triple of the elements before the focus, the focus element, and the elements after the focus,
052       *          respectively.
053       * @return a new Zipper created from the given triple.
054       */
055      public static <A> Zipper<A> zipper(final P3<Stream<A>, A, Stream<A>> p) {
056        return new Zipper<A>(p._1(), p._2(), p._3());
057      }
058    
059      /**
060       * First-class constructor of zippers.
061       *
062       * @return A function that yields a new zipper given streams on the left and right and a focus element.
063       */
064      public static <A> F3<Stream<A>, A, Stream<A>, Zipper<A>> zipper() {
065        return new F3<Stream<A>, A, Stream<A>, Zipper<A>>() {
066          public Zipper<A> f(final Stream<A> l, final A a, final Stream<A> r) {
067            return zipper(l, a, r);
068          }
069        };
070      }
071    
072      /**
073       * Returns the product-3 representation of this Zipper.
074       *
075       * @return the product-3 representation of this Zipper.
076       */
077      public P3<Stream<A>, A, Stream<A>> p() {
078        return P.p(left, focus, right);
079      }
080    
081      /**
082       * A first-class function that yields the product-3 representation of a given Zipper.
083       *
084       * @return A first-class function that yields the product-3 representation of a given Zipper.
085       */
086      public static <A> F<Zipper<A>, P3<Stream<A>, A, Stream<A>>> p_() {
087        return new F<Zipper<A>, P3<Stream<A>, A, Stream<A>>>() {
088          public P3<Stream<A>, A, Stream<A>> f(final Zipper<A> a) {
089            return a.p();
090          }
091        };
092      }
093    
094      /**
095       * An Ord instance for Zippers.
096       *
097       * @param o An Ord instance for the element type.
098       * @return An Ord instance for Zippers.
099       */
100      public static <A> Ord<Zipper<A>> ord(final Ord<A> o) {
101        final Ord<Stream<A>> so = Ord.streamOrd(o);
102        return Ord.p3Ord(so, o, so).comap(Zipper.<A>p_());
103      }
104    
105      /**
106       * An Equal instance for Zippers.
107       *
108       * @param e An Equal instance for the element type.
109       * @return An Equal instance for Zippers.
110       */
111      public static <A> Equal<Zipper<A>> eq(final Equal<A> e) {
112        final Equal<Stream<A>> se = Equal.streamEqual(e);
113        return Equal.p3Equal(se, e, se).comap(Zipper.<A>p_());
114      }
115    
116      /**
117       * A Show instance for Zippers.
118       *
119       * @param s A Show instance for the element type.
120       * @return A Show instance for Zippers.
121       */
122      public static <A> Show<Zipper<A>> show(final Show<A> s) {
123        final Show<Stream<A>> ss = Show.streamShow(s);
124        return Show.p3Show(ss, s, ss).comap(Zipper.<A>p_());
125      }
126    
127      /**
128       * Maps the given function across the elements of this zipper (covariant functor pattern).
129       *
130       * @param f A function to map across this zipper.
131       * @return A new zipper with the given function applied to all elements.
132       */
133      public <B> Zipper<B> map(final F<A, B> f) {
134        return zipper(left.map(f), f.f(focus), right.map(f));
135      }
136    
137      /**
138       * Performs a right-fold reduction across this zipper.
139       *
140       * @param f The function to apply on each element of this zipper.
141       * @param z The beginning value to start the application from.
142       * @return the final result after the right-fold reduction.
143       */
144      public <B> B foldRight(final F<A, F<B, B>> f, final B z) {
145        return left.foldLeft(flip(f),
146                             right.cons(focus).foldRight(compose(
147                                 Function.<P1<B>, B, B>andThen().f(P1.<B>__1()), f), z));
148      }
149    
150      /**
151       * Creates a new zipper with a single element.
152       *
153       * @param a The focus element of the new zipper.
154       * @return a new zipper with a single element which is in focus.
155       */
156      public static <A> Zipper<A> single(final A a) {
157        return zipper(Stream.<A>nil(), a, Stream.<A>nil());
158      }
159    
160      /**
161       * Possibly create a zipper if the provided stream has at least one element, otherwise None.
162       * The provided stream's head will be the focus of the zipper, and the rest of the stream will follow
163       * on the right side.
164       *
165       * @param a The stream from which to create a zipper.
166       * @return a new zipper if the provided stream has at least one element, otherwise None.
167       */
168      public static <A> Option<Zipper<A>> fromStream(final Stream<A> a) {
169        if (a.isEmpty())
170          return none();
171        else
172          return some(zipper(Stream.<A>nil(), a.head(), a.tail()._1()));
173      }
174    
175      /**
176       * Possibly create a zipper if the provided stream has at least one element, otherwise None.
177       * The provided stream's last element will be the focus of the zipper, following the rest of the stream in order,
178       * to the left.
179       *
180       * @param a The stream from which to create a zipper.
181       * @return a new zipper if the provided stream has at least one element, otherwise None.
182       */
183      public static <A> Option<Zipper<A>> fromStreamEnd(final Stream<A> a) {
184        if (a.isEmpty())
185          return none();
186        else {
187          final Stream<A> xs = a.reverse();
188          return some(zipper(xs.tail()._1(), xs.head(), Stream.<A>nil()));
189        }
190      }
191    
192      /**
193       * Returns the focus element of this zipper.
194       *
195       * @return the focus element of this zipper.
196       */
197      public A focus() {
198        return focus;
199      }
200    
201      /**
202       * Possibly moves the focus to the next element in the list.
203       *
204       * @return An optional zipper with the focus moved one element to the right, if there are elements to the right of
205       *         focus, otherwise None.
206       */
207      public Option<Zipper<A>> next() {
208        return right.isEmpty() ? Option.<Zipper<A>>none() : some(tryNext());
209      }
210    
211      /**
212       * Attempts to move the focus to the next element, or throws an error if there are no more elements.
213       *
214       * @return A zipper with the focus moved one element to the right, if there are elements to the right of
215       *         focus, otherwise throws an error.
216       */
217      public Zipper<A> tryNext() {
218        if (right.isEmpty())
219          throw new Error("Tried next at the end of a zipper.");
220        else
221          return zipper(left.cons(focus), right.head(), right.tail()._1());
222      }
223    
224      /**
225       * Possibly moves the focus to the previous element in the list.
226       *
227       * @return An optional zipper with the focus moved one element to the left, if there are elements to the left of
228       *         focus, otherwise None.
229       */
230      public Option<Zipper<A>> previous() {
231        return left.isEmpty() ? Option.<Zipper<A>>none() : some(tryPrevious());
232      }
233    
234      /**
235       * Attempts to move the focus to the previous element, or throws an error if there are no more elements.
236       *
237       * @return A zipper with the focus moved one element to the left, if there are elements to the left of
238       *         focus, otherwise throws an error.
239       */
240      public Zipper<A> tryPrevious() {
241        if (left.isEmpty())
242          throw new Error("Tried previous at the beginning of a zipper.");
243        else
244          return zipper(left.tail()._1(), left.head(), right.cons(focus));
245      }
246    
247      /**
248       * First-class version of the next() function.
249       *
250       * @return A function that moves the given zipper's focus to the next element.
251       */
252      public static <A> F<Zipper<A>, Option<Zipper<A>>> next_() {
253        return new F<Zipper<A>, Option<Zipper<A>>>() {
254          public Option<Zipper<A>> f(final Zipper<A> as) {
255            return as.next();
256          }
257        };
258      }
259    
260      /**
261       * First-class version of the previous() function.
262       *
263       * @return A function that moves the given zipper's focus to the previous element.
264       */
265      public static <A> F<Zipper<A>, Option<Zipper<A>>> previous_() {
266        return new F<Zipper<A>, Option<Zipper<A>>>() {
267          public Option<Zipper<A>> f(final Zipper<A> as) {
268            return as.previous();
269          }
270        };
271      }
272    
273      /**
274       * Inserts an element to the left of the focus, then moves the focus to the new element.
275       *
276       * @param a A new element to insert into this zipper.
277       * @return A new zipper with the given element in focus, and the current focus element on its right.
278       */
279      public Zipper<A> insertLeft(final A a) {
280        return zipper(left, a, right.cons(focus));
281      }
282    
283      /**
284       * Inserts an element to the right of the focus, then moves the focus to the new element.
285       *
286       * @param a A new element to insert into this zipper.
287       * @return A new zipper with the given element in focus, and the current focus element on its left.
288       */
289      public Zipper<A> insertRight(final A a) {
290        return zipper(left.cons(focus), a, right);
291      }
292    
293      /**
294       * Possibly deletes the element at the focus, then moves the element on the left into focus.
295       * If no element is on the left, focus on the element to the right.
296       * Returns None if the focus element is the only element in this zipper.
297       *
298       * @return A new zipper with this zipper's focus element removed, or None if deleting the focus element
299       *         would cause the zipper to be empty.
300       */
301      public Option<Zipper<A>> deleteLeft() {
302        return left.isEmpty() && right.isEmpty()
303               ? Option.<Zipper<A>>none()
304               : some(zipper(left.isEmpty() ? left : left.tail()._1(),
305                             left.isEmpty() ? right.head() : left.head(),
306                             left.isEmpty() ? right.tail()._1() : right));
307      }
308    
309      /**
310       * Possibly deletes the element at the focus, then moves the element on the right into focus.
311       * If no element is on the right, focus on the element to the left.
312       * Returns None if the focus element is the only element in this zipper.
313       *
314       * @return A new zipper with this zipper's focus element removed, or None if deleting the focus element
315       *         would cause the zipper to be empty.
316       */
317      public Option<Zipper<A>> deleteRight() {
318        return left.isEmpty() && right.isEmpty()
319               ? Option.<Zipper<A>>none()
320               : some(zipper(right.isEmpty() ? left.tail()._1() : left,
321                             right.isEmpty() ? left.head() : right.head(),
322                             right.isEmpty() ? right : right.tail()._1()));
323      }
324    
325      /**
326       * Deletes all elements in the zipper except the focus.
327       *
328       * @return A new zipper with the focus element as the only element.
329       */
330      public Zipper<A> deleteOthers() {
331        final Stream<A> nil = nil();
332        return zipper(nil, focus, nil);
333      }
334    
335      /**
336       * Returns the length of this zipper.
337       *
338       * @return the length of this zipper.
339       */
340      public int length() {
341        return foldRight(Function.<A, F<Integer, Integer>>constant(Integers.add.f(1)), 0);
342      }
343    
344      /**
345       * Returns whether the focus is on the first element.
346       *
347       * @return true if the focus is on the first element, otherwise false.
348       */
349      public boolean atStart() {
350        return left.isEmpty();
351      }
352    
353      /**
354       * Returns whether the focus is on the last element.
355       *
356       * @return true if the focus is on the last element, otherwise false.
357       */
358      public boolean atEnd() {
359        return right.isEmpty();
360      }
361    
362      /**
363       * Creates a zipper of variations of this zipper, in which each element is focused,
364       * with this zipper as the focus of the zipper of zippers (comonad pattern).
365       *
366       * @return a zipper of variations of the provided zipper, in which each element is focused,
367       *         with this zipper as the focus of the zipper of zippers.
368       */
369      public Zipper<Zipper<A>> positions() {
370        final Stream<Zipper<A>> left = Stream.unfold(
371            new F<Zipper<A>, Option<P2<Zipper<A>, Zipper<A>>>>() {
372              public Option<P2<Zipper<A>, Zipper<A>>> f(final Zipper<A> p) {
373                return p.previous().map(join(P.<Zipper<A>, Zipper<A>>p2()));
374              }
375            }, this);
376        final Stream<Zipper<A>> right = Stream.unfold(
377            new F<Zipper<A>, Option<P2<Zipper<A>, Zipper<A>>>>() {
378              public Option<P2<Zipper<A>, Zipper<A>>> f(final Zipper<A> p) {
379                return p.next().map(join(P.<Zipper<A>, Zipper<A>>p2()));
380              }
381            }, this);
382    
383        return zipper(left, this, right);
384      }
385    
386      /**
387       * Maps over variations of this zipper, such that the given function is applied to each variation (comonad pattern).
388       *
389       * @param f The comonadic function to apply for each variation of this zipper.
390       * @return A new zipper, with the given function applied for each variation of this zipper.
391       */
392      public <B> Zipper<B> cobind(final F<Zipper<A>, B> f) {
393        return positions().map(f);
394      }
395    
396      /**
397       * Zips the elements of this zipper with a boolean that indicates whether that element has focus.
398       * All of the booleans will be false, except the focused element.
399       *
400       * @return A new zipper of pairs, with each element of this zipper paired with a boolean that is true if that
401       *         element has focus, and false otherwise.
402       */
403      public Zipper<P2<A, Boolean>> zipWithFocus() {
404        return zipper(left.zip(repeat(false)), P.p(focus, true), right.zip(repeat(false)));
405      }
406    
407      /**
408       * Move the focus to the specified index.
409       *
410       * @param n The index to which to move the focus.
411       * @return A new zipper with the focus moved to the specified index, or none if there is no such index.
412       */
413      public Option<Zipper<A>> move(final int n) {
414        final int ll = left.length();
415        final int rl = right.length();
416        Option<Zipper<A>> p = some(this);
417        if (n < 0 || n >= length())
418          return none();
419        else if (ll >= n)
420          for (int i = ll - n; i > 0; i--)
421            p = p.bind(Zipper.<A>previous_());
422        else if (rl >= n)
423          for (int i = rl - n; i > 0; i--)
424            p = p.bind(Zipper.<A>next_());
425        return p;
426      }
427    
428      /**
429       * A first-class version of the move function.
430       *
431       * @return A function that moves the focus of the given zipper to the given index.
432       */
433      public static <A> F<Integer, F<Zipper<A>, Option<Zipper<A>>>> move() {
434        return curry(new F2<Integer, Zipper<A>, Option<Zipper<A>>>() {
435          public Option<Zipper<A>> f(final Integer i, final Zipper<A> a) {
436            return a.move(i);
437          }
438        });
439      }
440    
441      /**
442       * Moves the focus to the element matching the given predicate, if present.
443       *
444       * @param p A predicate to match.
445       * @return A new zipper with the nearest matching element focused if it is present in this zipper.
446       */
447      public Option<Zipper<A>> find(final F<A, Boolean> p) {
448        if (p.f(focus()))
449          return some(this);
450        else {
451          final Zipper<Zipper<A>> ps = positions();
452          return ps.lefts().interleave(ps.rights()).find(new F<Zipper<A>, Boolean>() {
453            public Boolean f(final Zipper<A> zipper) {
454              return p.f(zipper.focus());
455            }
456          });
457        }
458      }
459    
460      /**
461       * Returns the index of the focus.
462       *
463       * @return the index of the focus.
464       */
465      public int index() {
466        return left.length();
467      }
468    
469      /**
470       * Move the focus to the next element. If the last element is focused, loop to the first element.
471       *
472       * @return A new zipper with the next element focused, unless the last element is currently focused, in which case
473       *         the first element becomes focused.
474       */
475      public Zipper<A> cycleNext() {
476        if (left.isEmpty() && right.isEmpty())
477          return this;
478        else if (right.isEmpty()) {
479          final Stream<A> xs = left.reverse();
480          return zipper(Stream.<A>nil(), xs.head(), xs.tail()._1().snoc(P.p(focus)));
481        } else
482          return tryNext();
483      }
484    
485      /**
486       * Move the focus to the previous element. If the first element is focused, loop to the last element.
487       *
488       * @return A new zipper with the previous element focused, unless the first element is currently focused,
489       *         in which case the last element becomes focused.
490       */
491      public Zipper<A> cyclePrevious() {
492        if (left.isEmpty() && right.isEmpty())
493          return this;
494        else if (left.isEmpty()) {
495          final Stream<A> xs = right.reverse();
496          return zipper(xs.tail()._1().snoc(P.p(focus)), xs.head(), Stream.<A>nil());
497        } else
498          return tryPrevious();
499      }
500    
501      /**
502       * Possibly deletes the element at the focus, then move the element on the left into focus. If no element is on the
503       * left, focus on the last element. If the deletion will cause the list to be empty, return None.
504       *
505       * @return A new zipper with the focused element removed, and focus on the previous element to the left, or the last
506       *         element if there is no element to the left.
507       */
508      public Option<Zipper<A>> deleteLeftCycle() {
509        if (left.isEmpty() && right.isEmpty())
510          return none();
511        else if (left.isNotEmpty())
512          return some(zipper(left.tail()._1(), left.head(), right));
513        else {
514          final Stream<A> xs = right.reverse();
515          return some(zipper(xs.tail()._1(), xs.head(), Stream.<A>nil()));
516        }
517      }
518    
519      /**
520       * Possibly deletes the element at the focus, then move the element on the right into focus. If no element is on the
521       * right, focus on the first element. If the deletion will cause the list to be empty, return None.
522       *
523       * @return A new zipper with the focused element removed, and focus on the next element to the right, or the first
524       *         element if there is no element to the right.
525       */
526      public Option<Zipper<A>> deleteRightCycle() {
527        if (left.isEmpty() && right.isEmpty())
528          return none();
529        else if (right.isNotEmpty())
530          return some(zipper(left, right.head(), right.tail()._1()));
531        else {
532          final Stream<A> xs = left.reverse();
533          return some(zipper(Stream.<A>nil(), xs.head(), xs.tail()._1()));
534        }
535      }
536    
537      /**
538       * Replaces the element in focus with the given element.
539       *
540       * @param a An element to replace the focused element with.
541       * @return A new zipper with the given element in focus.
542       */
543      public Zipper<A> replace(final A a) {
544        return zipper(left, a, right);
545      }
546    
547      /**
548       * Returns the Stream representation of this zipper.
549       *
550       * @return A stream that contains all the elements of this zipper.
551       */
552      public Stream<A> toStream() {
553        return left.reverse().snoc(P.p(focus)).append(right);
554      }
555    
556      /**
557       * Returns a Stream of the elements to the left of focus.
558       *
559       * @return a Stream of the elements to the left of focus.
560       */
561      public Stream<A> lefts() {
562        return left;
563      }
564    
565      /**
566       * Returns a Stream of the elements to the right of focus.
567       *
568       * @return a Stream of the elements to the right of focus.
569       */
570      public Stream<A> rights() {
571        return right;
572      }
573    
574      /**
575       * Zips this Zipper with another, applying the given function lock-step over both zippers in both directions.
576       * The structure of the resulting Zipper is the structural intersection of the two Zippers.
577       *
578       * @param bs A Zipper to zip this one with.
579       * @param f  A function with which to zip together the two Zippers.
580       * @return The result of applying the given function over this Zipper and the given Zipper, location-wise.
581       */
582      public <B, C> Zipper<C> zipWith(final Zipper<B> bs, final F2<A, B, C> f) {
583        return $$(f).zipZipper().f(this, bs);
584      }
585    
586    
587      /**
588       * Zips this Zipper with another, applying the given function lock-step over both zippers in both directions.
589       * The structure of the resulting Zipper is the structural intersection of the two Zippers.
590       *
591       * @param bs A Zipper to zip this one with.
592       * @param f  A function with which to zip together the two Zippers.
593       * @return The result of applying the given function over this Zipper and the given Zipper, location-wise.
594       */
595      public <B, C> Zipper<C> zipWith(final Zipper<B> bs, final F<A, F<B, C>> f) {
596        return zipWith(bs, uncurryF2(f));
597      }
598    
599      /**
600       * Returns an iterator of all the positions of this Zipper, starting from the leftmost position.
601       *
602       * @return An iterator of all the positions of this Zipper, starting from the leftmost position.
603       */
604      public Iterator<Zipper<A>> iterator() { return positions().toStream().iterator(); }
605    }