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.

2 files changed, 16 insertions, 82 deletions

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 <code>that</code> not contained in this, otherwise the
-   *  index where <code>that</code> is contained
-   *  @see String.indexOf
+   *  first index where <code>that</code> 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 <code>that</code> not contained in this, otherwise the
+  *  last index where <code>that</code> 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 <code>elem</code> 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, <code>-1</code> is returned.
    *  @throws NullPointerException if <code>str</code> is <code>null</code>.
    */
-  def indexOf(str: String): Int = indexOf(str, 0)
+  def indexOf(str: String): Int = indexOfSeq(str.toArray)
 
   /** <p>
    *    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)
 
   /** <p>
    *    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, <code>-1</code> is returned.
    * @throws NullPointerException  if <code>str</code> is <code>null</code>.
    */
-  def lastIndexOf(str: String): Int = lastIndexOf(str, count)
+  def lastIndexOf(str: String): Int = lastIndexOfSeq(str.toArray, count)
 
   /** <p>
    *    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)
 
   /** <p>
    *    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
-      }
-    }
 }