String zipper?
| sealed trait StringZipper { | |
| // The length of the zipper. | |
| // O(1) if there have not been any length-altering updates, O(n) otherwise. | |
| def length: Option[Int] = | |
| this match { | |
| case EmptyZ => Some(0) | |
| case OffBoundsZ => None | |
| case StringZ(_, x, _, y) => Some(y - x) | |
| case ListZ(l, _, r, n) => n orElse Some(l.length + 1 + r.length) | |
| } | |
| // Normalise the zipper's length so that access is to length O(1) until the next length-altering update. | |
| def mLength: StringZipper = | |
| this match { | |
| case ListZ(l, x, r, None) => ListZ(l, x, r, Some(l.length + 1 + r.length)) | |
| case _ => this | |
| } | |
| // The current focus of the zipper, if there is one. | |
| def focus: Option[Char] = | |
| this match { | |
| case EmptyZ => None | |
| case OffBoundsZ => None | |
| case StringZ(s, _, i, _) => Some(s(i)) | |
| case ListZ(_, x, _, _) => Some(x) | |
| } | |
| // Return whether or not this zipper has focus. | |
| def hasFocus: Boolean = | |
| this match { | |
| case EmptyZ => false | |
| case OffBoundsZ => false | |
| case _ => true | |
| } | |
| // Run the given function on the focus of the zipper (or no-op if there is no focus). | |
| def ~(k: Char => Char): StringZipper = | |
| this match { | |
| case EmptyZ => EmptyZ | |
| case OffBoundsZ => OffBoundsZ | |
| case StringZ(s, x, i, y) => { | |
| val c = s(i) | |
| val d = k(c) | |
| if(c == d) | |
| this | |
| else { | |
| val (lefts, w, rights) = StringZListZ(s, x, i, y) | |
| ListZ(lefts, k(w), rights, Some(y - x)) | |
| } | |
| } | |
| case ListZ(l, x, r, n) => ListZ(l, k(x), r, n) | |
| } | |
| // Set the focus to the given value (or no-op if there is no focus). | |
| def :=(c: Char): StringZipper = | |
| this ~ (_ => c) | |
| // Return this zipper if it has a focus, otherwise, the given zipper. | |
| def |(other: => StringZipper) = | |
| if(hasFocus) this else other | |
| // Move the focus to the given absolute index in the zipper. | |
| def !(q: Int): StringZipper = | |
| if(q < 0) | |
| OffBoundsZ | |
| else | |
| this match { | |
| case EmptyZ => OffBoundsZ | |
| case OffBoundsZ => OffBoundsZ | |
| case StringZ(s, x, i, y) => | |
| if(q >= x && q < y) | |
| StringZ(s, x, q, y) | |
| else | |
| OffBoundsZ | |
| case ListZ(l, x, r, n) => | |
| // if carrying length, check bounds quickly | |
| if(n forall (q < _)) { | |
| @annotation.tailrec | |
| def tryLeft(n: Int, z: StringZipper, g: Int): (Int, StringZipper) = | |
| if(n == 0) | |
| (g, z) | |
| else | |
| z.left match { | |
| case EmptyZ => (0, EmptyZ) | |
| case OffBoundsZ => (g, OffBoundsZ) | |
| case zz => tryLeft(n - 1, zz, g + 1) | |
| } | |
| val (h, u) = tryLeft(q, this, 0) | |
| u match { | |
| case EmptyZ => EmptyZ | |
| case OffBoundsZ => this + (q - h) | |
| case _ => this - u.nLeft | |
| } | |
| } else | |
| OffBoundsZ | |
| } | |
| // Returns whether this zipper is of an empty string. | |
| def isEmpty: Boolean = | |
| this == EmptyZ | |
| // Returns whether the focus of this zipper is within bounds. | |
| def isInBounds: Boolean = | |
| this != OffBoundsZ | |
| // Move the focus of this zipper to the right the given number of times. | |
| @annotation.tailrec | |
| final def +(q: Int): StringZipper = | |
| this match { | |
| case EmptyZ => OffBoundsZ | |
| case OffBoundsZ => OffBoundsZ | |
| case StringZ(s, x, i, y) => { | |
| val b = i + q | |
| if(b >= x && b < y) | |
| StringZ(s, x, b, y) | |
| else | |
| OffBoundsZ | |
| } | |
| case ListZ(l, x, r, n) => | |
| if(q == Int.MinValue) | |
| l match { | |
| case Nil => OffBoundsZ | |
| case h::t => ListZ(t, h, x::t, n) - Int.MaxValue | |
| } | |
| else if(q < 0) | |
| this - (-q) | |
| else if(q == 0) | |
| ListZ(l, x, r, n) | |
| else | |
| r match { | |
| case Nil => OffBoundsZ | |
| case h::t => (ListZ(x::l, h, t, n): StringZipper) + (q - 1) | |
| } | |
| } | |
| // Move the focus of this zipper to the left the given number of times. | |
| @annotation.tailrec | |
| final def -(q: Int): StringZipper = | |
| this match { | |
| case EmptyZ => OffBoundsZ | |
| case OffBoundsZ => OffBoundsZ | |
| case StringZ(s, x, i, y) => { | |
| val b = i - q | |
| if(b >= x && b < y) | |
| StringZ(s, x, b, y) | |
| else | |
| OffBoundsZ | |
| } | |
| case ListZ(l, x, r, n) => | |
| if(q == Int.MinValue) | |
| r match { | |
| case Nil => OffBoundsZ | |
| case h::t => ListZ(x::l, h, t, n) + Int.MaxValue | |
| } | |
| else if(q < 0) | |
| this + (-q) | |
| else if(q == 0) | |
| ListZ(l, x, r, n) | |
| else | |
| l match { | |
| case Nil => OffBoundsZ | |
| case h::t => (ListZ(t, h, x::r, n): StringZipper) - (q - 1) | |
| } | |
| } | |
| // Move the focus of this zipper one position to the left. | |
| def left: StringZipper = | |
| this - 1 | |
| // Move the focus of this zipper one position to the right. | |
| def right: StringZipper = | |
| this + 1 | |
| // Returns whether this zipper has a value to the left of focus. | |
| def hasLeft: Boolean = | |
| this match { | |
| case EmptyZ => false | |
| case OffBoundsZ => false | |
| case StringZ(_, x, i, _) => i >= x | |
| case ListZ(q, _, _, _) => !q.isEmpty | |
| } | |
| // Returns whether this zipper has a value to the right of focus. | |
| def hasRight: Boolean = | |
| this match { | |
| case EmptyZ => false | |
| case OffBoundsZ => false | |
| case StringZ(_, _, i, y) => i < y | |
| case ListZ(_, _, q, _) => !q.isEmpty | |
| } | |
| // Returns the number of values to the left of focus (or 0 if there is no focus). | |
| def nLeft: Int = | |
| this match { | |
| case EmptyZ => 0 | |
| case OffBoundsZ => 0 | |
| case StringZ(_, x, i, _) => i - x | |
| case ListZ(q, _, _, _) => q.length | |
| } | |
| // Returns the number of values to the right of focus (or 0 if there is no focus). | |
| def nRight: Int = | |
| this match { | |
| case EmptyZ => 0 | |
| case OffBoundsZ => 0 | |
| case StringZ(_, _, i, y) => y - i - 1 | |
| case ListZ(_, _, q, _) => q.length | |
| } | |
| // Drop all values to the left of focus (no-op if there is no focus). | |
| def dropLefts: StringZipper = | |
| this match { | |
| case EmptyZ => EmptyZ | |
| case OffBoundsZ => OffBoundsZ | |
| case StringZ(s, x, i, y) => StringZ(s, i, i, y) | |
| case ListZ(_, x, r, _) => ListZ(Nil, x, r, None) | |
| } | |
| // Drop all values to the right of focus (no-op if there is no focus). | |
| def dropRights: StringZipper = | |
| this match { | |
| case EmptyZ => EmptyZ | |
| case OffBoundsZ => OffBoundsZ | |
| case StringZ(s, x, i, y) => StringZ(s, x, i, i + 1) | |
| case ListZ(l, x, _, _) => ListZ(l, x, Nil, None) | |
| } | |
| // Move the focus of this zipper to the first position to the left that matches the given predicate (no-op if there is no focus). | |
| @annotation.tailrec | |
| final def <<:(p: Char => Boolean): StringZipper = | |
| this match { | |
| case EmptyZ => EmptyZ | |
| case OffBoundsZ => OffBoundsZ | |
| case _ => { | |
| val l = left | |
| l.focus match { | |
| case None => this | |
| case Some(q) => if(p(q)) l else p <<: l | |
| } | |
| } | |
| } | |
| // Move the focus of this zipper to the first position to the right that matches the given predicate (no-op if there is no focus). | |
| @annotation.tailrec | |
| final def :>>(p: Char => Boolean): StringZipper = | |
| this match { | |
| case EmptyZ => EmptyZ | |
| case OffBoundsZ => OffBoundsZ | |
| case _ => { | |
| val r = right | |
| r.focus match { | |
| case None => this | |
| case Some(q) => if(p(q)) r else r :>> p | |
| } | |
| } | |
| } | |
| // Drop the element to the left of focus, out of bounds if there is no left (no-op if there is no focus). | |
| def dropLeft: StringZipper = | |
| this match { | |
| case EmptyZ => EmptyZ | |
| case OffBoundsZ => OffBoundsZ | |
| case StringZ(s, x, i, y) => | |
| if(y - x == 1) | |
| EmptyZ | |
| else { | |
| val j = i - 1 | |
| if(j >= x && j < y) | |
| StringZListZLefts(s, x, i) match { | |
| case Nil => OffBoundsZ | |
| case h::t => ListZ(t, h, StringZListZRights(s, i, y), Some(y - x - 1)) | |
| } | |
| else | |
| OffBoundsZ | |
| } | |
| case ListZ(l, _, r, n) => | |
| l match { | |
| case Nil => if(r.isEmpty) EmptyZ else OffBoundsZ | |
| case h::t => ListZ(t, h, r, n map (_-1)) | |
| } | |
| } | |
| // Drop the element to the right of focus, out of bounds if there is no right (no-op if there is no focus). | |
| def dropRight: StringZipper = | |
| this match { | |
| case EmptyZ => EmptyZ | |
| case OffBoundsZ => OffBoundsZ | |
| case StringZ(s, x, i, y) => | |
| if(y - x == 1) | |
| EmptyZ | |
| else { | |
| val j = i - 1 | |
| if(j >= x && j < y) | |
| StringZListZRights(s, i, y) match { | |
| case Nil => OffBoundsZ | |
| case h::t => ListZ(StringZListZLefts(s, x, i), h, t, Some(y - x - 1)) | |
| } | |
| else | |
| OffBoundsZ | |
| } | |
| case ListZ(l, _, r, n) => | |
| r match { | |
| case Nil => if(l.isEmpty) EmptyZ else OffBoundsZ | |
| case h::t => ListZ(l, h, t, n map (_-1)) | |
| } | |
| } | |
| // Insert the given element to the left of focus (no-op if there is no focus). | |
| def <+:(q: Char): StringZipper = | |
| this match { | |
| case EmptyZ => EmptyZ | |
| case OffBoundsZ => OffBoundsZ | |
| case StringZ(s, x, i, y) => { | |
| val (lefts, w, rights) = StringZListZ(s, x, i, y) | |
| ListZ(q::lefts, w, rights, Some(y - x + 1)) | |
| } | |
| case ListZ(l, x, r, n) => ListZ(q::l, x, r, n map (_+1)) | |
| } | |
| // Insert the given elements to the left of focus (no-op if there is no focus). | |
| def <++:(s: String): StringZipper = | |
| s.foldRight(this)(_ <+: _) | |
| // Insert the given element to the right of focus (no-op if there is no focus). | |
| def :+>(q: Char): StringZipper = | |
| this match { | |
| case EmptyZ => EmptyZ | |
| case OffBoundsZ => OffBoundsZ | |
| case StringZ(s, x, i, y) => { | |
| val (lefts, w, rights) = StringZListZ(s, x, i, y) | |
| ListZ(lefts, w, q::rights, Some(y - x + 1)) | |
| } | |
| case ListZ(l, x, r, n) => ListZ(l, x, q::r, n map (_+1)) | |
| } | |
| // Insert the given elements to the right of focus (no-op if there is no focus). | |
| def :++>(s: String): StringZipper = | |
| s.foldRight(this)((a, b) => b :+> a) | |
| // Returns a possible string representation of this zipper (no value if the zipper is out of bounds). | |
| def unary_- : Option[String] = | |
| this match { | |
| case EmptyZ => Some("") | |
| case OffBoundsZ => None | |
| case StringZ(s, x, i, y) => Some(s.substring(x, y)) | |
| case ListZ(l, x, r, n) => Some({ | |
| val b = n match { | |
| case Some(o) => new StringBuilder(o) | |
| case None => new StringBuilder | |
| } | |
| l foreach (b insert (0, _)) | |
| b += x | |
| r foreach (b += _) | |
| b.toString | |
| }) | |
| } | |
| // A string representation of this zipper. Empty string if the zipper is out of bounds. | |
| override def toString: String = | |
| -this getOrElse "" | |
| // BEGIN unsafe, unexported | |
| private def StringZListZLefts(s: String, x: Int, i: Int): List[Char] = { | |
| var lefts: List[Char] = Nil | |
| x to i-1 foreach (c => lefts = s(c) :: lefts) | |
| lefts | |
| } | |
| private def StringZListZRights(s: String, i: Int, y: Int): List[Char] = { | |
| var rights: List[Char] = Nil | |
| y-1 to i+1 by -1 foreach (c => rights = s(c) :: rights) | |
| rights | |
| } | |
| private def StringZListZ(s: String, x: Int, i: Int, y: Int): (List[Char], Char, List[Char]) = | |
| (StringZListZLefts(s, x, i), s(i), StringZListZRights(s, i, y)) | |
| // END unsafe, unexported | |
| } | |
| private case object EmptyZ extends StringZipper | |
| private case object OffBoundsZ extends StringZipper | |
| private case class StringZ(s: String, start: Int, index: Int, end: Int) extends StringZipper | |
| private case class ListZ(lefts: List[Char], x: Char, rights: List[Char], l: Option[Int]) extends StringZipper | |
| object StringZipper { | |
| def apply(s: String): StringZipper = | |
| if(s.length == 0) | |
| EmptyZ | |
| else | |
| StringZ(s, 0, 0, s.length) | |
| case class ZipperString(s: String) { | |
| def unary_+ : StringZipper = | |
| StringZipper(s) | |
| } | |
| implicit def StringZipperString(s: String): ZipperString = | |
| ZipperString(s) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment