From ea45f483bd7b487cfb5cd956c964c34809caa84d Mon Sep 17 00:00:00 2001 From: Paul Phillips Date: Fri, 17 Jul 2009 16:55:28 +0000 Subject: Now that there's a KMP implementation in Seq, r... Now that there's a KMP implementation in Seq, removed the Char-specific one from StringBuilder. Added lastIndexOfSeq method to SequenceTemplate - for StringBuilder primarily, but available to be enjoyed by all the world's sequences. --- src/compiler/scala/tools/nsc/InterpreterLoop.scala | 2 +- .../collection/generic/SequenceTemplate.scala | 16 +++-- .../scala/collection/mutable/StringBuilder.scala | 82 ++-------------------- 3 files changed, 17 insertions(+), 83 deletions(-) diff --git a/src/compiler/scala/tools/nsc/InterpreterLoop.scala b/src/compiler/scala/tools/nsc/InterpreterLoop.scala index 2beeec28e4..9d4e734a40 100644 --- a/src/compiler/scala/tools/nsc/InterpreterLoop.scala +++ b/src/compiler/scala/tools/nsc/InterpreterLoop.scala @@ -215,7 +215,7 @@ class InterpreterLoop(in0: Option[BufferedReader], out: PrintWriter) { val futLine = scala.concurrent.ops.future(readOneLine) bindSettings() if (!processLine(futLine())) - return out.println("Leaving already? That hurts, it really does.") + return // loops until false, then returns while (processLine(readOneLine)) { } diff --git a/src/library/scala/collection/generic/SequenceTemplate.scala b/src/library/scala/collection/generic/SequenceTemplate.scala index ecc65ebf15..6696ca9e8c 100644 --- a/src/library/scala/collection/generic/SequenceTemplate.scala +++ b/src/library/scala/collection/generic/SequenceTemplate.scala @@ -314,8 +314,7 @@ trait SequenceTemplate[+A, +This <: IterableTemplate[A, This] with Sequence[A]] } /** @return -1 if that not contained in this, otherwise the - * index where that is contained - * @see String.indexOf + * first index where that is contained. */ def indexOfSeq[B >: A](that: Sequence[B]): Int = indexOfSeq(that, 0) @@ -335,6 +334,16 @@ trait SequenceTemplate[+A, +This <: IterableTemplate[A, This] with Sequence[A]] -1 } + /** @return -1 if that not contained in this, otherwise the + * last index where that is contained. + * @note may not terminate for infinite-sized collections. + */ + def lastIndexOfSeq[B >: A](that: Sequence[B]): Int = lastIndexOfSeq(that, that.length) + + // since there's no way to find the last index in an infinite sequence, + // we just document it may not terminate and assume it will. + def lastIndexOfSeq[B >: A](that: Sequence[B], fromIndex: Int): Int = + lastIndexOf_KMP(thisCollection, 0, length, that, 0, that.length, fromIndex) /** Tests if the given value elem is a member of this * sequence. @@ -492,7 +501,7 @@ trait SequenceTemplate[+A, +This <: IterableTemplate[A, This] with Sequence[A]] private def KMP[B](S: Seq[B], W: Seq[B]): Option[Int] = { // trivial cases if (W.isEmpty) return Some(0) - else if (W drop 1 isEmpty) return S.indexOf(W(0)) match { + else if (W drop 1 isEmpty) return (S indexOf W(0)) match { case -1 => None case x => Some(x) } @@ -559,7 +568,6 @@ trait SequenceTemplate[+A, +This <: IterableTemplate[A, This] with Sequence[A]] } } - override def equals(that: Any): Boolean = that match { case that1: Sequence[a] => val these = this.iterator diff --git a/src/library/scala/collection/mutable/StringBuilder.scala b/src/library/scala/collection/mutable/StringBuilder.scala index 6afd4edf8d..2238f4b0ea 100644 --- a/src/library/scala/collection/mutable/StringBuilder.scala +++ b/src/library/scala/collection/mutable/StringBuilder.scala @@ -716,7 +716,7 @@ final class StringBuilder(initCapacity: Int, private val initValue: String) * substring, -1 is returned. * @throws NullPointerException if str is null. */ - def indexOf(str: String): Int = indexOf(str, 0) + def indexOf(str: String): Int = indexOfSeq(str.toArray) /**

