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 }