001    package fj.data;
002    
003    import fj.Effect;
004    import fj.F;
005    import fj.FW;
006    import static fj.data.Option.some;
007    import static fj.data.Option.somes;
008    
009    import java.util.Collection;
010    import java.util.Iterator;
011    
012    /**
013     * Provides an in-memory, immutable, singly linked list with total <code>head</code> and <code>tail</code>.
014     *
015     * @version %build.number%<br>
016     *          <ul>
017     *          <li>$LastChangedRevision: 180 $</li>
018     *          <li>$LastChangedDate: 2009-06-28 09:59:09 +1000 (Sun, 28 Jun 2009) $</li>
019     *          </ul>
020     */
021    public final class NonEmptyList<A> implements Iterable<A> {
022      /**
023       * Returns an iterator for this non-empty list. This method exists to permit the use in a <code>for</code>-each loop.
024       *
025       * @return A iterator for this non-empty list.
026       */
027    
028      public Iterator<A> iterator() {
029        return toCollection().iterator();
030      }
031    
032      /**
033       * The first element of this linked list.
034       */
035      @SuppressWarnings({"PublicField", "ClassEscapesDefinedScope"})
036      public final A head;
037    
038      /**
039       * This list without the first element.
040       */
041      @SuppressWarnings({"PublicField"})
042      public final List<A> tail;
043    
044      private NonEmptyList(final A head, final List<A> tail) {
045        this.head = head;
046        this.tail = tail;
047      }
048    
049      /**
050       * Prepend the given value to this list.
051       *
052       * @param a The value to prepend.
053       * @return A non-empty list with an extra element.
054       */
055      public NonEmptyList<A> cons(final A a) {
056        return nel(a, tail.cons(head));
057      }
058    
059      /**
060       * Appends the given list to this list.
061       *
062       * @param as The list to append.
063       * @return A new list with the given list appended.
064       */
065      public NonEmptyList<A> append(final NonEmptyList<A> as) {
066        final List.Buffer<A> b = new List.Buffer<A>();
067        b.append(tail);
068        b.snoc(as.head);
069        b.append(as.tail);
070        final List<A> bb = b.toList();
071        return nel(head, bb);
072      }
073    
074      /**
075       * Maps the given function across this list.
076       *
077       * @param f The function to map across this list.
078       * @return A new list after the given function has been applied to each element.
079       */
080      public <B> NonEmptyList<B> map(final F<A, B> f) {
081        return nel(f.f(head), tail.map(f));
082      }
083    
084      /**
085       * Binds the given function across each element of this list with a final join.
086       *
087       * @param f The function to apply to each element of this list.
088       * @return A new list after performing the map, then final join.
089       */
090      public <B> NonEmptyList<B> bind(final F<A, NonEmptyList<B>> f) {
091        final List.Buffer<B> b = new List.Buffer<B>();
092        final NonEmptyList<B> p = f.f(head);
093        b.snoc(p.head);
094        b.append(p.tail);
095        tail.foreach(new Effect<A>() {
096          public void e(final A a) {
097            final NonEmptyList<B> p = f.f(a);
098            b.snoc(p.head);
099            b.append(p.tail);
100          }
101        });
102        final List<B> bb = b.toList();
103        return nel(bb.head(), bb.tail());
104      }
105    
106      /**
107       * Returns a NonEmptyList of the sublists of this list.
108       *
109       * @return a NonEmptyList of the sublists of this list.
110       */
111      public NonEmptyList<NonEmptyList<A>> sublists() {
112        return fromList(
113            somes(toList().toStream().substreams()
114                .map(FW.<List<A>, Option<NonEmptyList<A>>>$(new F<List<A>, Option<NonEmptyList<A>>>() {
115                  public Option<NonEmptyList<A>> f(final List<A> list) {
116                    return fromList(list);
117                  }
118                }).o(Conversions.<A>Stream_List())).toList())).some();
119      }
120    
121      /**
122       * Returns a NonEmptyList of the tails of this list. A list is considered a tail of itself for the purpose of this
123       * function (Comonad pattern).
124       *
125       * @return A NonEmptyList of the tails of this list.
126       */
127      public NonEmptyList<NonEmptyList<A>> tails() {
128        return fromList(somes(toList().tails().map(new F<List<A>, Option<NonEmptyList<A>>>() {
129          public Option<NonEmptyList<A>> f(final List<A> list) {
130            return fromList(list);
131          }
132        }))).some();
133      }
134    
135      /**
136       * Maps the given function across the tails of this list (comonad pattern).
137       *
138       * @param f The function to map across the tails of this list.
139       * @return The results of applying the given function to the tails of this list, as a NonEmptyList.
140       */
141      public <B> NonEmptyList<B> mapTails(final F<NonEmptyList<A>, B> f) {
142        return tails().map(f);
143      }
144    
145      /**
146       * Returns a <code>List</code> projection of this list.
147       *
148       * @return A <code>List</code> projection of this list.
149       */
150      public List<A> toList() {
151        return tail.cons(head);
152      }
153    
154      /**
155       * Projects an immutable collection of this non-empty list.
156       *
157       * @return An immutable collection of this non-empty list.
158       */
159      public Collection<A> toCollection() {
160        return toList().toCollection();
161      }
162    
163      /**
164       * Returns a function that takes a non-empty list to a list.
165       *
166       * @return A function that takes a non-empty list to a list.
167       */
168      public static <A> F<NonEmptyList<A>, List<A>> toList_() {
169        return new F<NonEmptyList<A>, List<A>>() {
170          public List<A> f(final NonEmptyList<A> as) {
171            return as.toList();
172          }
173        };
174      }
175    
176      /**
177       * Return a non-empty list with the given head and tail.
178       *
179       * @param head The first element of the new list.
180       * @param tail The remaining elements of the new list.
181       * @return A non-empty list with the given head and tail.
182       */
183      public static <A> NonEmptyList<A> nel(final A head, final List<A> tail) {
184        return new NonEmptyList<A>(head, tail);
185      }
186    
187      /**
188       * Return a non-empty list with the given value.
189       *
190       * @param head The value in the non-empty list.
191       * @return A non-empty list with the given value.
192       */
193      public static <A> NonEmptyList<A> nel(final A head) {
194        return nel(head, List.<A>nil());
195      }
196    
197      /**
198       * Returns a function that puts an element into a non-empty list.
199       *
200       * @return A function that puts an element into a non-empty list.
201       */
202      public static <A> F<A, NonEmptyList<A>> nel() {
203        return new F<A, NonEmptyList<A>>() {
204          public NonEmptyList<A> f(final A a) {
205            return nel(a);
206          }
207        };
208      }
209    
210      /**
211       * Returns a potential non-empty list from the given list. A non-value is returned if the given list is empty.
212       *
213       * @param as The list to construct a potential non-empty list with.
214       * @return A potential non-empty list from the given list.
215       */
216      public static <A> Option<NonEmptyList<A>> fromList(final List<A> as) {
217        return as.isEmpty() ?
218               Option.<NonEmptyList<A>>none() :
219               some(nel(as.head(), as.tail()));
220      }
221    }