* Returns the index within this string of the first occurrence of the @@ -735,8 +735,7 @@ final class StringBuilder(initCapacity: Int, private val initValue: String) * @return the index within this string of the first occurrence * of the specified substring, starting at the specified index. */ - def indexOf(str: String, fromIndex: Int): Int = - StringBuilder.indexOf(array, 0, count, str.toCharArray, 0, str.length(), fromIndex) + def indexOf(str: String, fromIndex: Int): Int = indexOfSeq(str.toArray, fromIndex) /**

* Returns the index within this string of the rightmost occurrence @@ -758,7 +757,7 @@ final class StringBuilder(initCapacity: Int, private val initValue: String) * a substring, -1 is returned. * @throws NullPointerException if str is null. */ - def lastIndexOf(str: String): Int = lastIndexOf(str, count) + def lastIndexOf(str: String): Int = lastIndexOfSeq(str.toArray, count) /**

* Returns the index within this string of the last occurrence of the @@ -777,8 +776,7 @@ final class StringBuilder(initCapacity: Int, private val initValue: String) * @return the index within this sequence of the last occurrence * of the specified substring. */ - def lastIndexOf(str: String, fromIndex: Int): Int = - StringBuilder.lastIndexOf(array, 0, count, str.toCharArray, 0, str.length(), fromIndex) + def lastIndexOf(str: String, fromIndex: Int): Int = lastIndexOfSeq(str.toArray, fromIndex) /**

* Causes this character sequence to be replaced by the reverse of the @@ -872,76 +870,4 @@ object StringBuilder { arraycopy(src, 0, dest, 0, Math.min(src.length, newLength)) dest } - - // KMP implementation by paulp, based on the undoubtedly reliable wikipedia entry - private def KMP(S: Array[Char], W: Array[Char]): Option[Int] = { - // trivial cases - if (W.length == 0) return Some(0) - else if (W.length == 1) return S.indexOf(W(0)) match { - case -1 => None - case x => Some(x) - } - - val T: Array[Int] = { - val arr = new Array[Int](W.length) - var pos = 2 - var cnd = 0 - arr(0) = -1 - arr(1) = 0 - while (pos < W.length) { - if (W(pos - 1) == W(cnd)) { - arr(pos) = cnd + 1 - pos += 1 - cnd += 1 - } - else if (cnd > 0) { - cnd = arr(cnd) - } - else { - arr(pos) = 0 - pos += 1 - } - } - arr - } - - var m, i = 0 - def mi = m + i - - while (mi < S.length) { - if (W(i) == S(mi)) { - i += 1 - if (i == W.length) - return Some(m) - } - else { - m = mi - T(i) - if (i > 0) - i = T(i) - } - } - None - } - - private def indexOf( - source: Array[Char], sourceOffset: Int, sourceCount: Int, - target: Array[Char], targetOffset: Int, targetCount: Int, - fromIndex: Int): Int = - KMP(source.slice(sourceOffset, sourceCount) drop fromIndex, target.slice(targetOffset, targetCount)) match { - case None => -1 - case Some(x) => x + fromIndex - } - - private def lastIndexOf( - source: Array[Char], sourceOffset: Int, sourceCount: Int, - target: Array[Char], targetOffset: Int, targetCount: Int, - fromIndex: Int): Int = { - val src = (source.slice(sourceOffset, sourceCount) take fromIndex).reverse - val tgt = target.slice(targetOffset, targetCount).reverse - - KMP(src, tgt) match { - case None => -1 - case Some(x) => (src.length - tgt.length - x) + sourceOffset - } - } } -- cgit v1.2.3