001    package fj.data;
002    
003    import fj.F;
004    import fj.F2;
005    import static fj.Function.compose;
006    import static fj.Function.curry;
007    import static fj.P.p;
008    import fj.P1;
009    import fj.P2;
010    import static fj.data.Option.none;
011    import static fj.data.Option.some;
012    import static fj.data.Stream.join;
013    import static fj.function.Booleans.or;
014    import static fj.function.Characters.isSpaceChar;
015    import fj.pre.Equal;
016    import static fj.pre.Equal.charEqual;
017    import static fj.pre.Equal.streamEqual;
018    
019    import java.util.regex.Pattern;
020    
021    /**
022     * A lazy (non-evaluated) immutable character string.
023     */
024    public final class LazyString implements CharSequence {
025      private final Stream<Character> s;
026    
027      private LazyString(final Stream<Character> s) {
028        this.s = s;
029      }
030    
031      /**
032       * Constructs a lazy string from a String.
033       *
034       * @param s A string from which to construct a lazy string.
035       * @return A lazy string with the characters from the given string.
036       */
037      public static LazyString str(final String s) {
038        return new LazyString(Stream.unfold(new F<P2<String, Integer>, Option<P2<Character, P2<String, Integer>>>>() {
039          public Option<P2<Character, P2<String, Integer>>> f(final P2<String, Integer> o) {
040            final String s = o._1();
041            final int n = o._2();
042            final Option<P2<Character, P2<String, Integer>>> none = none();
043            return s.length() <= n ? none : some(p(s.charAt(n), p(s, n + 1)));
044          }
045        }, p(s, 0)));
046      }
047    
048      /**
049       * The empty string.
050       */
051      public static final LazyString empty = str("");
052    
053      /**
054       * Constructs a lazy string from a stream of characters.
055       *
056       * @param s A stream of characters.
057       * @return A lazy string with the characters from the given stream.
058       */
059      public static LazyString fromStream(final Stream<Character> s) {
060        return new LazyString(s);
061      }
062    
063      /**
064       * Gives a stream representation of this lazy string.
065       *
066       * @return A stream representation of this lazy string.
067       */
068      public Stream<Character> toStream() {
069        return s;
070      }
071    
072      /**
073       * The length of the lazy string. Note that this operation is O(n).
074       *
075       * @return The length of this lazy string.
076       */
077      public int length() {
078        return s.length();
079      }
080    
081      /**
082       * Returns the caracter at the specified index.
083       *
084       * @param index The index for the character to be returned.
085       * @return The character at the specified index.
086       */
087      public char charAt(final int index) {
088        return s.index(index);
089      }
090    
091      /**
092       * Gets the specified subsequence of this lazy string.
093       * This operation does not fail for indexes that are out of bounds. If the start index is past the end
094       * of this lazy string, then the resulting character sequence will be empty. If the end index is past the
095       * end of this lazy string, then the resulting character sequence will be truncated.
096       *
097       * @param start The character index of this lazy string at which to start the subsequence.
098       * @param end   The character index of this lazy string at which to end the subsequence.
099       * @return A character sequence containing the specified character subsequence.
100       */
101      public CharSequence subSequence(final int start, final int end) {
102        return fromStream(s.drop(start).take(end - start));
103      }
104    
105      /**
106       * Returns the String representation of this lazy string.
107       *
108       * @return The String representation of this lazy string.
109       */
110      public String toString() {
111        return new StringBuilder(this).toString();
112      }
113    
114      /**
115       * Appends the given lazy string to the end of this lazy string.
116       *
117       * @param cs A lazy string to append to this one.
118       * @return A new lazy string that is the concatenation of this string and the given string.
119       */
120      public LazyString append(final LazyString cs) {
121        return fromStream(s.append(cs.s));
122      }
123    
124      /**
125       * Appends the given String to the end of this lazy string.
126       *
127       * @param s A String to append to this lazy string.
128       * @return A new lazy string that is the concatenation of this lazy string and the given string.
129       */
130      public LazyString append(final String s) {
131        return append(str(s));
132      }
133    
134      /**
135       * Returns true if the given lazy string is a substring of this lazy string.
136       *
137       * @param cs A substring to find in this lazy string.
138       * @return True if the given string is a substring of this string, otherwise False.
139       */
140      public boolean contains(final LazyString cs) {
141        return or(s.tails().map(compose(startsWith().f(cs), fromStream)));
142      }
143    
144      /**
145       * Returns true if the given lazy string is a suffix of this lazy string.
146       *
147       * @param cs A string to find at the end of this lazy string.
148       * @return True if the given string is a suffix of this lazy string, otherwise False.
149       */
150      public boolean endsWith(final LazyString cs) {
151        return reverse().startsWith(cs.reverse());
152      }
153    
154      /**
155       * Returns true if the given lazy string is a prefix of this lazy string.
156       *
157       * @param cs A string to find at the start of this lazy string.
158       * @return True if the given string is a prefix of this lazy string, otherwise False.
159       */
160      public boolean startsWith(final LazyString cs) {
161        return cs.isEmpty() || !isEmpty() && charEqual.eq(head(), cs.head()) && tail().startsWith(cs.tail());
162      }
163    
164    
165      /**
166       * First-class prefix check.
167       *
168       * @return A function that yields true if the first argument is a prefix of the second.
169       */
170      public static F<LazyString, F<LazyString, Boolean>> startsWith() {
171        return curry(new F2<LazyString, LazyString, Boolean>() {
172          public Boolean f(final LazyString needle, final LazyString haystack) {
173            return haystack.startsWith(needle);
174          }
175        });
176      }
177    
178      /**
179       * Returns the first character of this string.
180       *
181       * @return The first character of this string, or error if the string is empty.
182       */
183      public char head() {
184        return s.head();
185      }
186    
187      /**
188       * Returns all but the first character of this string.
189       *
190       * @return All but the first character of this string, or error if the string is empty.
191       */
192      public LazyString tail() {
193        return fromStream(s.tail()._1());
194      }
195    
196      /**
197       * Checks if this string is empty.
198       *
199       * @return True if there are no characters in this string, otherwise False.
200       */
201      public boolean isEmpty() {
202        return s.isEmpty();
203      }
204    
205      /**
206       * Returns the reverse of this string.
207       *
208       * @return the reverse of this string.
209       */
210      public LazyString reverse() {
211        return fromStream(s.reverse());
212      }
213    
214      /**
215       * Returns the first index of the given character in this lazy string, if present.
216       *
217       * @param c A character to find in this lazy string.
218       * @return The first index of the given character in this lazy string, or None if the character is not present.
219       */
220      public Option<Integer> indexOf(final char c) {
221        return s.indexOf(Equal.charEqual.eq(c));
222      }
223    
224      /**
225       * Returns the first index of the given substring in this lazy string, if present.
226       *
227       * @param cs A substring to find in this lazy string.
228       * @return The first index of the given substring in this lazy string, or None if there is no such substring.
229       */
230      public Option<Integer> indexOf(final LazyString cs) {
231        return s.substreams().indexOf(eqS.eq(cs.s));
232      }
233    
234      /**
235       * Regular expression pattern matching.
236       *
237       * @param regex A regular expression to match this lazy string.
238       * @return True if this string mathches the given regular expression, otherwise False.
239       */
240      public boolean matches(final String regex) {
241        return Pattern.matches(regex, this);
242      }
243    
244      /**
245       * Splits this lazy string by characters matching the given predicate.
246       *
247       * @param p A predicate that matches characters to be considered delimiters.
248       * @return A stream of the substrings in this lazy string, when separated by the given predicate.
249       */
250      public Stream<LazyString> split(final F<Character, Boolean> p) {
251        final Stream<Character> findIt = s.dropWhile(p);
252        final P2<Stream<Character>, Stream<Character>> ws = findIt.split(p);
253        return findIt.isEmpty() ? Stream.<LazyString>nil()
254                                : Stream.cons(fromStream(ws._1()), new P1<Stream<LazyString>>() {
255                                  public Stream<LazyString> _1() {
256                                    return fromStream(ws._2()).split(p);
257                                  }
258                                });
259      }
260    
261      /**
262       * Splits this lazy string by the given delimiter character.
263       *
264       * @param c A delimiter character at which to split.
265       * @return A stream of substrings of this lazy string, when separated by the given delimiter.
266       */
267      public Stream<LazyString> split(final char c) {
268        return split(charEqual.eq(c));
269      }
270    
271      /**
272       * Splits this lazy string into words by spaces.
273       *
274       * @return A stream of the words in this lazy string, when split by spaces.
275       */
276      public Stream<LazyString> words() {
277        return split(isSpaceChar);
278      }
279    
280      /**
281       * Splits this lazy string into lines.
282       *
283       * @return A stream of the lines in this lazy string, when split by newlines.
284       */
285      public Stream<LazyString> lines() {
286        return split('\n');
287      }
288    
289      /**
290       * Joins the given stream of lazy strings into one, separated by newlines.
291       *
292       * @param str A stream of lazy strings to join by newlines.
293       * @return A new lazy string, consisting of the given strings separated by newlines.
294       */
295      public static LazyString unlines(final Stream<LazyString> str) {
296        return fromStream(join(str.intersperse(str("\n")).map(toStream)));
297      }
298    
299      /**
300       * Joins the given stream of lazy strings into one, separated by spaces.
301       *
302       * @param str A stream of lazy strings to join by spaces.
303       * @return A new lazy string, consisting of the given strings with spaces in between.
304       */
305      public static LazyString unwords(final Stream<LazyString> str) {
306        return fromStream(join(str.intersperse(str(" ")).map(toStream)));
307      }
308    
309      /**
310       * First-class conversion from lazy strings to streams.
311       */
312      public static final F<LazyString, Stream<Character>> toStream =
313          new F<LazyString, Stream<Character>>() {
314            public Stream<Character> f(final LazyString string) {
315              return string.toStream();
316            }
317          };
318    
319      /**
320       * First-class conversion from character streams to lazy strings.
321       */
322      public static final F<Stream<Character>, LazyString> fromStream =
323          new F<Stream<Character>, LazyString>() {
324            public LazyString f(final Stream<Character> s) {
325              return fromStream(s);
326            }
327          };
328    
329      private static final Equal<Stream<Character>> eqS = streamEqual(charEqual);
330    
331    }