A start on a more comprehensive test suite for ...

A start on a more comprehensive test suite for sequences. It performs
3600 different tests attempting to exercise the potentially buggy
variations of startsWith, endsWith, indexOfSeq, and sameElements.

And, a KMP implementation of indexOfSeq which in addition to being a
lot faster for definite sized sequences, should give the wrong answer
somewhat less frequently.

5 files changed, 221 insertions, 16 deletions

diff --git a/src/library/scala/collection/SequenceProxy.scala b/src/library/scala/collection/SequenceProxy.scala
index fa3d939e72..a3e9497029 100644
--- a/src/library/scala/collection/SequenceProxy.scala
+++ b/src/library/scala/collection/SequenceProxy.scala
@@ -14,8 +14,8 @@ package scala.collection
 import generic._
 
 
-/** This trait implements a proxy for iterable objects. It forwards
- *  all calls to a different iterable object
+/** This trait implements a proxy for sequence objects. It forwards
+ *  all calls to a different sequence object.
  *
  *  @author  Martin Odersky
  *  @version 2.8
diff --git a/src/library/scala/collection/generic/SequenceTemplate.scala b/src/library/scala/collection/generic/SequenceTemplate.scala
index df49b442bb..ee0f94a583 100644
--- a/src/library/scala/collection/generic/SequenceTemplate.scala
+++ b/src/library/scala/collection/generic/SequenceTemplate.scala
@@ -317,15 +317,24 @@ trait SequenceTemplate[+A, +This <: IterableTemplate[A, This] with Sequence[A]]
    *  index where <code>that</code> is contained
    *  @see String.indexOf
    */
