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 }