package scalaz
import annotation.tailrec
sealed trait Zipper[+A] {
val focus: A
val lefts: Stream[A]
val rights: Stream[A]
import Scalaz._
def toStream: Stream[A] =
lefts.reverse ++ focus #:: rights
def next: Option[Zipper[A]] = rights match {
case Stream.Empty => None
case r #:: rs => Some(zipper(Stream.cons(focus, lefts), r, rs))
}
def tryNext: Zipper[A] = next err "cannot move to next element"
def previous: Option[Zipper[A]] = lefts match {
case Stream.Empty => None
case l #:: ls => Some(zipper(ls, l, Stream.cons(focus, rights)))
}
def tryPrevious: Zipper[A] = previous err "cannot move to previous element"
def insert[AA >: A]: (AA => Zipper[AA]) = insertRight(_: AA)
def insertLeft[AA >: A](y: AA): Zipper[AA] = zipper(lefts, y, focus #:: rights)
def insertRight[AA >: A](y: AA): Zipper[AA] = zipper(focus #:: lefts, y, rights)
def delete: Option[Zipper[A]] = deleteRight
def deleteLeft: Option[Zipper[A]] = rights match {
case Stream.Empty => None
case r #:: rs => Some(lefts match {
case Stream.Empty => zipper(Stream.Empty, r, rs)
case l #:: ls => zipper(ls, l, rights)
})
}
def deleteRight: Option[Zipper[A]] = rights match {
case Stream.Empty => None
case r #:: rs => Some(lefts match {
case Stream.Empty => zipper(Stream.Empty, r, rs)
case l #:: ls => zipper(ls, l, rights)
})
}
def deleteOthers: Zipper[A] = zipper(Stream.Empty, focus, Stream.Empty)
def length: Int = this.foldr(0)(((a: Any, b: Int) => b + 1)(_, _))
def atStart: Boolean = lefts.isEmpty
def atEnd: Boolean = rights.isEmpty
def withFocus: Zipper[(A, Boolean)] = zipper(lefts.zip(Stream.continually(false)), (focus, true), rights.zip(Stream.continually(false)))
def move(n: Int): Option[Zipper[A]] = {
@tailrec
def move0(z: Option[Zipper[A]], n: Int): Option[Zipper[A]] =
if (n > 0 && rights.isEmpty || n < 0 && lefts.isEmpty) None
else {
if (n == 0) z
else if (n > 0) move0(z >>= ((_:Zipper[A]).next), n - 1)
else move0(z >>= ((_:Zipper[A]).previous), n + 1)
}
move0(Some(this), n)
}
def findZ(p: A => Boolean): Option[Zipper[A]] =
if (p(focus)) Some(this)
else {
val c = this.positions
c.lefts.merge(c.rights).find((x => p(x.focus)))
}
def findBy[AA >: A](f: Zipper[AA] => Option[Zipper[AA]])(p: AA => Boolean): Option[Zipper[AA]] = {
f(this) ∗ (x => if (p(x.focus)) Some(x) else x.findBy(f)(p))
}
def findNext[AA >: A](p: AA => Boolean): Option[Zipper[AA]]= findBy((z: Zipper[A]) => z.next)(p)
def findPrevious[AA >: A](p: AA => Boolean): Option[Zipper[AA]]= findBy((z: Zipper[A]) => z.previous)(p)
def positions: Zipper[Zipper[A]] = {
val left = this.unfold[Stream, Zipper[A]]((p: Zipper[A]) => p.previous.map(x => (x, x)))
val right = this.unfold[Stream, Zipper[A]]((p: Zipper[A]) => p.next.map(x => (x, x)))
zipper(left, this, right)
}
def index: Int = lefts.length
def nextC: Zipper[A] = (lefts, rights) match {
case (Stream.Empty, Stream.Empty) => this
case (_, Stream.Empty) => {
val xs = lefts.reverse
zipper(rights, xs.head, xs.tail.append(Stream(focus)))
}
case (_, _) => tryNext
}
def previousC: Zipper[A] = (lefts, rights) match {
case (Stream.Empty, Stream.Empty) => this
case (Stream.Empty, _) => {
val xs = rights.reverse
zipper(xs.tail.append(Stream(focus)), xs.head, lefts)
}
case (_, _) => tryPrevious
}
def deleteLeftC: Option[Zipper[A]] = rights match {
case Stream.Empty => None
case _ #:: _ => Some(lefts match {
case l #:: ls => zipper(ls, l, rights)
case Stream.Empty => {
val r = rights.reverse
zipper(r.tail, r.head, Stream.Empty)
}
})
}
def deleteRightC: Option[Zipper[A]] = lefts match {
case Stream.Empty => None
case _ #:: _ => Some(rights match {
case r #:: rs => zipper(lefts, r, rs)
case Stream.Empty => {
val l = lefts.reverse
zipper(Stream.Empty, l.head, l.tail)
}
})
}
def deleteC: Option[Zipper[A]] = deleteRightC
}
trait Zippers {
def zipper[A](ls: Stream[A], a: A, rs: Stream[A]): Zipper[A] = new Zipper[A] {
val focus = a
val lefts = ls
val rights = rs
override def toString = "<zipper>"
}
}