-  def indexOfSeq[B >: A](that: Sequence[B]): Int = {
-    var i = 0
-    var s: Sequence[A] = thisCollection
-    while (!s.isEmpty && !(s startsWith that)) {
-      i += 1
-      s = s.tail
+  def indexOfSeq[B >: A](that: Sequence[B]): Int = indexOfSeq(that, 0)
+
+  def indexOfSeq[B >: A](that: Sequence[B], fromIndex: Int): Int =
+    if (that.hasDefiniteSize)
+      indexOf_KMP(thisCollection, 0, length, that, 0, that.length, fromIndex)
+    else {
+      var i = fromIndex
+      var s: Sequence[A] = thisCollection drop i
+      while (!s.isEmpty) {
+        if (s startsWith that)
+          return i
+
+        i += 1
+        s = s.tail
+      }
+      -1
     }
-    if (!s.isEmpty || that.isEmpty) i else -1
-  }
+
 
   /** Tests if the given value <code>elem</code> is a member of this
    *  sequence.
@@ -479,6 +488,78 @@ trait SequenceTemplate[+A, +This <: IterableTemplate[A, This] with Sequence[A]]
 
   override def view(from: Int, until: Int) = view.slice(from, until)
 
+  // KMP implementation by paulp, based on the undoubtedly reliable wikipedia entry
+  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 {
+      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_KMP[B](
+    source: Seq[B], sourceOffset: Int, sourceCount: Int,
+    target: Seq[B], 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_KMP[B](
+    source: Seq[B], sourceOffset: Int, sourceCount: Int,
+    target: Seq[B], 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
+      }
+    }
+
+
   override def equals(that: Any): Boolean = that match {
     case that1: Sequence[a] =>
       val these = this.iterator
diff --git a/src/library/scala/collection/generic/VectorTemplate.scala b/src/library/scala/collection/generic/VectorTemplate.scala
index f8be15016a..31f728e835 100644
--- a/src/library/scala/collection/generic/VectorTemplate.scala
+++ b/src/library/scala/collection/generic/VectorTemplate.scala
@@ -257,12 +257,12 @@ trait VectorTemplate[+A, +This <: VectorTemplate[A, This] with Vector[A]] extend
       super.endsWith(that)
   }
 
-  override def indexOfSeq[B >: A](that: Sequence[B]): Int = {
-    var i = 0
-    val last = length - that.length
-    while (i <= last && !startsWith(that, i)) i += 1
-    negLength(i)
-  }
+  // override def indexOfSeq[B >: A](that: Sequence[B]): Int = {
+  //   var i = 0
+  //   val last = length - that.length
+  //   while (i <= last && !startsWith(that, i)) i += 1
+  //   negLength(i)
+  // }
 
   override def equals(that: Any): Boolean = that match {
     case that1: Vector[a] =>
diff --git a/test/files/run/sequenceComparisons.check b/test/files/run/sequenceComparisons.check
new file mode 100644
index 0000000000..bb7669b154
--- /dev/null
+++ b/test/files/run/sequenceComparisons.check
@@ -0,0 +1 @@
+All 3600 tests passed.
diff --git a/test/files/run/sequenceComparisons.scala b/test/files/run/sequenceComparisons.scala
new file mode 100644
index 0000000000..ee4df8e40e
--- /dev/null
+++ b/test/files/run/sequenceComparisons.scala
@@ -0,0 +1,123 @@
+import scala.collection.{ mutable, immutable }
+import collection.{ Sequence, Traversable }
+
+object Test {
+  // TODO:
+  //
+  // SequenceProxy
+  // SequenceForwarder
+  // the commented out ones in seqMakers
+
+  val seqMakers = List[List[Int] => Sequence[Int]](
+    mutable.ArrayBuffer(_: _*),
+    // mutable.ArrayStack(_: _*),
+    mutable.Buffer(_: _*),
+    mutable.LinearSequence(_: _*),
+    // null on Nil
+    // mutable.LinkedList(_: _*),
+    mutable.ListBuffer(_: _*),
+    // immutable.Queue(_: _*),
+    // mutable.Queue(_: _*),
+    immutable.Sequence(_: _*),
+    mutable.Sequence(_: _*),
+    // immutable.Stack(_: _*),
+    // mutable.Stack(_: _*),
+    immutable.Vector(_: _*),
+    mutable.Vector(_: _*),
+    immutable.List(_: _*),
+    immutable.Stream(_: _*)
+  )
+
+  abstract class Data[T] {
+    val seq: Sequence[T]
+    // _1 is inputs which must be true, _2 which must be false
+    type Inputs = (List[List[T]], List[List[T]])
+    case class Method(
+      f: (Sequence[T], Sequence[T]) => Boolean,
+      inputs: Inputs,
+      descr: String
+    ) {
+      def trueList  = inputs._1
+      def falseList = inputs._2
+    }
+
+    val startsWithInputs: Inputs
+    lazy val startsWith = Method(_ startsWith _, startsWithInputs, "%s startsWith %s")
+
+    val endsWithInputs: Inputs
+    lazy val endsWith = Method(_ endsWith _, endsWithInputs, "%s endsWith %s")
+
+    val indexOfSeqInputs: Inputs
+    private def subseqTest(s1: Sequence[T], s2: Sequence[T]) = (s1 indexOfSeq s2) != -1
+    lazy val indexOfSeq = Method(subseqTest _, indexOfSeqInputs, "(%s indexOfSeq %s) != -1")
+
+    val sameElementsInputs: Inputs
+    lazy val sameElements = Method(_ sameElements _, sameElementsInputs, "%s sameElements %s")
+
+    def methodList = List(startsWith, endsWith, indexOfSeq, sameElements)
+  }
+
+  object test1 extends Data[Int] {
+    val seq = List(1,2,3,4,5)
+
+    val startsWithInputs = (
+      List(Nil, List(1), List(1,2), seq),
+      List(List(1,2,3,4,6), seq ::: List(5), List(0))
+    )
+
+    val endsWithInputs = (
+      List(Nil, List(5), List(4,5), seq),
+      List(0 :: seq, List(5,2,3,4,5), List(3,4), List(5,6))
+    )
+
+    val indexOfSeqInputs = (
+      List(Nil, List(1), List(3), List(5), List(1,2), List(2,3,4), List(4,5), seq),
+      List(List(1,2,3,5), List(6), List(5,4,3,2,1), List(2,1))
+    )
+
+    val sameElementsInputs = (
+      List(List(1,2,3,4,5)),
+      List(Nil, List(1), List(1,2), List(2,3,4), List(2,3,4,5), List(2,3,4,5,1), List(1,2,3,5,4), seq reverse)
+    )
+  }
+
+  val failures = new mutable.ListBuffer[String]
+  var testCount = 0
+
+  def assertOne(op1: Any, op2: Any, res: Boolean, str: String) {
+    testCount += 1
+    val resStr = str.format(op1, op2)
+    // println(resStr)
+    if (!res)
+      failures += ("FAIL: " + resStr)
+    // assert(res, resStr)
+  }
+
+  def runSeqs() = {
+    for (s1f <- seqMakers ; s2f <- seqMakers ; testData <- List(test1)) {
+      import testData._
+      val scrut = s1f(seq)
+
+      // for (s <- starters ; val rhs = s2f(s))
+      //   assertOne(scrut, rhs, scrut startsWith rhs, "%s startsWith %s")
+      //
+      // for (ns <- nonStarters ; val rhs = s2f(ns))
+      //   assertOne(scrut, rhs, !(scrut startsWith rhs), "!(%s startsWith %s)")
+
+      for (Method(f, (trueList, falseList), descr) <- methodList) {
+        for (s <- trueList; val rhs = s2f(s))
+          assertOne(scrut, rhs, f(scrut, rhs), descr)
+
+        for (s <- falseList; val rhs = s2f(s))
+          assertOne(scrut, rhs, !f(scrut, rhs), "!(" + descr + ")")
+      }
+    }
+  }
+
+  def main(args: Array[String]): Unit = {
+    runSeqs()
+
+    if (failures.isEmpty) println("All %d tests passed.".format(testCount))
+    else failures foreach println
+  }
+}
\ No newline at end of file